Сортировать точки по часовой стрелке?
учитывая массив точек 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
4 ответов:
сначала вычислить центральную точку. Затем отсортируйте точки, используя любой алгоритм сортировки, который вам нравится, но используйте специальную процедуру сравнения, чтобы определить, меньше ли одна точка, чем другая.
вы можете проверить, находится ли одна точка (a) слева или справа от другой (b) по отношению к центру с помощью этого простого вычисления:
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 имеют тип, который сможет содержать результат выполненных вычислений.
если вы хотите достичь чего-то, выглядящего твердым, как можно более выпуклым, то я думаю, вы ищете Выпуклой Оболочки. Вы можете вычислить его с помощью Грэхема. В этом алгоритме, вы также должны отсортировать точки по часовой стрелке (или против часовой стрелки), начиная от особой точки разворота. Затем вы повторяете простые шаги цикла каждый раз, проверяя, поворачиваете ли вы влево или вправо, добавляя новые точки к выпуклой оболочке, эта проверка основана на перекрестном продукте, как и в приведенной выше функции сравнения.
Edit:
добавлен еще один оператор 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 должно быть истинным. Я решил, однако, оставить код как есть ради простоты. Вполне возможно, что компилятор оптимизирует код и в любом случае даст тот же результат.
то, что вы просите-это система, известная как полярные координаты. Преобразование декартовых координат в полярные легко выполняется на любом языке. Формулы можно найти в в этом разделе.
Я не знаю Луа, но на этой странице предлагает фрагменты кода для этого преобразования.
после преобразования в полярные координаты, просто на угол тета.
интересным альтернативным подходом к вашей проблеме было бы найти приблизительный минимум к проблеме коммивояжера (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наслаждайтесь.
Comments