digitalmars.D.learn - Check of point inside/outside polygon
- Suliman (17/17) Jul 26 2016 Ideally I need algorithm that can return bool if one polygon
- H. S. Teoh via Digitalmars-d-learn (24/29) Jul 26 2016 Are you talking about triangles, or general polygons? Are the polygons
- Suliman (2/2) Jul 26 2016 I have arbitrary polygon. I need any solution. Performance is
- H. S. Teoh via Digitalmars-d-learn (8/10) Jul 26 2016 In that case, maybe you'd want to look at:
- Gorge Jingale (14/16) Jul 26 2016 A polygon is made up of lines. For a point to be inside a convex
- H. S. Teoh via Digitalmars-d-learn (7/13) Jul 26 2016 [...]
- Gorge Jingale (4/17) Jul 26 2016 The example was for convex, the method using intersections was
- chmike (54/54) Jul 27 2016 The algorithm is to draw a horizontal (or vertical) half line
- Suliman (5/59) Jul 27 2016 Big thanks!
- chmike (11/15) Jul 27 2016 Sorry, I may have misunderstood the initial problem. You were
- Suliman (10/25) Jul 27 2016 Sorry, its my issue I am thinging about polygons, but for me
- CRAIG DILLABAUGH (9/20) Jul 27 2016 So when you say you want polygon intersection, is one of the
- Craig Dillabaugh (11/75) Jul 27 2016 Easiest solution (if you don't care about performance) is to
- Basile B. (5/23) Jan 11 2017 How could I miss this. Working:
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]
Jul 26 2016
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
I have arbitrary polygon. I need any solution. Performance is does not matter at current moment.
Jul 26 2016
"H. S. Teoh via Digitalmars-d-learn" <digitalmars-d-learn puremagic.com> 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
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
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:[...] 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.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.
Jul 26 2016
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: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.On Tuesday, 26 July 2016 at 17:38:43 UTC, Suliman wrote:[...] Unfortunately he wants to handle arbitrary polygons that are not necessarily convex. TI 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.
Jul 26 2016
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
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
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
On Wednesday, 27 July 2016 at 12:47:14 UTC, chmike wrote:On Wednesday, 27 July 2016 at 09:39:18 UTC, Suliman wrote: ...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_ heavyBig 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
On Wednesday, 27 July 2016 at 14:56:13 UTC, Suliman wrote:On Wednesday, 27 July 2016 at 12:47:14 UTC, chmike wrote:clipOn Wednesday, 27 July 2016 at 09:39:18 UTC, Suliman wrote: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_ heavySo 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
On Wednesday, 27 July 2016 at 09:39:18 UTC, Suliman wrote:On Wednesday, 27 July 2016 at 08:40:15 UTC, chmike wrote: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.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
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]
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 2017