是否有检测除PathGeometry.FillContainsWithDetail多边形重叠/交叉点

我有一个在占用我的CPU时间25％的方法。我打电话约每秒27000次此方法。（是啊，很多电话，因为它经常更新）。我想知道如果任何人知道一个更快的方法，如果2个多边形重叠检测。基本上，我有要检查的屏幕上静止物体在屏幕上移动的物体。我使用的PathGeometry和下方的两个呼叫使用了由我的程序所使用的CPU时间的25％。我传递的PointCollection对象只包含代表4角的多边形的4分。他们可能不创建一个矩形区域，但所有的点连接。我猜trapazoid将是形状。

这些方法很短，很容易实现，但我想我可能要选择一个更复杂的解决方案，如果我能有比下面的代码运行得更快。有任何想法吗？

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;
}

好了，大量的研究和发现许多部分答案，但没有能够完全回答了这个问题之后，我已经找到了更快的方法，它实际上是比旧方法快约4.6倍。

我创建了一个特殊的测试程序来测试速度这一点。你可以找到测试程序在这里。如果你下载它，你可以在应用程序的顶部看到一个复选框。检查并取消它的老路上和新方式之间来回切换。该应用程序产生一个随机一堆多边形和多边形的边框变为白色，当它们相交的另一面。到“重绘”按钮左边的数字是允许你进入多边形的数量，侧面的最大长度，和最大的广场偏移量（以使他们少方，更奇形）。按“刷新”来清除和再生与您输入的设置新的多边形。

不管怎么说，这是两个不同的实现代码。您通过组成每个多边形点的收藏。旧的方式使用更少的代码，但比新的方法要慢4.6倍 。

哦，一个快速的注意。新办法有几个调用“PointIsInsidePolygon”。这些都是必要的，因为没有它，当一个多边形不同的多边形内被完全包含在方法返回false。但PointIsInsidePolygon方法解决这个问题。

希望这一切都有助于别人出与多边形拦截和重叠。

老方法（4.6倍慢是真的慢4.6次 ）。：

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;
}

新路（快4.6倍是真的4.6倍的速度 ）：

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);
}