Quad tree based algorithm for building of network model from road layers of vector maps

Modeling of a graph corresponding to transport network from vector layers of a digital map is essential to carry out any sort of network analysis operations. In vector maps, feature objects in road layers are generally modeled as simple features which do not capture the connectivity information. This paper proposes a method for building a network/graph model from such road layers of a vector map. In this work a quad tree based algorithm for building of network is proposed, which offers a linear time complexity whereas the trivial method is quadratic in order of complexity.