Sorting clockwise polygon points in MATLAB

问题:

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]

回答1:

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);

回答2:

Python version (numpy) for Ben Voigt's algorithm:

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])

Example:

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]])

回答3:

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.

回答4:

This algorithm does not apply to non-convex polygons. Instead, consider using MATLAB's poly2cw()