Wie kann ich feststellen, ob ein 2D-Punkt innerhalb eines Polygons?
https://stackoverflow.com/questions/217578
-
03-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Ich bin versucht, zu erstellen eine schnell 2D-Punkt in polygon-Algorithmus, für den Einsatz in der hit-testing (z.B. Polygon.contains(p:Point)).Vorschläge für eine effektive Techniken würde geschätzt.
Lösung
Für die Grafiken, die ich lieber nicht lieber zahlen.Viele Systeme verwenden Ganzzahlen für UI-Malerei (Pixel ints, nachdem alle), aber macOS zum Beispiel verwendet float für alles.macOS kennt nur Punkte, und ein Punkt übersetzen kann, um ein pixel, aber je nach Bildschirmauflösung, könnte es übersetzen, um etwas anderes.Auf retina-Bildschirmen einen halben Punkt (0.5/0.5) ist pixel.Immer noch, ich habe nie bemerkt, dass macOS-UIs sind deutlich langsamer als die anderen UIs.Nachdem alle 3D-APIs (OpenGL oder Direct3D) funktioniert auch mit Schwimmern und moderne Grafik-Bibliotheken sehr oft nehmen Vorteil der GPU-Beschleunigung.
Nun, Sie sagten Geschwindigkeit Ihr Hauptanliegen ist, okay, lasst uns gehen Sie für die Geschwindigkeit.Führen Sie vor jeder komplexen Algorithmus zuerst einen einfachen test.Erstellen Sie eine axis aligned bounding box um das polygon.Dies ist sehr einfach, schnell und kann bereits sicher, dass Sie eine Menge Berechnungen.Wie funktioniert das?Iterieren über alle Punkte des Polygons und finden Sie die min/max Werte von X und Y.
E. g.Sie haben die Punkte (9/1), (4/3), (2/7), (8/2), (3/6).Dies bedeutet, Xmin 2, Xmax 9, Ymin 1 und Ymax ist 7.Einen Punkt außerhalb des Rechtecks mit den zwei Kanten (2/1) und (9/7) nicht innerhalb des Polygons.
// p is your point, p.x is the x coord, p.y is the y coord
if (p.x < Xmin || p.x > Xmax || p.y < Ymin || p.y > Ymax) {
// Definitely not within the polygon!
}
Dies ist der erste test laufen für einen beliebigen Punkt.Wie Sie sehen können, ist dieser test ist extrem schnell, aber es ist auch sehr grob.Zu handhaben Punkte, die innerhalb der bounding rectangle, wir brauchen eine ausgefeilte Algorithmus.Es gibt ein paar Möglichkeiten, wie diese berechnet werden kann.Die Methode funktioniert, hängt auch von der Tatsache, ob das polygon können Löcher oder immer solide.Hier sind Beispiele von festen, (einer konvexen, einer konkaven):
Und hier ist man mit einem Loch:
Der grüne hat ein Loch in der Mitte!
Der einfachste Algorithmus,, dass kann Griff alle drei oben genannten Fälle-und ist immer noch ziemlich schnell ist benannt ray casting.Die Idee des Algorithmus ist ziemlich einfach:Zeichnen Sie eine virtuelle ray von einem beliebigen Ort außerhalb des Polygons, zu Ihrem Punkt und zählen Sie, wie oft es trifft einen Seite des Polygons.Wenn die Anzahl der Treffer selbst, es ist außerhalb des Polygons, wenn es ist seltsam, es ist im inneren.
Die winding number-Algorithmus wäre eine alternative, es ist mehr genaue für die Punkte, die sehr nah an ein polygon Linie, aber es ist auch viel langsamer.Ray casting-kann fehlschlagen, um die Punkte zu nah an einer polygon-Seite wegen des begrenzten floating-point-Präzision und Rundung Probleme, aber in Wirklichkeit ist kaum ein problem, da liegt ein Punkt, der in der Nähe einer Seite, oft ist es optisch gar nicht möglich ist für einen Betrachter zu erkennen, wenn es bereits drinnen oder weiterhin draußen.
Sie haben immer noch die bounding-box von oben, erinnern Sie sich?Wählen Sie einfach einen Punkt außerhalb des Begrenzungsrahmens, und verwenden Sie es als Ausgangspunkt für Ihre ray.E. g.der Punkt (Xmin - e/p.y) außerhalb des Polygons für Sie sicher.
Aber was ist e?Gut, e (eigentlich epsilon) gibt den Begrenzungsrahmen einige Polsterung.Als ich sagte, raytracing schlägt fehl, wenn wir beginnen zu schließen, um eine polygonlinie.Da die bounding-box kann gleich das polygon (wenn das polygon ist eine Achse ausgerichtet Rechteck, das umgebende Feld ist gleich das polygon selbst!), wir brauchen eine Polsterung, um diese sicher, das ist alles.Wie groß sollten Sie wählen Sie e?Nicht zu groß.Es hängt davon ab, auf das Koordinatensystem skalieren verwenden Sie für die Zeichnung.Wenn Sie Ihr pixel-Schrittweite ist 1.0, dann wählen Sie einfach 1.0 (noch 0.1 hätte auch funktioniert)
Nun, wir haben die ray mit start-und end-Koordinaten, das problem aus Verschiebungen "ist der Punkt innerhalb des Polygons"zu "wie oft tritt der Strahl schneidet eine polygon-Seite".Daher können wir nicht nur die Arbeit mit dem polygon-Punkte als, bevor, jetzt müssen wir die eigentlichen Seiten.Eine Seite ist immer durch zwei Punkte definiert.
side 1: (X1/Y1)-(X2/Y2)
side 2: (X2/Y2)-(X3/Y3)
side 3: (X3/Y3)-(X4/Y4)
:
Sie müssen testen Sie die ray-gegen alle Seiten.Betrachten Sie den Strahl ein Vektor und jeder Seite ein Vektor.Der Strahl muss Treffer auf jeder Seite genau einmal oder gar nicht.Es kann nicht auf die gleiche Seite zweimal.Zwei Linien im 2D-Raum wird immer genau einmal schneiden, wenn Sie parallel sind, in welchem Fall Sie nie kreuzen.Aber da die Vektoren haben eine begrenzte Länge, zwei Vektoren kann nicht parallel sein, und noch nie kreuzen, weil Sie zu kurz sind, um jemals aufeinander treffen.
// Test the ray against all sides
int intersections = 0;
for (side = 0; side < numberOfSides; side++) {
// Test if current side intersects with ray.
// If yes, intersections++;
}
if ((intersections & 1) == 1) {
// Inside of polygon
} else {
// Outside of polygon
}
So weit So gut, aber wie wollen Sie testen, ob zwei Vektoren schneiden?Hier sind einige C-code (nicht getestet), das sollte den trick tun:
#define NO 0
#define YES 1
#define COLLINEAR 2
int areIntersecting(
float v1x1, float v1y1, float v1x2, float v1y2,
float v2x1, float v2y1, float v2x2, float v2y2
) {
float d1, d2;
float a1, a2, b1, b2, c1, c2;
// Convert vector 1 to a line (line 1) of infinite length.
// We want the line in linear equation standard form: A*x + B*y + C = 0
// See: http://en.wikipedia.org/wiki/Linear_equation
a1 = v1y2 - v1y1;
b1 = v1x1 - v1x2;
c1 = (v1x2 * v1y1) - (v1x1 * v1y2);
// Every point (x,y), that solves the equation above, is on the line,
// every point that does not solve it, is not. The equation will have a
// positive result if it is on one side of the line and a negative one
// if is on the other side of it. We insert (x1,y1) and (x2,y2) of vector
// 2 into the equation above.
d1 = (a1 * v2x1) + (b1 * v2y1) + c1;
d2 = (a1 * v2x2) + (b1 * v2y2) + c1;
// If d1 and d2 both have the same sign, they are both on the same side
// of our line 1 and in that case no intersection is possible. Careful,
// 0 is a special case, that's why we don't test ">=" and "<=",
// but "<" and ">".
if (d1 > 0 && d2 > 0) return NO;
if (d1 < 0 && d2 < 0) return NO;
// The fact that vector 2 intersected the infinite line 1 above doesn't
// mean it also intersects the vector 1. Vector 1 is only a subset of that
// infinite line 1, so it may have intersected that line before the vector
// started or after it ended. To know for sure, we have to repeat the
// the same test the other way round. We start by calculating the
// infinite line 2 in linear equation standard form.
a2 = v2y2 - v2y1;
b2 = v2x1 - v2x2;
c2 = (v2x2 * v2y1) - (v2x1 * v2y2);
// Calculate d1 and d2 again, this time using points of vector 1.
d1 = (a2 * v1x1) + (b2 * v1y1) + c2;
d2 = (a2 * v1x2) + (b2 * v1y2) + c2;
// Again, if both have the same sign (and neither one is 0),
// no intersection is possible.
if (d1 > 0 && d2 > 0) return NO;
if (d1 < 0 && d2 < 0) return NO;
// If we get here, only two possibilities are left. Either the two
// vectors intersect in exactly one point or they are collinear, which
// means they intersect in any number of points from zero to infinite.
if ((a1 * b2) - (a2 * b1) == 0.0f) return COLLINEAR;
// If they are not collinear, they must intersect in exactly one point.
return YES;
}
Die Eingabewerte sind die zwei Endpunkten der Vektor 1 (v1x1/v1y1 und v1x2/v1y2) und Vektor 2 (v2x1/v2y1 und v2x2/v2y2).Sie haben also 2 Vektoren, 4 Punkte, 8 Koordinaten. YES und NO klar. YES erhöht Kreuzungen, NO macht nichts.
Was ist KOLLINEAREN?Es bedeutet, dass beide Vektoren liegen auf einer unendlichen Linie, je nach Lage und Länge, Sie nicht zu schneiden, oder Sie schneiden sich in einer endlosen Anzahl von Punkten.Ich bin mir nicht absolut sicher sind, wie Sie in diesem Fall behandeln, würde ich mich nicht verlassen es als Kreuzung der beiden Wege.Gut, dieser Fall ist in der Praxis eher selten weil eh von Gleitkomma-Rundungsfehler;besser-code würde wahrscheinlich nicht testen == 0.0f aber stattdessen für etwas wie < epsilon, wo epsilon ist eine eher kleine Nummer.
Wenn Sie müssen test eine größere Anzahl der Punkte, Sie kann sicherlich beschleunigt die ganze Sache ein wenig, indem die lineare Gleichung standard-Formen der polygon-Seiten im Speicher, so dass Sie nicht haben, um diese nicht jedes mal neu berechnen.Dadurch sparen Sie zwei Fließkomma-Multiplikationen und drei floating-point-Abzüge auf jeden test, den Sie im Austausch für die Speicherung von drei floating-point-Werte pro polygon-Seite im Speicher.Es ist eine typische memory-vs-Berechnung-Zeit-trade-off.
Last but not least:Wenn Sie können, verwenden Sie 3D-hardware, um das problem zu lösen, gibt es eine interessante alternative.Lass die GPU tun alle die Arbeit für Sie.Erstellen Sie ein Gemälde Oberfläche, dass ist außerhalb des Bildschirms.Füllen Sie es vollständig mit der Farbe schwarz.Lassen Sie uns nun die OpenGL-oder Direct3D-malen Sie Ihr polygon (oder sogar alle Ihre Polygone, wenn Sie wollen einfach nur, um zu testen, ob der Punkt innerhalb jeder von Ihnen, aber Sie kümmern sich nicht um die ein und füllen Sie das polygon(s) mit einer anderen Farbe, z.B.weiß.Um zu überprüfen, ob ein Punkt innerhalb des Polygons, die Farbe von dieser Stelle aus der Zeichnung Oberfläche.Dies ist nur eine O(1) Speicher Holen.
Natürlich ist diese Methode nur geeignet, wenn Sie Ihre Zeichnung Oberfläche nicht zu groß sein.Wenn es nicht passen in den GPU-Speicher-diese Methode ist langsamer, als wenn man es auf die CPU an.Wenn es sein müsste, eine riesige und Ihre GPU unterstützt moderne Shader, Sie können immer noch die GPU nutzen durch die Implementierung des ray casting oben gezeigt als einen GPU-shader, das ist absolut möglich.Für eine größere Anzahl von Polygonen oder eine große Anzahl von Punkten zu testen, das wird sich auszahlen, betrachten wir einige GPUs werden in der Lage sein zu testen, 64 bis 256 Punkte in parallel.Beachten Sie jedoch, dass die übertragung der Daten von der CPU zur GPU und zurück ist immer teuer, so zum testen nur ein paar der Punkte, die gegen ein paar von einfachen Polygonen, wo entweder die Punkte oder Polygone sind dynamisch und ändern sich Häufig, eine GPU-Ansatz wird selten auszahlen.
Andere Tipps
Ich denke, das folgende Stück Code ist die beste Lösung (aus hier ):
int pnpoly(int nvert, float *vertx, float *verty, float testx, float testy)
{
int i, j, c = 0;
for (i = 0, j = nvert-1; i < nvert; j = i++) {
if ( ((verty[i]>testy) != (verty[j]>testy)) &&
(testx < (vertx[j]-vertx[i]) * (testy-verty[i]) / (verty[j]-verty[i]) + vertx[i]) )
c = !c;
}
return c;
}
Argumente
- nvert : Anzahl der Eckpunkte des Polygons. Ob die erste Ecke am Ende zu wiederholen hat in dem Artikel genannten oben diskutiert.
- VertX, verty :. Arrays, die die x- und y-Koordinaten der Eckpunkte des Polygons mit
- testx, reizbar . X- und Y-Koordinate des Testpunkt
Es ist sowohl kurz und effizient und arbeitet sowohl für konvexe und konkave Polygone. Wie zuvor vorgeschlagen, sollten Sie das Begrenzungsrechteck zuerst prüfen und Polygon Löcher separat behandeln.
Die Idee dahinter ist recht einfach. Der Autor beschreibt es wie folgt:
Ich betreibe ein semiinfiniten ray horizontal (zunehmende x, feste y) aus dem Testpunkt und zählen, wie viele Kanten kreuzt. An jedem Kreuzungs schaltet der Strahl zwischen innen und außen. Dies ist der Jordan Kurvensatz genannt.
Die Variable c ist von 0 auf 1 und 1 auf 0 bei jedem Umschalten der horizontale Strahl jede Kante kreuzt. Also im Grunde ist es zu verfolgen, ob die Anzahl der Kanten gekreuzt ist gerade oder ungerade. 0 bedeutet auch und 1 bedeutet, ungerade ist.
Hier ist eine C # Version der von nirg gegebene Antwort, die von dieser RPI Professor . Beachten Sie, dass die Verwendung des Codes aus dieser RPI Quelle erfordert Zuschreibung.
Ein Begrenzungsrahmen Scheck wurde an der Spitze gegeben. Doch wie James Brown betont, ist der Hauptcode fast so schnell wie der Begrenzungskasten selbst überprüfen, so dass die Begrenzungsrahmen Prüfung tatsächlich den gesamten Betrieb verlangsamen kann, in dem Fall, dass die meisten der Punkte, die Sie in dem Begrenzungsrahmen werden überprüft werden . So könnte man den Begrenzungsrahmen verlassen Check-out, oder eine Alternative wäre, die Begrenzungsboxen Ihrer Polygone vorauszuberechnen, wenn sie Form nicht zu oft ändern.
public bool IsPointInPolygon( Point p, Point[] polygon )
{
double minX = polygon[ 0 ].X;
double maxX = polygon[ 0 ].X;
double minY = polygon[ 0 ].Y;
double maxY = polygon[ 0 ].Y;
for ( int i = 1 ; i < polygon.Length ; i++ )
{
Point q = polygon[ i ];
minX = Math.Min( q.X, minX );
maxX = Math.Max( q.X, maxX );
minY = Math.Min( q.Y, minY );
maxY = Math.Max( q.Y, maxY );
}
if ( p.X < minX || p.X > maxX || p.Y < minY || p.Y > maxY )
{
return false;
}
// http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html
bool inside = false;
for ( int i = 0, j = polygon.Length - 1 ; i < polygon.Length ; j = i++ )
{
if ( ( polygon[ i ].Y > p.Y ) != ( polygon[ j ].Y > p.Y ) &&
p.X < ( polygon[ j ].X - polygon[ i ].X ) * ( p.Y - polygon[ i ].Y ) / ( polygon[ j ].Y - polygon[ i ].Y ) + polygon[ i ].X )
{
inside = !inside;
}
}
return inside;
}
Hier ist eine JavaScript-Variante der Antwort von M. Katz basierend auf Nirg Ansatz:
function pointIsInPoly(p, polygon) {
var isInside = false;
var minX = polygon[0].x, maxX = polygon[0].x;
var minY = polygon[0].y, maxY = polygon[0].y;
for (var n = 1; n < polygon.length; n++) {
var q = polygon[n];
minX = Math.min(q.x, minX);
maxX = Math.max(q.x, maxX);
minY = Math.min(q.y, minY);
maxY = Math.max(q.y, maxY);
}
if (p.x < minX || p.x > maxX || p.y < minY || p.y > maxY) {
return false;
}
var i = 0, j = polygon.length - 1;
for (i, j; i < polygon.length; j = i++) {
if ( (polygon[i].y > p.y) != (polygon[j].y > p.y) &&
p.x < (polygon[j].x - polygon[i].x) * (p.y - polygon[i].y) / (polygon[j].y - polygon[i].y) + polygon[i].x ) {
isInside = !isInside;
}
}
return isInside;
}
Berechnen Sie die orientierte Summe des Winkels zwischen dem Punkt p und jeder des Polygonapizes. Wenn die Gesamtorientierungswinkel 360 Grad ist, ist der Punkt innen. Wenn die Gesamt 0 ist, ist der Punkt außerhalb.
Ich mag diese Methode besser, weil sie robuster und weniger abhängig von numerischer Genauigkeit ist.
Methoden, die Gleichmäßigkeit der Anzahl von Kreuzungen berechnen begrenzt sind, weil Sie ‚Hit‘ einen Scheitelpunkt bei der Berechnung der Anzahl der Kreuzungen.
EDIT: By the way, funktioniert diese Methode mit konkaven und konvexen Polygonen
.EDIT: Ich fand vor kurzem eine ganze Wikipedia-Artikel zum Thema
.Die Eric Haines Artikel von bobobobo zitiert ist wirklich ausgezeichnet. Besonders interessant sind die Tabellen Leistung der Algorithmen zu vergleichen; der Winkel Summierungsmethode ist wirklich schlecht im Vergleich zu den anderen. Interessant ist auch, dass Optimierungen wie ein Lookup-Raster mit dem Polygon in „in“ und „out“ Sektoren weiter unterteilen können den Test unglaublich schnell, auch auf Polygone mit> 1000 Seiten machen.
Wie auch immer, ist es noch zu früh, aber meine Stimme geht an die „Kreuzungen“ Methode, die ziemlich viel ist, was Mecki beschreibt, denke ich. Allerdings fand ich es am meisten erschöpfende beschrieben und kodifiziert durch David Bourke . Ich liebe, dass es keine wirkliche Trigonometrie ist erforderlich, und es funktioniert für konvexe und konkave und führt sie einigermaßen gut wie die Anzahl der Seiten erhöht.
übrigens, hier ist einer der Performance-Tabellen aus dem Artikel Eric Haines für Interesse, Prüfung auf zufällige Polygonen.
number of edges per polygon
3 4 10 100 1000
MacMartin 2.9 3.2 5.9 50.6 485
Crossings 3.1 3.4 6.8 60.0 624
Triangle Fan+edge sort 1.1 1.8 6.5 77.6 787
Triangle Fan 1.2 2.1 7.3 85.4 865
Barycentric 2.1 3.8 13.8 160.7 1665
Angle Summation 56.2 70.4 153.6 1403.8 14693
Grid (100x100) 1.5 1.5 1.6 2.1 9.8
Grid (20x20) 1.7 1.7 1.9 5.7 42.2
Bins (100) 1.8 1.9 2.7 15.1 117
Bins (20) 2.1 2.2 3.7 26.3 278
Diese Frage ist so interessant. Ich habe eine andere praktikable Idee unterscheidet sich von anderen Antworten von diesem Beitrag.
Die Idee ist, die Summe des Winkels zu verwenden, um zu entscheiden, ob das Ziel innerhalb oder außerhalb ist. Wenn das Ziel innerhalb eines Bereichs ist, wird die Summe der Winkelform durch das Ziel und alle zwei Grenzpunkte seines 360. Wenn das Ziel außerhalb ist, wird die Summe nicht 360. sein, der Winkel hat Richtung. Wenn der Winkel nach hinten geht, ist der Winkel ein negativer. Das ist wie die Nummer Wicklung.
zu diesem Bild finden Sie ein grundlegendes Verständnis der Vorstellung zu bekommen:
Mein Algorithmus nimmt der im Uhrzeigersinn die positive Richtung ist. Hier ist ein Potentialeingang:
[[-122.402015, 48.225216], [-117.032049, 48.999931], [-116.919132, 45.995175], [-124.079107, 46.267259], [-124.717175, 48.377557], [-122.92315, 47.047963], [-122.402015, 48.225216]]
Im Folgenden ist der Python-Code, der die Idee implementiert:
def isInside(self, border, target):
degree = 0
for i in range(len(border) - 1):
a = border[i]
b = border[i + 1]
# calculate distance of vector
A = getDistance(a[0], a[1], b[0], b[1]);
B = getDistance(target[0], target[1], a[0], a[1])
C = getDistance(target[0], target[1], b[0], b[1])
# calculate direction of vector
ta_x = a[0] - target[0]
ta_y = a[1] - target[1]
tb_x = b[0] - target[0]
tb_y = b[1] - target[1]
cross = tb_y * ta_x - tb_x * ta_y
clockwise = cross < 0
# calculate sum of angles
if(clockwise):
degree = degree + math.degrees(math.acos((B * B + C * C - A * A) / (2.0 * B * C)))
else:
degree = degree - math.degrees(math.acos((B * B + C * C - A * A) / (2.0 * B * C)))
if(abs(round(degree) - 360) <= 3):
return True
return False
Swift-Version der Antwort von nirg :
extension CGPoint {
func isInsidePolygon(vertices: [CGPoint]) -> Bool {
guard !vertices.isEmpty else { return false }
var j = vertices.last!, c = false
for i in vertices {
let a = (i.y > y) != (j.y > y)
let b = (x < (j.x - i.x) * (y - i.y) / (j.y - i.y) + i.x)
if a && b { c = !c }
j = i
}
return c
}
}
habe ich auf dieser wieder etwas Arbeit, als ich ein Forscher unter Michael Stonebraker - Sie wissen, ist der Professor, der kam mit Ingres , PostgreSQL , etc
.Wir stellten fest, dass der schnellste Weg war, zunächst eine Begrenzungsrahmen zu tun, weil es SUPER schnell ist. Wenn es außerhalb des Begrenzungsrahmens ist, ist es draußen. Ansonsten haben Sie die härtere Arbeit ...
Wenn Sie einen großen Algorithmus wollen, schauen Sie auf den Open-Source-Projekt PostgreSQL-Quellcode für die geo Arbeit ...
Ich möchte darauf hinweisen, wir haben nie einen Einblick in die richtige vs Linkshändigkeit (auch ausdrückbar als „innen“ vs „außen“ Problem ...
UPDATE
BKB Link eine gute Anzahl von vernünftigen Algorithmen zur Verfügung gestellt. Ich arbeitete an Earth Science Probleme und deshalb eine Lösung benötigt, die in Breite / Länge arbeitet, und es hat die eigentümliche Problem der Händigkeit - ist der Bereich innerhalb des kleineren Bereich oder die größere Fläche? Die Antwort ist, dass die „Richtung“ der verticies Sachen - es ist entweder links- oder rechtshändig und auf diese Weise können Sie entweder Bereich als „innerhalb“ einer gegebenen Polygon anzeigen kann. Als solche meine Arbeit drei verwendeten Lösung auf dieser Seite aufgelistet.
Darüber hinaus meine Arbeit verwendete separate Funktionen für „auf der Linie“ -Tests.
... Da fragte jemand: wir herausgefunden, dass Begrenzungsbox Tests am besten waren, wenn die Anzahl der verticies über eine bestimmte Anzahl ging - machen einen sehr schnellen Test vor den längeren Test machen, wenn nötig ... Ein Begrenzungsrahmen erstellt wird einfach die größten x nehmen, kleinste x, y größte und kleinste y und sie zusammen setzen vier Punkte einer Box zu machen ...
Noch ein Tipp für diejenigen, die folgen: wir haben alle unsere anspruchsvollere und „light-dimmen“ Computing in einem Gitterraum alle in positive Punkte auf einer Ebene und dann projiziert wieder zurück in „echten“ Länge / Breite, wodurch vermieden wird mögliche Fehler herum Umwickeln wenn eine Linie gekreuzt 180 Längen- und beim Umgang mit den Polarregionen. Hat super funktioniert!
Wirklich wie die Lösung von Nirg geschrieben und von bobobobo bearbeitet. Ich habe gerade es JavaScript freundlich und ein wenig mehr lesbar für meine Verwendung:
function insidePoly(poly, pointx, pointy) {
var i, j;
var inside = false;
for (i = 0, j = poly.length - 1; i < poly.length; j = i++) {
if(((poly[i].y > pointy) != (poly[j].y > pointy)) && (pointx < (poly[j].x-poly[i].x) * (pointy-poly[i].y) / (poly[j].y-poly[i].y) + poly[i].x) ) inside = !inside;
}
return inside;
}
David Segond Antwort ist so ziemlich der Standard allgemeine Antwort, und Richard-t ist die häufigste Optimierung, obwohl therre einige andere sind. Andere starke Optimierungen basieren auf weniger allgemeinen Lösungen. Zum Beispiel, wenn Sie vorhaben, das gleiche Polygon mit vielen Punkten zu überprüfen, um das Polygon Triangulation kann die Dinge beschleunigen enorm, da es eine Reihe von sehr schnellen TIN Suchalgorithmen ist. Ein weiterer Grund ist, wenn das Polygon und Punkte auf einer begrenzten Ebene mit niedriger Auflösung sind, sagen eine Bildschirmanzeige, können Sie das Polygon auf einen Speicher abgebildeten Anzeigepuffer in einer bestimmten Farbe malen kann, und überprüfen Sie die Farbe eines bestimmten Pixels zu sehen, ob es liegt in den Polygonen.
Wie viele Optimierungen, werden diese auf der Grundlage spezifischer und nicht allgemeine Fälle, und die Ausbeute beneifits basierend auf den fortgeführten Anschaffungs Zeit eher als Einzelnutzung.
in diesem Bereich arbeiten, fand ich Joeseph O'Rourkes 'Algorithmische Geometrie in C' ISBN 0-521-44034-3 eine große Hilfe zu sein.
Die triviale Lösung wäre, das Polygon in Dreiecke zu unterteilen, und die Dreiecke treffen testen wie erläutert hier
Wenn Ihr Polygon ist KONVEXEN könnte es zwar ein besserer Ansatz sein. Schauen Sie sich das Polygon als eine Sammlung von unendlichen Linien. Jede Zeile Teilungsraum in zwei. für jeden Punkt ist es einfach, seine zu sagen, wenn auf der einen Seite oder der anderen Seite der Linie. Wenn ein Punkt auf der gleichen Seite aller Linien ist, dann ist es innerhalb des Polygons.
Ich weiß, das alt ist, aber hier ist ein Ray-Casting-Algorithmus in Cocoa umgesetzt werden, falls es jemanden interessiert. Nicht sicher, dass es der effizienteste Weg ist, die Dinge zu tun, aber es kann jemand helfen.
- (BOOL)shape:(NSBezierPath *)path containsPoint:(NSPoint)point
{
NSBezierPath *currentPath = [path bezierPathByFlatteningPath];
BOOL result;
float aggregateX = 0; //I use these to calculate the centroid of the shape
float aggregateY = 0;
NSPoint firstPoint[1];
[currentPath elementAtIndex:0 associatedPoints:firstPoint];
float olderX = firstPoint[0].x;
float olderY = firstPoint[0].y;
NSPoint interPoint;
int noOfIntersections = 0;
for (int n = 0; n < [currentPath elementCount]; n++) {
NSPoint points[1];
[currentPath elementAtIndex:n associatedPoints:points];
aggregateX += points[0].x;
aggregateY += points[0].y;
}
for (int n = 0; n < [currentPath elementCount]; n++) {
NSPoint points[1];
[currentPath elementAtIndex:n associatedPoints:points];
//line equations in Ax + By = C form
float _A_FOO = (aggregateY/[currentPath elementCount]) - point.y;
float _B_FOO = point.x - (aggregateX/[currentPath elementCount]);
float _C_FOO = (_A_FOO * point.x) + (_B_FOO * point.y);
float _A_BAR = olderY - points[0].y;
float _B_BAR = points[0].x - olderX;
float _C_BAR = (_A_BAR * olderX) + (_B_BAR * olderY);
float det = (_A_FOO * _B_BAR) - (_A_BAR * _B_FOO);
if (det != 0) {
//intersection points with the edges
float xIntersectionPoint = ((_B_BAR * _C_FOO) - (_B_FOO * _C_BAR)) / det;
float yIntersectionPoint = ((_A_FOO * _C_BAR) - (_A_BAR * _C_FOO)) / det;
interPoint = NSMakePoint(xIntersectionPoint, yIntersectionPoint);
if (olderX <= points[0].x) {
//doesn't matter in which direction the ray goes, so I send it right-ward.
if ((interPoint.x >= olderX && interPoint.x <= points[0].x) && (interPoint.x > point.x)) {
noOfIntersections++;
}
} else {
if ((interPoint.x >= points[0].x && interPoint.x <= olderX) && (interPoint.x > point.x)) {
noOfIntersections++;
}
}
}
olderX = points[0].x;
olderY = points[0].y;
}
if (noOfIntersections % 2 == 0) {
result = FALSE;
} else {
result = TRUE;
}
return result;
}
Obj-C-Version von nirg Antwort mit Probenmethode für Prüfpunkte. Nirg Antwort war für mich gut.
- (BOOL)isPointInPolygon:(NSArray *)vertices point:(CGPoint)test {
NSUInteger nvert = [vertices count];
NSInteger i, j, c = 0;
CGPoint verti, vertj;
for (i = 0, j = nvert-1; i < nvert; j = i++) {
verti = [(NSValue *)[vertices objectAtIndex:i] CGPointValue];
vertj = [(NSValue *)[vertices objectAtIndex:j] CGPointValue];
if (( (verti.y > test.y) != (vertj.y > test.y) ) &&
( test.x < ( vertj.x - verti.x ) * ( test.y - verti.y ) / ( vertj.y - verti.y ) + verti.x) )
c = !c;
}
return (c ? YES : NO);
}
- (void)testPoint {
NSArray *polygonVertices = [NSArray arrayWithObjects:
[NSValue valueWithCGPoint:CGPointMake(13.5, 41.5)],
[NSValue valueWithCGPoint:CGPointMake(42.5, 56.5)],
[NSValue valueWithCGPoint:CGPointMake(39.5, 69.5)],
[NSValue valueWithCGPoint:CGPointMake(42.5, 84.5)],
[NSValue valueWithCGPoint:CGPointMake(13.5, 100.0)],
[NSValue valueWithCGPoint:CGPointMake(6.0, 70.5)],
nil
];
CGPoint tappedPoint = CGPointMake(23.0, 70.0);
if ([self isPointInPolygon:polygonVertices point:tappedPoint]) {
NSLog(@"YES");
} else {
NSLog(@"NO");
}
}
C # Version von nirg Antwort der ist hier: Ich werde nur den Code teilen. Es kann jemand etwas Zeit sparen.
public static bool IsPointInPolygon(IList<Point> polygon, Point 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;
}
Es gibt nichts beutiful als eine induktive Definition eines Problems. Aus Gründen der Vollständigkeit hier eine Version in Prolog hast, die auch die thoughs hinter klären könnten Ray-Casting :
Auf der Basis der Simulation der Einfachheit Algorithmus in http: // www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html
Einige Helfer Prädikate:
exor(A,B):- \+A,B;A,\+B.
in_range(Coordinate,CA,CB) :- exor((CA>Coordinate),(CB>Coordinate)).
inside(false).
inside(_,[_|[]]).
inside(X:Y, [X1:Y1,X2:Y2|R]) :- in_range(Y,Y1,Y2), X > ( ((X2-X1)*(Y-Y1))/(Y2-Y1) + X1),toggle_ray, inside(X:Y, [X2:Y2|R]); inside(X:Y, [X2:Y2|R]).
get_line(_,_,[]).
get_line([XA:YA,XB:YB],[X1:Y1,X2:Y2|R]):- [XA:YA,XB:YB]=[X1:Y1,X2:Y2]; get_line([XA:YA,XB:YB],[X2:Y2|R]).
Die Gleichung einer Linie 2 angegebenen Punkte A und B (Linie (A, B)) ist:
(YB-YA)
Y - YA = ------- * (X - XA)
(XB-YB)
Es ist wichtig, dass die Drehrichtung für die Linie ist setted zu dem Uhrzeigersinn für Grenzen und anti-Uhrzeigersinn für Löcher. Wir werden prüfen, ob der Punkt (X, Y), das heißt der getesteten Punkt auf der linken Seite Halbebene unserer Linie (es Geschmackssache ist, könnte es auch sein, die rechte Seite, sondern hat auch die Richtung der Grenzen Linien geändert wird in Dieser Fall), ist dies den Strahl von dem Punkt nach rechts (oder links zu projizieren) und erkennt den Schnittpunkt mit der Linie. Wir haben zu projizieren gewählt der Strahl in horizontaler Richtung (wieder ist es eine Frage des Geschmacks, es könnte auch in vertikaler mit ähnlichen Einschränkungen durchgeführt werden), so haben wir:
(XB-XA)
X < ------- * (Y - YA) + XA
(YB-YA)
Jetzt müssen wir wissen, ob der Punkt auf der linken (oder rechten) Seite von nur das Liniensegment, nicht die gesamte Ebene, so müssen wir schränken die Suche nur auf dieses Segment, aber das ist einfach, da werden soll, kann innerhalb des Segments nur ein Punkt in der Leitung höher als Y in der vertikalen Achse. Da es sich um eine stärkere Beschränkung es muss der erste sein, um zu überprüfen, so dass wir zunächst nur die Zeilen die Erfüllung dieser Forderung und dann seine possition überprüfen. Durch den Jordan Kurvensatz jeder Strahl auf ein Polygon projiziert auf ein schneiden müssen geraden Anzahl von Linien. Also wir fertig sind, werden wir den Strahl auf das werfen rechts und dann schneidet, jedes Mal wenn eine Linie, Toggle seines Zustandes. Doch in unserer Implementierung sind wir goint die Länge des überprüfen der Beutel von Lösungen, die die gegebenen Einschränkungen zu treffen und entscheiden, die innership darauf. für jede Zeile in dem Polygon dies getan werden muß.
is_left_half_plane(_,[],[],_).
is_left_half_plane(X:Y,[XA:YA,XB:YB], [[X1:Y1,X2:Y2]|R], Test) :- [XA:YA, XB:YB] = [X1:Y1, X2:Y2], call(Test, X , (((XB - XA) * (Y - YA)) / (YB - YA) + XA));
is_left_half_plane(X:Y, [XA:YA, XB:YB], R, Test).
in_y_range_at_poly(Y,[XA:YA,XB:YB],Polygon) :- get_line([XA:YA,XB:YB],Polygon), in_range(Y,YA,YB).
all_in_range(Coordinate,Polygon,Lines) :- aggregate(bag(Line), in_y_range_at_poly(Coordinate,Line,Polygon), Lines).
traverses_ray(X:Y, Lines, Count) :- aggregate(bag(Line), is_left_half_plane(X:Y, Line, Lines, <), IntersectingLines), length(IntersectingLines, Count).
% This is the entry point predicate
inside_poly(X:Y,Polygon,Answer) :- all_in_range(Y,Polygon,Lines), traverses_ray(X:Y, Lines, Count), (1 is mod(Count,2)->Answer=inside;Answer=outside).
Java Version:
public class Geocode {
private float latitude;
private float longitude;
public Geocode() {
}
public Geocode(float latitude, float longitude) {
this.latitude = latitude;
this.longitude = longitude;
}
public float getLatitude() {
return latitude;
}
public void setLatitude(float latitude) {
this.latitude = latitude;
}
public float getLongitude() {
return longitude;
}
public void setLongitude(float longitude) {
this.longitude = longitude;
}
}
public class GeoPolygon {
private ArrayList<Geocode> points;
public GeoPolygon() {
this.points = new ArrayList<Geocode>();
}
public GeoPolygon(ArrayList<Geocode> points) {
this.points = points;
}
public GeoPolygon add(Geocode geo) {
points.add(geo);
return this;
}
public boolean inside(Geocode geo) {
int i, j;
boolean c = false;
for (i = 0, j = points.size() - 1; i < points.size(); j = i++) {
if (((points.get(i).getLongitude() > geo.getLongitude()) != (points.get(j).getLongitude() > geo.getLongitude())) &&
(geo.getLatitude() < (points.get(j).getLatitude() - points.get(i).getLatitude()) * (geo.getLongitude() - points.get(i).getLongitude()) / (points.get(j).getLongitude() - points.get(i).getLongitude()) + points.get(i).getLatitude()))
c = !c;
}
return c;
}
}
NET-Port:
static void Main(string[] args)
{
Console.Write("Hola");
List<double> vertx = new List<double>();
List<double> verty = new List<double>();
int i, j, c = 0;
vertx.Add(1);
vertx.Add(2);
vertx.Add(1);
vertx.Add(4);
vertx.Add(4);
vertx.Add(1);
verty.Add(1);
verty.Add(2);
verty.Add(4);
verty.Add(4);
verty.Add(1);
verty.Add(1);
int nvert = 6; //Vértices del poligono
double testx = 2;
double testy = 5;
for (i = 0, j = nvert - 1; i < nvert; j = i++)
{
if (((verty[i] > testy) != (verty[j] > testy)) &&
(testx < (vertx[j] - vertx[i]) * (testy - verty[i]) / (verty[j] - verty[i]) + vertx[i]))
c = 1;
}
}
VBA VERSION:
Hinweis: Denken Sie daran, dass, wenn Ihr Polygon ist ein Bereich innerhalb einer Karte, die Breite / Länge ist Y / X-Werte im Gegensatz zu X / Y (Breite = Y, Länge = X) wegen dem, was ich sind historische Implikationen verstehe aus Weg zurück, wenn Longitude war keine Messung.
CLASS MODUL: CPoint
Private pXValue As Double
Private pYValue As Double
'''''X Value Property'''''
Public Property Get X() As Double
X = pXValue
End Property
Public Property Let X(Value As Double)
pXValue = Value
End Property
'''''Y Value Property'''''
Public Property Get Y() As Double
Y = pYValue
End Property
Public Property Let Y(Value As Double)
pYValue = Value
End Property
MODUL:
Public Function isPointInPolygon(p As CPoint, polygon() As CPoint) As Boolean
Dim i As Integer
Dim j As Integer
Dim q As Object
Dim minX As Double
Dim maxX As Double
Dim minY As Double
Dim maxY As Double
minX = polygon(0).X
maxX = polygon(0).X
minY = polygon(0).Y
maxY = polygon(0).Y
For i = 1 To UBound(polygon)
Set q = polygon(i)
minX = vbMin(q.X, minX)
maxX = vbMax(q.X, maxX)
minY = vbMin(q.Y, minY)
maxY = vbMax(q.Y, maxY)
Next i
If p.X < minX Or p.X > maxX Or p.Y < minY Or p.Y > maxY Then
isPointInPolygon = False
Exit Function
End If
' SOURCE: http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html
isPointInPolygon = False
i = 0
j = UBound(polygon)
Do While i < UBound(polygon) + 1
If (polygon(i).Y > p.Y) Then
If (polygon(j).Y < p.Y) Then
If p.X < (polygon(j).X - polygon(i).X) * (p.Y - polygon(i).Y) / (polygon(j).Y - polygon(i).Y) + polygon(i).X Then
isPointInPolygon = True
Exit Function
End If
End If
ElseIf (polygon(i).Y < p.Y) Then
If (polygon(j).Y > p.Y) Then
If p.X < (polygon(j).X - polygon(i).X) * (p.Y - polygon(i).Y) / (polygon(j).Y - polygon(i).Y) + polygon(i).X Then
isPointInPolygon = True
Exit Function
End If
End If
End If
j = i
i = i + 1
Loop
End Function
Function vbMax(n1, n2) As Double
vbMax = IIf(n1 > n2, n1, n2)
End Function
Function vbMin(n1, n2) As Double
vbMin = IIf(n1 > n2, n2, n1)
End Function
Sub TestPointInPolygon()
Dim i As Integer
Dim InPolygon As Boolean
' MARKER Object
Dim p As CPoint
Set p = New CPoint
p.X = <ENTER X VALUE HERE>
p.Y = <ENTER Y VALUE HERE>
' POLYGON OBJECT
Dim polygon() As CPoint
ReDim polygon(<ENTER VALUE HERE>) 'Amount of vertices in polygon - 1
For i = 0 To <ENTER VALUE HERE> 'Same value as above
Set polygon(i) = New CPoint
polygon(i).X = <ASSIGN X VALUE HERE> 'Source a list of values that can be looped through
polgyon(i).Y = <ASSIGN Y VALUE HERE> 'Source a list of values that can be looped through
Next i
InPolygon = isPointInPolygon(p, polygon)
MsgBox InPolygon
End Sub
Ich habe eine Python-Implementierung von nirg der c ++ Code :
Eingänge
- bounding_points:. Knoten, die das Polygon bilden
-
bounding_box_positions: Kandidatenpunkte zu filtern. (In meiner Implementierung von dem Begrenzungsrahmen erstellt.
(Die Eingänge sind Listen von Tupeln im Format:
[(xcord, ycord), ...])
Returns
- Alle Punkte, die innerhalb des Polygons sind.
def polygon_ray_casting(self, bounding_points, bounding_box_positions):
# Arrays containing the x- and y-coordinates of the polygon's vertices.
vertx = [point[0] for point in bounding_points]
verty = [point[1] for point in bounding_points]
# Number of vertices in the polygon
nvert = len(bounding_points)
# Points that are inside
points_inside = []
# For every candidate position within the bounding box
for idx, pos in enumerate(bounding_box_positions):
testx, testy = (pos[0], pos[1])
c = 0
for i in range(0, nvert):
j = i - 1 if i != 0 else nvert - 1
if( ((verty[i] > testy ) != (verty[j] > testy)) and
(testx < (vertx[j] - vertx[i]) * (testy - verty[i]) / (verty[j] - verty[i]) + vertx[i]) ):
c += 1
# If odd, that means that we are inside the polygon
if c % 2 == 1:
points_inside.append(pos)
return points_inside
Auch hier ist die Idee genommen von hier
Hier ist ein Punkt in Polygon-Test in C, die nicht Ray-Casting verwendet. Und es kann für überlappende Bereiche (Selbstschnitt) arbeiten, das use_holes Argument sehen.
/* math lib (defined below) */
static float dot_v2v2(const float a[2], const float b[2]);
static float angle_signed_v2v2(const float v1[2], const float v2[2]);
static void copy_v2_v2(float r[2], const float a[2]);
/* intersection function */
bool isect_point_poly_v2(const float pt[2], const float verts[][2], const unsigned int nr,
const bool use_holes)
{
/* we do the angle rule, define that all added angles should be about zero or (2 * PI) */
float angletot = 0.0;
float fp1[2], fp2[2];
unsigned int i;
const float *p1, *p2;
p1 = verts[nr - 1];
/* first vector */
fp1[0] = p1[0] - pt[0];
fp1[1] = p1[1] - pt[1];
for (i = 0; i < nr; i++) {
p2 = verts[i];
/* second vector */
fp2[0] = p2[0] - pt[0];
fp2[1] = p2[1] - pt[1];
/* dot and angle and cross */
angletot += angle_signed_v2v2(fp1, fp2);
/* circulate */
copy_v2_v2(fp1, fp2);
p1 = p2;
}
angletot = fabsf(angletot);
if (use_holes) {
const float nested = floorf((angletot / (float)(M_PI * 2.0)) + 0.00001f);
angletot -= nested * (float)(M_PI * 2.0);
return (angletot > 4.0f) != ((int)nested % 2);
}
else {
return (angletot > 4.0f);
}
}
/* math lib */
static float dot_v2v2(const float a[2], const float b[2])
{
return a[0] * b[0] + a[1] * b[1];
}
static float angle_signed_v2v2(const float v1[2], const float v2[2])
{
const float perp_dot = (v1[1] * v2[0]) - (v1[0] * v2[1]);
return atan2f(perp_dot, dot_v2v2(v1, v2));
}
static void copy_v2_v2(float r[2], const float a[2])
{
r[0] = a[0];
r[1] = a[1];
}
Hinweis: Dies ist eine der weniger optimalen Methoden, da es eine Menge Anrufe enthält atan2f, aber es kann für Entwickler von Interesse Lesen dieses Themas (dann mit der Linie Schnittverfahren in meinen Tests seine ~ 23x langsamer) sein.
Für Detecting auf Polygon treffen müssen wir zwei Dinge testen:
- Wenn Punkt innerhalb Polygonfläche ist. (Kann von Ray-Casting-Algorithmus erreicht werden)
- Wenn Punkt auf der Polygon Grenze ist (kann durch denselben Algorithmus erreicht werden, die für Punkterkennung auf Linienzug (line) verwendet wird).
mit den folgenden Sonderfällen in Ray Casting-Algorithmus umgehen
- Der Strahl überlappt einer der Polygon-Seite.
- Der Punkt befindet sich innerhalb des Polygons und der Strahl geht durch einen Scheitelpunkt des Polygons.
- Der Punkt ist, außerhalb des Polygons und der Strahl berührt nur eine der Polygon-Winkel.
Überprüfen Sie Bestimmung, ob ein Punkt innerhalb eines komplexen Polygon . Der Artikel bietet eine einfache Möglichkeit, sie zu lösen, so wird es keine Sonderbehandlung für die oben genannten Fälle erforderlich sein.
Sie können dies tun, indem geprüft wird, ob der Bereich, indem Sie den gewünschten Punkt mit den Eckpunkten des Polygons gebildet sich die Fläche des Polygons entspricht.
Oder Sie könnten überprüfen, ob die Summe des Innenwinkels von Ihrem Punkt zu jedem Paar von zwei aufeinanderfolgenden Polygon-Scheitelpunkten zu Ihrem Kontrollpunkt Summe bis 360, aber ich das Gefühl habe, dass die erste Option schneller ist, weil es nicht beteiligt ist Divisionen noch Berechnungen der inversen trigonometrischen Funktionen.
Ich weiß nicht, was passiert, wenn Ihr Polygon ein Loch in ihm hat, aber es scheint mir, dass die Grundidee kann auf diese Situation angepasst werden
Sie können auch schreiben die Frage in einer Mathe-Community. Ich wette, sie haben eine Million Möglichkeiten, das zu tun
Wenn Sie einen JavaScript-Bibliothek suchen gibt es eine JavaScript v3 Erweiterung für die Polygon-Klasse ordnet zu erkennen, ob ein Punkt in ihm wohnt.
var polygon = new google.maps.Polygon([], "#000000", 1, 1, "#336699", 0.3);
var isWithinPolygon = polygon.containsLatLng(40, -90);
Die Antwort hängt davon ab, wenn Sie die einfache oder komplexe Polygone haben. Einfache Polygone dürfen keine Liniensegment Kreuzungen haben. So können sie die Löcher haben, aber Linien können nicht kreuzen. Komplexe Regionen können die Linienkreuzungen haben -. So können sie die Überlappungsbereiche haben oder Regionen, die sich nur durch einen einzigen Punkt berühren
Für einfache Polygone der beste Algorithmus ist Ray (Crossing-Nummer) Algorithmus Gießen. Für komplexe Polygone, wird dieser Algorithmus keine Punkte erkennen, die in den Überlappungsbereichen sind. Also für komplex Polygone müssen Sie die Nummer Algorithmus verwenden Winding.
Hier ist ein ausgezeichneter Artikel mit C-Implementierung beider Algorithmen. Ich versuchte, sie und sie funktionieren gut.
Scala Version der Lösung von nirg (annimmt, umschließende Rechteck pre-check getrennt durchgeführt wird):
def inside(p: Point, polygon: Array[Point], bounds: Bounds): Boolean = {
val length = polygon.length
@tailrec
def oddIntersections(i: Int, j: Int, tracker: Boolean): Boolean = {
if (i == length)
tracker
else {
val intersects = (polygon(i).y > p.y) != (polygon(j).y > p.y) && p.x < (polygon(j).x - polygon(i).x) * (p.y - polygon(i).y) / (polygon(j).y - polygon(i).y) + polygon(i).x
oddIntersections(i + 1, i, if (intersects) !tracker else tracker)
}
}
oddIntersections(0, length - 1, tracker = false)
}
Hier ist golang Version von @nirg Antwort (inspiriert von C # -Code von @@ m-katz)
func isPointInPolygon(polygon []point, testp point) bool {
minX := polygon[0].X
maxX := polygon[0].X
minY := polygon[0].Y
maxY := polygon[0].Y
for _, p := range polygon {
minX = min(p.X, minX)
maxX = max(p.X, maxX)
minY = min(p.Y, minY)
maxY = max(p.Y, maxY)
}
if testp.X < minX || testp.X > maxX || testp.Y < minY || testp.Y > maxY {
return false
}
inside := false
j := len(polygon) - 1
for i := 0; i < len(polygon); i++ {
if (polygon[i].Y > testp.Y) != (polygon[j].Y > testp.Y) && testp.X < (polygon[j].X-polygon[i].X)*(testp.Y-polygon[i].Y)/(polygon[j].Y-polygon[i].Y)+polygon[i].X {
inside = !inside
}
j = i
}
return inside
}
überraschte niemand brachte dies früher, aber für die Pragmatiker eine Datenbank erfordern. MongoDB hat eine hervorragende Unterstützung für Geo-Abfragen einschließlich diesem
Was Sie suchen ist:
db.neighborhoods.findOne ({Geometrie: {$ geoIntersects: {$ Geometrie: { Typ: "Punkt", Koordinaten: [ "geographische Länge", "Breite"]}}} })
Neighborhoods ist die Sammlung, die eine oder mehr Polygone in Standard GeoJSON Format speichert. Wenn die Abfrage null ist es nicht anders geschnitten ist.
Sehr gut dokumentiert: https://docs.mongodb.com/manual/tutorial/geospatial-tutorial/
Die Leistung für mehr als 6.000 Punkte in einem 330 unregelmäßigen Vieleck Gitter klassifizierten war weniger als eine Minute ohne Optimierung auf allen und einschließlich der Zeit, Dokumente mit ihrem jeweiligen Polygon zu aktualisieren.
