Geo Fencing – point intérieur / extérieur polygone

Jetez simplement un coup d’œil au problème du point dans le polygone (PIP) .

Si je me souviens bien, l’algorithme consiste à tracer une ligne horizontale à travers votre sharepoint test. Comptez le nombre de lignes du polygone que vous croisez pour atteindre votre point.

Si la réponse est étrange, vous êtes à l’intérieur. Si la réponse est égale, vous êtes dehors.

Edit: Ouais, ce qu’il a dit ( Wikipedia ):

Code C #

bool IsPointInPolygon(List poly, Loc point) { int i, j; bool c = false; for (i = 0, j = poly.Count - 1; i < poly.Count; j = i++) { if ((((poly[i].Lt <= point.Lt) && (point.Lt < poly[j].Lt)) || ((poly[j].Lt <= point.Lt) && (point.Lt < poly[i].Lt))) && (point.Lg < (poly[j].Lg - poly[i].Lg) * (point.Lt - poly[i].Lt) / (poly[j].Lt - poly[i].Lt) + poly[i].Lg)) c = !c; } } return c; } 

Classe loc

 public class Loc { private double lt; private double lg; public double Lg { get { return lg; } set { lg = value; } } public double Lt { get { return lt; } set { lt = value; } } public Loc(double lt, double lg) { this.lt = lt; this.lg = lg; } } 

