analytics

Sunday, May 3, 2015

Point in Convex polygon using cross products

Suppose you have a convex polygon like below labeling vertices clockwise from A, and we want to know whether some point Z is inside or outside the polygon...
Clearly if vector v from point B to point Z makes an angle greater than 180 degrees with vector u from point A to point B, the point is outside of the polygon, as the polygon is convex, and that would make the polygon concave if Z was inside of the polygon and the angle was greater than 180 degrees...
This is equivalent to saying if cross product uxv is positive point Z is definitely outside the polygon! A simple calculation...

Now consider u(2) to be vector BC and v(2) to be vector CZ, the same reasoning holds and we see that if u(2)xv(2) is positive the point Z must be outside the polygon,  in fact going all the way around if any such cross product is positive, the point Z must be outside the polygon...

So it's necessary that none of those cross products are positive, as it turns out it is evidently also sufficient, as determined by drawing many such polygons in a program like Geogebra and dragging the vector around and noting the angles when the point is inside and when it is outside but I haven't thought of a good proof.

No comments:

Post a Comment