@gizmo_zx

Как из массива отрезков построить дерево и посчитать длину пути?

Бодрого дня.
Имеется массив с координатами начала и конца отрезков.
Нужно построить дерево для подсчета пути к конечным точкам (для каждой точки отдельно)
Отрезки (ответвления) могут соединятся не только в конечных точках.
Пример:
60af4759471ab387639765.jpeg

Посчитать длину (по отрезкам) от 0 до 1 , и от 0 до 2.
Как из отрезков построить дерево, что бы посчитать по нему длину пути?
  • Вопрос задан
  • 84 просмотра
Пригласить эксперта
Ответы на вопрос 2
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
Сначала перенумеруйте все точки. Для этого заведите ассоциативный массив/сет/словарь, который по координатам возвращает номер точки. Пройдитесь по всем концам отрезков и добавляйте их туда с новым номером, если их там еще нет.

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

Для проверки принадлежности точки отрезку можно воспользоваться свойствами векторов. Точка C лежит на отрезке AB, если
1) векторное произведение <AB,AC> = 0
2) Скалярное произведение (AB,AC) > 0
3) Скалярное произведение (AB,AC) < |AB|^2 (длина отрезка в квадрате).

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

UPD, ах да... забыл про переходы внутри одного отрезка. Когда добавляете точки на отрезке, запоминайте все точки на нем. Потом добавьте ребра между каждой парой.
Ответ написан
Комментировать
Rsa97
@Rsa97
Для правильного вопроса надо знать половину ответа
Значит первым делом надо найти все точки ответвлений, то есть для каждого отрезка и каждой точки проверить, не лежит ли точка на отрезке. Если лежит, то разбить отрезок на два по этой точке.
Затем составить массив уникальных точек.
Потом преобразовать исходный массив к виду (индекс первой точки, индекс второй точки, длина).
Получаем обычный граф, путь в котором находится любым стандартном алгоритме.
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы