[GIS] How to find all intersections and count lines arriving at each intersection

intersectionpyqgisqgis

I'm having a hard time getting off the ground with this, and am trying to move away from ArcGIS / arcpy.

I have a shapefile with a network of polylines. I want to find/count all 2-way intersections, 3-way intersections, 4-way, etc. This would involve, I think:

  • splitting all lines at intersections

  • deleting identical segments (with some spatial tolerance)

  • create points at the end of each new line segment

  • buffer the line ends, and count the number of points near/at each line end

I would like to do this in a python script. Is this overall plan easily implementable in pyQGIS? An outline of the calls I would be using would be very helpful.

Best Answer

There are a number of ways to approach this and several different ready-to-go python modules at your disposal. However I cannot directly comment on the Qgis calls but am confident most if not all of these processes are available and documents in the API: http://docs.qgis.org/1.8/html/en/docs/user_manual/index.html

Going in order of your requests:

> splitting all lines at intersections

You can first test to see which lines intersect and then find the intersecting points between any two lines.

There is an excellent example of how to do this in python on compiledreams.com:

Part 1) Testing for line intersection Part 2) Finding the point of intersection

Alternatively you can use the python module Shapely that offers a robust set of geometric relationship methods including intersection. Fiona was also written to work very nicely with shapely and can provide a means of data-structure translation (assuming you will be using a friendly GDAL/ORG format)

Qgis does offer similar capabilities but depending on the size of the dataset could be rather time consuming.

> deleting identical segments (with some spatial tolerance)

I am not sure where you would be getting identical segments from because you are essentially breaking a line feature at the point and making what was one two separate line features.

> create points at the end of each new line segment

So if we break a line a = [(2,0),(2,1),(2,2),(2,3)] at the intersection point of line b = [(0,2),(1,2),(2,2),(3,2)] we would get a1 = [(2,0),(2,1),(2,2)] and a2 = [(2,2),(2,3)] as the return. There is no duplicated geometries and the endpoints of the lines would be the first and last vertices's in the array. So for a1 it would have endpoints e1 = (2,0) and e2 = (2,2).

>buffer the line ends, and count the number of points near/at each line

So again shapely offers a very easy method to do this by any number of units you choose (same units as the input data is in).

Alternatively, you would define a radius around each point and create a separate polygon feature that acts as the buffer. [I am going to forgo writing out the algorithm here because I doubt that this is what you really want to do].

Then you would test to see which points fall within the buffer polygon while keeping a simple count.

Similar to the testing if lines intersect example above you can test if a point is within a polygon using an algorithm like the one defined here: http://www.ariel.com.au/a/python-point-int-poly.html

You can however just find all of the intersection points within a certain distance of any given intersection with some threshold distance. This would also save the need to create buffer polygons and performing various tests.

Without knowing much about your specific end goal you can also treat the network of polylines just as that by treating it as a network graph. This could simplify the whole process by using Networkx, which also lets you read in shapefiles. Although the topological relationships between the line features must be accurate already (meaning having already broke lines at intersection points). The counting of intersections is then just a matter of calculating the network statistic of "degree", which again is a simple method call in Networkx.