Учитывая массив точек 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
ipairs(tbl)которая перебирает индексы и значения tbl от 1 до #tbl. Таким образом, для расчета суммы вы можете сделать это, что большинство людей считает чище:for _, p in ipairs(points) do pointsSum.x = pointsSum.x + p.x; pointsSum.y = pointsSum.y + p.y endipairsзначительно медленнее, чем числовой для цикла.Ответы:
Сначала вычислите центральную точку. Затем сортируйте точки, используя любой алгоритм сортировки, который вам нравится, но используйте специальную процедуру сравнения, чтобы определить, меньше ли одна точка, чем другая.
Вы можете проверить, находится ли одна точка (а) слева или справа от другой (б) относительно центра, с помощью простого вычисления:
если результат равен нулю, то они находятся на одной линии от центра, если он положительный или отрицательный, то он находится на одной или другой стороне, поэтому одна точка будет предшествовать другой. Используя его, вы можете построить отношение меньше чем, чтобы сравнить точки и определить порядок, в котором они должны появляться в отсортированном массиве. Но вы должны определить, где находится начало этого порядка, я имею в виду, какой угол будет начальным (например, положительная половина оси X).
Код для функции сравнения может выглядеть так:
Это упорядочит точки по часовой стрелке, начиная с 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 должно быть истинным. Однако я решил оставить код таким, какой он есть, ради простоты. Вполне возможно, что компилятор все равно оптимизирует код и даст тот же результат.источник
atan(), нет квадратного корня и даже нет делений. Это хороший пример мышления компьютерной графики. Отберите все простые случаи как можно скорее, и даже в сложных случаях рассчитайте как можно меньше, чтобы узнать требуемый ответ.Интересным альтернативным подходом к вашей проблеме было бы найти приблизительный минимум для задачи коммивояжера (TSP), т.е. кратчайший маршрут, связывающий все ваши точки. Если ваши точки образуют выпуклую форму, это должно быть правильным решением, в противном случае они все равно должны хорошо выглядеть («сплошная» форма может быть определена как форма с низким отношением периметр / площадь, что мы и оптимизируем здесь) ,
Вы можете использовать любую реализацию оптимизатора для TSP, и я уверен, что вы сможете найти тонну на вашем языке.
источник
То, что вы просите, это система, известная как полярные координаты . Преобразование из декартовых в полярные координаты легко выполняется на любом языке. Формулы можно найти в этом разделе .
После преобразования в полярные координаты, просто отсортируйте по углу, тета.
источник
Другая версия (верните true, если a предшествует b в направлении против часовой стрелки):
Это быстрее, потому что компилятор (протестированный на Visual C ++ 2015) не генерирует переход для вычисления dax, day, dbx, dby. Вот выходная сборка от компилятора:
Наслаждаться.
источник
Наконец, вы получите Anticlockwize отсортированные верты
list.Reverse () .................. Clockwise_order
источник