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]

Community
  • 1
  • 1
brio
  • 155
  • 1
  • 1
  • 6

4 Answers4

25

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);
Ben Voigt
  • 277,958
  • 43
  • 419
  • 720
  • What if the points form a concave polygon? Is there any workaround for that scenerio? – Sibbs Gambling Nov 22 '13 at 09: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 '13 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: https://stackoverflow.com/a/44972382/7919597 – Joe Jul 19 '17 at 08: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 '20 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]])
mclafee
  • 1,406
  • 3
  • 18
  • 25
  • 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: https://stackoverflow.com/a/44972382/7919597 – Joe Jul 19 '17 at 08: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.

Joe
  • 6,758
  • 2
  • 26
  • 47
  • 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 '18 at 09:08
  • Yes, that's correct. For this algorithm to work, the polygon has to be really really well behaved :) – Joe Jul 13 '18 at 11:23
0

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

Netanel
  • 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 '16 at 22:15