I had to perform the treatment you describe on the road network of German city (about 200.000 inhabitants). I devised a procedure that produced great results: the road network has over 2000 road portions and about 200 connection failures and the procedure was able to fix automatically 95% of the failures and to mark the remaining ones as “requiring attention”. There were so few of them that manual editing was affordable.
Let me now go into the details.
Wishlist
We want to build a procedure which, given the set M of missing or faulty connections,
- detects and fixes automatically a large subset A of M
- detects problematic places P in the network that require manual treatment.
We want to conduct step 1. without producing any false positive i.e. without introducing non-existant connections, i.e. enforcing the condition “A is a subset of M”.
We want to conduct step 2. so that all of M is in the union of A and P. It is fine to have false positives here, as long as the ratio ”false positive / true positive” remains low.
Algorithm
The input is a road network R, i.e. a list of road portions (broken lines) represented by the list of their vertices. (This is what is stored in ESRI files.)
The output is an amended road network S together with a list P of places (points) requiring manual treatment.
Choose two thresholds α = 2.5m and β = 20m
Replace R by an equivalent network where road portions can only cross at a vertex and where if two road portions have points whose distance is smaller than α then they have two vertices whose distance is smaller than α. This is achieved by introducing supplementary vertices in the descriptions of road portions.
Go through all the vertices of all the road portions of the road network and create equivalence classes for the relation A “vertices are closer than α” and B ”vertices are closer than β”.
To each equivalence class of A associate a point (e.g. center of mass) and replace each member of the class by that point. The result is the final network S.
To each equivalence class of B not reduced to a point associate a point (e.g. center of mass), the list of points thus obtained is P.