Страницы

Поиск по вопросам

воскресенье, 12 мая 2019 г.

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

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


Ответ

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

Комментариев нет:

Отправить комментарий