C # Point in polygon

Sto provando a determinare se un punto si trova all’interno di un poligono. il poligono è definito da una matrice di oggetti punto. Posso facilmente capire se il punto si trova all’interno della casella del poligono delimitata, ma non sono sicuro di come dire se si trova all’interno del poligono reale o meno. Se ansible, mi piacerebbe usare solo C # e WinForms. Preferisco non chiamare su OpenGL o qualcosa per fare questo compito semplice.

Ecco il codice che ho finora:

private void CalculateOuterBounds() { //m_aptVertices is a Point[] which holds the vertices of the polygon. // and X/Y min/max are just ints Xmin = Xmax = m_aptVertices[0].X; Ymin = Ymax = m_aptVertices[0].Y; foreach(Point pt in m_aptVertices) { if(Xmin > pt.X) Xmin = pt.X; if(Xmax  pt.Y) Ymin = pt.Y; if(Ymax < pt.Y) Ymax = pt.Y; } } public bool Contains(Point pt) { bool bContains = true; //obviously wrong at the moment :) if(pt.X  Xmax || pt.Y  Ymax) bContains = false; else { //figure out if the point is in the polygon } return bContains; } 

Vedi questo è in c ++ e può essere fatto in c # allo stesso modo.

per poligono convesso è troppo facile:

Se il poligono è convesso, allora si può considerare il poligono come un “percorso” dal primo vertice. Un punto si trova all’interno di questi poligoni se è sempre sullo stesso lato di tutti i segmenti di linea che costituiscono il percorso.

Dato un segmento di linea tra P0 (x0, y0) e P1 (x1, y1), un altro punto P (x, y) ha la seguente relazione con il segmento di linea. Calcola (y – y0) (x1 – x0) – (x – x0) (y1 – y0)

se è inferiore a 0, P si trova a destra del segmento di linea, se maggiore di 0 è a sinistra, se uguale a 0, si trova sul segmento di linea.

Ecco il suo codice in c #, non ho controllato casi limite.

  public static bool IsInPolygon(Point[] poly, Point point) { var coef = poly.Skip(1).Select((p, i) => (point.Y - poly[i].Y)*(pX - poly[i].X) - (point.X - poly[i].X) * (pY - poly[i].Y)) .ToList(); if (coef.Any(p => p == 0)) return true; for (int i = 1; i < coef.Count(); i++) { if (coef[i] * coef[i - 1] < 0) return false; } return true; } 

Lo collaudo con un semplice rettangolo funziona bene:

  Point[] pts = new Point[] { new Point { X = 1, Y = 1 }, new Point { X = 1, Y = 3 }, new Point { X = 3, Y = 3 }, new Point { X = 3, Y = 1 } }; IsInPolygon(pts, new Point { X = 2, Y = 2 }); ==> true IsInPolygon(pts, new Point { X = 1, Y = 2 }); ==> true IsInPolygon(pts, new Point { X = 0, Y = 2 }); ==> false 

Spiegazione sulla query linq:

poly.Skip(1) ==> crea una nuova lista avviata dalla posizione 1 della lista poly e quindi da (point.Y - poly[i].Y)*(pX - poly[i].X) - (point.X - poly[i].X) * (pY - poly[i].Y) andremo a calcolare la direzione (che è menzionata nel paragrafo di riferimento). esempio simile (con un'altra operazione):

 lst = 2,4,8,12,7,19 lst.Skip(1) ==> 4,8,12,7,19 lst.Skip(1).Select((p,i)=>p-lst[i]) ==> 2,4,4,-5,12 

Ho controllato i codici qui e tutti hanno problemi.

Il metodo migliore è:

  ///  /// Determines if the given point is inside the polygon ///  /// the vertices of polygon /// the given point /// true if the point is inside the polygon; otherwise, false public static bool IsPointInPolygon4(PointF[] polygon, PointF testPoint) { bool result = false; int j = polygon.Count() - 1; for (int i = 0; i < polygon.Count(); i++) { if (polygon[i].Y < testPoint.Y && polygon[j].Y >= testPoint.Y || polygon[j].Y < testPoint.Y && polygon[i].Y >= testPoint.Y) { if (polygon[i].X + (testPoint.Y - polygon[i].Y) / (polygon[j].Y - polygon[i].Y) * (polygon[j].X - polygon[i].X) < testPoint.X) { result = !result; } } j = i; } return result; } 

La risposta accettata non ha funzionato per me nel mio progetto. Ho finito per usare il codice trovato qui .

 public static bool IsInPolygon(Point[] poly, Point p) { Point p1, p2; bool inside = false; if (poly.Length < 3) { return inside; } var oldPoint = new Point( poly[poly.Length - 1].X, poly[poly.Length - 1].Y); for (int i = 0; i < poly.Length; i++) { var newPoint = new Point(poly[i].X, poly[i].Y); if (newPoint.X > oldPoint.X) { p1 = oldPoint; p2 = newPoint; } else { p1 = newPoint; p2 = oldPoint; } if ((newPoint.X < pX) == (pX <= oldPoint.X) && (pY - (long) p1.Y)*(p2.X - p1.X) < (p2.Y - (long) p1.Y)*(pX - p1.X)) { inside = !inside; } oldPoint = newPoint; } return inside; } 

Puoi usare l’algoritmo di ray casting. È ben descritto nella pagina di wikipedia per il problema Punto nel poligono .

È semplice contare il numero di volte in cui un raggio dall’esterno a quel punto tocca i confini del poligono. Se tocca un numero pari di volte, il punto si trova all’esterno del poligono. Se tocca un numero dispari di volte, il punto è all’interno.

Per contare il numero di volte che il raggio tocca, controlli le intersezioni tra il raggio e tutti i lati del poligono.

La mia risposta è presa da qui: Link

Ho preso il codice C e l’ho convertito in C # e l’ho fatto funzionare

 static bool pnpoly(PointD[] poly, PointD pnt ) { int i, j; int nvert = poly.Length; bool c = false; for (i = 0, j = nvert - 1; i < nvert; j = i++) { if (((poly[i].Y > pnt.Y) != (poly[j].Y > pnt.Y)) && (pnt.X < (poly[j].X - poly[i].X) * (pnt.Y - poly[i].Y) / (poly[j].Y - poly[i].Y) + poly[i].X)) c = !c; } return c; } 

Puoi testarlo con questo esempio:

 PointD[] pts = new PointD[] { new PointD { X = 1, Y = 1 }, new PointD { X = 1, Y = 2 }, new PointD { X = 2, Y = 2 }, new PointD { X = 2, Y = 3 }, new PointD { X = 3, Y = 3 }, new PointD { X = 3, Y = 1 }}; List lst = new List(); lst.Add(pnpoly(pts, new PointD { X = 2, Y = 2 })); lst.Add(pnpoly(pts, new PointD { X = 2, Y = 1.9 })); lst.Add(pnpoly(pts, new PointD { X = 2.5, Y = 2.5 })); lst.Add(pnpoly(pts, new PointD { X = 1.5, Y = 2.5 })); lst.Add(pnpoly(pts, new PointD { X = 5, Y = 5 })); 

Algoritmo completo insieme al codice C è disponibile su http://alienryderflex.com/polygon/
La conversione in c # / winforms sarebbe banale.

Raccomando questo meraviglioso documento di 15 pagine di Kai Hormann (Università di Erlangen) e Alexander Agathos (Università di Atene). Consolida tutti i migliori algoritmi e consente di rilevare sia le soluzioni di avvolgimento che quelle di ray-casting.

Il punto nel problema del poligono per i poligoni arbitrari

L’algoritmo è interessante da implementare e ne vale la pena. Tuttavia, è così complesso che è inutile per me per qualsiasi parte di esso direttamente. Continuerò invece a dire che se si desidera l’algoritmo più efficiente e versatile, sono certo che sia così.

L’algoritmo si complica perché è molto ottimizzato, quindi richiederà molte letture per capire e implementare. Tuttavia, combina i vantaggi degli algoritmi del numero di raggi e degli avvolgimenti e il risultato è un numero singolo che fornisce entrambe le risposte contemporaneamente. Se il risultato è maggiore di zero e dispari, il punto è completamente contenuto, ma se il risultato è un numero pari, il punto è contenuto in una sezione del poligono che si ripiega su se stesso.

In bocca al lupo.

meowNET anwser non include i vertici di Polygon nel poligono e punta esattamente sui bordi orizzontali. Se hai bisogno di un algoritmo “inclusivo” esatto:

 public static bool IsInPolygon(this Point point, IEnumerable polygon) { bool result = false; var a = polygon.Last(); foreach (var b in polygon) { if ((bX == point.X) && (bY == point.Y)) return true; if ((bY == aY) && (point.Y == aY) && (aX <= point.X) && (point.X <= bX)) return true; if ((bY < point.Y) && (aY >= point.Y) || (aY < point.Y) && (bY >= point.Y)) { if (bX + (point.Y - bY) / (aY - bY) * (aX - bX) <= point.X) result = !result; } a = b; } return result; }