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.

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

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.

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.