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

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.

I have arbitrary polygon. I need any solution. Performance is does not matter at current moment.

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

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.

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.

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.

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.

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.

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 ?