How can I tell if two polygons intersect?

Question

Imagine I have the coordinate of 4 points that form a polygon. These points are represented using PointF in C#. If I have 2 polygons (using 8 points), how can I tell if they intersect?

Rectangle class has a method called IntersectsWith but I couldn't find something similar for GraphicsPath or Region.

Any advice would be greatly appreciated.

Mosh

Answer 1

As Charlie already pointed out you can use the Separating Axis theorem. Check out this article for a C# implementation and example of polygon collision detection.

I have also answered this question here which deals with 2D collision in C#.

Answer 2

Strictly speaking, the other answers suggesting an algorithm are probably your best bet. But performance aside, you mentioned that you couldn't find anything like IntersectsWith for GraphicsPath or Region. However there is an Intersect method that updates a region to be the intersection of itself and another region or path. You could create two regions, Intersect() one with the other, then test for Region.IsEmpty().

But I imagine this is probably a pretty slow way to do it and would probably result in a lot of allocations if done in a loop.

Answer 3

If your polygons are convex then you should be able to use separating axis theorem. A demo is available here (It's in actionscript but the code should be easy to port to c#)

This is really not my area but I hope it helps anyway.

Answer 4

This is an old question, but I thought I would share my solution also. Region.IsEmpty() requires a Graphics context and from my understanding is only designed to perform pixel precision hit testing. This is not ideal for many situations. A much better solution is to use the Clipper library by Angus Johnson. In my experience this is a fast well tested library. You can provide your own precision and it handles extremely complex polygons.

http://www.angusj.com/delphi/clipper.php

There is a C# implementation. What you would need to do is perform an intersection operation just like the System.Drawing.Region method. Then examine the result of the operation. If it is empty there was no intersection. If it contains data then the data is the intersecting points.

http://www.angusj.com/delphi/clipper/documentation/Docs/Units/ClipperLib/Types/ClipType.htm

Some methods you would find useful for this.

private static int scale = 1000; //your desired precision

        public static List<List<IntPoint>> ConvertToClipperPolygons(GraphicsPath path)
    {
        var Polygon = new List<IntPoint>();
        var Polygons = new List<List<IntPoint>>();

        var it = new GraphicsPathIterator(path);
        it.Rewind();
        bool isClosed;
        int startIndex;
        int endIndex;
        for (int i = 0; i < it.SubpathCount; i++)
        {
            var PointCount = it.NextSubpath(out startIndex, out endIndex, out isClosed);

            var Points = new PointF[PointCount];
            var Types = new byte[PointCount];
            it.CopyData(ref Points, ref Types, startIndex, endIndex);
            Polygons.Add(new List<IntPoint>(Points.Select(x => new IntPoint(Convert.ToInt64(x.X * scale), Convert.ToInt64(x.Y * scale)))));

        }
        it.Dispose();
        return Polygons;
    }

And to perform an intersection

        public static GraphicsPath intersect(ref GraphicsPath p1, ref GraphicsPath p2)
    {
        List<List<IntPoint>> polygonB = ConvertToClipperPolygons(p1);
        List<List<IntPoint>> polygons = new List<List<IntPoint>>();
        List<List<IntPoint>> polygonA = ConvertToClipperPolygons(p2);

        Clipper c = new Clipper();
        c.AddPolygons(polygonB, PolyType.ptSubject);
        c.AddPolygons(polygonA, PolyType.ptClip);
        c.Execute(ClipType.ctIntersection, polygons, PolyFillType.pftEvenOdd, PolyFillType.pftEvenOdd);

        return ConvertClipperToGraphicsPath(polygons);
    }
        public static GraphicsPath ConvertClipperToGraphicsPath(List<List<IntPoint>> path)
    {
        GraphicsPath returnPath = new GraphicsPath();

        for (int i = 0; i < path.Count; i++)
        {
            returnPath.AddPolygon(ToPointList(path[i]).ToArray());
        }
        return returnPath;
    }
        private static List<PointF> ToPointList(List<IntPoint> pointList)
    {

        List<PointF> newList = new List<PointF>();
        foreach (IntPoint pt in pointList)
        {
            newList.Add(new PointF(((float)pt.X / (float)scale), ((float)pt.Y / (float)scale)));
        }

        return newList;
    }