Automatic Calculation of Road Centerlines

I've been planning to use massive amount of traces to find automatically road center lines from the trace cloud. One useful toolset is libcgal which provides all what is necessary for triangulation and related tasks. It is also expected to have reasonable speed. The sketched process:

1. Input traces
2. Calculate alpha shape out of the gpx point cloud - Done (the shape looks blocky because of the used output accuracy):

   

3. Using the Delaunay triangulated gpx point area, identify road segments (from intersection to intersection bounded by the alpha shapes)
4. Extract relevant parts of the traces
5. (Optional) Calculate seed centerline from the segment edges if the next step needs initial centerline estimate (can be done with Voronoi Diagram trivially)
6. Calculate centerline, most likely discard first 10-50% as "outliers" and then take median or average of the rest.

Refinement ideas:

• Usually all carriages including cycleways and footways merge because of GPS inaccuracies. This is undesirable as then the centerline could depend on distribution of the traces among the carriages. Use more sophisticated analysis, ideas include:
  • Find out where the trace hot-spots (hot-lines really for ways) exist within a road segment
  • Some shape-finding would be nice to identify road crossings etc (e.g. 90deg,-90deg turns).
  • Follow traces for longer distance in-order to identify the mode of transport
  • Some filtering first + more restrictive alpha shapes
  • Possibly even trace relocation to fix its offset w.r.t. to an estimated centerline, and then retry alpha shapes.
• Differentiate based on direction