Geo Fencing - Punkt innerhalb / außerhalb Polygon
Ich möchte feststellen, ein polygon und implementieren Sie einen Algorithmus, der zu überprüfen wäre, ob ein Punkt innerhalb oder außerhalb des Polygons.
Weiß jemand, ob es irgendein Beispiel von einer ähnlichen Algorithmus?
InformationsquelleAutor der Frage Niko Gamulin | 2009-05-29
Du musst angemeldet sein, um einen Kommentar abzugeben.
Werfen Sie einen Blick auf die Punkt-in-polygon - (PIP -) problem.
InformationsquelleAutor der Antwort Daniel Brückner
Wenn ich mich richtig erinnere, wird der Algorithmus zum zeichnen einer horizontalen Linie durch Ihre test-Punkt. Zählen Sie, wie viele Zeilen des Polygons schneiden Sie erreichen Ihre Stelle.
Wenn die Antwort ist seltsam, Sie sind im inneren. Wenn die Antwort selbst, du bist draußen.
Edit: Yeah, was er sagte (Wikipedia):
InformationsquelleAutor der Antwort Ian Boyd
C# - code
Loc Klasse
InformationsquelleAutor der Antwort Jan Kobersky
Nachdem die Suche im web und versuchen verschiedene Implementierungen und portieren von C++ auf C# habe ich endlich meinen code gerade:
Den isLeft Funktion war mir rundungsungenauigkeiten und ich haben Stunden damit verbracht, ohne zu merken, dass ich gerade die Umstellung falsch, so verzeihen Sie mir für die lahm, wenn-block an das Ende der Funktion.
BTW, dies ist der ursprüngliche code und Artikel:
http://softsurfer.com/Archive/algorithm_0103/algorithm_0103.htm
InformationsquelleAutor der Antwort Manuel Castro
Ich denke, es gibt eine einfachere und effizientere Lösung.
Hier ist der code in C++. Ich sollte einfach konvertieren C#.
InformationsquelleAutor der Antwort wael
Bei weitem die beste Erklärung und Umsetzung können gefunden werden bei
Punkt-In-Polygon-Wicklung Anzahl Inklusion
Gibt es auch eine C++ - Implementierung am Ende der gut erklärten Artikel. Diese Website enthält auch einige gute algorithmen/Lösungen für andere geometrie Probleme.
Habe ich geändert und verwendet die C++ - Implementierung und erstellte auch eine C# - Implementierung. Sie definitiv möchten, verwenden Sie die Winding Number Algorithmus, da er genauer ist als die edge-crossing-Algorithmus und ist sehr schnell.
InformationsquelleAutor der Antwort eesh
Nur ein heads-up (mit Antwort, da ich nicht kommentieren), wenn Sie wollen, verwenden Sie die point-in-polygon für geo Fechten, dann müssen Sie ändern Ihren Algorithmus für die Arbeit mit sphärischen Koordinaten. -180 Länge ist die gleiche wie 180 Längen-und point-in-polygon-brechen in solcher situation.
InformationsquelleAutor der Antwort Justin Zhang
Der kompletten Lösung asp.Net C# können Sie die vollständigen Details hier können Sie sehen, wie zu finden, Punkt(lat,lon), ob Ihr innerhalb oder Außerhalb des Polygons mit der breiten-und Längengrade ?
Artikel Referenz Link
private static bool checkPointExistsInGeofencePolygon(string latlnglist, string lat, string lng)
{
InformationsquelleAutor der Antwort user1920890
Überprüfen, ob ein Punkt im inneren eines Polygons oder nicht -
Betrachten Sie das polygon die Eckpunkte a1,a2,a3,a4,a5. Die folgenden Schritte sollten helfen, bei der Ermittlung, ob der Punkt P liegt innerhalb des Polygons oder außerhalb.
Berechnen Sie den Vektor-Bereich im Dreieck durch die Kante a1->a2 und die Vektoren Anschluss a2 an P und P zu a1. Ebenso berechnen Sie die Vektoren der einzelnen möglichen Dreiecken mit einer Seite wie der Seite des Polygons und die anderen zwei anschließen P-Seite.
Für einen Punkt im inneren eines Polygons, die jeweils die Dreiecke müssen positiven Bereich. Auch wenn eines der Dreiecke haben einen negativen Bereich, dann ist der Punkt P steht aus dem polygon.
Zur Berechnung der Fläche eines Dreiecks-Vektoren, die seine 3 Kanten, siehe http://www.jtaylor1142001.net/calcjat/Solutions/VCrossProduct/VCPATriangle.htm
InformationsquelleAutor der Antwort Arnkrishn
Das problem ist einfacher, wenn Ihr polygon ist konvex. Wenn ja, können Sie einen einfachen test für jede Zeile, um zu sehen, wenn der Punkt auf der innen-oder Außenseite der Linie (Verlängerung bis unendlich in beide Richtungen). Ansonsten, für konkave Polygone, zeichnen Sie einen imaginären Strahl von Ihrem Punkt aus in die Unendlichkeit (in jede Richtung). Zählen, wie viele Male es kreuzt eine Grenzlinie. Ungerade bedeutet der Punkt im inneren, auch bedeutet, dass der Punkt ausserhalb.
Dieser Letzte Algorithmus ist komplizierter als es aussieht. Sie müssen sehr vorsichtig sein, was passiert, wenn Sie Ihre imaginären Strahl genau trifft immerhin die polygon-Eckpunkte.
Wenn Ihre imaginären ray geht in die -x-Richtung, können Sie nur Zeilen, die mindestens einen Punkt, dessen y-Koordinate ist kleiner als die y-Koordinate von Ihr zeigen. Dies ist, wie Sie die meisten der seltsamen Grenzfälle, um korrekt zu arbeiten.
InformationsquelleAutor der Antwort Dietrich Epp
Wenn Sie haben ein einfaches polygon (keine der Linien kreuzen) und Sie don ' T haben Löcher können Sie auch das polygon triangulieren, das Sie wahrscheinlich sowieso in eine GIS-app zu zeichnen, ZINN, testen Sie dann die Punkte in jedem Dreieck. Wenn Sie eine kleine Anzahl von Kanten des Polygons, aber eine große Anzahl von Punkten ist das schnell.
Für eine interessante Stelle im Dreieck siehe link-text
Sonst auf jeden Fall nutzen die Wicklung eher die Regel als die edge crossing, crossing edge hat echte Probleme mit den Punkten auf Kanten, die, wenn Sie Ihre Daten generiert, form a-GPS mit begrenzten Genauigkeit ist sehr wahrscheinlich.
InformationsquelleAutor der Antwort Martin Beckett
polygon ist definiert als eine sequenzielle Liste von Punkt-Paaren A, B, C .... A.
keine Seite A-B, B-C ... kreuzen andere Seite
Bestimmen-box Xmin, Xmax, Ymin, Ymax
Fall 1 der test-Punkt P liegt außerhalb der box
Fall 2 der test-Punkt P liegt im inneren der box:
Bestimmung der 'Durchmesser' D von der box {[Xmin,Ymin] - [Xmax, Ymax]} ( und noch ein kleines extra, um zu vermeiden, Verwechslungen mit D auf einer Seite)
Bestimmen Sie die Steigung M von allen Seiten
Finden Sie eine Steigung Mt meisten Verschieden von allen Steigungen M
Die test-Linie verläuft vom P an der Steigung Mt Abstand D.
Legen Sie die Anzahl der Kreuzungen auf null
Für jede der Seiten A-B, B-C-test für die Kreuzung der P-D mit einer Seite
von Anfang bis EINSCHLIEßLICH, aber NICHT sein Ende. Erhöht die Anzahl der Kreuzungen
wenn erforderlich. Beachten Sie, dass eine null-Abstand von P zum Schnittpunkt gibt an, dass P AUF einer Seite
Eine ungerade Zahl anzeigt, dass P innerhalb des Polygons
InformationsquelleAutor der Antwort david n laine
Ich übersetzt c# - Methode in Php und ich habe viele Kommentare zu verstehen code.
Beschreibung PolygonHelps:
Überprüfen Sie, ob ein Punkt innerhalb oder außerhalb eines Polygons. Dieses Verfahren verwendet die gps-Koordinaten und Sie funktioniert, wenn polygon hat einen kleinen geographischen Bereich.
EINGANG:
$poly: array von Point: polygon-vertices list; [{Punkt}, {Zeigen}, ...];
$Punkt: Punkt; Punkt: {"lat" => "x.xxx", "lng" => "y".yyy"}
Wenn $c ist falsch, die Anzahl der Schnittpunkte mit dem polygon selbst, so ist der Punkt außerhalb des Polygons;
Wenn $c wahr ist, die Anzahl der Schnittpunkte mit dem polygon ist ungerade, so ist der Punkt innerhalb des Polygons;
$n ist die Anzahl der vertices im polygon;
Für jeden vertex im polygon-Methode berechnet Linie durch den aktuellen vertex-und vorherigen Ecke und prüfen, ob die beiden Linien einen Schnittpunkt.
$c ändert sich, wenn Sie den Schnittpunkt vorhanden ist.
So, können Sie die Methode true zurück, wenn der Punkt innerhalb des Polygons, sonst false zurück.
InformationsquelleAutor der Antwort Pietro La Grotta
Füge ich ein detail, um zu helfen Menschen, die in den Süden... der Erde!!
Wenn Sie in Brasilien (das ist mein Fall), unsere GPS coord sind alle negativen.
Und all diese algo geben falsche Ergebnisse.
Der einfachste Weg ist die Verwendung der absoluten Werte für Lat und Long der ganze Punkt. Und in diesem Fall Jan Kobersky ' s algo ist perfekt.
InformationsquelleAutor der Antwort Peter