Return home

Home
Links
Gallery
Download
Shapes
PDF
Wish list
Software

Polygonal Intersection

PaperCut home page on SourceForge.net
Stellated icosahedron

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.

 


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