Сначала вычислите центральную точку.
Затем сортируйте точки, используя любой алгоритм сортировки, который вам нравится, но используйте специальную процедуру сравнения, чтобы определить, меньше ли одна точка, чем другая.
Вы можете проверить, находится ли одна точка (а) слева или справа от другой (б) относительно центра, с помощью простого вычисления:
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 относятся к типу, который сможет содержать результат выполненных вычислений.
Если вы хотите добиться чего-то твердого, максимально выпуклого, тогда, я думаю, вы ищете Выпуклый корпус . Вы можете вычислить его, используя Graham Scan .
В этом алгоритме вы также должны отсортировать точки по часовой стрелке (или против часовой стрелки), начиная со специальной точки поворота. Затем вы повторяете простые шаги цикла каждый раз, проверяя, поворачиваете ли вы влево или вправо, добавляя новые точки к выпуклой оболочке, эта проверка основана на перекрестном произведении, как в приведенной выше функции сравнения.
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 должно быть истинным. Однако я решил оставить код таким, какой он есть, ради простоты. Вполне возможно, что компилятор все равно оптимизирует код и даст тот же результат.