Сортировка точек по часовой стрелке?
Учитывая массив точек x,y, как мне отсортировать точки этого массива по часовой стрелке (вокруг их средней средней точки)? Моя цель состоит в том, чтобы передать точки в функцию создания линий, чтобы в итоге получилось нечто "сплошное", настолько выпуклое, насколько это возможно, без пересекающихся линий.
Для чего это стоит, я использую Lua, но любой псевдокод был бы оценен. Большое спасибо за любую помощь!
Обновление: для справки, это код Lua, основанный на превосходном ответе Ciamej (игнорируйте мой префикс "app"):
function appSortPointsClockwise(points)
local centerPoint = appGetCenterPointOfPoints(points)
app.pointsCenterPoint = centerPoint
table.sort(points, appGetIsLess)
return points
end
function appGetIsLess(a, b)
local center = app.pointsCenterPoint
if a.x >= 0 and b.x < 0 then return true
elseif a.x == 0 and b.x == 0 then return a.y > b.y
end
local det = (a.x - center.x) * (b.y - center.y) - (b.x - center.x) * (a.y - center.y)
if det < 0 then return true
elseif det > 0 then return false
end
local d1 = (a.x - center.x) * (a.x - center.x) + (a.y - center.y) * (a.y - center.y)
local d2 = (b.x - center.x) * (b.x - center.x) + (b.y - center.y) * (b.y - center.y)
return d1 > d2
end
function appGetCenterPointOfPoints(points)
local pointsSum = {x = 0, y = 0}
for i = 1, #points do pointsSum.x = pointsSum.x + points[i].x; pointsSum.y = pointsSum.y + points[i].y end
return {x = pointsSum.x / #points, y = pointsSum.y / #points}
end
8 ответов
Сначала вычислите центральную точку. Затем сортируйте точки, используя любой алгоритм сортировки, который вам нравится, но используйте специальную процедуру сравнения, чтобы определить, меньше ли одна точка, чем другая.
Вы можете проверить, находится ли одна точка (а) слева или справа от другой (б) относительно центра, с помощью этого простого вычисления:
det = (a.x - center.x) * (b.y - center.y) - (b.x - center.x) * (a.y - center.y)
если результат равен нулю, то они находятся на одной линии от центра, если он положительный или отрицательный, то он находится на одной или другой стороне, поэтому одна точка будет предшествовать другой. Используя его, вы можете построить отношение меньше чем, чтобы сравнить точки и определить порядок, в котором они должны появляться в отсортированном массиве. Но вы должны определить, где находится начало этого порядка, я имею в виду, какой угол будет начальным (например, положительная половина оси X).
Код для функции сравнения может выглядеть так:
bool less(point a, point b)
{
if (a.x - center.x >= 0 && b.x - center.x < 0)
return true;
if (a.x - center.x < 0 && b.x - center.x >= 0)
return false;
if (a.x - center.x == 0 && b.x - center.x == 0) {
if (a.y - center.y >= 0 || b.y - center.y >= 0)
return a.y > b.y;
return b.y > a.y;
}
// compute the cross product of vectors (center -> a) x (center -> b)
int det = (a.x - center.x) * (b.y - center.y) - (b.x - center.x) * (a.y - center.y);
if (det < 0)
return true;
if (det > 0)
return false;
// points a and b are on the same line from the center
// check which point is closer to the center
int d1 = (a.x - center.x) * (a.x - center.x) + (a.y - center.y) * (a.y - center.y);
int d2 = (b.x - center.x) * (b.x - center.x) + (b.y - center.y) * (b.y - center.y);
return d1 > d2;
}
Это упорядочит точки по часовой стрелке, начиная с 12 часов. Очки в тот же "час" будут заказываться, начиная с тех, которые находятся дальше от центра.
Если вы используете целочисленные типы (которых нет в Lua), вам нужно убедиться, что переменные det, d1 и d2 относятся к типу, который сможет содержать результат выполненных вычислений.
Если вы хотите добиться чего-то твердого, выпуклого, насколько это возможно, то я думаю, что вы ищете выпуклый корпус. Вы можете вычислить его, используя сканирование Грэма. В этом алгоритме вы также должны отсортировать точки по часовой стрелке (или против часовой стрелки), начиная со специальной точки поворота. Затем вы повторяете простые шаги цикла каждый раз, проверяя, поворачиваете ли вы влево или вправо, добавляя новые точки к выпуклой оболочке, эта проверка основана на перекрестном произведении, как в приведенной выше функции сравнения.
Редактировать:
Добавлен еще один оператор if if (a.y - center.y >= 0 || b.y - center.y >=0) чтобы убедиться, что точки с x=0 и отрицательным y отсортированы, начиная с тех, которые находятся дальше от центра. Если вас не волнует порядок точек в один и тот же "час", вы можете опустить это выражение if и всегда возвращать a.y > b.y,
Исправлены первые операторы if с добавлением -center.x а также -center.y,
Добавлен второй оператор if (a.x - center.x < 0 && b.x - center.x >= 0), Это было очевидное упущение, что оно отсутствовало. Операторы if могут быть реорганизованы сейчас, потому что некоторые проверки являются избыточными. Например, если первое условие в первом операторе if является ложным, то первое условие второго условия if должно быть истинным. Однако я решил оставить код таким, какой он есть, ради простоты. Вполне возможно, что компилятор все равно оптимизирует код и даст тот же результат.
То, что вы просите, это система, известная как полярные координаты. Преобразование из декартовых в полярные координаты легко выполняется на любом языке. Формулы можно найти в этом разделе.
Я не знаю Lua, но эта страница предлагает фрагменты кода для этого преобразования.
После преобразования в полярные координаты, просто отсортируйте по углу, тета.
Интересным альтернативным подходом к вашей проблеме было бы найти приблизительный минимум для задачи коммивояжера (TSP), т.е. кратчайший маршрут, связывающий все ваши точки. Если ваши точки образуют выпуклую форму, это должно быть правильным решением, в противном случае они все равно должны выглядеть хорошо ("сплошная" форма может быть определена как форма с низким отношением периметр / площадь, что мы и оптимизируем здесь),
Вы можете использовать любую реализацию оптимизатора для TSP, и я уверен, что вы сможете найти тонну на вашем языке.
Другая версия (верните true, если a предшествует b в направлении против часовой стрелки):
bool lessCcw(const Vector2D ¢er, const Vector2D &a, const Vector2D &b) const
{
// Computes the quadrant for a and b (0-3):
// ^
// 1 | 0
// ---+-->
// 2 | 3
const int dax = ((a.x() - center.x()) > 0) ? 1 : 0;
const int day = ((a.y() - center.y()) > 0) ? 1 : 0;
const int qa = (1 - dax) + (1 - day) + ((dax & (1 - day)) << 1);
/* The previous computes the following:
const int qa =
( (a.x() > center.x())
? ((a.y() > center.y())
? 0 : 3)
: ((a.y() > center.y())
? 1 : 2)); */
const int dbx = ((b.x() - center.x()) > 0) ? 1 : 0;
const int dby = ((b.y() - center.y()) > 0) ? 1 : 0;
const int qb = (1 - dbx) + (1 - dby) + ((dbx & (1 - dby)) << 1);
if (qa == qb) {
return (b.x() - center.x()) * (a.y() - center.y()) < (b.y() - center.y()) * (a.x() - center.x());
} else {
return qa < qb;
}
}
Это быстрее, потому что компилятор (протестированный на Visual C++ 2015) не генерирует переход для вычисления dax, day, dbx, dby. Вот выходная сборка от компилятора:
; 28 : const int dax = ((a.x() - center.x()) > 0) ? 1 : 0;
vmovss xmm2, DWORD PTR [ecx]
vmovss xmm0, DWORD PTR [edx]
; 29 : const int day = ((a.y() - center.y()) > 0) ? 1 : 0;
vmovss xmm1, DWORD PTR [ecx+4]
vsubss xmm4, xmm0, xmm2
vmovss xmm0, DWORD PTR [edx+4]
push ebx
xor ebx, ebx
vxorps xmm3, xmm3, xmm3
vcomiss xmm4, xmm3
vsubss xmm5, xmm0, xmm1
seta bl
xor ecx, ecx
vcomiss xmm5, xmm3
push esi
seta cl
; 30 : const int qa = (1 - dax) + (1 - day) + ((dax & (1 - day)) << 1);
mov esi, 2
push edi
mov edi, esi
; 31 :
; 32 : /* The previous computes the following:
; 33 :
; 34 : const int qa =
; 35 : ( (a.x() > center.x())
; 36 : ? ((a.y() > center.y()) ? 0 : 3)
; 37 : : ((a.y() > center.y()) ? 1 : 2));
; 38 : */
; 39 :
; 40 : const int dbx = ((b.x() - center.x()) > 0) ? 1 : 0;
xor edx, edx
lea eax, DWORD PTR [ecx+ecx]
sub edi, eax
lea eax, DWORD PTR [ebx+ebx]
and edi, eax
mov eax, DWORD PTR _b$[esp+8]
sub edi, ecx
sub edi, ebx
add edi, esi
vmovss xmm0, DWORD PTR [eax]
vsubss xmm2, xmm0, xmm2
; 41 : const int dby = ((b.y() - center.y()) > 0) ? 1 : 0;
vmovss xmm0, DWORD PTR [eax+4]
vcomiss xmm2, xmm3
vsubss xmm0, xmm0, xmm1
seta dl
xor ecx, ecx
vcomiss xmm0, xmm3
seta cl
; 42 : const int qb = (1 - dbx) + (1 - dby) + ((dbx & (1 - dby)) << 1);
lea eax, DWORD PTR [ecx+ecx]
sub esi, eax
lea eax, DWORD PTR [edx+edx]
and esi, eax
sub esi, ecx
sub esi, edx
add esi, 2
; 43 :
; 44 : if (qa == qb) {
cmp edi, esi
jne SHORT $LN37@lessCcw
; 45 : return (b.x() - center.x()) * (a.y() - center.y()) < (b.y() - center.y()) * (a.x() - center.x());
vmulss xmm1, xmm2, xmm5
vmulss xmm0, xmm0, xmm4
xor eax, eax
pop edi
vcomiss xmm0, xmm1
pop esi
seta al
pop ebx
; 46 : } else {
; 47 : return qa < qb;
; 48 : }
; 49 : }
ret 0
$LN37@lessCcw:
pop edi
pop esi
setl al
pop ebx
ret 0
?lessCcw@@YA_NABVVector2D@@00@Z ENDP ; lessCcw
Наслаждаться.
Я знаю, что это несколько старый пост с отличным принятым ответом, но я чувствую, что все еще могу внести что-то полезное. Все ответы до сих пор по существу используют функцию сравнения для сравнения двух точек и определения их порядка, но что, если вы хотите использовать только одну точку за раз и ключевую функцию ?
Это не только возможно, но полученный код также чрезвычайно компактен. Вот полное решение с использованием встроенной функции сортировки Python:
# Create some random points
num = 7
points = np.random.random((num, 2))
# Compute their center
center = np.mean(points, axis=0)
# Make arctan2 function that returns a value from [0, 2 pi) instead of [-pi, pi)
arctan2 = lambda s, c: angle if (angle := np.arctan2(s, c)) >= 0 else 2 * np.pi + angle
# Define the key function
def clockwise_around_center(point):
diff = point - center
rcos = np.dot(diff, center)
rsin = np.cross(diff, center)
return arctan2(rsin, rcos)
# Sort our points using the key function
sorted_points = sorted(points, key=clockwise_around_center)
Этот ответ также будет работать в 3D, если точки находятся на 2D-плоскости, встроенной в 3D. Нам нужно было бы только изменить вычисление, расставив точки над вектором нормали к плоскости. Например
rsin = np.dot([0,0,1], np.cross(diff, center))
если этот самолетe_zкак его нормальный вектор.
Преимущество этого кода в том, что он работает только в одной точке одновременно, используя ключевую функцию. Величина , если разобраться на уровне коэффициентов, точно такая же, как то, что называетсяdetв ответе принимающего, за исключением того, что я вычисляю его между и , а не междуpoint1 - centerиpoint2 - center. Но геометрический смысл этой величины — радиус, умноженный на грех угла, поэтому я называю эту переменнуюrsin. Точно так же для скалярного произведения, которое представляет собой произведение радиуса на косинус угла и, следовательно, называетсяrcos.
Можно утверждать, что это решение использует , и поэтому менее чистое. Однако лично я считаю, что ясность использования ключевой функции перевешивает необходимость одного вызова триггерной функции. Обратите внимание, что я предпочитаю иметьarctan2вернуть значение из[0, 2 pi), потому что тогда мы получим угол0когда окажется идентичным , и, таким образом, это будет первая точка в нашем отсортированном списке. Это необязательный выбор.
Чтобы понять, почему этот код работает, важно понять, что все наши точки определяются как стрелки относительно начала координат, включая саму точку. Итак, если мы посчитаем , это эквивалентно размещению стрелки от кончика до кончикаpoint, в начале. Следовательно, мы можем отсортировать стрелкуpoint - centerотносительно угла, который он образует со стрелкой, указывающей наcenter.
- vector3 a = новый вектор3(1, 0, 0).............. относительно X_axis
- vector3 b = любая_точка - Центр;
- y = |a * b| , x = a . b
- Atan2(y , x)...............................gives angle between -PI to + PI in radians
- (Input % 360 + 360) % 360................to convert it from 0 to 2PI in radians
- sort by adding_points to list_of_polygon_verts by angle we got 0 to 360
Наконец вы получите Anticlockwize отсортированные верты
list.Reverse()..................Clockwise_order
С пустым:
import matplotlib.pyplot as plt
import numpy as np
# List of coords
coords = np.array([7,7, 5, 0, 0, 0, 5, 10, 10, 0, 0, 5, 10, 5, 0, 10, 10, 10]).reshape(-1, 2)
centroid = np.mean(coords, axis=0)
sorted_coords = coords[np.argsort(np.arctan2(coords[:, 1] - centroid[1], coords[:, 0] - centroid[0])), :]
plt.scatter(coords[:,0],coords[:,1])
plt.plot(coords[:,0],coords[:,1])
plt.plot(sorted_coords[:,0],sorted_coords[:,1])
plt.show()
Вот способ отсортировать вершины прямоугольника по часовой стрелке. Я изменил исходное решение, предоставленное pyimagesearch , и избавился от зависимости scipy.
import numpy as np
def pointwise_distance(pts1, pts2):
"""Calculates the distance between pairs of points
Args:
pts1 (np.ndarray): array of form [[x1, y1], [x2, y2], ...]
pts2 (np.ndarray): array of form [[x1, y1], [x2, y2], ...]
Returns:
np.array: distances between corresponding points
"""
dist = np.sqrt(np.sum((pts1 - pts2)**2, axis=1))
return dist
def order_points(pts):
"""Orders points in form [top left, top right, bottom right, bottom left].
Source: https://www.pyimagesearch.com/2016/03/21/ordering-coordinates-clockwise-with-python-and-opencv/
Args:
pts (np.ndarray): list of points of form [[x1, y1], [x2, y2], [x3, y3], [x4, y4]]
Returns:
[type]: [description]
"""
# sort the points based on their x-coordinates
x_sorted = pts[np.argsort(pts[:, 0]), :]
# grab the left-most and right-most points from the sorted
# x-roodinate points
left_most = x_sorted[:2, :]
right_most = x_sorted[2:, :]
# now, sort the left-most coordinates according to their
# y-coordinates so we can grab the top-left and bottom-left
# points, respectively
left_most = left_most[np.argsort(left_most[:, 1]), :]
tl, bl = left_most
# now that we have the top-left coordinate, use it as an
# anchor to calculate the Euclidean distance between the
# top-left and right-most points; by the Pythagorean
# theorem, the point with the largest distance will be
# our bottom-right point. Note: this is a valid assumption because
# we are dealing with rectangles only.
# We need to use this instead of just using min/max to handle the case where
# there are points that have the same x or y value.
D = pointwise_distance(np.vstack([tl, tl]), right_most)
br, tr = right_most[np.argsort(D)[::-1], :]
# return the coordinates in top-left, top-right,
# bottom-right, and bottom-left order
return np.array([tl, tr, br, bl], dtype="float32")