Home Links Gallery Download Shapes PDF Wish list Software	Polygonal Intersection

My solution for determining interior region intersections

Recent development on PaperCut brought a long-standing bug to the forefront. Previously it was an annoyance with some compound stellations where the number of faces on a single printed page was high. Actually getting complex 3D shape import working properly meant that there were many "crab claws", "nautilii" and other artifacts on the net layouts.

I needed a way to determine, with minimal computation, whether any point on the interior of a given polygon intersected any point on the interior of another polygon. I further constrained my test to apply only to convex polygons. The approach described here may apply to non-convex polygons with one interior region, but has not been tested extensively.

For any polygon and a coplanar point, there is a test to determine whether that point lies within the interior of the polygon. If the point lies within the interior of all angles of a convex polygon, it is in the interior of the polygon.

To determine whether any point within the interior of polygon B lies within the interior of polygon A, we use a similar approach.

Starting with polygon A, consider each vertex of polygon B. Call the function which yields the number of vertices of polygon B included in an angle of polygon A the vertex inclusion count. Call the set of vertex inclusion counts for A with respect to B VIC(A,B). Call the side count of A SIDES(A), and the side count of B SIDES(B). Call the count of non-zero values in VIC(A,B) VICNZ(A,B).

The postulate is this: Polygon A and polygon B have mutually intersecting interior regions iff either of the following are true:

1. Inclusion
If either VIC(A,B) = {SIDES(B),...} (the set is composed of SIDES(A) elements of the value of SIDES(B)) or VIC(B,A) = {SIDES(A),...}, one is included entirely within the other.

2. Intersection
If VICNZ(A,B) >= SIDES(A)-1and VICNZ(B,A) >= SIDES(B)-1, some part of the interior regions of A and B intersect.