Есть массив точек с координатами x, y.
Точки разбросаны хаотично, но если соединить каждую из них с ближайшими, то получим ломаную, с началом и концом, пример:
Задача: отсортировать точки от начала ломаной к концу (не важно, в каком направлении), либо (приоритетнее) составить массив ребер (с концами в известных вершинах) так же отсортированный по порядку от начала ломаной к концу.
То, что набыдлокодил я в состоянии невменяемости, выкладывать с вашего позволения не стану.
upd: Что я попробовал: перебираю точки в массиве, для выбранной точки (пусть будет 2), ищу двух ближайших соседов, добавляю новые ребра в массив: 2-4 и 2-5. При дальнейшем переборе ребра 4-2 и 5-2 отсеиваются как повторы. Но, для начала, ребер в некоторых случаях получится не 5, а 6-7, например для приведенного рисунка у точки 1 будет так же два ребра: 1-2 и 1-4, что неверно и нужна пост-обработка массива для отсеивания лишних ребер. А потом эти ребра еще и отсортировать нужно, пока не соображу как.
Ответ
Мне алгоритм решения задачи видится следующим образом:
Найти конец ломаной линии.
Конечную точку поместить в начало массива.
Использовать конечную точку как текущую.
Сравнить расстояния от текущей точки до всех остальных и найти ближайшую точку (если есть несколько точек с одинаковым расстоянием, равным минимальному, можно взять любую из них).
Переместить ближайшую точку в массиве, в позицию, следующую за текущей.
Использовать ближайшую точку как текущую.
Повторить пункты 4 - 7 для всех оставшихся точек
На выходе вы получите массив точек удовлетворяющий начальному условию.
UPD:
Поскольку в задаче не сказано, откуда должна начинаться ломаная линия, я бы предложил сначала найти геометрический центр скопления точек и использовать наиболее удаленную от центра точку как конечную.
Комментариев нет:
Отправить комментарий