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

Question

[gizmo_zx]

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


Посчитать длину (по отрезкам) от 0 до 1 , и от 0 до 2.
Как из отрезков построить дерево, что бы посчитать по нему длину пути?

Comments

[Rsa97]

Как именно заданы отрезки? Скажем, для вашего примера.

[gizmo_zx]

координаты начала и конца , в 2Д
x1n, y1n, x1k, y1k
x2n, y2n, x2k, y2k
....
n - начало
к- конец

[Rsa97]

gizmo_zx, Для вашего примера сколько отрезков будет в массиве? Два, три, четыре?

[gizmo_zx]

Количество переменно.
Условно на каждый запуск программки свой массив.
Количество отрезков до 1000
Причем ветви могут пересекаться:
1-\/ -2
.. / \
/.......\
\------|----0
От 0 к 1 идем по правой ветви
От 0 к 2 идем по левой
Условно отрезки могут иметь общую точку в своей "середине"
А при ответвлении отрезок всегда лежит началом (или концом) на другом отрезке

[gizmo_zx]

[Rsa97]

gizmo_zx, На вашем примере пересечение красной и синей линий - это допустимая точка смены маршрута? В месте, где идёт ответвление, отрезок разбит точкой? Допустим ли следующий вариант?
(0, 0) - (0, 2)
(0, 1) - (1, 1)
Или же должно быть так?
(0, 0) - (0, 1)
(0, 1) - (0, 2)
(0, 1) - (1, 1)

[gizmo_zx]

На вашем примере пересечение красной и синей линий - это допустимая точка смены маршрута? Нет
В месте, где идёт ответвление, отрезок разбит точкой? Допустим ли следующий вариант? да, допустим
(0, 0) - (0, 2)
(0, 1) - (1, 1)

[Akina]

Ну так соберите все координаты (пофиг, начальные они или конечные), пронумеруйте всквозную, затем превратите отрезки в рёбра (а пронумерованные точки - это соответственно узлы) графа и решайте стандартную задачу поиска путей в графе.

Условно отрезки могут иметь общую точку в своей "середине"

Не понял... это что, при движении от точки 0 к точке 1 можно пойти "синим" путём, а потом в точке пересечения перескочить на "красный", что ли? тогда дополнительно следует найти все точки пересечений и включить их в граф как узлы.

А если нет - то какая разница, пересекаются отрезки визуально или нет?

Answer 1

[Wataru]

Сначала перенумеруйте все точки. Для этого заведите ассоциативный массив/сет/словарь, который по координатам возвращает номер точки. Пройдитесь по всем концам отрезков и добавляйте их туда с новым номером, если их там еще нет.

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

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

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

UPD, ах да... забыл про переходы внутри одного отрезка. Когда добавляете точки на отрезке, запоминайте все точки на нем. Потом добавьте ребра между каждой парой.

Answer 2

[Rsa97]

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