www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Check of point inside/outside polygon

reply Suliman <evermind live.ru> writes:
Ideally I need algorithm that can return bool if one polygon 
overlapped/intersected by another. But I do not know math.

After some googling I found topic on SO[1] about point 
inside/outside polygon. It's not directly what I need, but as 
temporal solution would be enough.

Maybe somebody already wrote this algorithm in D. Could you share 
it plz.

I tried to translate algorithm in D, but I do not understand some 
things. For example:

public static bool PointInPolygon(LatLong p, List<LatLong> poly) 
// Ok we are getting `p` - looking point, and `poly` -- our 
polygon. But what format it should have? WKT? Something else?

poly.Add(new LatLong { Lat = poly[0].Lat, Lon = poly[0].Lon }); 
// Why we add Lat and Long to poly? And again what it's format?

All other code look work in D to.


[1] 
http://stackoverflow.com/questions/924171/geo-fencing-point-inside-outside-polygon/6786279#6786279
Jul 26 2016
next sibling parent reply "H. S. Teoh via Digitalmars-d-learn" <digitalmars-d-learn puremagic.com> writes:
On Tue, Jul 26, 2016 at 01:32:00PM +0000, Suliman via Digitalmars-d-learn wrote:
 Ideally I need algorithm that can return bool if one polygon
 overlapped/intersected by another. But I do not know math.
Are you talking about triangles, or general polygons? Are the polygons convex or arbitrary? Depending on what kind of polygon it is, the solution may be more or less complex. If you're dealing with convex polygons (including triangles -- though you can probably simplify things a bit more for triangles), take a look at this: http://www.iro.umontreal.ca/~plante/compGeom/algorithm.html If your polygons are non-convex, the solution will be quite complicated and may not have good performance. You might want to consider various algorithms for decomposing such polygons into convex pieces for easier handling.
 After some googling I found topic on SO[1] about point inside/outside
 polygon. It's not directly what I need, but as temporal solution would
 be enough.
[...] This approach may not be as straightforward as you think. Consider two equilateral triangles inscribed inside a regular hexagon (i.e., "David's Star", or the 6/3 star polygon). Neither of the triangles's vertices lie inside the other triangle, yet the two triangles do intersect each other. You may say, test the centers of the polygons too, however, it's easy to come up with other pairs of polygons where the respective centers don't lie in the other polygon but the two polygons nevertheless still intersect. You need a general algorithm for finding the intersection; point-sampling generally is not good enough. T -- Gone Chopin. Bach in a minuet.
Jul 26 2016
parent reply Suliman <evermind live.ru> writes:
I have arbitrary polygon. I need any solution. Performance is 
does not matter at current moment.
Jul 26 2016
next sibling parent "H. S. Teoh via Digitalmars-d-learn" <digitalmars-d-learn puremagic.com> writes:
On Tue, Jul 26, 2016 at 05:38:43PM +0000, Suliman via Digitalmars-d-learn wrote:
 I have arbitrary polygon. I need any solution. Performance is does not
 matter at current moment.
In that case, maybe you'd want to look at: https://en.wikipedia.org/wiki/Vatti_clipping_algorithm Note, however, that this only works in 2D, and doesn't generalize to higher dimensional shapes. T -- Let X be the set not defined by this sentence...
Jul 26 2016
prev sibling parent reply Gorge Jingale <Frifj mail.com> writes:
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.
Jul 26 2016
parent reply "H. S. Teoh via Digitalmars-d-learn" <digitalmars-d-learn puremagic.com> writes:
On Tue, Jul 26, 2016 at 06:39:58PM +0000, Gorge Jingale via Digitalmars-d-learn
wrote:
 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.
[...] Unfortunately he wants to handle arbitrary polygons that are not necessarily convex. T -- Be in denial for long enough, and one day you'll deny yourself of things you wish you hadn't.
Jul 26 2016
parent reply Gorge Jingale <Frifj mail.com> writes:
On Tuesday, 26 July 2016 at 19:08:09 UTC, H. S. Teoh wrote:
 On Tue, Jul 26, 2016 at 06:39:58PM +0000, Gorge Jingale via 
 Digitalmars-d-learn wrote:
 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.
