4

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

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

1 ответ 1

1

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

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

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

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