我正在寻找一个好的算法来找到一个（不一定是凸面）多边形内的轴对齐矩形 . 最大的矩形会很好，但不是必需的 - 任何可以找到“相当好”的矩形的算法都可以 .
多边形也可能有孔，但任何只适用于凸多边形或简单多边形的算法指针也会有所帮助 .
在我的实现中，对于边的交叉测试相当便宜，但是“多边形点”测试是昂贵的，因此理想情况下应该最小化 .
http://cgm.cs.mcgill.ca/~athens/cs507/Projects/2003/DanielSud/有一个凸算法，引用可能值得一看 .不确定它是否可以扩展到非凸 .
一种解决方案是将凹多边形分成凸段然后使用cobbal的链接 .
由于您确实有两个不同的基本问题，您是否考虑过其他替代命中测试问题的方法，例如使用BSP树？您可以通过在多边形上铺设网格并为每个网格方块构建BSP树来进一步加快速度 . 或者每片叶子最多有一个边缘的kd树？
编辑：我会详细说明kd-tree（出于厌倦，即使它可能对任何人都有用）：
kd-trees具有以下属性：
他们是二进制的
每个非叶节点沿垂直于轴的平面分割空间，每个子节点一侧 . 例如 . root将空格分成x <x0和x> = x0
树级别沿着不同的轴轮流分裂，例如等级0（根）垂直于X，等级1 - > Y等分割 .
要将其用于多边形命中检测，请按如下方式构造树：
选择要分割的顶点 . （对于 balancer 的树，最好是接近中间的某个地方） .
将其他顶点拆分为两个集合，一个用于拆分的任一侧 . 上面的顶点不会进入任何一组 .
也将边缘放入集合中 . 与分割线相交的任何边都进入两个集合 .
从上述组递归构造子项 .
如果适当选择分割顶点，则树的深度应接近log（N），其中N是顶点数 . 每个叶节点最多只有一个边缘通过它 . 要进行命中检测：
找到该点落入的叶子 .
如果叶子中有边缘，则将其与点进行比较 . 如果不是，那么该点是在内部还是外部应该是显而易见的（在构造树时将此信息存储在这样的叶子中） .
仅供参考，到目前为止，我所拥有的只是蛮力：制作网格，对于网格上的点，如果它们在多边形内，则通过依次展开每个角或边直到它撞到一侧来制作一系列矩形 . 然后选择最大的 .
最简单（也是非常有效）的优化只是测试网格点是否在多边形中，一旦检查到它没有包含在已经构造的一个矩形中，因为“矩形点”检查是快速的 .
出于显而易见的原因，这是相当缓慢和不精确的，更不用说不优雅:)
用耳夹怎么样？您可以在每个三角形中找到最大的轴对齐矩形 . 然后你可以尝试连接三角形并重新计算你的矩形 .
4 回答
http://cgm.cs.mcgill.ca/~athens/cs507/Projects/2003/DanielSud/
有一个凸算法，引用可能值得一看 .
不确定它是否可以扩展到非凸 .
一种解决方案是将凹多边形分成凸段然后使用cobbal的链接 .
由于您确实有两个不同的基本问题，您是否考虑过其他替代命中测试问题的方法，例如使用BSP树？您可以通过在多边形上铺设网格并为每个网格方块构建BSP树来进一步加快速度 . 或者每片叶子最多有一个边缘的kd树？
编辑：我会详细说明kd-tree（出于厌倦，即使它可能对任何人都有用）：
kd-trees具有以下属性：
他们是二进制的
每个非叶节点沿垂直于轴的平面分割空间，每个子节点一侧 . 例如 . root将空格分成x <x0和x> = x0
树级别沿着不同的轴轮流分裂，例如等级0（根）垂直于X，等级1 - > Y等分割 .
要将其用于多边形命中检测，请按如下方式构造树：
选择要分割的顶点 . （对于 balancer 的树，最好是接近中间的某个地方） .
将其他顶点拆分为两个集合，一个用于拆分的任一侧 . 上面的顶点不会进入任何一组 .
也将边缘放入集合中 . 与分割线相交的任何边都进入两个集合 .
从上述组递归构造子项 .
如果适当选择分割顶点，则树的深度应接近log（N），其中N是顶点数 . 每个叶节点最多只有一个边缘通过它 . 要进行命中检测：
找到该点落入的叶子 .
如果叶子中有边缘，则将其与点进行比较 . 如果不是，那么该点是在内部还是外部应该是显而易见的（在构造树时将此信息存储在这样的叶子中） .
仅供参考，到目前为止，我所拥有的只是蛮力：制作网格，对于网格上的点，如果它们在多边形内，则通过依次展开每个角或边直到它撞到一侧来制作一系列矩形 . 然后选择最大的 .
最简单（也是非常有效）的优化只是测试网格点是否在多边形中，一旦检查到它没有包含在已经构造的一个矩形中，因为“矩形点”检查是快速的 .
出于显而易见的原因，这是相当缓慢和不精确的，更不用说不优雅:)
用耳夹怎么样？您可以在每个三角形中找到最大的轴对齐矩形 . 然后你可以尝试连接三角形并重新计算你的矩形 .