Сортировка массива точек, расположенных вдоль замкнутого контура.

#алгоритм #сортировка

Есть массив точек X{x,y}, образующих замкнутый гладкий контур (аэродинамический профиль).
Точки изначально расположены в массиве хаотично и неравномерно. Подскажите алгоритм
сортировки, позволяющий расположить точки по логическому порядку.

UPD. Лимит коментариев((. Точки на профиле расположены примерно так (в большинстве
случаев)



т.е. в местах с большим радиусом кривизны пореже и наоборот. Шаг точеки может быть
как маленьким, так и относительно большим. (@alexz) 
    

Ответы

Ответ 1

Или я неправильно понял условие или однозначного решения нет.
Например на приведеной ниже картинке точки можно расположить как минимум в 2-х разных
порядках:


UPD: если предположить, что профиль выпуклый, то можно просто найти выпуклую оболочку
множества (одним из алгоритмов из приведенных в конце статьи на Википедии), а затем
взять точки в том порядке, в котором они встречаются в выпуклой оболочке.


Ответ 2

По мне - для начала достаточно отсортировать по возрастанию координат. Например,
по x. Если будут точки с одинаковой координатой x - отсортировать их по y. Теперь если
их соединить получается ломаная. Зигзагообразная. А теперь нужно придумать как разбить
точки на два класса - на одну кривую аэродинамического профиля и на другую. Пока идеи
нет как это сделать.
Если фигура стабильно выпуклая - можно заюзать алгоритмы триангуляции. Они как раз
делают массив "ребер" на выходе, а затем уже можно выбрать среди них нужные.


Ответ 3

Находим центр. Точка с коорд x0 = средняя X всех точек, y0 аналогично. Вариант: (xmin+xmax)/2,
и y так же
Вычисляете угол между центром и точкой (центр в полярной системе координат) в диапазоне
 от 0 до 2pi (или -pi до pi)
Сортируете в нужном Вам порядке обхода


Но это только для выпуклых фигур.

Пример неправильного порядка при обходе против часовой стрелки (для вогнутого участка)
Профиль конечно от огурца, но тут уж увы.



Вот тут одна из проблем автоматического построения


Ответ 4

Берем произвольную точку.
Вычеркиваем из общего списка неразобранных точек, помещаем в выходной список.
Находим точку, которая ближе всего к исходной. Используем обычную декартовскую меру
расстояния.
Вычеркиваем ее из списка неразобранных, помещаем в выходной список.
Если есть еще неразобранные точки - идем к п.3.

По замечаниям и обсуждениям усисливаем позицию :-) :

Классический сплайн одной переменной строится так: область определения разбивается
на конечное число отрезков, на каждом из которых сплайн совпадает с некоторым алгебраическим
полиномом. Максимальная степень из использованных полиномов называется степенью сплайна.
Разность между степенью сплайна и получившейся гладкостью называется дефектом сплайна.
Например, непрерывная ломаная есть сплайн степени 1 и дефекта 1.

Если простая декартова мера оказывается недостаточной, можно воспользоваться старыми
добрыми сплайнами. Заметьте, не я усложняю задачу... строим сплайн для комбинаций из
4 ближайших точек и выбираем ту, для которой степень слайна оказывается минимальной.
Но начинать надо с одного из концов фигуры - чтобы мы сразу начали двигаться по одной
из долей - верхней или нижней.