在凹/凸多边形内找到有界矩形
我正在寻找一种在凹面或凸面多边形内找到轴对齐矩形的方法。
我一直在寻找网络，我能找到的最接近的解决方案只适合凸多边形，而不是凹多边形。 例如 –
在多边形内找到轴对齐的矩形
说实话，我不是一个伟大的数学专家，所以我宁愿找到代码示例或代码库，但我想我可以自己处理一些数学，或者找人来帮助我。
如果解决方案也可以在Java中，那将是非常好的，但也许我太贪心了：P
编辑 ：回应罗素的评论，我正在添加更多信息。
有界矩形应尽可能大。 矩形旨在包含其中的文本。 最多1到4个字，支持文本换行。 因此，如果它太薄，我会将文本垂直放置而不是水平放置。 所以对于宽高比，我想它需要足够包含1-4个单词垂直或水平与自动换行。 如果矩形很小，我可以调整文本大小，但最好是文本尽可能大。
另一个很好的要求是，如果多边形的一般方向是对角线，并且当对角线方向对齐时文本会更好，那么矩形不一定与轴对齐，而是与多边形的对角线。 我想这个要求让这个变得非常棘手，但是如果你们认为它可能那么它会很棒！
我想我现在已经涵盖了所有要求。 ：P
谢谢！
既然你想为文本做这件事，我会假设速度很重要，准确性不那么重要。 我建议这样：
- 将多边形放在网格上，单元格与文本尺寸成比例。
- 使用Bresenham的线算法去除边界上的单元格。 。
- 移除边界单元格外的单元格（通过向内网格边缘处理）。
- 找到剩余单元格上的最大矩形，例如此处显示的方法。
另请参见拼图：查找最大的矩形（最大矩形问题） 。
编辑：我刚刚注意到如果多边形以一个角度定向，该算法会调整的请求。 我的建议是找到多边形的主轴来检查方向，旋转它以使主轴与x轴对齐，并应用上面的算法。
另外，我想要注意“移除单元格”实际上只意味着在表示网格单元的2D数组中设置一个位。
我曾经通过搜索可能的矩形并在它们上使用Shape.contains()来实现类似的系统。 这有点慢 – 可能是一个椭圆形的Gettsburg地址布局 – 但对于静态文本和简单形状的小文本很有用。
如果您有兴趣，可以在这里解压缩jar文件并查看TextWrappingLayout 。 它可能比你需要的要复杂得多，因为它不是在一个矩形中布置，而是试图将每条线尽可能靠近边缘放置，但你可以看到基本的想法。