I've gone ahead and implemented 3 different ways of determining if a point is in a polygon. Method 1: checks if the point is in the same half space for each edge Method 2: uses binary search to determine which triangle fan of the polygon the point lies in Method 3: casts a ray to the right and checks if the number of intersections is odd (crossings test) There is also a hybrid of method 1 and 2 which should be used when dealing with arbitrarily sized convex polygons
When to use which method? ------------------------------------ N = number of vertices - Method 1 is O(n) and is the fastest method if N<=7 - Method 2 is O(log n) and is the fastest method if N>7 - Method 3 should only be used if you need to test a concave polygon
