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

我正在寻找一种在凹或多边形内查找轴对齐矩形的方法。在凹/凸多边形内部查找有界矩形

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

Finding an axis-aligned rectangle inside a polygon

说实话，我不是一个伟大的数学奇才，所以我宁愿找代码示例或代码库，但我想我可以通过自己处理一些数学运算，或找人帮助我。

这将是非常好的，如果该解决方案可以在Java中也一样，但也许我太贪婪：P

编辑：针对罗素的评论，我加入多一点的信息。

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

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

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

谢谢！

既然你想这样做的文字，我会假设速度很重要，精度不那么重要。我建议如下：

参见Puzzle: Find largest rectangle (maximal rectangle problem)。

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

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

我曾经通过对可能的矩形进行搜索并在其上使用Shape.contains()，以一种非常奇怪的方式实现了类似的系统。它有点慢 - 可能是1s，用于布局Gettsburg地址的椭圆形 - 但对于静态文本和简单形状的小文本很有用。

如果你有兴趣，你可以解压缩jar文件here并看看TextWrappingLayout。这可能比你需要的复杂得多，因为它不是在一个矩形中进行布局，而是尽可能地将每条线放在边缘附近，但是你可以看到基本的想法。