寻找凹/凸多边形内的有界矩形

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

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

在多边形内查找轴对齐的矩形 https://stackoverflow.com/questions/610462/finding-an-axis-aligned-rectangle-inside-a-polygon

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

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

Edit：为了回应拉塞尔的评论，我添加了更多信息。

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

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

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

Thanks!

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

1. 将多边形放置在网格上，网格上的单元格与文本尺寸成比例。
2. 使用删除边界上的单元格布雷森纳姆直线算法。 http://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm.
3. 删除边界单元外部的单元（通过从网格边缘向内进行操作。
4. 找到剩余单元格上的最大矩形，例如所示方法here http://www.drdobbs.com/database/184410529.

也可以看看谜题：找到最大的矩形（最大矩形问题） https://stackoverflow.com/questions/7245/puzzle-find-largest-rectangle-maximal-rectangle-problem.

编辑：我刚刚注意到如果多边形以一定角度定向，则该算法需要调整的请求。我的建议是找到主轴 http://en.wikipedia.org/wiki/Principal_axis_theorem多边形的形状来检查方向，旋转它以将主导轴与 x 轴对齐，然后应用上面的算法。

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