Sunday, May 11, 2014

Tell whether a point is inside a polygon by reflection

I noticed if you have a convex polygon like so:
You can reflect this polygon across a point, in this case G...
And anytime G is outside of the original polygon, the polygons won't intersect...
But if G is inside the original polygon the reflected polygon will overlap:
So since there is an easy way to tell whether two lines intersect, one can look pairwise at every line and check for intersection to find whether g is inside the original polygon. It should also scale easily to 3 dimensions.
A much faster way computationally than checking every pairwise intersection as I mentioned before, is to take your polygon with centroid marked as F:
Reflect across the test point G as before:
Now consider the parameterization of the line from F to F(1), if that line crosses a line in the original polygon first, then G is outside of the polygon. Or conversely:
If the parameterization crosses a line in the reflected polygon first or does not cross a line from either polygon as, G is inside the original polygon. If the parameterization is in terms of S, this would mean the crossing with the original polygon has a higher S value.  This takes the algorithm from having to check intersections of N^2 lines to just 2*N.

No comments:

Post a Comment