On Wednesday, 27 July 2016 at 08:40:15 UTC, chmike wrote:
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.
Big thanks!
Ehm... Now I should add iteration on array of points in first and
second polygon? If it's not hard for you could you show how it
should look please.
