如何判断两个多边形是否相交？

Question

想象一下，我有4个点的坐标形成一个多边形。这些点在C＃中使用PointF表示。如果我有2个多边形（使用8点），我怎么知道它们是否相交？

Rectangle类有一个名为IntersectsWith的方法，但我找不到类似的GraphicsPath或Region。

任何意见将不胜感激。

MOSH

Answer 1

查理已经指出你可以使用分离轴定理。 检查出this article的C＃实现和多边形碰撞检测的例子。

我也回答了这个问题here它处理C＃中的二维碰撞。

Answer 2

如果您的多边形是凸的，那么你应该能够使用separating axis theorem。一个演示可用here（它是在actionscript中，但代码应该很容易移植到C＃）

这真的不是我的领域，但我希望它有帮助。

Answer 3

严格地说，其他答案暗示算法可能是你最好的选择。但除了性能，你提到你找不到像GraphicsPath或Region的IntersectsWith。然而，有一种Intersect方法将区域更新为自身与其他区域或路径的交集。您可以创建两个区域，即Intersect（）与另一个区域，然后测试Region.IsEmpty（）。

但我想这可能是一个非常缓慢的方式来做到这一点，如果在循环中完成，可能会导致大量的分配。

Answer 4

这是一个老问题，但我想我也会分享我的解决方案。 Region.IsEmpty（）需要一个Graphics上下文，根据我的理解，它只是设计用于执行像素精度命中测试。这在许多情况下并不理想。更好的解决方案是使用Angus Johnson的Clipper库。根据我的经验，这是一个快速经过良好测试的库。您可以提供自己的精度，并处理极其复杂的多边形。

http://www.angusj.com/delphi/clipper.php

有一个C＃实现。你需要做的就是像System.Drawing.Region方法一样执行交集操作。然后检查操作的结果。如果它是空的，那就没有交集。如果它包含数据，那么数据就是相交点。

http://www.angusj.com/delphi/clipper/documentation/Docs/Units/ClipperLib/Types/ClipType.htm

一些方法，你会发现这个有用。

private static int scale = 1000; //your desired precision 

     public static List<List<IntPoint>> ConvertToClipperPolygons(GraphicsPath path) 
    { 
     var Polygon = new List<IntPoint>(); 
     var Polygons = new List<List<IntPoint>>(); 

     var it = new GraphicsPathIterator(path); 
     it.Rewind(); 
     bool isClosed; 
     int startIndex; 
     int endIndex; 
     for (int i = 0; i < it.SubpathCount; i++) 
     { 
      var PointCount = it.NextSubpath(out startIndex, out endIndex, out isClosed); 

      var Points = new PointF[PointCount]; 
      var Types = new byte[PointCount]; 
      it.CopyData(ref Points, ref Types, startIndex, endIndex); 
      Polygons.Add(new List<IntPoint>(Points.Select(x => new IntPoint(Convert.ToInt64(x.X * scale), Convert.ToInt64(x.Y * scale))))); 

     } 
     it.Dispose(); 
     return Polygons; 
    } 

而执行交叉点

 public static GraphicsPath intersect(ref GraphicsPath p1, ref GraphicsPath p2) 
    { 
     List<List<IntPoint>> polygonB = ConvertToClipperPolygons(p1); 
     List<List<IntPoint>> polygons = new List<List<IntPoint>>(); 
     List<List<IntPoint>> polygonA = ConvertToClipperPolygons(p2); 

     Clipper c = new Clipper(); 
     c.AddPolygons(polygonB, PolyType.ptSubject); 
     c.AddPolygons(polygonA, PolyType.ptClip); 
     c.Execute(ClipType.ctIntersection, polygons, PolyFillType.pftEvenOdd, PolyFillType.pftEvenOdd); 

     return ConvertClipperToGraphicsPath(polygons); 
    } 
     public static GraphicsPath ConvertClipperToGraphicsPath(List<List<IntPoint>> path) 
    { 
     GraphicsPath returnPath = new GraphicsPath(); 

     for (int i = 0; i < path.Count; i++) 
     { 
      returnPath.AddPolygon(ToPointList(path[i]).ToArray()); 
     } 
     return returnPath; 
    } 
     private static List<PointF> ToPointList(List<IntPoint> pointList) 
    { 

     List<PointF> newList = new List<PointF>(); 
     foreach (IntPoint pt in pointList) 
     { 
      newList.Add(new PointF(((float)pt.X/(float)scale), ((float)pt.Y/(float)scale))); 
     } 

     return newList; 
    }