fttx network design in QGIS: how to calculate distance to network backbone or another connected node, whichever is closer

Question

I have a KML file of a fiber regional network (covers 2 US States) and a geocoded list of ~500 building addresses (nodes). I'd like to calculate two numbers for every address:

1. The distance back to the network backbone
2. The distance to the next closest point on a hypothetical "extended network" (if it's a shorter distance than the distance to the backbone)

By "extended network" I mean that if I were to build the "last mile" of fiber from the network backbone out to the closest address (lets call it building A) and another building is slightly further away from the network in the same direction (building B), then I would not want to build redundant network from building B all the way back to the backbone. I would build from the backbone to building A and then continue to building B.

I'm able to get the first calculation just using the "shortest line between features" tool (nodes are green, network is pink, shortest lines are orange):

What I'm looking for to get my second number is something like this (my own rough drawing connecting the nodes in blue):

I then want to calculate the distance of each incremental span that would need to be built to connect to the broader network for each node. So for the red dot, my distance calculation would be the red line:

I believe that what I am looking for is akin to a minimum spanning tree but I think I am having trouble finding the shortest distances out to the nodes if I assume I'm starting from the network (a linestring).

I've tried the v.net.spanningtree GRASS tool using the fiber network as my "Input Vector Line Layer" and my list of geocoded addresses as the "Input Point Layer". The result is a partial tracing of my network but the nodes are not connected.

I've also tried the Minimum Spanning Tree Plugin for QGIS but have not be able to get the plugin to actually run. I'm trying to use the same files as inputs but keep getting an error message that my inputs are invalid. I'm struggling to find tutorials for this issue online.

I may be going down the wrong rabbit hole with Minimum Spanning Trees so I'm all ears if there is a different way to accomplish this.

These calculations are just being used as rough approximations, hence why other barriers like roads are not being considered yet.

Answer 1

An algorithmic approach. Implementation in QGIS below - if you create it as model, you can re-run it to create the result automatically.

This is how the output looks like after the steps that follow below. I have two groups (clusters) of points (one above, the other below the line) that are treated separately. start: backbone (black line) and addresses (blue points); 1: connect the closest point of each groupt to the backbone; 2: connect all other points to nearest neighbour; [3: merge/dissolve lines]; 4: service area (yellow lines) from where the connection from the backbone to the nearest addresses start (orange points): it shows which lines/points are already connected to the backbone; 5: connect yet unconnected lines to the closest line (of the same cluster):

Algorithmic approach

This works also for different groups of points (clusters) separately as you can see in the screenshot above.

1. Calculate the distance of each point to the closest point on the line. Connect the point with the smallest distance to the line.

2. For all other points, connect them with the closest neighboring point. Use e.g. QGIS expressions/ Geometry by expression with function overlay_ nearest.

3. Combine lines from steps 1 and 2, dissolve the result and convert from multiparty to single parts.

4. Check if every point is reachable from the backbone over a network consisting of the lines from step 3. If so, you're done. If not, continue.

5. For each line A (from step 3) find the closest neighboring line B and on this B the point b closest to the current line A (QGIS expression with function closest_point). Find the point a on the current line A closest to point b and connect these points, thereby connecting line A to line B.

6. Repeat steps 3 to 5 until you're done (condition in step 4).

7. When done, merge the resulting lines and aggregate them based on the group the points belong to to get one line per point cluster.

---

Implementing it in QGIS

If needed, group clusters of points together that will be treated separately and create an attribute cluster_id, e.g. based on a dissolved buffer around addresses like here: https://gis.stackexchange.com/a/470630/88814

1. Create a new boolean attribute con_to_net at the point layer with this expression

    with_variable(
        'dist',
        'distance (
            geometry (get_feature_by_id(''point'', $id)),
            closest_point (
                overlay_nearest(''line'',$geometry)[0],
                $geometry
            )
        )',
        eval (@dist) = 
        array_min (
            array_agg (eval(@dist),group_by:=cluster_id)
        )
    )
   

   Then run Geoemtry by expression with this expression:

    case 
    when con_to_net is true
    then make_line (
        $geometry, 
        closest_point (
            overlay_nearest('line',$geometry)[0],
            $geometry
        )
    )
    end
   

2. On the point layer, run Geoemtry by expression with this expression:

    make_line (
        $geometry, 
        overlay_nearest('point', $geometry,limit:=-1)[1]
    )
   

3. use the respective QGIS tools:

   • Merge vector layers
   • Dissolve and be sure to check the box next to Keep disjoint features separate

4. Create the point where the backbone connects to the network linking the addresses with Geomtry by expression on the layer from steps 3/4 with this expression:

    centroid(
        intersection (
            $geometry, 
            overlay_nearest ('line',$geometry)[0]
        )
    )
   

   Run service area (from layer) with the network from step 4 and the start points created now.

5. Now you can use this service area that covers all points that are already connected to the backbone to create the additional lines of not yet connected points. Use Geometry by expression with this expression:

    case 
    when overlay_disjoint ('Service area (lines)')
    then make_line (
        closest_point (
            overlay_nearest('Dissolved',nodes_to_points($geometry),limit:=-1)[1],
            $geometry
        ),
        closest_point(
            nodes_to_points($geometry), 
            closest_point (
                overlay_nearest('Dissolved',nodes_to_points($geometry),limit:=-1)[1],
                $geometry
            )
        )
    )
    end
   

6. When done, merge the resulting line layers and aggregate them base on cluster_id to get one (multipart) line feature per group of points (cluster). Decide yourself if you want to convert Multipart to single parts.