

My solution for determining interior region intersections
Recent development on PaperCut brought a longstanding 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 nonconvex 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 nonzero 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.


Home  Links  Gallery  Download  Shapes  History  Samples  Wish list  Software  SourceForge  PDF 