## 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:
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
"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
Suliman <evermind live.ru> writes:
```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> 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
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
"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
```
Jul 26 2016
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
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
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
```
Jul 27 2016
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

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
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

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
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
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

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
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 2017