我有一组简单的（无气孔，无自交）的多边形，而且我需要检查，他们不相互交叉（一个可以完全包含在另一个，这是正常情况）。我可以通过简单地检查每个顶点的内部岬一个多边形与其他多边形检查。

I have a set of simple (no holes, no self-intersections) polygons, and I need to check that they don't intersect each other (one can be entirely contained in another; that is okay). I can check this by simply checking the per-vertex inside-ness of one polygon versus other polygons.

我还需要确定遏制树，这是一套说哪个面包含任何给定的多边形关系。由于没有多边形可以相交的任何其他，则任何包含多边形具有独特的容器;在下一个大之一。换句话说，如果A包含B包含C，则A是B的父级，B是C的父，我们不考虑C A父。

I also need to determine the containment tree, which is the set of relationships that say which polygon contains any given polygon. Since no polygon can intersect any other, then any contained polygon has a unique container; the "next-bigger" one. In other words, if A contains B contains C, then A is the parent of B, and B is the parent of C, and we don't consider A the parent of C.

这样的问题：我如何有效地确定了包含关系，并检查非交集的标准？我问这是一个问题，因为可能的组合算法比单独解决每个问题的更有效。该算法应该采取作为输入的多边形的列表，通过它们的顶点的列表给出。它应该产生一个布尔乙表示，如果没有一个多边形相交任何其他多边​​形，并且如果B =真，对（P，C），其中多边形P是孩子C的父母。名单

The question: How do I efficiently determine the containment relationships and check the non-intersection criterion? I ask this as one question because maybe a combined algorithm is more efficient than solving each problem separately. The algorithm should take as input a list of polygons, given by a list of their vertices. It should produce a boolean B indicating if none of the polygons intersect any other polygon, and also if B = true, a list of pairs (P, C) where polygon P is the parent of child C.

这是不是功课。这是一个爱好的项目我的工作。

This is not homework. This is for a hobby project I am working on.

推荐答案

首先，你的算法进行测试遏制不交点正确测试。想象一下，两个矩形是这样的：

First, your algorithm for testing containment does not test for intersection correctly. Imagine two rectangles like this:

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

顶点。将在（1,2）（1,3）（4,2）（4,3）和（2,1）（3,1）（2,4）（3,4） - 没有顶点位于任何多边形内部，但多边形做其实相交。

Vertices would be at (1, 2) (1,3) (4,2) (4,3) and (2,1) (3,1) (2,4) (3,4) -- no vertex lies inside any polygon, but the polygons do in fact intersect.

要测试这种相交，必须确定是必要的是否有任何多边形'的边缘的的相交。为了您的目的，如果边相交，但是一个多边形不包含在其他的，那么你就知道他们在非允许的方式重叠。

To test for this kind of intersection, it is necessary to determine whether any of the polygons' edges intersect. For your purposes, if edges intersect but one polygon is not contained within the other, then you know they overlap in a non-permitted fashion.

作为确定围堵树，要做到这一点的方法之一是按面积从小到大的多边形进行排序。所提供的多边形不重叠且不遏制，则在树中任何多边形的父将后它的第一含多边形未来在列表中。

As for determining the containment tree, one way to do that is to sort the polygons from smallest to largest by area. Provided the polygons don't overlap-without-containment, then any polygon's parent in the tree will be the first containing polygon coming after it in the list.

编辑：哦，还有，我建议写一个快速包围盒或包围圈的重叠程序，并用它来避免做的所有线的交点和顶点遏制测试。如果仍然不够快，你可能想建立一个四或BSP树;将事情复杂化了不少，但也将消除大量的交叉检查的全部。

Oh, also, I advise writing a fast bounding-box or bounding-circle overlap routine, and using that to avoid having to do all the line intersection and vertex containment tests. If that still isn't fast enough, you probably want to build a quad or BSP tree; that will complicate things quite a bit but will also eliminate a lot of the intersection checks entirely.