I am working on geographical data which represents the road network of some city and I need to automatically fix inaccuracies in the data.Data was manually produced by drawing the road network over some actual map overlay with a geographical system like qgis.  As a result, many road portions which connect in reality are not connected in the data, that is, endpoints of connected roads might be off by a few centimeters or sometimes a few meters.As a result, the road network is wrongly digitized as a graph or combinatorial objectthat is, the simple algorithm assuming that roads are connected when they have a common endpoint is too optimistic and misses a lot of connections.  How can I process and fix the geographic data to recover the correct combinatorial road network?
How to canonise a road network
algorithms;graph;geospatial
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.WishlistWe want to build a procedure which, given the set M of missing or faulty connections,detects and fixes automatically a large subset A of Mdetects 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.AlgorithmThe 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  = 20mReplace 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.