Come posso sapere se due poligoni si intersecano?

Question

Immaginate di avere le coordinate di 4 punti che formano un poligono. Questi punti sono rappresentati usando PointF in C#. Se ho 2 poligoni (usando 8 punti), come posso sapere se si intersecano?

La classe Rectangle ha un metodo denominato IntersectsWith ma non è stato possibile trovare qualcosa di simile per GraphicsPath o Region.

Qualsiasi consiglio sarebbe molto apprezzato.

Mosh

Answer 1

Come già sottolineato da Charlie, è possibile utilizzare il teorema dell'asse di separazione. Verificare this article per un'implementazione C# e un esempio di rilevamento di collisione poligono.

Ho anche risposto a questa domanda here che si occupa della collisione 2D in C#.

Answer 2

Se i poligoni sono convesse allora si dovrebbe essere in grado di utilizzare separating axis theorem. È disponibile una demo here (È in ActionScript ma il codice dovrebbe essere facile da portare a C#)

Questa non è la mia area ma spero che sia d'aiuto comunque.

Answer 3

In senso stretto, le altre risposte che suggeriscono un algoritmo sono probabilmente la soluzione migliore. Ma a parte le prestazioni, hai detto che non potresti trovare nulla come IntersectsWith per GraphicsPath o Region. Tuttavia esiste un metodo Intersect che aggiorna una regione come intersezione di se stessa e un'altra regione o percorso. È possibile creare due regioni, Intersect() l'una con l'altra, quindi testare per Region.IsEmpty().

Ma immagino che questo sia probabilmente un modo piuttosto lento per farlo e probabilmente si tradurrebbe in un sacco di allocazioni se fatto in un ciclo.

Answer 4

Questa è una vecchia domanda, ma ho pensato di condividere anche la mia soluzione. Region.IsEmpty() richiede un contesto di grafica e dalla mia comprensione è progettato solo per eseguire il test di hit precisione pixel. Questo non è l'ideale per molte situazioni. Una soluzione molto migliore è usare la libreria Clipper di Angus Johnson. Nella mia esperienza questa è una libreria veloce e ben testata. Puoi fornire la tua precisione e gestisce poligoni estremamente complessi.

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

C'è un'implementazione C#. Quello che dovresti fare è eseguire un'operazione di intersezione come il metodo System.Drawing.Region. Quindi esaminare il risultato dell'operazione. Se è vuoto non ci sono intersezioni. Se contiene dati, i dati sono i punti di intersezione.

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

Alcuni metodi si potrebbe trovare utile per questo.

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

E per eseguire un incrocio

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