Retrieving the Topology from the Road Network (.NET)

Question

We have several high quality road networks available from several sources (Open Street Map, TomTom ...). These sources contain more information than we need, effectively blocking our calculations. Filtering out minor roads is easy. Our main problems are the representation of highways (two roads in opposite directions), complex crossings on the highway (various exit routes, crossings are not points). For our purposes, a more “topological” road network would be ideal.

Very detailed data source:

Ideal simplified network:

Are there any algorithms that will help us extract a simplified road network? If .NET even has an implementation, it will be a real winner.

UPDATE:

The source data is presented as polylines with some limited metadata attached. The metadata indicates the identification of the road (name or number), the "rank" of the road (highway, primary, secondary, etc.), as well as some details, such as speed limits, whether it is a section of the line — a bridge or tunnel. The data quality is very good, we can easily combine the segments of the polyline, which together form a road based on the identification of the road. Similarly, it is very easy to ignore secondary roads. Accelerated / decelerated lanes on the highway exit are also clearly marked in their rank, so they are also easily filtered.

We see two main problems:

1) Highways: replace two (or more) roads with one road

2) Crossings on the highway: determine the central point of junctions and make sure that our simplified roads are connected with this.

UPDATE 2: Data is stored in EZRI Shape files . Using the SharpMap library , they are relatively easy to parse or perform geospatial searches. The source data is segmented by country, one country - one form file (if the country is too large, like the USA, Germany), it is further divided into smaller regions. And yes, this separation causes an additional problem. How to make sure that simplified roads on the border of France and Germany meet each other?

Thanx for attention

Answer 1

This is only a sketch of the solution, but:

• Determine the distance metric between the pairs of curves. The first thing that comes to mind is the area surrounded by two curves divided by their lengths. You can increase this with your metadata. The goal is to create a metric that gives you a short distance to pairs of roads that you consider to be similar, and large compared to those that you consider to be dissimilar.

• Now select the clustering algorithm and ask it to group the roads according to the distance that you just determined. Be very generous with the number of clusters that you allowed him to use. When he returns, find clusters with a very low "diameter", which means that every point in the cluster is very similar to everyone else. A “complete clustering of relationships” is probably a good place to start your research, as it leads to just such a cluster.

• Then you can take the average value in each of these clusters to turn collections of very similar roads into one road, solving your problem (1) (and hopefully (2) too).

So, the next task is to distinguish "important" roads from "non-essential" roads. The best approach here would be to sit down and build a training set of several hundred random roads, manually marking them whether they are important or not. Then take a classifier of some type and train them in your manual set. Then ask him to predict what other roads are important.

I can’t say which classifier is best used, but if you can save time creating a large set of training materials and studying literature, "neural networks" can give impressive results. If you want something simpler, look at “random forests” or (even easier) “logistic regression”.