Добрый день, может кто подскажет алгоритм сбора ломаных из набора отрезков? Дано: список отрезков с указанием на две точки, из набора надо собрать какое-то количество ломаных (чаще всего замкнутые) по совпадению у двух отрезков двух точек. Может как-то надо модифицировать добавление отрезков в список для облегчения задачи? Единственное что я представляю: выбирать отрезок из списка и добавлять в текущую кривую, потом для всех оставшихся отрезков из списка искать следующий по совпадению с одной из точек, если не найдено, то добавлять новую кривую для первого отрезка из оставшегося списка. Но многовато операций, есть что-то лучше?
Ответ
Создаем по отрезкам матрицу смежности. В цикле по вершинам определяем к какой компоненте графа относится каждая вершина, совершая обход для каждой из ранее не пройденных вершин. Тут решение. Оптимальность здесь на ваш вкус. Можно вероятно и оптимальнее, но без обхода никак, и без поиска вершин среди других отрезков тоже. имхо, годный вариант.
Комментариев нет:
Отправить комментарий