Is there a more efficient way to detect polygon overlap/intersection than PathGeometry.FillContainsWithDetail()?

Question

I have a method that is gobbling up 25% of my cpu time. I call this method about 27,000 times per second. (Yup, lots of calls since it's updating frequently). I am wondering if anybody knows a faster way to detect if 2 polygons overlap. Basically, I have to check the moving objects on the screen against stationary objects on the screen. I am using PathGeometry and the two calls below are using up 25% of the cpu time used by my program. The PointCollection objects I am passing just contain 4 points representing 4 corners of a polygon. They may not create a rectangular area, but all the points are connected. I guess a trapazoid would be the shape.

These methods are short and were very easy to implement, but I think I might want to opt for a more complicated solution if I can have it run more quickly than the code below. Any ideas?

public static bool PointCollectionsOverlap(PointCollection area1, PointCollection area2)
{
    PathGeometry pathGeometry1 = GetPathGeometry(area1);
    PathGeometry pathGeometry2 = GetPathGeometry(area2);
    return pathGeometry1.FillContainsWithDetail(pathGeometry2) != IntersectionDetail.Empty;
}

public static PathGeometry GetPathGeometry(PointCollection polygonCorners)
{
    List<PathSegment> pathSegments = new List<PathSegment> 
                                         { new PolyLineSegment(polygonCorners, true) };
    PathGeometry pathGeometry = new PathGeometry();
    pathGeometry.Figures.Add(new PathFigure(polygonCorners[0], pathSegments, true));
    return pathGeometry;
}

If you have so many objects, are you always testing every shape against every shape? Because first of all, you don't need to test all against all, set{a, b} 1)a->a, 2)a->b 3)b->a, 4)b->a; 4 tests that could be reduced to 1(just to explain what i meant). Otherwise you could sort your shapes into a quadtree or a simple grid for simplicity, and only use the expensive overlap test if 2 shapes share the same cell. You could also cache the PathGeometry object in your second method, at least for your stationary shapes. — dowhilefor, Jun 25 '12 at 18:59
At most, there are 100 shapes in set A and 16 shapes in set B. I loop through set A and for each item in set A, I check all shapes in set B, so I'm only checking what I need to and not duplicating any of the checking. I could cache the PathGeometries of my SetB shapes since they don't change very often. That would help. I'm not sure what is meant by sorting shapes into a quadtree though.. — Curtis, Jun 25 '12 at 19:24
Consider this image http://www.codeproject.com/KB/recipes/QuadTree/QuadTree4.png. You place your stationary shapes in the quadtree, generate bounding boxes for your dynamic ones, instead of testing every shape against every stationary shape. You first let your dynamic shape retrieve the cells in the quadtree which it currently overlaps, and these cells have the stationary shapes attached, so you know you only need to test these. Google Quadtree, its a pretty common and widely used datastructur for exactly this case. — dowhilefor, Jun 25 '12 at 20:12

Curtis · Accepted Answer · 2018-06-14T23:17:03.297

Ok, after lots of research and finding many partial answers, but none that fully answered the question, I have found a faster way and it is actually about 4.6 times faster than the old way.

I created a special test app to test the speed this. You can find the test app here. If you download it, you can see a checkbox at the top of the app. Check and uncheck it to switch back and forth between the old way and the new way. The app generates a bunch of random polygons and the borders of the polygons change to white when they intersect another polygon. The numbers to the left of the 'Redraw' button are to allow you to enter the Number of Polygons, Max Length of a side, and Max offset from square (to make them less square and more odd shaped). Push 'Refresh' to clear and regenerate new polygons with the settings you've entered.

Anyway, here is the code for the two different implementations. You pass in a collection of the points that make up each polygon. The old way uses less code, but is 4.6 times slower than the new way.

Oh, one quick note. The new way has a couple calls to 'PointIsInsidePolygon'. These were necessary because without it, the method returned false when one polygon was entirely contained within a different polygon. But the PointIsInsidePolygon method fixes that problem.

Hope this all helps somebody else out with polygon intercepts and overlaps.

Old Way (4.6 times slower. YES REALLY 4.6 TIMES slower):

public static bool PointCollectionsOverlap_Slow(PointCollection area1, PointCollection area2)
{
    PathGeometry pathGeometry1 = GetPathGeometry(area1);
    PathGeometry pathGeometry2 = GetPathGeometry(area2);
    bool result = pathGeometry1.FillContainsWithDetail(pathGeometry2) != IntersectionDetail.Empty;
    return result;
}

public static PathGeometry GetPathGeometry(PointCollection polygonCorners)
{
    List<PathSegment> pathSegments = new List<PathSegment> { new PolyLineSegment(polygonCorners, true) };
    PathGeometry pathGeometry = new PathGeometry();
    pathGeometry.Figures.Add(new PathFigure(polygonCorners[0], pathSegments, true));
    return pathGeometry;
}

New Way (4.6 times faster. YES REALLY 4.6 TIMES faster):

public static bool PointCollectionsOverlap_Fast(PointCollection area1, PointCollection area2)
{
    for (int i = 0; i < area1.Count; i++)
    {
        for (int j = 0; j < area2.Count; j++)
        {
            if (lineSegmentsIntersect(area1[i], area1[(i + 1) % area1.Count], area2[j], area2[(j + 1) % area2.Count]))
            {
                return true;
            }
        }
    }

    if (PointCollectionContainsPoint(area1, area2[0]) ||
        PointCollectionContainsPoint(area2, area1[0]))
    {
        return true;
    }

    return false;
}

public static bool PointCollectionContainsPoint(PointCollection area, Point point)
{
    Point start = new Point(-100, -100);
    int intersections = 0;

    for (int i = 0; i < area.Count; i++)
    {
        if (lineSegmentsIntersect(area[i], area[(i + 1) % area.Count], start, point))
        {
            intersections++;
        }
    }

    return (intersections % 2) == 1;
}

private static double determinant(Vector vector1, Vector vector2)
{
    return vector1.X * vector2.Y - vector1.Y * vector2.X;
}

private static bool lineSegmentsIntersect(Point _segment1_Start, Point _segment1_End, Point _segment2_Start, Point _segment2_End)
{
    double det = determinant(_segment1_End - _segment1_Start, _segment2_Start - _segment2_End);
    double t = determinant(_segment2_Start - _segment1_Start, _segment2_Start - _segment2_End) / det;
    double u = determinant(_segment1_End - _segment1_Start, _segment2_Start - _segment1_Start) / det;
    return (t >= 0) && (u >= 0) && (t <= 1) && (u <= 1);
}

Thank you so much for this. I was able to port this to javascript. To do that I borrowed this Point class http://upshots.org/javascript/javascript-point-class. Javascript Polyoverlap created here as gist: https://gist.github.com/3753426 — sdailey, Sep 20 '12 at 01:24
The linked website (gpwiki.org) is now serving malicious ads. Still available on the internet archive. — ManIkWeet, Jun 13 '18 at 12:19
Thank you for this, I just do not understand why Point start = new Point(-100, -100); ? — camillo777, Aug 06 '20 at 10:33
Well, it's been 8 years since I first wrote this up. I am sorry to say that I have no idea why I set Point start=new Point(-100, -100)... I just don't remember... I must be getting old.. — Curtis, Aug 08 '20 at 20:49
Note: If you have polygons with 100 to 1000 points, the '_Fast' method is ~40 times slower than '_Slow'. — sa.he, Mar 23 '23 at 09:00

Is there a more efficient way to detect polygon overlap/intersection than PathGeometry.FillContainsWithDetail()?

1 Answers1

Linked