Determining polygon intersection and containment

Question

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.

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.

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.

Answer 1

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

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

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.

Edit: 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.

Answer 2

Determining whether none of the polygons intersect can be done in O(n*log(n)) by applying the Shamos-Hoey algorithm. Depending on what the Shamos-Hoey algorithm returns, a polygon P_i contains polygon P_j if any vertex from P_j is inside P_i which is done in O(n) for two polygons.