Сортировка точек ломаной линии на 2D плоскости

#массивы #сортировка #графы

Есть массив точек с координатами x, y.
Точки разбросаны хаотично, но если соединить каждую из них с ближайшими, то получим
ломаную, с началом и концом, пример:

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

То, что набыдлокодил я в состоянии невменяемости, выкладывать с вашего позволения
не стану.

upd: Что я попробовал: перебираю точки в массиве, для выбранной точки (пусть будет
2), ищу двух ближайших соседов, добавляю новые ребра в массив: 2-4 и 2-5. При дальнейшем
переборе ребра 4-2 и 5-2 отсеиваются как повторы. Но, для начала, ребер в некоторых
случаях получится не 5, а 6-7, например для приведенного рисунка у точки 1 будет так
же два ребра: 1-2 и 1-4, что неверно и нужна пост-обработка массива для отсеивания
лишних ребер. А потом эти ребра еще и отсортировать нужно, пока не соображу как.
    

Ответы

Ответ 1

Мне алгоритм решения задачи видится следующим образом:


Найти конец ломаной линии.
Конечную точку поместить в начало массива.
Использовать конечную точку как текущую.
Сравнить расстояния от текущей точки до всех остальных и найти ближайшую точку (если
есть несколько точек с одинаковым расстоянием, равным минимальному, можно взять любую
из них).
Переместить ближайшую точку в массиве, в позицию, следующую за текущей.
Использовать ближайшую точку как текущую.
Повторить пункты 4 - 7 для всех оставшихся точек


На выходе вы получите массив точек удовлетворяющий начальному условию.

UPD:

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


Ответ 2

Для начала определяете начальную точку (я так понимаю это будет точка с минимальными
координатам)
Далее от неё ищете ближайшую (для простоты перебором из оставшихся точек)
Исключаете точку
Повторяете пункт 2 пока есть точки


Можно ещё предварительно отсортировать точки по расстоянию к первой, тогда можно
сократить перебор оставшихся точек исходя из этой метрики. Правда, скорее всего на
каждом шаге эту метрику надо будет корректировать, надо тут подумать.

Для других алгоритмов, на мой взгляд, необходимы уточнения:


Критерий начальной точки
Ближайшая точка - это модуль вектора (длинна ребра) или ближайшая по оси X например?
Как правильно соединить такой набор точек: