Добрый день, может кто подскажет алгоритм сбора ломаных из набора отрезков? Дано: список отрезков с указанием на две точки, из набора надо собрать какое-то количество ломаных (чаще всего замкнутые) по совпадению у двух отрезков двух точек. Может как-то надо модифицировать добавление отрезков в список для облегчения задачи? Единственное что я представляю: выбирать отрезок из списка и добавлять в текущую кривую, потом для всех оставшихся отрезков из списка искать следующий по совпадению с одной из точек, если не найдено, то добавлять новую кривую для первого отрезка из оставшегося списка. Но многовато операций, есть что-то лучше?
-
1На первый взгляд, только поиск ускорить, сделав хэш-таблицу по точкам отрезков с разрешением коллизий цепочками. Там хранить пары (точка, адрес-отрезка-в-списке). А отрезки в списке помечать номером кривой (это чтобы не зациклиться). Сходу, как-то так.– avp22 мая 2012 в 8:39
-
Я бы наверное наборы отсортировал, что сократило бы перебор до соседних элементов– Чад25 мая 2012 в 20:01
1 ответ
Создаем по отрезкам матрицу смежности. В цикле по вершинам определяем к какой компоненте графа относится каждая вершина, совершая обход для каждой из ранее не пройденных вершин. Тут решение.
Оптимальность здесь на ваш вкус. Можно вероятно и оптимальнее, но без обхода никак, и без поиска вершин среди других отрезков тоже. имхо, годный вариант.