确定多边形交叉和包含

Question

我有一组简单的(没有洞,没有自交叉)多边形,我需要检查它们是否相互交叉(一个可以完全包含在另一个中;这没关系).我可以通过简单地检查一个多边形与其他多边形的每个顶点内部的关系来检查这一点.

我还需要确定包含树,它是一组关系,说明哪个多边形包含任何给定的多边形.由于没有多边形可以与任何其他多边形相交,因此任何包含的多边形都具有唯 "下一个更大的".换句话说,如果A包含B包含C,则A是B的父亲,B是C的父亲,我们不认为A是C的父亲.

问题:如何有效地确定包含关系并检查非交叉标准？我问这个问题是因为组合算法可能比单独解决每个问题更有效.该算法应该将多边形列表作为输入,由它们的顶点列表给出.它应该产生一个布尔B,表明没有多边形与任何其他多边形相交,如果B =真,则产生一对(P,C)的列表,其中多边形P是子C的父.

这不是功课.这是我正在做的一个爱好项目.

Answer 1

首先,您的测试包含的算法不能正确测试交叉.想象一下这样的两个矩形:

    +--+
 +--+--+--+
 |  |  |  |
 +--+--+--+
    +--+

顶点位于(1,2)(1,3)(4,2)(4,3)和(2,1)(3,1)(2,4)(3,4) - 没有顶点所在在任何多边形内部,但多边形实际上相交.

为了测试这种交叉,有必要确定是否有任何多边形的边相交.为了您的目的,如果边相交但一个多边形不包含在另一个中,那么您知道它们以不允许的方式重叠.

至于确定包容树,一种方法是按面积将多边形从最小到最大排序.如果多边形不重叠 - 不包含,则树中任何多边形的父级将是列表中第一个包含多边形的多边形.

编辑:哦,另外,我建议写一个快速边界框或边界圆重叠例程,并使用它来避免必须进行所有线交叉和顶点包含测试.如果仍然不够快,你可能想要构建一个四元组或BSP树; 这会使事情变得复杂,但也会完全消除很多交叉检查.

Answer 2

O(n*log(n))通过应用Shamos-Hoey算法可以确定是否没有多边形相交.根据什么Shamos -霍伊算法返回,一个多边形P _我包含多边形P _Ĵ如果与P任何顶点_Ĵ是内部P _我这是在做O(n)了两个多边形.