在凹/凸多边形内部找到有界的矩形 [英] Finding a bounded rectangle inside a concave/convex polygon

问题描述

我一直在寻找网络，最接近于网络我能找到的解决方案只适合一个凸多边形，而不是一个凹多边形。例如 -

在多边形内找到一个轴对齐的矩形

说实话，我不是一个好的数学工具，所以我宁愿找到代码示例或一个代码库，但我想我可以自己处理一些数学，或者找人来帮助我。

如果解决方案可以在也是Java，但也许我太贪心：P

编辑：为了回应罗素的评论，我添加了更多信息。

有界的矩形应该尽可能大。该矩形旨在包含其中的文本。最多1到4个单词，支持文字换行。因此，如果例如它太薄，我会垂直放置文本而不是水平放置。所以对于宽高比，我想它应该足以包含1-4个单词，或者垂直或水平地使用单词换行。如果矩形很小，我可以调整文本大小，但最好是文本应该尽可能大。

另一个很好的要求是，如果多边形的一般方向是对角线，当对角线取向时文本会更好地适合，那么矩形不一定与轴对齐，而是与多边形的对角线对齐。我想这个要求使得这个要求非常棘手，但是如果你们认为它是可能的，那么它会很棒！

我想我已经涵盖了所有的要求。 ：P

谢谢！

解决方案

既然你想这样做对于文字，我会假设速度很重要，准确性不那么重要。然后我建议：

1. 将多边形放置在网格上，单元格与文本尺寸成比例。


2. 使用 Bresenham的线条算法删除边界上的单元格。


3. 在边界单元格外移除单元格（通过从网格边界向内进行操作）。
   
4. 在剩余单元格中查找最大矩形，例如显示的方法 here 。
   

另请参见拼图：查找最大矩形（最大矩形问题）。

编辑：我只是注意到这个算法调整的要求，如果多边形是以一个角度定位的，我的建议是找到主轴来检查方向，旋转它以将主轴与x轴对齐，并应用上述算法。

<另外，我想说明的是，移除单元格的确意味着在代表网格单元格的二维数组中设置一个位。

I'm looking for a method for finding an axis-aligned rectangle inside a concave or convex polygon.

I've been looking around the web, the closest solutions I could find would only fit a convex polygon, and not a concave one. For example -

Finding an axis-aligned rectangle inside a polygon

To be honest I'm not a great math wiz, so I would rather find code samples or a code library, but I guess I could handle some math by myself, or find someone to help me with it.

It would be really nice if the solution could be in Java too, but maybe I'm too greedy :P

Edit: In response to Russell's comment, I'm adding a bit more information.

The bounded rectangle should be as large as possible. The rectangle is intended to contain text inside it. 1 to 4 words max, with support for text wrapping. So if for example it would be too thin, I would place the text vertically instead of horizontally. So for aspect ratio, I guess it needs to be enough for containing 1-4 words either vertically or horizontally with word wrapping. I can resize the text if the rectangle is small, but preferably the text should be as large as possible.

Another requirement that would be nice to have would be that if the general orientation of the polygon is diagonal and the text would fit much better when it's oriented diagonally, then the rectangle wouldn't necessarily be aligned with the axis' but instead be aligned with the diagonal lines of the polygon. I guess this demand is making this really tricky, but if you guys think its possible then it would be great!

I think I've covered all of the requirements now. :P

Thanks!

解决方案

Since you want to do this for text, I'll assume speed is important, accuracy less important. I suggest this then:

1. Place the polygon on a grid with cells proportional to text dimensions.
2. Remove cells on the boundary using Bresenham's line algorithm..
3. Remove cells outside the boundary cells (by working from the edges of the grid inward.
4. Find the maximal rectangle on the remaining cells, e.g. the method shown here.

See also Puzzle: Find largest rectangle (maximal rectangle problem).

EDIT: I just noticed the request that this algorithm adjust if the polygon is oriented at an angle. My suggest is to find the principle axes of the polygon to check the orientation, rotate it to align the dominant axis to the x-axis, and apply the algorithm above.

Also, I want to note that "removing a cell" really just means setting a bit in a 2D array that represents the grid cells.

这篇关于在凹/凸多边形内部找到有界的矩形的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！