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

Question

我有一个与此非常相似的问题：

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

我正在寻找一种方法（在 C# 中）来判断是否线与任意多边形相交。

我认为 Chris Marasti-Georg 的算法非常有帮助，但缺少最重要的方法，即线与线相交。

有谁知道线相交方法来完成 Chris Marasti-Georg 的代码或有类似的方法吗？

C# 中有内置代码吗？

此方法适用于通过禁区功能增强的 Bing 地图算法。 生成的路径不得穿过禁区（任意多边形）。

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

Answer 2

有点偏离主题，但如果该线是无限，我认为有一个更简单的解决方案：

如果所有点都位于多边形的同一侧，则该线不会穿过多边形线。

在这两个的帮助下：

• 使用 linq 或其他方式，如何检查所有列表项是否具有相同的值并返回它，或者如果没有则返回“otherValue”？
• 确定点位于线的哪一侧

我得到了这个小宝石：

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

Answer 3

为了检测 silverlight 地图项目中多边形之间的碰撞，我们使用 Clipper 库：

免费用于商业用途、尺寸小、性能出色且非常易于使用。

Clipper 网页

Answer 4

这篇文章看起来会有所帮助

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

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