Làm cách nào để biết hai đa giác có giao nhau không?

Question

Hãy tưởng tượng tôi có tọa độ của 4 điểm tạo thành một đa giác. Những điểm này được biểu diễn bằng PointF trong C#. Nếu tôi có 2 đa giác (sử dụng 8 điểm), làm thế nào tôi có thể biết liệu chúng có giao nhau không?

Lớp hình chữ nhật có một phương thức gọi là IntersectsWith nhưng tôi không thể tìm thấy thứ gì đó tương tự cho GraphicsPath hoặc Region.

Mọi lời khuyên sẽ được đánh giá cao.

Mosh

Answer 1

Vì Charlie đã chỉ ra rằng bạn có thể sử dụng định lý Trục tách. Kiểm tra this article để thực hiện C# và ví dụ về phát hiện va chạm đa giác.

Tôi cũng đã trả lời câu hỏi này here đề cập đến xung đột 2D trong C#.

Answer 2

Nếu đa giác của bạn là lồi sau đó bạn sẽ có thể sử dụng separating axis theorem. Một bản demo có sẵn here (Đó là trong actionscript nhưng mã nên dễ dàng để cổng để C#)

Điều này thực sự không phải là khu vực của tôi nhưng tôi hy vọng nó sẽ giúp anyway.

Answer 3

Nói đúng ra, các câu trả lời khác cho thấy thuật toán có lẽ là cách tốt nhất cho bạn. Nhưng hiệu suất sang một bên, bạn đã đề cập rằng bạn không thể tìm thấy bất cứ thứ gì như IntersectsWith cho GraphicsPath hoặc Region. Tuy nhiên, có một phương thức Intersect cập nhật một vùng là giao điểm của chính nó và một vùng hoặc đường dẫn khác. Bạn có thể tạo hai vùng, Intersect() cái kia, sau đó kiểm tra Region.IsEmpty().

Nhưng tôi tưởng tượng điều này có lẽ là một cách khá chậm để làm điều đó và có thể sẽ dẫn đến rất nhiều phân bổ nếu thực hiện trong một vòng lặp.

Answer 4

Đây là một câu hỏi cũ, nhưng tôi nghĩ tôi cũng sẽ chia sẻ giải pháp của mình. Region.IsEmpty() đòi hỏi một bối cảnh đồ họa và từ sự hiểu biết của tôi chỉ được thiết kế để thực hiện kiểm tra hit chính xác pixel. Đây không phải là lý tưởng cho nhiều tình huống. Một giải pháp tốt hơn là sử dụng thư viện Clipper của Angus Johnson. Theo kinh nghiệm của tôi, đây là một thư viện được kiểm tra nhanh. Bạn có thể cung cấp độ chính xác của riêng bạn và nó xử lý các đa giác cực kỳ phức tạp.

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

Có triển khai C#. Những gì bạn cần làm là thực hiện một thao tác giao cắt giống như phương thức System.Drawing.Region. Sau đó kiểm tra kết quả của hoạt động. Nếu nó trống không có giao lộ. Nếu nó chứa dữ liệu thì dữ liệu là điểm giao nhau.

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

Một số phương pháp bạn sẽ thấy hữu ích cho việc này.

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

Và để thực hiện một giao

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