Sortieren von Polygonpunkten im Uhrzeigersinn in MATLAB

Question

Ich habe 2 Vektoren, die die x- und y-Koordinaten der 8 Scheitelpunkte eines Polygons sind

x=[5 5 7 7 9 9 5 7]

y=[8 6 6 8 6 8 10 10]

Ich möchte sie sortieren (im Uhrzeigersinn), um die richtigen Vektoren zu erhalten (um das Polygon korrekt zu zeichnen)

x=[5 7 9 9 7 7 5 5]

y=[6 6 6 8 8 10 10 8]

Answer 1

Schritt 1: Ermitteln Sie den ungewichteten Mittelwert der Scheitelpunkte:

cx = mean(x);
cy = mean(y);

Schritt 2: Finde die Winkel:

a = atan2(y - cy, x - cx);

Schritt 3: Finden Sie die richtige Sortierreihenfolge:

[~, order] = sort(a);

Schritt 4: Ordnen Sie die Koordinaten neu an:

x = x(order);
y = y(order);

Answer 2

Python-Version (numpy) für den Algorithmus von Ben Voigt:

def clockwise(points):
    x = points[0,:]
    y = points[1,:]
    cx = np.mean(x)
    cy = np.mean(y)
    a = np.arctan2(y - cy, x - cx)
    order = a.ravel().argsort()
    x = x[order]
    y = y[order]
    return np.vstack([x,y])

Beispiel:

In [281]: pts
Out[281]: 
array([[7, 2, 2, 7],
       [5, 1, 5, 1]])

In [282]: clockwise(pts)
Out[282]: 
array([[2, 7, 7, 2],
       [1, 1, 5, 5]])

Answer 3

Ich habe die Lösungen von @ben-voight und @mclafee ausprobiert, aber ich glaube, sie sortieren in die falsche Richtung.

Bei der Verwendung von atan2 werden die Winkel auf folgende Weise angegeben:

Matlab Atan2

Der Winkel ist positiv bei Winkeln gegen den Uhrzeigersinn (nach oben y > 0), und negativ für Winkel im Uhrzeigersinn (untere Halbebene, y < 0).

Wikipedia Atan2

Das bedeutet, dass die Verwendung von ascending sort() von Numpy oder Matlab gegen den Uhrzeigersinn erfolgt.

Dies kann mit Hilfe der Schnürsenkelgleichung überprüft werden

Wikipedia Schnürsenkel

Python Schnürsenkel

Wenn man also die oben genannten Antworten so anpasst, dass die absteigende Sortierung verwendet wird, lautet die richtige Lösung in Matlab

cx = mean(x);
cy = mean(y);
a = atan2(y - cy, x - cx);
[~, order] = sort(a, 'descend');
x = x(order);
y = y(order);

Die Lösung in Numpy lautet

import numpy as np

def clockwise(points):
    x = points[0,:]
    y = points[1,:]
    cx = np.mean(x)
    cy = np.mean(y)
    a = np.arctan2(y - cy, x - cx)
    order = a.ravel().argsort()[::-1]
    x = x[order]
    y = y[order]
    return np.vstack([x,y])

pts = np.array([[7, 2, 2, 7],
                [5, 1, 5, 1]])

clockwise(pts)

pts = np.array([[1.0, 1.0],
                [-1.0, -1.0],
                [1.0, -1.0],
                [-1.0, 1.0]]).transpose()

clockwise(pts)

Ausgabe:

[[7 2 2 7]
 [5 1 5 1]]

[[2 7 7 2]
 [5 5 1 1]]

[[ 1. -1.  1. -1.]
 [ 1. -1. -1.  1.]]

[[-1.  1.  1. -1.]
 [ 1.  1. -1. -1.]]

Bitte beachten Sie die [::-1] zum Invertieren von Arrays/Listen verwendet.

Answer 4

Dieser Algorithmus gilt nicht für nicht-konvexe Polygone. Verwenden Sie stattdessen die MATLAB-Funktion poly2cw()