4

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

2
  • 1
    На первый взгляд, только поиск ускорить, сделав хэш-таблицу по точкам отрезков с разрешением коллизий цепочками. Там хранить пары (точка, адрес-отрезка-в-списке). А отрезки в списке помечать номером кривой (это чтобы не зациклиться). Сходу, как-то так.
    – avp
    22 мая 2012 в 8:39
  • Я бы наверное наборы отсортировал, что сократило бы перебор до соседних элементов
    – Чад
    25 мая 2012 в 20:01

1 ответ 1

1

Создаем по отрезкам матрицу смежности. В цикле по вершинам определяем к какой компоненте графа относится каждая вершина, совершая обход для каждой из ранее не пройденных вершин. Тут решение.

Оптимальность здесь на ваш вкус. Можно вероятно и оптимальнее, но без обхода никак, и без поиска вершин среди других отрезков тоже. имхо, годный вариант.

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.