Check of point inside/outside polygon

[chmike via Digitalmars-d-learn]

The algorithm is to draw a horizontal (or vertical) half line 
starting at your point and count the number of polygon edges 
crossed by the line. If that number is even, the point is outside 
the polygon, if it's odd, the point is inside.

Let (x,y) be the point to test and (x1,y1)(x2,y2) the end points 
on each segment. Let n be the number of crossing that you 
initialize to 0. (x1,y1)(x2,y2) are also the corners of the 
rectangle enclosing the segment.

You then have to examine each segment one after the other. The 
nice thing is that there are only two cases to consider.
1. When the point is on the left side of the rectangle enclosing 
the segment.
2. When the point is inside the rectangle enclosing

if (y1 <= y2)
{
     if ((y1 <= y) && (y2 >= y))
     {
        if ((x1 < x) && (x2 < x))
        {
           // case 1 : point on the left of the rectangle
           ++n;
        }
        else if (((x1 <= x) && (x2 >= x)) || ((x1 >= x) && (x2 <= 
x)))
        {
           // case 2 : point is inside of the rectangle
           if ((x2 - x1)*(y - y1) >= (y2 - y1)*(x - x1))
               ++n; // Increment n because point is on the segment 
or on its left
        }
     }
}
else
{
     if ((y1 >= y) && (y2 <= y))
     {
        if ((x1 < x) && (x2 < x))
        {
           // case 1 : point on the left of the rectangle
           ++n;
        }
        else if (((x1 <= x) && (x2 >= x)) || ((x1 => x) && (x2 <= 
x)))
        {
           // case 2 : point is inside of the rectangle
           if ((x2 - x1)*(y - y2) >= (y1 - y2)*(x - x1))
               ++n; // Increment n because point is on the segment 
or on its left
        }
     }
}

This algorithm is very fast.

I didn't tested the above code. You might have to massage it a 
bit for corner cases. It should give you a good push to start.