5

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

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

在多边形内查找轴对齐的矩形

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

如果解决方案也可以在 Java 中使用，那就太好了，但也许我太贪婪了：P

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

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

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

我想我现在已经涵盖了所有要求。:P

谢谢！

4

2 回答 2

1

我曾经以一种非常笨拙的方式实现了一个类似的系统，只是通过搜索可能的矩形并Shape.contains()在它们上使用。它有点慢 - 将 Gettsburg Address 布局成椭圆形可能需要 1 秒 - 但对于静态文本和简单形状的小文本很有用。

如果您有兴趣，可以在这里解压缩 jar 文件并查看TextWrappingLayout. 它可能比您需要的要复杂得多，因为它不是在单个矩形中布局，而是尝试将每条线尽可能靠近边缘放置，但是您可以看到基本思想。

于 2012-04-18T18:21:07.220 回答
1

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

  1. 将多边形放在网格上，其单元格与文本尺寸成比例。
  2. 使用Bresenham 的线算法删除边界上的单元格。.
  3. 移除边界单元之外的单元（通过从网格边缘向内工作。
  4. 找到剩余单元格上的最大矩形，例如此处显示的方法。

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

编辑：我刚刚注意到如果多边形以一定角度定向，该算法会调整的请求。我的建议是找到多边形的主轴来检查方向，旋转它以将主轴与 x 轴对齐，然后应用上面的算法。

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

于 2012-04-19T00:04:23.703 回答