logo标签列表

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

c#geometry2dbing-mapscomputational-geometry
9
我有一个问题与这个非常相似：

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

我正在寻找一种方法（使用C#语言），可以判断一条线是否与任意多边形相交。
我认为Chris Marasti-Georg的算法非常有帮助，但缺少最重要的方法，即线与线的交点。
有人知道一个线段交点的方法来完成Chris Marasti-Georg的代码或类似的代码吗？
在C#中是否有内置代码可用于此？
这种方法是用于Bing Maps算法的，增加了禁止区域功能。结果路径必须不穿过禁止区域（任意多边形）。
4个回答
22

在.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;
 }
3
略微偏题，但如果这条线是无限长的，我认为有一个更简单的解决方案：
当所有点都在同一条线的一侧时，该线就不会穿过多边形。
借助以下两个链接： 我得到了这个小技巧：
  public class PointsAndLines
  {
    public static bool IsOutside(Point lineP1, Point lineP2, IEnumerable<Point> region)
    {
      if (region == null || !region.Any()) return true;
      var side = GetSide(lineP1, lineP2, region.First());
      return
        side == 0
        ? false
        : region.All(x => GetSide(lineP1, lineP2, x) == side);
    }

    public static int GetSide(Point lineP1, Point lineP2, Point queryP)
    {
      return Math.Sign((lineP2.X - lineP1.X) * (queryP.Y - lineP1.Y) - (lineP2.Y - lineP1.Y) * (queryP.X - lineP1.X));
    }
  }
1
在我们的Silverlight地图项目中，为了检测多边形之间的碰撞，我们使用Clipper库：
该库免费商用，体积小，性能出色且非常易于使用。 Clipper网页
0

这篇文章看起来很有帮助

http://www.codeproject.com/KB/recipes/2dpolyclip.aspx

这段代码是一个二维多边形裁剪算法，可以精确地确定一条直线与多边形边界相交的位置。此代码适用于任意形状的凸多边形和凹多边形，并能够处理任何线的方向。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接