Check of point inside/outside polygon

Craig Dillabaugh via Digitalmars-d-learn digitalmars-d-learn at puremagic.com
Wed Jul 27 06:01:07 PDT 2016


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.


More information about the Digitalmars-d-learn mailing list