2

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 object—that 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?

1
  • 3
    The question is devoid of meaning without specifying your costs of both types of error. The usual algorithm is set a threshold, find nodes within this distance from each other, check for false positives, merge, rinse, repeat. Jun 2, 2014 at 9:06

1 Answer 1

1
+250

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,

  1. detects and fixes automatically a large subset A of M
  2. 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.

  1. Choose two thresholds α = 2.5m and β = 20m

  2. 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.

  3. 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 β”.

  4. 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.

  5. 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.

2
  • I think you're saying what DeerHunter said in his comment...
    – gbjbaanb
    Jul 15, 2014 at 14:08
  • 1
    @gbjbaanb What do you mean? I provided more details than DeerHunter did: I kind of specified error costs, suggested concrete values for thresholds based on concrete experience in the field and described carefully a concrete algorithm. But if you neglect all these differences, yes the answers are the same! Jul 15, 2014 at 15:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.