如何判断一条线是否与C#中的多边形相交？

Question

我有一个非常类似的问题:

如何知道一条线是否与C#中的平面相交？

我正在寻找一种方法(在C#中),它告诉一条线是否与任意多边形相交.

我认为Chris Marasti-Georg的算法非常有用,但缺少最重要的方法,即线对线交叉.

有没有人知道一个线交叉方法来完成Chris Marasti-Georg的代码或有类似的东西？

在C#中是否有内置代码？

此方法适用于使用禁区功能增强的Bing Maps算法.生成的路径不得通过禁区(任意多边形).

Answer 1

.NET框架内置的边缘检测没有内置代码.

这里的代码(移植到C#)可以满足您的需求(实际的算法可以在Google组上的comp.graphics.algorithms中找到):

public static PointF FindLineIntersection(PointF start1, PointF end1, PointF start2, PointF end2)
{
    float denom = ((end1.X - start1.X) * (end2.Y - start2.Y)) - ((end1.Y - start1.Y) * (end2.X - start2.X));

    //  AB & CD are parallel 
    if (denom == 0)
        return PointF.Empty;

    float numer = ((start1.Y - start2.Y) * (end2.X - start2.X)) - ((start1.X - start2.X) * (end2.Y - start2.Y));

    float r = numer / denom;

    float numer2 = ((start1.Y - start2.Y) * (end1.X - start1.X)) - ((start1.X - start2.X) * (end1.Y - start1.Y));

    float s = numer2 / denom;

    if ((r < 0 || r > 1) || (s < 0 || s > 1))
        return PointF.Empty;

    // Find intersection point
    PointF result = new PointF();
    result.X = start1.X + (r * (end1.X - start1.X));
    result.Y = start1.Y + (r * (end1.Y - start1.Y));

    return result;
 }