On Tuesday, 26 July 2016 at 17:38:43 UTC, Suliman wrote:
I have arbitrary polygon. I need any solution. Performance is does not matter at current moment.
A polygon is made up of lines. For a point to be inside a convex polygon, it must be to the "right" of all the lines with clockwise orientation.
One way for this to work is simply draw a line segment from each vertex to the point and compare it to the number of intersections with other lines. The number of intersections must be odd for it to be inside the polygon. Think of a regular polygon, any point inside will have no other line segments between it and the point. All intersection values will be 0.
So, for each n vertices we have n line segments, we must the find the number of intersection points for the other n-1 line segments. This reduces the problem to line segment intersection but is of the order O(n^2), but works in general.
