I have 2 vectors that are x and y coordinates of the 8 vertexes of a polygon
x=[5 5 7 7 9 9 5 7]
y=[8 6 6 8 6 8 10 10]
I wanna sort them (clockwise) to obtain the right vectors (to draw the polygon correctly)
x=[5 7 9 9 7 7 5 5]
y=[6 6 6 8 8 10 10 8]
I tried the solutions by @ben-voight and @mclafee, but I think they are sorting the wrong way.
When using atan2 the angles are stated in the following way:
Matlab Atan2
The angle is positive for counter-clockwise angles (upper half-plane, y > 0), and negative for clockwise angles (lower half-plane, y < 0).
Wikipedia Atan2
This means that using ascending sort() of Numpy or Matlab will progress counterclockwise.
This can be verified using the Shoelace equation
Wikipedia Shoelace
Python Shoelace
So, adjusting the answers mentioned above to use descending sorting the correct solution in Matlab is
cx = mean(x);
cy = mean(y);
a = atan2(y - cy, x - cx);
[~, order] = sort(a, 'descend');
x = x(order);
y = y(order);
The solution in numpy is
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)
Output:
[[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.]]
Please notice the [::-1]
used to invert arrays / lists.
Step 1: Find the unweighted mean of the vertices:
cx = mean(x);
cy = mean(y);
Step 2: Find the angles:
a = atan2(y - cy, x - cx);
Step 3: Find the correct sorted order:
[~, order] = sort(a);
Step 4: Reorder the coordinates:
x = x(order);
y = y(order);
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With