У меня есть 2 вектора, которые являются координатами x и y из 8 вершин многоугольника
x = [5 5 7 7 9 9 5 7]
y = [8 6 6 8 6 8 10 10]
Я хочу сортировать их (по часовой стрелке) для получения правильных векторов (правильно рисовать многоугольник)
x = [5 7 9 9 7 7 5 5]
y = [6 6 6 8 8 10 10 8]
Шаг 1: Найдите центр тяжести:
cx = mean(x);
cy = mean(y);
Шаг 2: Найдите углы:
a = atan2(y - cy, x - cx);
Шаг 3: Найдите правильный порядок сортировки:
[~, order] = sort(a);
Шаг 4: Изменить порядок координат:
x = x(order);
y = y(order);
Версия Python (numpy) для алгоритма Бен-Фойгта:
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])
Пример:
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]])
Этот алгоритм не применим к невыпуклым многоугольникам. Вместо этого рассмотрите возможность использования MATLAB poly2cw()
Я попробовал решения @ben-voight и @mclafee, но я думаю, что они сортируют неправильный путь.
При использовании atan2 углы обозначаются следующим образом:
Угол положительный для углов против часовой стрелки (верхняя полуплоскость, y > 0) и отрицательный для углов по часовой стрелке (нижняя полуплоскость, y < 0).
Это означает, что использование возрастающей сортировки() для Numpy или Matlab будет прогрессивно против часовой стрелки.
Это можно проверить, используя уравнение Шойласа
Итак, при настройке ответов, упомянутых выше, для использования сортировки по убыванию правильного решения в Matlab,
cx = mean(x);
cy = mean(y);
a = atan2(y - cy, x - cx);
[~, order] = sort(a, 'descend');
x = x(order);
y = y(order);
Решение в numpy равно
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)
Вывод:
[[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.]]
Обратите внимание, что [::-1] используется для инвертирования массивов/списков.