How to detect overlapping polygons?

Question

I have a canvas where there are several polygons, what I want to do is try detect whether the polygons are overlapping. I'v looked around on various websites and most of what i'v found is to do with object collision - this for example, my polygons aren't moving so that's not going to be an issue. I was wondering if someone could point me in the right direction on how to detect if they are overlapping. Is there a method that can calculate the space that's used on screen? or the region of the Polygon to compare the two?

So for example like the mock up here, the red shape overlaps the green one. essentially all i want is to say yes they are overlapping or no they are not.

http://peterfleming.net84.net/Slice%201.png

Thanks in advance.

Pete

score 2 · Answer 1 · edited May 23 '17 at 11:53

This library here (free and open source) will show polygon clipping: http://www.angusj.com/delphi/clipper.php

That said, if by polygons overlapping you mean at least one point of one is inside the other, you can test each polygon's point against the others by either looking at the point in point polygon problem or checking each polygons lines to see if it cuts across another polygon.

These methods will all work with different efficiency, try and see what's best for your situation.

However, your diagram seems to suggest you want to see if these polygons are 'side by side' or something similar. It would help to get clarification on this. Overlapping generally needs some coordinate plan to determine overlap against.

Thanks @yamen, i will look at these solutions and see if they work for my situation. the diagram is isometric view of these shapes, so if you were to look down, on a plan view they would be one in front of the other, so i know that no polygons intersect each other or go through one another. — Peter, May 17 '12 at 12:55

score 0 · Answer 2 · answered May 17 '12 at 11:49

0

Assuming that each polygon is a Shape (either Path or Polygon) you could use the FillContainsWithDetail method of their RenderedGeometry to pairwise check interscetion.

answered May 17 '12 at 11:49

Clemens

123,504
12
155
268

score 0 · Answer 3 · answered Jun 17 '20 at 15:23

I was having the same problem too and I used this implementation (which is heavenly inspired by this: C# Point in polygon ):

bool DoesPolygonsOverlap(IList<Point> firstPolygon, IList<Point> secondPolygon)
{
    foreach (var item in firstPolygon)
    {
        if (IsPointInPolygon(secondPolygon, item))
        {
            return true;
        }
    }
    foreach (var item in secondPolygon)
    {
        if (IsPointInPolygon(firstPolygon, item))
        {
            return true;
        }
    }
    return false;
}

bool IsPointInPolygon(IList<Point> polygon, Point testPoint)
{
    bool result = false;
    int j = polygon.Count() - 1;
    for (int i = 0; i < polygon.Count(); i++)
    {
        if (polygon[i].Y < testPoint.Y && polygon[j].Y >= testPoint.Y || polygon[j].Y < testPoint.Y && polygon[i].Y >= testPoint.Y)
        {
            if (polygon[i].X + (testPoint.Y - polygon[i].Y) / (polygon[j].Y - polygon[i].Y) * (polygon[j].X - polygon[i].X) < testPoint.X)
            {
                result = !result;
            }
        }
        j = i;
    }
    return result;
}

Attention: The function was not very much tested and has a big potential for improvement. Please tell me if you find a bug/problem.

How to detect overlapping polygons?

3 Answers3