[...] Unfortunately he wants to handle arbitrary polygons that are not necessarily convex. T
The example was for convex, the method using intersections was for general polygons that do not have self-intersections. Convex polygons have 0 intersection numbers.
Jul 26 2016
parent reply chmike <christophe meessen.net> writes:
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.
Jul 27 2016
parent reply Suliman <evermind live.ru> writes:
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.
Jul 27 2016
next sibling parent reply chmike <christophe meessen.net> writes:
On Wednesday, 27 July 2016 at 09:39:18 UTC, Suliman wrote:

...
 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.
Sorry, I may have misunderstood the initial problem. You were asking how to test if a point is inside a polygon. Now you are referring to two polygons. This sound different. Iterating on segments of a polygon is not so difficult and is highly dependent of the data structure you use to represent points, segments and polygons. This really looks like an assignment or a D learning exercise. What do you need this for ? Do you have the data structures already defined ?
Jul 27 2016
parent reply Suliman <evermind live.ru> writes:
On Wednesday, 27 July 2016 at 12:47:14 UTC, chmike wrote:
 On Wednesday, 27 July 2016 at 09:39:18 UTC, Suliman wrote:

 ...
 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.
Sorry, I may have misunderstood the initial problem. You were asking how to test if a point is inside a polygon. Now you are referring to two polygons. This sound different. Iterating on segments of a polygon is not so difficult and is highly dependent of the data structure you use to represent points, segments and polygons. This really looks like an assignment or a D learning exercise. What do you need this for ? Do you have the data structures already defined ?
Sorry, its my issue I am thinging about polygons, but for me would be enought points. The problem is next. I am writhing geo portal where user can draw shape. I need to get users images that user shape cross. But as temporal solution it would be enough to detect if image central point inside this polygon (I know its coordinates). I can do its on DB level, but I would like to use SQLite that do bot have geometry support. So i am looking for any solution. I can use gdal but its _very_ heavy
Jul 27 2016
parent CRAIG DILLABAUGH <craig.dillabaugh gmail.com> writes:
On Wednesday, 27 July 2016 at 14:56:13 UTC, Suliman wrote:
 On Wednesday, 27 July 2016 at 12:47:14 UTC, chmike wrote:
 On Wednesday, 27 July 2016 at 09:39:18 UTC, Suliman wrote:
clip
 Sorry, its my issue I am thinging about polygons, but for me 
 would be enought points.
 The problem is next. I am writhing geo portal where user can 
 draw shape. I need to get users images that user shape cross. 
 But as temporal solution it would be enough to detect if image 
 central point inside this polygon (I know its coordinates).

 I can do its on DB level, but I would like to use SQLite that 
 do bot have geometry support. So i am looking for any solution. 
 I can use gdal but its _very_ heavy
So when you say you want polygon intersection, is one of the polygons you are interested in the shape of the images (ie. roughly a rectangle)? If this is the case then you can likely just take the bounding rectangle (easily calculated) of your polygon and check if that intersects the bounding rectangle for the the image and that should work 95% of the time.
Jul 27 2016
prev sibling parent Craig Dillabaugh <craig.dillabaugh gmail.com> writes:
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.
Jul 27 2016
prev sibling parent Basile B. <b2.temp gmx.com> writes:
On Tuesday, 26 July 2016 at 13:32:00 UTC, Suliman wrote:
 Ideally I need algorithm that can return bool if one polygon 
 overlapped/intersected by another. But I do not know math.

 After some googling I found topic on SO[1] about point 
 inside/outside polygon. It's not directly what I need, but as 
 temporal solution would be enough.

 Maybe somebody already wrote this algorithm in D. Could you 
 share it plz.

 I tried to translate algorithm in D, but I do not understand 
 some things. For example:

 public static bool PointInPolygon(LatLong p, List<LatLong> 
 poly) // Ok we are getting `p` - looking point, and `poly` -- 
 our polygon. But what format it should have? WKT? Something 
 else?

 poly.Add(new LatLong { Lat = poly[0].Lat, Lon = poly[0].Lon }); 
 // Why we add Lat and Long to poly? And again what it's format?

 All other code look work in D to.


 [1] 
 http://stackoverflow.com/questions/924171/geo-fencing-point-inside-outside-polygon/6786279#6786279
How could I miss this. Working: https://github.com/BBasile/kheops/blob/master/src/kheops/helpers/polygons.d#L130 It works fine. I've tested it after translation and rotation: Okay.
Jan 11