Derivation of road network from land parcels

This paper presents an adapted algorithm to derive road network from land parcels based on skeleton operator. The spaces among the neighboring parcels are assumed to be occupied by roads. These potential roads are decomposed and approximated to generate road centerlines. The proposed algorithm minimizes unwanted artifacts by computing the negative minima curvature of the boundary. The algorithm includes three parts: 1) shape decomposition; 2) skeleton approximation; and 3) topology reconstruction. A pruning procedure is followed by the decomposition results, which can yield shared edges for neighboring sub-regions, so the direction of the centerline has been smoothed when it passes the shared edges. The straight skeleton (SS) algorithm can generate straight line, and the result is most reasonable for road network. Our proposed algorithm keeps the time complexity of straight skeleton algorithm, however, it partitions the target region into subregions where the skeletons have been computed in individual subregion instead of the whole region, and crossing patterns have been found and utilized to prune the results, hence it is not only much faster in practical computation, but also it is more suited to human perceptions. It can generate centerlines with correct topology in our cadastral test datasets from part of Barcelona. 97% of the decomposed region can get reasonable centerlines compared to a reference dataset, whereas 2% reveals incorrect reconstruction, and only 1% keep the original results from straight skeleton algorithm.