[math] Wie kann man feststellen, ob eine Liste von Polygonpunkten im Uhrzeigersinn angeordnet ist?



8 Answers

Das Kreuzprodukt misst den Grad der Rechtwinkligkeit zweier Vektoren. Stellen Sie sich vor, dass jede Kante Ihres Polygons ein Vektor in der xy-Ebene eines dreidimensionalen (3-D) xyz-Raums ist. Dann ist das Kreuzprodukt von zwei aufeinanderfolgenden Kanten ein Vektor in der 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 zwei ursprünglichen Kanten, so dass er ein Maximum erreicht, wenn sie senkrecht sind, und sich verjüngt, um zu verschwinden, wenn die Kanten kollinear (parallel) sind.

Berechnen Sie also für jeden Eckpunkt (Punkt) des Polygons die produktübergreifende Größe der beiden angrenzenden Kanten:

Using your data:
point[0] = (5, 0)
point[1] = (6, 4)
point[2] = (4, 5)
point[3] = (1, 5)
point[4] = (1, 0)

So beschriften Sie die Kanten nacheinander als
edgeA ist das Segment von point0 nach point1 und
edgeB zwischen point1 bis point2
...
edgeE liegt zwischen point4 und point0 .

Dann ist Vertex A ( point0 ) dazwischen
edgeE [Von point4 nach point0 ]
edgeA [Von point0 nach `Punkt1 '

Diese beiden Kanten sind selbst Vektoren, deren x- und y-Koordinaten durch Subtraktion der Koordinaten ihrer Start- und Endpunkte bestimmt werden können:

edgeE = point0 - point4 = (1, 0) - (5, 0) = (-4, 0) und
edgeA = point1 - point0 = (6, 4) - (1, 0) = (5, 4) und

Und das Kreuzprodukt dieser zwei angrenzenden Kanten wird unter Verwendung der Determinante der folgenden Matrix berechnet, die konstruiert wird, indem die Koordinaten der zwei Vektoren unter die Symbole gesetzt werden, die die drei Koordinatenachsen ( i , j , & k ) darstellen. Die dritte (Null) -bewertete Koordinate ist da, weil das Kreuzprodukt-Konzept ein 3-D-Konstrukt ist, und so erweitern wir diese 2-D-Vektoren in 3-D, um das Kreuzprodukt anzuwenden:

 i    j    k 
-4    0    0
 1    4    0    

Vorausgesetzt, dass alle Kreuzprodukte einen Vektor senkrecht zur Ebene von zwei Vektoren erzeugen, die multipliziert werden, hat die Determinante der obigen Matrix nur eine k (oder z-Achsen-) Komponente.
Die Formel zum Berechnen der Größe der k oder z-Achsenkomponente ist
a1*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 Originalvektoren, multipliziert mit dem Produkt der Größen der beiden Vektoren.
Eigentlich ist eine andere Formel für ihren Wert
AXB (Cross Product) = |A| * |B| * sin(AB) AXB (Cross Product) = |A| * |B| * sin(AB) .

Um zu einem Maß für den Winkel zurückzukehren, müssen Sie diesen Wert ( -16 ) durch das Produkt der Größen der beiden Vektoren teilen.

|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 das nächste Segment nach dem Scheitelpunkt nach links oder rechts gebogen ist und um wie viel. Es ist nicht notwendig, Arc-Sinus zu nehmen. Alles, was uns interessiert, ist seine Größe und natürlich sein Vorzeichen (positiv oder negativ)!

Tun Sie dies für jeden der anderen 4 Punkte um den geschlossenen Pfad, und addieren Sie die Werte aus dieser Berechnung an jedem Knoten.

Wenn die letzte Summe positiv ist, ging es im Uhrzeigersinn, negativ, gegen den Uhrzeigersinn.

Question

Wie finde ich anhand einer Liste von Punkten heraus, ob sie im Uhrzeigersinn angeordnet sind?

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 manche Leute).




Hier ist eine einfache C # Implementierung des Algorithmus basierend auf dieser Antwort .

Nehmen wir an, wir haben einen Vector mit X und Y Eigenschaften vom Typ double .

public bool IsClockwise(IList<Vector> vertices)
{
    double sum = 0.0;
    for (int i = 0; i < vertices.Count; i++) {
        Vector v1 = vertices[i];
        Vector v2 = vertices[(i + 1) % vertices.Count]; // % is the modulo operator
        sum += (v2.X - v1.X) * (v2.Y + v1.Y);
    }
    return sum > 0.0;
}



Ich denke, damit einige Punkte im Uhrzeigersinn gegeben werden, müssen alle Kanten positiv sein, nicht nur die Summe der Kanten. Wenn eine Kante negativ ist, werden mindestens 3 Punkte gegen den Uhrzeigersinn gegeben.




Wie auch in diesem Wikipedia-Artikel Curve orientation erläutert, können Sie bei 3 Punkten p , q und r auf der Ebene (dh mit x- und y-Koordinaten) das Vorzeichen der folgenden Determinante berechnen

Wenn die Determinante negativ ist (dh Orient(p, q, r) < 0 ), dann ist das Polygon im Uhrzeigersinn orientiert (CW). Wenn die Determinante positiv ist (dh Orient(p, q, r) > 0 ), ist das Polygon gegen den Uhrzeigersinn orientiert (CCW). Die Determinante ist Null (dh Orient(p, q, r) == 0 ), wenn die Punkte p , q und r collinear .

In der obigen Formel werden die vor den Koordinaten von p , q und r da wir homogene Koordinaten verwenden .




Nach dem Testen mehrerer unzuverlässiger Implementierungen war der Algorithmus, der zufriedenstellende Ergebnisse in Bezug auf die CW / CCW-Orientierung lieferte, der von OP in this Thread ( shoelace_formula_3 ) geschriebene.

Wie immer steht eine positive Zahl für eine CW-Orientierung, eine negative Zahl für CCW.




Eine Implementierung von Seans Antwort in JavaScript:

function calcArea(poly) {
    if(!poly || poly.length < 3) return null;
    let end = poly.length - 1;
    let sum = poly[end][0]*poly[0][1] - poly[0][0]*poly[end][1];
    for(let i=0; i<end; ++i) {
        const n=i+1;
        sum += poly[i][0]*poly[n][1] - poly[n][0]*poly[i][1];
    }
    return sum;
}

function isClockwise(poly) {
    return calcArea(poly) > 0;
}

let poly = [[352,168],[305,208],[312,256],[366,287],[434,248],[416,186]];

console.log(isClockwise(poly));

let poly2 = [[618,186],[650,170],[701,179],[716,207],[708,247],[666,259],[637,246],[615,219]];

console.log(isClockwise(poly2));

Ziemlich sicher, das ist richtig. Es scheint zu funktionieren :-)

Diese Polygone sehen so aus, wenn Sie sich fragen:




Dies ist meine Lösung mit den Erklärungen in den anderen Antworten:

def segments(poly):
    """A sequence of (x,y) numeric coordinates pairs """
    return zip(poly, poly[1:] + [poly[0]])

def check_clockwise(poly):
    clockwise = False
    if (sum(x0*y1 - x1*y0 for ((x0, y0), (x1, y1)) in segments(poly))) < 0:
        clockwise = not clockwise
    return clockwise

poly = [(2,2),(6,2),(6,6),(2,6)]
check_clockwise(poly)
False

poly = [(2, 6), (6, 6), (6, 2), (2, 2)]
check_clockwise(poly)
True



Eine andere Lösung dafür;

const isClockwise = (vertices=[]) => {
    const len = vertices.length;
    const sum = vertices.map(({x, y}, index) => {
        let nextIndex = index + 1;
        if (nextIndex === len) nextIndex = 0;

        return {
            x1: x,
            x2: vertices[nextIndex].x,
            y1: x,
            y2: vertices[nextIndex].x
        }
    }).map(({ x1, x2, y1, y2}) => ((x2 - x1) * (y1 + y2))).reduce((a, b) => a + b);

    if (sum > -1) return true;
    if (sum < 0) return false;
}

Nimm alle Ecken als ein Array wie dieses;

const vertices = [{x: 5, y: 0}, {x: 6, y: 4}, {x: 4, y: 5}, {x: 1, y: 5}, {x: 1, y: 0}];
isClockwise(vertices);



Beginne an einem der Scheitelpunkte und berechne den Winkel, der auf jeder Seite liegt.

Die erste und die letzte werden Null sein (also überspringen Sie diese); im übrigen wird der Sinus des Winkels durch das Kreuzprodukt der Normierungen auf die Einheitslänge von (Punkt [n] -Punkt [0]) und (Punkt [n-1] -Punkt [0]) gegeben.

Wenn die Summe der Werte positiv ist, wird Ihr Polygon im Gegenuhrzeigersinn gezeichnet.






Related