How to build a tree from an array of segments and calculate the length of the path?

Question

Algorithms

Cheerful day.
There is an array with the coordinates of the beginning and end of the segments.
You need to build a tree to count the path to the end points (for each point separately)
Segments (branches) can be connected not only at the end points.
Example:


Calculate the length (by segments) from 0 to 1, and from 0 to 2.
How to build a tree from segments to calculate the length of the path along it?

Answer 1

First renumber all points. To do this, create an associative array/set/dictionary that returns the point number by coordinates. Go through all the ends of the segments and add them there with a new number if they are not already there.
Next, build a graph. Vertices - all unique points from the dictionary. Add edges between the ends of all line segments. Further, I understand that if the end of the segment lies on another segment, then you can jump back and forth. In this case, you need to iterate over all segments and all points, and if the point lies inside the segment, then add edges between it and the ends of the segment.
To check whether a point belongs to a segment, you can use the properties of vectors. Point C lies on segment AB if
1) vector product <AB,AC> = 0
2) Dot product(AB,AC) > 0
3) Dot product (AB,AC) < |AB|^2(length of the segment squared).
Next, here you have built a graph. Run any algorithm for finding paths from the starting point in it. If the length of the path is considered as the physical length of the segments, then Dijkstra's algorithm is needed (and when you add edges, count their lengths as distances between points). If your length is the number of segments passed, then breadth-first search will do.
UPD, oh yes... I forgot about the transitions within one segment. When you add points on a line, remember all the points on it. Then add edges between each pair.

Answer 2

This means that the first step is to find all the branch points, that is, for each segment and each point, check whether the point lies on the segment. If lies, then split the segment into two by this point.
Then make an array of unique points.
Then convert the original array to the form (index of the first point, index of the second point, length).
We get a regular graph, the path in which is found by any standard algorithm.