Automated extraction of road network from points

Question

I have a huge dataset containing about zillion of points representing tracking locations of cars on the roads.

I also have roads datasets to compare to (from 3 different sources), to use for training machine learning models. Preferably using PyTorch or Tensorflow. Ideally re-using some existing model.

How to generate the road network, as automated as possible, using the point dataset representing tracking of these roads?

Note: The goal is NOT to snap points to existing roads, I know how to do that easily. The goal is to automatically generate reasonably good road network from points. Any research article or example related to automated network creation from points is welcome.

Example of points (red color at 10% opacity), and existing tracks over it (yellow dotted line):

Answer 1

If you have your data in postgis then you could use st_reduceprecision or st_snap_to_grid function and take only uniques geometries. This allows you to drastically minimize count of your points. In second step I would create vector grid. Size of grid cell should depend on distance between points you will regard as separate track. The bigger the cell the more generalized network. For points in every grid cell I would calculate st_geometric_median. After this you have only one point in grid cell, not necessarily in the center of cell which is good because you don't want to have 90 degrees angles in you network. The last step is to connect the dots to its nearest neighbours.

This was the vector solution. It maybe could be better to go raster solution if you have zylion points. First you have to make raster from your data. I would use gdal_rasterize. Then, on such raster, you could make dense contour lines (isolines) using gdal_contour and at the end choose one of isolines as your road. Maybe you could search in grass algorithms, there are tons of them, but I'm not familiar with it.

Your task is rather challenging thus there won't be simple answer.

Answer 2

I would not recommend any basic point rasterization approaches if you want to generate a routable road network. You'll have to handle the car trajectories to learn the turning possibilities at intersections and to distinguish between real intersections vs. bridge or underpass situations.

There are lots of papers on this topic, e.g.

• Cao, L., & Krumm, J. (2009, November). From GPS traces to a routable road map. In Proceedings of the 17th ACM SIGSPATIAL international conference on advances in geographic information systems (pp. 3-12).

but nothing has been integrated into GIS tools afaik.

Answer 3

Not tried this, just thinking off the top of my head. How about using the point density tool in Arcmap, to create a raster, then threshold that, for example you decide a density of 10 points or greater is a road, everything else becomes no data. Then use the raster to polyline tool. Not sure how this would work when comparing highways with single tracks? You will probably want to use the Thin tool before the final conversion to a polyline dataset. The Thin tool tends to create spurs which need editing out and gaps closed. So a lot of work...

Changing the cell size of your density raster will influence what gets generated.

Answer 4

Conceptually you could turn each string of points into a line and then merge adjacent lines. Points to Line could be used for the first step. Not sure technically how to accomplish the second step - maybe something along the lines of identifying similar lines as is discussed in this post?