运用图论进行道路网网格模式提取

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. Experi- mental results show that the proposed method is valid in extracting the grid pattern. Advan- tages and limitations are discussed.