Grid Pattern Extraction in Road Networks with Graph

Pattern recognition of road networks plays an important role in map generalization,data matching and spatial analysis.A grid is characterized by a set of mostly parallel lines,which are crossed by a second set of parallel lines with roughly right angle.We propose a method for extracting the grid pattern based on graph theory.First,relation graphs of roads are created,in which the vertices represent road segments and the edges represent the roads' relation.Then grid pattern is extracted via some graph-theoretic operators such as finding connected component,creating maximal complete sub-graph,join and intersection.Experimental results show that the proposed method is valid in extracting the grid pattern.Advantages and limitations are discussed.