An Efficient GIS Algorithm for Detecting Topological Polygonal Chains

摘要

An efficient algorithm named Redundant Edges Backtracking Algorithm (REBA) is proposed for detecting topological polygonal chains and its advantages in time performance is analyzed and validated. Using the nesting relationship between redundant edges and polygonal chains in left-turning loops, the proposed algorithm, which solved the problem existing in available algorithms of failing to identified redundant edges whe next racting polygonal chains, needs only one left-turning calculation for each directed edge in the whole process of extracting polygonal chains and identifying redundant edges. Algorithm analysis and experiment results show that the time complexity of REBA is O(ε~2/N) and close to O(ε) in practical applications.