On Wednesday, 27 July 2016 at 09:39:18 UTC, Suliman wrote:
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.
Easiest solution (if you don't care about performance) is to
pairwise compare every segment of both polygons to see if they
intersect, and if that fails, then run point-in-polygon algorithm
with one vertex from each polygon and the other (catches the case
where one polygon is entirely contained within the other).
Now you have the point in polygon algorithm (kindly provided by
chmike) and testing for segment intersection is a basic primitive
geometric operation, so there are lots of examples on the web.
You should certainly be able to find working C code for this
without much trouble.
