Check of point inside/outside polygon

[Gorge Jingale via Digitalmars-d-learn]

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.