İki poligonun kesiştiğini nasıl anlarım?

Question

Bir çokgen oluşturan 4 noktanın koordinatına sahip olduğumu düşünün. Bu noktalar C# ile PointF kullanılarak temsil edilir. Eğer 2 çokgen varsa (8 puan kullanarak), kesişip kırılmadıklarını nasıl anlarım?

Rectangle sınıfında IntersectsWith adlı bir yöntem var ancak GraphicsPath veya Region için benzer bir şey bulamadım.

Her türlü öneri çok takdir edilecektir.

Mosh

Answer 1

Charlie'nin zaten işaret ettiği gibi, Ayırma Ekseni teoremini kullanabilirsiniz. C# uygulaması ve çokgen çarpışma algılaması örneği için this article'a bakın.

Ayrıca C# 2'de 2 boyutlu çarpışma ile ilgilenen bu soruyu here da yanıtladı.

Answer 2

sizin çokgenler dışbükey ise o zaman separating axis theorem kullanmak gerekir. Bir demo kullanılabilir here (Bu actioncript içinde ama kod c port için kolay olmalıdır)

Bu gerçekten benim alanım değil ama umarım yine de yardımcı olur.

Answer 3

Kesinlikle, bir algoritmayı öneren diğer cevaplar muhtemelen en iyi bahistir. Ancak performans bir yana, GraphicsPath veya Region için IntersectsWith gibi bir şey bulamadığınızı belirttiniz. Bununla birlikte, bir bölgenin kendisini ve başka bir bölgeyi veya yolu kesiştirmesi için güncelleyen bir Kesişim yöntemi vardır. İki bölgeyi, Intersect() birini diğeriyle oluşturabilir, ardından Region.IsEmpty() için test edebilirsiniz.

Ama bunun muhtemelen yapmanın oldukça yavaş bir yolu olduğunu ve muhtemelen bir döngüde gerçekleştirildiğinde çok fazla tahsisatla sonuçlanacağını hayal ediyorum.

Answer 4

Bu eski bir soru, ama çözümümü de paylaşacağımı düşündüm. Region.IsEmpty() bir Grafik içeriği gerektirir ve benim anlayışım sadece piksel hassas vuruş testi yapmak için tasarlanmıştır. Bu birçok durum için ideal değildir. Çok daha iyi bir çözüm, Clipper kütüphanesinin Angus Johnson tarafından kullanılmasıdır. Benim tecrübemde bu hızlı test edilmiş bir kütüphanedir. Kendi hassaslığınızı sağlayabilir ve son derece karmaşık çokgenler kullanır.

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

C# uygulaması vardır. Yapmanız gereken şey, System.Drawing.Region yöntemi gibi bir kesişim işlemi gerçekleştirmektir. Ardından işlemin sonucunu inceleyin. Boşsa, kesişme yoktu. Veri içeriyorsa, veriler kesişen noktalardır.

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

Bazı yöntemler bunun için kullanışlı bulur. iki kesişen değilse

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

Ve bir kesişme Şaşırtıcı

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