Après avoir effectué des recherches sur le Web et essayé diverses implémentations et les avoir scopes de C ++ à C #, j’ai finalement obtenu mon code:

  public static bool PointInPolygon(LatLong p, List poly) { int n = poly.Count(); poly.Add(new LatLong { Lat = poly[0].Lat, Lon = poly[0].Lon }); LatLong[] v = poly.ToArray(); int wn = 0; // the winding number counter // loop through all edges of the polygon for (int i = 0; i < n; i++) { // edge from V[i] to V[i+1] if (v[i].Lat <= p.Lat) { // start y <= Py if (v[i + 1].Lat > p.Lat) // an upward crossing if (isLeft(v[i], v[i + 1], p) > 0) // P left of edge ++wn; // have a valid up intersect } else { // start y > Py (no test needed) if (v[i + 1].Lat <= p.Lat) // a downward crossing if (isLeft(v[i], v[i + 1], p) < 0) // P right of edge --wn; // have a valid down intersect } } if (wn != 0) return true; else return false; } private static int isLeft(LatLong P0, LatLong P1, LatLong P2) { double calc = ((P1.Lon - P0.Lon) * (P2.Lat - P0.Lat) - (P2.Lon - P0.Lon) * (P1.Lat - P0.Lat)); if (calc > 0) return 1; else if (calc < 0) return -1; else return 0; } 

La fonction isLeft me posait des problèmes d'arrondi et j'ai passé des heures sans me rendre compte que je faisais la conversion de manière incorrecte, alors pardonnez-moi le boitier si à la fin de cette fonction.

BTW, ceci est le code et l'article d'origine: http://softsurfer.com/Archive/algorithm_0103/algorithm_0103.htm

Je pense qu’il existe une solution plus simple et plus efficace.

Voici le code en C ++. Je devrais être simple pour le convertir en C #.

 int pnpoly(int npol, float *xp, float *yp, float x, float y) { int i, j, c = 0; for (i = 0, j = npol-1; i < npol; j = i++) { if ((((yp[i] <= y) && (y < yp[j])) || ((yp[j] <= y) && (y < yp[i]))) && (x < (xp[j] - xp[i]) * (y - yp[i]) / (yp[j] - yp[i]) + xp[i])) c = !c; } return c; } 

De loin, la meilleure explication et implémentation peut être trouvée à Point In Polygon Inclusion de numéro de bobinage

Il y a même une implémentation C ++ à la fin de l’article bien expliqué. Ce site contient également quelques excellents algorithmes / solutions pour d’autres problèmes basés sur la géomésortinge.

J’ai modifié et utilisé l’implémentation C ++ et créé une implémentation C #. Vous voulez certainement utiliser l’algorithme Winding Number, car il est plus précis que l’algorithme de croisement des bords et très rapide.

Juste un heads-up (en utilisant la réponse que je ne peux pas commenter), si vous souhaitez utiliser le point-dans-polygone pour la géo-clôture, vous devez modifier votre algorithme pour travailler avec des coordonnées sphériques. La longitude -180 est la même que la longitude 180 et le point dans le polygone se brisera dans une telle situation.

La solution complète dans asp.Net C #, vous pouvez voir le détail complet ici, vous pouvez voir comment trouver un point (lat, lon) que ce soit à l’intérieur ou à l’extérieur du polygone en utilisant la latitude et les longitudes? Lien de référence d’article

bool statique privé checkPointExistsInGeofencePolygon (chaîne latlnglist, chaîne lat, chaîne lng) {

  List objList = new List(); // sample ssortingng should be like this strlatlng = "39.11495,-76.873259|39.114588,-76.872808|39.112921,-76.870373|"; ssortingng[] arr = latlnglist.Split('|'); for (int i = 0; i <= arr.Length - 1; i++) { string latlng = arr[i]; string[] arrlatlng = latlng.Split(','); Loc er = new Loc(Convert.ToDouble(arrlatlng[0]), Convert.ToDouble(arrlatlng[1])); objList.Add(er); } Loc pt = new Loc(Convert.ToDouble(lat), Convert.ToDouble(lng)); if (IsPointInPolygon(objList, pt) == true) { return true; } else { return false; } } private static bool IsPointInPolygon(List poly, Loc point) { int i, j; bool c = false; for (i = 0, j = poly.Count - 1; i < poly.Count; j = i++) { if ((((poly[i].Lt <= point.Lt) && (point.Lt < poly[j].Lt)) | ((poly[j].Lt <= point.Lt) && (point.Lt < poly[i].Lt))) && (point.Lg < (poly[j].Lg - poly[i].Lg) * (point.Lt - poly[i].Lt) / (poly[j].Lt - poly[i].Lt) + poly[i].Lg)) c = !c; } return c; } 

Vérifiez si un point est dans un polygone ou non –

Considérons le polygone qui a les sumts a1, a2, a3, a4, a5. Les étapes suivantes devraient vous aider à déterminer si le point P se trouve à l’intérieur du polygone ou à l’extérieur.

Calculer l’aire vectorielle du sortingangle formé par l’arête a1-> a2 et les vecteurs reliant a2 à P et P à a1. De même, calculez la zone vectorielle de chacun des sortingangles possibles ayant un côté comme côté du polygone et les deux autres reliant P à ce côté.

Pour qu’un point soit à l’intérieur d’un polygone, chacun des sortingangles doit avoir une aire positive. Même si l’un des sortingangles a une zone négative, alors le point P ressort du polygone.

Pour calculer l’aire d’un sortingangle à l’aide de vecteurs représentant ses 3 arêtes, reportez-vous à http://www.jtaylor1142001.net/calcjat/Solutions/VCrossProduct/VCPATriangle.htm

Le problème est plus facile si votre polygone est convexe. Si oui, vous pouvez faire un test simple pour chaque ligne pour voir si le point se trouve à l’intérieur ou à l’extérieur de cette ligne (s’étendant à l’infini dans les deux sens). Sinon, pour les polygones concaves, dessinez un rayon imaginaire de votre point à l’infini (dans n’importe quelle direction). Comptez combien de fois il traverse une ligne de démarcation. Odd signifie que le point est à l’intérieur, même si le point est à l’extérieur.

Ce dernier algorithme est plus complexe qu’il n’y paraît. Vous devrez faire très attention à ce qui se passe lorsque votre rayon imaginaire frappe exactement l’un des sumts du polygone.

Si votre rayon imaginaire va dans la direction -x, vous pouvez choisir de ne compter que les lignes comportant au moins un point dont la coordonnée y est ssortingctement inférieure à la coordonnée y de votre point. C’est ainsi que la plupart des cas de bords bizarres fonctionnent correctement.

Si vous avez un polygone simple (aucune des lignes ne se croisent) et que vous n’avez pas de trous, vous pouvez également sortinganguler le polygone, ce que vous allez probablement faire dans une application SIG pour dessiner un TIN. Triangle. Si vous avez un petit nombre d’arêtes au polygone mais un grand nombre de points, c’est rapide.

Pour un point intéressant en sortingangle, voir le texte du lien

Sinon, utilisez la règle des enroulements plutôt que le croisement des bords, le franchissement des bords pose de vrais problèmes avec les points sur les arêtes.

le polygone est défini comme une liste séquentielle de paires de points A, B, C …. A. aucun côté AB, BC … traverse un autre côté

Déterminer la case Xmin, Xmax, Ymin, Ymax

cas 1 le sharepoint test P se trouve en dehors de la boîte

cas 2 le sharepoint test P se trouve à l’intérieur de la boîte:

Déterminez le “diamètre” D de la boîte {[Xmin, Ymin] – [Xmax, Ymax]} (et ajoutez un petit extra pour éviter toute confusion possible avec D étant sur un côté)

Déterminer les dégradés M de tous les côtés

Trouver un gradient Mt le plus différent de tous les dégradés M

La ligne de test part de P au gradient Mt sur une distance D.

Définit le nombre d’intersections à zéro

Pour chacun des côtés AB, BC teste l’intersection de PD avec un côté de son début à mais sans y inclure sa fin. Incrémenter le nombre d’intersections si nécessaire. Notez qu’une distance nulle de P à l’intersection indique que P est sur un côté

Un compte impair indique que P est à l’intérieur du polygone

J’ai traduit la méthode c # dans Php et j’ai ajouté de nombreux commentaires pour comprendre le code.

Description de PolygonHelps:
Vérifiez si un point est à l’intérieur ou à l’extérieur d’un polygone. Cette procédure utilise les coordonnées gps et cela fonctionne lorsque le polygone a une petite zone géographique.

CONTRIBUTION:
$ poly: array of Point: liste des sumts des polygones; [{Point}, {Point}, …];
$ point: point à vérifier; Point: {“lat” => “x.xxx”, “lng” => “y.yyy”}

Lorsque $ c est faux, le nombre d’intersections avec le polygone est pair, donc le point est en dehors du polygone;
Lorsque $ c est vrai, le nombre d’intersections avec le polygone est impair, donc le point est à l’intérieur du polygone;
$ n est le nombre de sumts dans le polygone;
Pour chaque sumt en polygone, la méthode calcule la ligne à travers le sumt actuel et le sumt précédent et vérifie si les deux lignes ont un point d’intersection.
$ c change lorsque le point d’intersection existe.
Ainsi, la méthode peut retourner true si le point est à l’intérieur du polygone, sinon retourner false.

 class PolygonHelps { public static function isPointInPolygon(&$poly, $point){ $c = false; $n = $j = count($poly); for ($i = 0, $j = $n - 1; $i < $n; $j = $i++){ if ( ( ( ( $poly[$i]->lat <= $point->lat ) && ( $point->lat < $poly[$j]->lat ) ) || ( ( $poly[$j]->lat <= $point->lat ) && ( $point->lat < $poly[$i]->lat ) ) ) && ( $point->lng < ( $poly[$j]->lng - $poly[$i]->lng ) * ( $point->lat - $poly[$i]->lat ) / ( $poly[$j]->lat - $poly[$i]->lat ) + $poly[$i]->lng ) ){ $c = !$c; } } return $c; } } 

J’ajoute un détail pour aider les gens qui vivent dans le sud de la terre! Si vous êtes au Brésil (c’est mon cas), nos coordonnées GPS sont toutes négatives. Et tout cela donne des résultats erronés.

Le moyen le plus simple est d’utiliser les valeurs absolues de Lat et Long de tous les points. Et dans ce cas, l’algo de Jan Kobersky est parfait.