Point C # dans un polygone

J’essaie de déterminer si un point est à l’intérieur d’un polygone. le polygone est défini par un tableau d’objects Point. Je peux facilement déterminer si le point se trouve à l’intérieur de la boîte entourée du polygone, mais je ne sais pas comment dire s’il se trouve ou non à l’intérieur du polygone. Si possible, j’aimerais utiliser uniquement C # et WinForms. Je préférerais ne pas faire appel à OpenGL ou à quelque chose pour faire cette tâche simple.

Voici le code que j’ai jusqu’à présent:

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

Voyez cela c’est en c ++ et peut être fait en c # de la même manière.

pour un polygone convexe est trop facile:

Si le polygone est convexe, on peut le considérer comme un “chemin” à partir du premier sumt. Un point se trouve à l’intérieur de ces polygones s’il se trouve toujours du même côté de tous les segments constituant le tracé.

Soit un segment de droite compris entre P0 (x0, y0) et P1 (x1, y1), un autre point P (x, y) présente la relation suivante avec le segment de ligne. Calculer (y – y0) (x1 – x0) – (x – x0) (y1 – y0)

si elle est inférieure à 0 alors P est à droite du segment, si elle est supérieure à 0, elle est à gauche, si elle est égale à 0, elle est située sur le segment.

Voici son code en c #, je n’ai pas vérifié les cas de bord.

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

Je le teste avec un rectangle simple qui fonctionne bien:

  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 

Explication sur la requête linq:

poly.Skip(1) ==> crée une nouvelle liste à partir de la position 1 de la liste poly , puis de (point.Y - poly[i].Y)*(pX - poly[i].X) - (point.X - poly[i].X) * (pY - poly[i].Y) nous allons calculer la direction (indiquée dans le paragraphe référencé). exemple similaire (avec une autre opération):

 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 

J’ai vérifié les codes ici et tous ont des problèmes.

La meilleure méthode est:

  ///  /// 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 réponse acceptée n’a pas fonctionné pour moi dans mon projet. J’ai fini par utiliser le code trouvé ici .

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

Vous pouvez utiliser l’algorithme de casting de rayons. Il est bien décrit dans la page wikipedia du problème Point in polygon .

C’est aussi simple que de compter le nombre de fois qu’un rayon de l’extérieur à ce point touche les limites du polygone. S’il touche un nombre pair de fois, le point est en dehors du polygone. S’il touche un nombre impair de fois, le point est à l’intérieur.

Pour compter le nombre de fois que le rayon est en contact, vous vérifiez les intersections entre le rayon et tous les côtés du polygone.

Ma réponse est tirée d’ici: Lien

J’ai pris le code C et l’ai converti en C # et l’ai fait fonctionner

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

Vous pouvez le tester avec cet exemple:

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

L’algorithme complet avec le code C est disponible sur http://alienryderflex.com/polygon/
La convertir en c # / winforms serait sortingvial.

Je recommande ce merveilleux article de 15 pages rédigé par Kai Hormann (Université d’Erlangen) et Alexander Agathos (Université d’Athènes). Il consolide tous les meilleurs algorithmes et vous permettra de détecter les solutions de bobinage et de lancer de rayons.

Le problème du problème des polygones arbitraires

L’algorithme est intéressant à mettre en œuvre et en vaut la peine. Cependant, il est si complexe qu’il m’est inutile de le regarder directement. Je vais plutôt m’en tenir à dire que si vous voulez l’algorithme le plus efficace et le plus polyvalent, je suis certain que c’est ça.

L’algorithme devient complexe car très optimisé, il faudra donc beaucoup de lecture pour le comprendre et le mettre en œuvre. Cependant, il combine les avantages des algorithmes de nombre de rayons de diffusion et d’enroulement. Il en résulte un nombre unique qui fournit les deux réponses à la fois. Si le résultat est supérieur à zéro et impair, le point est entièrement contenu, mais si le résultat est un nombre pair, le point est contenu dans une section du polygone qui se replie sur lui-même.

Bonne chance.

meowNET anwser n’inclut pas les sumts Polygon dans le polygone et pointe exactement sur les arêtes horizontales. Si vous avez besoin d’un algorithme “inclusif” exact:

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