12

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]

4 Answers 4

24

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);
4
  • What if the points form a concave polygon? Is there any workaround for that scenerio? Nov 22, 2013 at 9:54
  • There's more than one polygon that cam be created with the same vertices. This will find one of them, and it will be a minimally concave polygon in some sense. I expect that the centroid will always lie inside the chosen polygon.
    – Ben Voigt
    Nov 22, 2013 at 13:38
  • I think this is sorting the wrong way. "The angle is positive for counter-clockwise angles (upper half-plane, y > 0), and negative for clockwise angles (lower half-plane, y < 0)." See my answer below: stackoverflow.com/a/44972382/7919597
    – Joe
    Jul 19, 2017 at 8:41
  • @Joe: Changing the sort order is absolutely trivial (just negate either one of the atan2 inputs, or negate the output, or reverse the order vector in step 4) and not worth fussing about. And the question says the purpose is "to draw them" so reversal of the sort makes no difference anyway.
    – Ben Voigt
    Oct 21, 2020 at 15:10
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]])
1
  • I think this is sorting the wrong way. "The angle is positive for counter-clockwise angles (upper half-plane, y > 0), and negative for clockwise angles (lower half-plane, y < 0)." See my answer below: stackoverflow.com/a/44972382/7919597
    – Joe
    Jul 19, 2017 at 8:39
1

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.

2
  • What you claim is correct. I agree, but your solution as well do not takes care of the concave nature polygons. In that case, if there are more than two points at the same angle, you don't know in what order they will be produced, and this may bring some future point of the actual order earlier and hence producing an incorrect sorted order.
    – Prem KTiw
    Jul 13, 2018 at 9:08
  • Yes, that's correct. For this algorithm to work, the polygon has to be really really well behaved :)
    – Joe
    Jul 13, 2018 at 11:23
0

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

1
  • You can't classify the input as convex or not, since the input is not a polygon, just a set of points in no particular order (if I'm understanding the question correctly). The output is the points ordered in one way that forms a simple polygon (the edges will never cross each other).
    – Ben Voigt
    Feb 15, 2016 at 22:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.