Wie finde ich eine Liste mit Punkten im Uhrzeigersinn?
Beispielsweise:
point[0] = (5,0)
point[1] = (6,4)
point[2] = (4,5)
point[3] = (1,5)
point[4] = (1,0)
würde sagen, dass es gegen den Uhrzeigersinn ist (oder gegen den Uhrzeigersinn für einige Leute).
Antworten:
Einige der vorgeschlagenen Methoden schlagen bei einem nicht konvexen Polygon wie einem Halbmond fehl. Hier ist eine einfache Methode, die mit nicht konvexen Polygonen funktioniert (sie funktioniert sogar mit einem sich selbst überschneidenden Polygon wie einer Acht, das Ihnen sagt, ob es größtenteils im Uhrzeigersinn ist).
Summiere über die Kanten (x 2 - x 1 ) (y 2 + y 1 ). Wenn das Ergebnis positiv ist, ist die Kurve im Uhrzeigersinn, wenn es negativ ist, ist die Kurve gegen den Uhrzeigersinn. (Das Ergebnis ist doppelt so groß wie der umschlossene Bereich mit einer +/- Konvention.)
quelle
Sum( (x[(i+1) mod N] - x[i]) * (y[i] + y[(i+1) mod N]) )
für i = 0 bis N-1. Dh muss den Index Modulo N (N ≡ 0
) annehmen. Die Formel funktioniert nur für geschlossene Polygone. Polygone haben keine imaginären Kanten.Das Kreuzprodukt misst den Grad der Rechtwinkligkeit zweier Vektoren. Stellen Sie sich vor, jede Kante Ihres Polygons ist ein Vektor in der xy-Ebene eines dreidimensionalen (3-D) xyz-Raums. Dann ist das Kreuzprodukt zweier aufeinanderfolgender Kanten ein Vektor in z-Richtung (positive z-Richtung, wenn das zweite Segment im Uhrzeigersinn ist, minus z-Richtung, wenn es gegen den Uhrzeigersinn ist). Die Größe dieses Vektors ist proportional zum Sinus des Winkels zwischen den beiden ursprünglichen Kanten, sodass er ein Maximum erreicht, wenn sie senkrecht stehen, und sich verjüngt, um zu verschwinden, wenn die Kanten kollinear (parallel) sind.
Berechnen Sie also für jeden Scheitelpunkt (Punkt) des Polygons die Kreuzproduktgröße der beiden benachbarten Kanten:
Beschriften Sie die Kanten nacheinander, so wie
edgeA
das Segment vonpoint0
bispoint1
undedgeB
zwischenpoint1
bispoint2
...
edgeE
zwischenpoint4
und istpoint0
.Dann liegt Vertex A (
point0
) zwischenedgeE
[Vonpoint4
bispoint0
]edgeA
[Vonpoint0
bis `Punkt1 'Diese beiden Kanten sind selbst Vektoren, deren x- und y-Koordinaten durch Subtrahieren der Koordinaten ihrer Start- und Endpunkte bestimmt werden können:
edgeE
=point0
-point4
=(1, 0) - (5, 0)
=(-4, 0)
undedgeA
=point1
-point0
=(6, 4) - (1, 0)
=(5, 4)
undUnd das Kreuzprodukt der beiden angrenzenden Kanten berechnet die Determinante der folgenden Matrix verwendet, die , indem sie die Koordinaten der beiden Vektoren unter den Symbolen aufgebaut ist , die die drei Koordinatenachsen (
i
,j
, &k
). Die dritte (null) -bewertige Koordinate ist vorhanden, da das Kreuzproduktkonzept ein 3D-Konstrukt ist. Daher erweitern wir diese 2D-Vektoren in 3D, um das Kreuzprodukt anzuwenden:Da alle Kreuzprodukte einen Vektor senkrecht zur Ebene zweier zu multiplizierender Vektoren erzeugen, hat die Determinante der obigen Matrix nur eine
k
(oder z-Achsen-) Komponente.Die Formel zur Berechnung der Größe der
k
Komponente oder der Z-Achse lauteta1*b2 - a2*b1 = -4* 4 - 0* 1
=-16
Die Größe dieses Wertes (
-16
) ist ein Maß für den Sinus des Winkels zwischen den beiden ursprünglichen Vektoren, multipliziert mit dem Produkt der Größen der beiden Vektoren.Eigentlich ist eine andere Formel für seinen Wert
A X B (Cross Product) = |A| * |B| * sin(AB)
.Um auf ein Maß des Winkels zurückzukommen, müssen Sie diesen Wert (
-16
) durch das Produkt der Größen der beiden Vektoren dividieren .|A| * |B|
=4 * Sqrt(17)
=16.4924...
Also das Maß der Sünde (AB) =
-16 / 16.4924
=-.97014...
Dies ist ein Maß dafür, ob und um wie viel sich das nächste Segment nach dem Scheitelpunkt nach links oder rechts gebogen hat. Es ist nicht erforderlich, Arc-Sinus zu nehmen. Wir werden uns nur um seine Größe und natürlich um sein Vorzeichen (positiv oder negativ) kümmern!
Führen Sie dies für jeden der anderen 4 Punkte um den geschlossenen Pfad aus und addieren Sie die Werte aus dieser Berechnung an jedem Scheitelpunkt.
Wenn die endgültige Summe positiv ist, sind Sie im Uhrzeigersinn, negativ und gegen den Uhrzeigersinn gegangen.
quelle
Ich denke, das ist eine ziemlich alte Frage, aber ich werde trotzdem eine andere Lösung herauswerfen, weil sie einfach und nicht mathematisch intensiv ist - sie verwendet nur die grundlegende Algebra. Berechnen Sie die vorzeichenbehaftete Fläche des Polygons. Wenn es negativ ist, sind die Punkte im Uhrzeigersinn, wenn es positiv ist, sind sie gegen den Uhrzeigersinn. (Dies ist der Beta-Lösung sehr ähnlich.)
Berechnen Sie die vorzeichenbehaftete Fläche: A = 1/2 * (x 1 * y 2 - x 2 * y 1 + x 2 * y 3 - x 3 * y 2 + ... + x n * y 1 - x 1 * y n )
Oder im Pseudocode:
Beachten Sie, dass Sie sich nicht die Mühe machen müssen, durch 2 zu teilen, wenn Sie nur die Bestellung überprüfen.
Quellen: http://mathworld.wolfram.com/PolygonArea.html
quelle
previousPoint
bei der nächsten Iteration speichert .previousPoint
Stellen Sie vor dem Starten der Schleife den letzten Punkt des Arrays ein. Ein Kompromiss ist eine zusätzliche lokale Variablenkopie, aber weniger Array-Zugriffe. Und vor allem müssen Sie das Eingabearray nicht berühren.Finden Sie den Scheitelpunkt mit dem kleinsten y (und dem größten x, wenn es Bindungen gibt). Der Scheitelpunkt sei
A
und der vorherige Scheitelpunkt in der Liste seiB
und der nächste Scheitelpunkt in der Liste seiC
. Berechnen Sie nun das Vorzeichen des Kreuzprodukts vonAB
undAC
.Verweise:
Wie finde ich die Ausrichtung eines einfachen Polygons? in häufig gestellten Fragen: comp.graphics.algorithms .
Kurvenorientierung bei Wikipedia.
quelle
O(1)
Lösung. Alle anderen Antworten ergebenO(n)
Lösungen fürn
die Anzahl der Polygonpunkte. Weitere Informationen zu noch tieferen Optimierungen finden Sie im Unterabschnitt " Praktische Überlegungen" des fantastischen Wikipedia- Artikels zur Kurvenorientierung .O(1)
nur verfügbar, wenn entweder (A) dieses Polygon konvex ist (in diesem Fall befindet sich ein beliebiger Scheitelpunkt auf der konvexen Hülle und reicht daher aus) oder (B) Sie den Scheitelpunkt mit der kleinsten Y-Koordinate bereits kennen. Wenn dies nicht der Fall ist (dh dieses Polygon ist nicht konvex und Sie wissen nichts darüber), ist eineO(n)
Suche erforderlich. Da jedoch keine Summierung erforderlich ist, ist dies immer noch erheblich schneller als jede andere Lösung für einfache Polygone.Hier ist eine einfache C # -Implementierung des Algorithmus basierend auf dieser Antwort .
Nehmen wir an, wir haben einen
Vector
Typ mitX
undY
Eigenschaften von Typdouble
.%
ist der Modulo- oder Restoperator, der die Modulo-Operation ausführt, die ( laut Wikipedia ) den Rest nach Division einer Zahl durch eine andere findet.quelle
Beginnen Sie an einem der Eckpunkte und berechnen Sie den Winkel, den jede Seite bildet.
Der erste und der letzte sind Null (überspringen Sie diese also); im übrigen wird der Sinus des Winkels durch das Kreuzprodukt der Normalisierungen zur Längeneinheit von (Punkt [n] -Punkt [0]) und (Punkt [n-1] -Punkt [0]) gegeben.
Wenn die Summe der Werte positiv ist, wird Ihr Polygon gegen den Uhrzeigersinn gezeichnet.
quelle
Für das, was es wert ist, habe ich dieses Mixin verwendet, um die Wicklungsreihenfolge für Google Maps API v3-Apps zu berechnen.
Der Code nutzt den Nebeneffekt von Polygonbereichen: Eine Wicklungsreihenfolge von Scheitelpunkten im Uhrzeigersinn ergibt eine positive Fläche, während eine Wicklungsreihenfolge derselben Scheitelpunkte gegen den Uhrzeigersinn dieselbe Fläche wie ein negativer Wert erzeugt. Der Code verwendet auch eine Art private API in der Google Maps-Geometriebibliothek. Ich habe mich wohl gefühlt - auf eigenes Risiko.
Beispielnutzung:
Vollständiges Beispiel mit Unit-Tests @ http://jsfiddle.net/stevejansen/bq2ec/
quelle
Eine Implementierung von Seans Antwort in JavaScript:
Ich bin mir ziemlich sicher, dass das richtig ist. Es scheint zu funktionieren :-)
Diese Polygone sehen so aus, wenn Sie sich fragen:
quelle
Dies ist die implementierte Funktion für OpenLayers 2 . Die Bedingung für ein Polygon im Uhrzeigersinn ist
area < 0
, wie durch diese Referenz bestätigt .quelle
Wenn Sie Matlab verwenden, gibt die Funktion
ispolycw
true zurück, wenn die Polygonscheitelpunkte im Uhrzeigersinn sind.quelle
Wie erläutert auch in diesem Artikel Wikipedia Orientierung Curve , 3 Punkte gegeben
p
,q
undr
auf der Ebene (dh mit x und y - Koordinaten), kann das Vorzeichen der folgenden Determinante berechnenWenn die Determinante negativ ist (dh
Orient(p, q, r) < 0
), ist das Polygon im Uhrzeigersinn ausgerichtet (CW). Wenn die Determinante positiv ist (dhOrient(p, q, r) > 0
), ist das Polygon gegen den Uhrzeigersinn (CCW) ausgerichtet. Die Determinante Null ist (dhOrient(p, q, r) == 0
) , wenn Punktep
,q
undr
sind kollinear .In der obigen Formel prepend wir die , die vor den Koordinaten
p
,q
undr
da wir verwenden homogene Koordinaten .quelle
Ich denke, damit einige Punkte im Uhrzeigersinn vergeben werden, müssen alle Kanten positiv sein, nicht nur die Summe der Kanten. Wenn eine Flanke negativ ist, werden mindestens 3 Punkte gegen den Uhrzeigersinn vergeben.
quelle
Meine C # / LINQ-Lösung basiert auf den produktübergreifenden Empfehlungen von @charlesbretana. Sie können eine Referenznormale für die Wicklung angeben. Es sollte funktionieren, solange sich die Kurve größtenteils in der durch den Aufwärtsvektor definierten Ebene befindet.
mit einem Unit-Test
quelle
Dies ist meine Lösung unter Verwendung der Erklärungen in den anderen Antworten:
quelle
Eine viel rechnerisch einfachere Methode, wenn Sie bereits einen Punkt innerhalb des Polygons kennen :
Wählen Sie ein beliebiges Liniensegment aus dem ursprünglichen Polygon, den Punkten und deren Koordinaten in dieser Reihenfolge.
Fügen Sie einen bekannten "inneren" Punkt hinzu und bilden Sie ein Dreieck.
Berechnen Sie CW oder CCW wie hier vorgeschlagen mit diesen drei Punkten.
quelle
Nach dem Testen mehrerer unzuverlässiger Implementierungen war der Algorithmus, der sofort zufriedenstellende Ergebnisse hinsichtlich der CW / CCW-Ausrichtung lieferte, derjenige, der von OP in diesem Thread veröffentlicht wurde (
shoelace_formula_3
) veröffentlicht wurde.Wie immer steht eine positive Zahl für eine CW-Ausrichtung, während eine negative Zahl CCW darstellt.
quelle
Hier ist eine schnelle 3.0-Lösung basierend auf den obigen Antworten:
quelle
Eine andere Lösung dafür;
Nehmen Sie alle Eckpunkte als Array wie dieses;
quelle
Lösung für R, um die Richtung zu bestimmen und im Uhrzeigersinn umzukehren (für Owin-Objekte erforderlich):
quelle
Diese Antworten sind zwar richtig, aber mathematisch intensiver als nötig. Nehmen Sie Kartenkoordinaten an, wobei der nördlichste Punkt der höchste Punkt auf der Karte ist. Finden Sie den nördlichsten Punkt, und wenn 2 Punkte gleich sind, ist es der nördlichste und dann der östlichste (dies ist der Punkt, den lhf in seiner Antwort verwendet). In Ihren Punkten,
Punkt [0] = (5,0)
Punkt [1] = (6,4)
Punkt [2] = (4,5)
Punkt [3] = (1,5)
Punkt [4] = (1,0)
Wenn wir annehmen, dass P2 der nördlichste und der östlichste Punkt ist, bestimmen entweder der vorherige oder der nächste Punkt im Uhrzeigersinn, CW oder CCW. Da sich der nördlichste Punkt auf der Nordseite befindet, ist die Richtung CW, wenn sich P1 (vorher) zu P2 nach Osten bewegt. In diesem Fall bewegt es sich nach Westen, sodass die Richtung CCW ist, wie in der akzeptierten Antwort angegeben. Wenn der vorherige Punkt keine horizontale Bewegung hat, gilt dasselbe System für den nächsten Punkt, P3. Wenn P3 westlich von P2 liegt, ist die Bewegung gegen den Uhrzeigersinn. Wenn die Bewegung von P2 nach P3 nach Osten, in diesem Fall nach Westen, ist die Bewegung CW. Angenommen, nte, P2 in Ihren Daten, ist der nördlichste und östlichste Punkt und prv ist der vorherige Punkt, P1 in Ihren Daten und nxt ist der nächste Punkt, P3 in Ihren Daten und [0] ist horizontal oder östlich / West, wo West weniger als Ost ist und [1] vertikal ist.
quelle
.x
und.y
eine Struktur, statt[0]
und[1]
ich wusste nicht , was Ihr Code sagt, erstes Mal , dass ich es sah..)C # -Code zur Implementierung der Antwort von lhf :
quelle
Hier ist eine einfache Python 3-Implementierung, die auf dieser Antwort basiert (die wiederum auf der in der akzeptierten Antwort vorgeschlagenen Lösung basiert ).
quelle
Finden Sie den Schwerpunkt dieser Punkte.
Angenommen, es gibt Linien von diesem Punkt zu Ihren Punkten.
Finden Sie den Winkel zwischen zwei Linien für Linie0, Linie1
als für line1 und line2
...
...
Wenn dieser Winkel monoton größer ist als gegen den Uhrzeigersinn,
sonst, wenn es monoton abnimmt, ist es im Uhrzeigersinn
sonst (es ist nicht monoton)
Sie können sich nicht entscheiden, also ist es nicht klug
quelle