java - 在凹/凸多边形内查找有界矩形

Question

我正在寻找一种在凹多边形或凸多边形内找到轴对齐矩形的方法。

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

Finding an axis-aligned rectangle inside a polygon

老实说，我不是一个伟大的数学天才，所以我宁愿找到代码示例或代码库，但我想我可以自己处理一些数学，或者找人帮助我。

如果解决方案也可以在 Java 中，那就太好了，但也许我太贪心了 :P

编辑:为了回应 Russell 的评论，我添加了更多信息。

边界矩形应尽可能大。该矩形旨在在其中包含文本。最多 1 到 4 个字，支持文本换行。因此，如果它太薄，我会垂直而不是水平放置文本。因此，对于宽高比，我想它需要足以包含 1-4 个单词，无论是垂直还是水平，并带有自动换行。如果矩形很小，我可以调整文本大小，但文本最好尽可能大。

另一个很好的要求是，如果多边形的总体方向是对角线，并且文本在对角线方向时更适合，那么矩形不一定与轴对齐，而是与多边形的对角线对齐。我想这个需求让这件事变得非常棘手，但如果你们认为这是可能的，那就太好了!

我想我现在已经满足了所有要求。 :P

谢谢!

Answer 1

由于您想对文本执行此操作，因此我假设速度很重要，准确性不太重要。那么我建议:

1. 将多边形放置在网格上，网格中的单元格与文本尺寸成比例。
2. 使用 Bresenham's line algorithm. 删除边界上的单元格.
3. 移除边界单元格外的单元格(通过从网格边缘向内工作。
4. 找到剩余单元格上的最大矩形，例如显示的方法 here .

另见 Puzzle: Find largest rectangle (maximal rectangle problem) .

编辑:我刚刚注意到如果多边形以一定角度定向，则该算法会进行调整。我的建议是找到 principle axes多边形的方向以检查方向，旋转它以将主导轴与 x 轴对齐，然后应用上述算法。

此外，我想指出，“删除单元格”实际上只是在表示网格单元格的二维数组中设置一个位。