我正在寻找一种好的算法来在(不一定是凸的)多边形内找到一个轴对齐的矩形。最大矩形会很好,但不是必需的 - 任何可以找到“相当好的”矩形的算法都可以。
多边形也可能有孔,但任何指向仅适用于凸多边形或简单多边形的算法的指针也会有所帮助。
在我的实现中,边的相交测试相当便宜,但“多边形中的点”测试很昂贵,因此理想情况下应该尽量减少。
我正在寻找一种好的算法来在(不一定是凸的)多边形内找到一个轴对齐的矩形。最大矩形会很好,但不是必需的 - 任何可以找到“相当好的”矩形的算法都可以。
多边形也可能有孔,但任何指向仅适用于凸多边形或简单多边形的算法的指针也会有所帮助。
在我的实现中,边的相交测试相当便宜,但“多边形中的点”测试很昂贵,因此理想情况下应该尽量减少。
http://cgm.cs.mcgill.ca/~athens/cs507/Projects/2003/DanielSud/
有一个凸算法,参考资料可能值得一看。
不确定它是否可以扩展到非凸的。
一种解决方案是将凹多边形拆分为凸段,然后使用 cobbal 的链接。
由于您确实有两个不同的基本问题,您是否考虑过命中测试问题的其他替代方案,例如使用 BSP 树?您可以通过在多边形上放置一个网格并为每个网格正方形构建一个 BSP 树来进一步加快速度。还是每片叶子最多有一个边的kd树?
编辑:我将详细介绍 kd-tree(出于无聊,即使它可能对任何人都有用):
kd-trees 具有以下属性:
要将其用于多边形命中检测,请按如下方式构建树:
如果选择合适的分割顶点,树的深度应该接近 log(N),其中 N 是顶点的数量。每个叶节点最多有一条边通过它。要进行命中检测:
仅供参考,到目前为止,我所拥有的只是蛮力:制作一个网格,对于网格上的点,如果它们在多边形内,则通过依次扩展每个角或边直到它碰到边来制作一系列矩形。然后只选择最大的。
最简单(并且非常有效)的优化只是在检查网格点是否不包含在已构建的矩形之一中后测试它是否在多边形中,因为“矩形中的点”检查速度非常快。
由于显而易见的原因,这相当缓慢且不准确,更不用说不雅了:)
使用耳夹怎么样?您可以在每个三角形中找到最大的轴对齐矩形。然后你可以尝试加入三角形并重新计算你的矩形。