Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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]

like image 758
brio Avatar asked Dec 18 '12 14:12

brio


2 Answers

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:

enter image description here

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.

like image 195
Joe Avatar answered Sep 18 '22 15:09

Joe


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);
like image 24
Ben Voigt Avatar answered Sep 19 '22 15:09

Ben Voigt