python – Getting Lines and Nodes Around the Confluence Point in a Network System (Line Shapefile)

Question

I got a network line shapefile and the figure below was part of it. I want to do task around confluence point, so I took photo around confluence point as figure below.

I want to get line segments (unique geometry of line) and nodes (coordinates of node) around every confluence point in the shapefile, as the schematic figure below (closer look of figure above).

Now I use QGIS and manually select those segments and store node coordinates (via extract node) in CSV files. Because the network is too complicated and has many confluences, I want to do this in a much more efficient way.

The Idea
I think that maybe I could scan the whole network to find every confluence by finding node with more than 2 intersecting lines, and get set of line segments (in figure above, lines = line1, line2, line3) and nodes on the other side of the segment. (in the figure above, nodes = node1, node2, node3) (To be more specific, segment here means the line with detail in every row of attribute table of this line shapefile, not the little segment showed as I start editting.) Each confluence has its specific set, and in the case above, the set is:

geom of line1, coordinates of node1
geom of line2, coordinates of node2
geom of line3, coordinates of node3

How can I get the line segment and its node around the confluence point (auto-determine-and-find) in a network-like line shapefile?

And as I described in the paragraph above, because line shapefile I got is complicated, there could be many confluence points, thus I want found lines and nodes could be grouped in the same set based on the confluence points which they intersected.

I don't know if my idea works and what function or tool could help me to achieve my goal. I want to achieve this via open-sources, and ultimately write a integrated python function to get those lines and nodes.

Answer 1

You work here with a Graph (Graph Theory) and your confluence point is simply a node with a degree (number of edges adjacent to that node) > 2.

As you mentioned a Python tag, a solution in Python with Fiona (for reading the shapefile) and NetworkX (Graph Theory)

The Polylines

Open the shapefile and convert all the segments of the Polylines in egdes of a Graph

import fiona
import networkx as nx
import itertools # for extracting all the line segments
# creation of an undirected Graph
G = nx.Graph()
for line in fiona.open("lines.shp"):
   # convert the line segments to Graph edges
   for seg_start, seg_end in itertools.izip(line['geometry']['coordinates'],line['geometry']['coordinates'][1:]):
       G.add_edge(seg_start, seg_end)

The Graph with Nodes(x) and edges

Now, in NetworkX, the degrees of a node are obtained by degree (I use Shapely here but you can save the resulting shapefiles with Fiona and even Networkx)

from shapely.geometry import Point, LineString
for node in G.nodes_iter():
    if G.degree(node) > 2:
        print Point(node) #the nodes
        for edge in G.edges(node):
            print LineString(edge) # the edges (>2)

Result

You can translate easily the Fiona solution in PyQGIS.