An Efficient GIS Algorithm for Detecting Topological Polygonal Chains

DOI

10.2991/iccita-16.2016.54How to use a DOI?

Keywords

Left-turning loop, Redundant edges, Polygonal chains, Nesting relationship, Backtracking algorithm.

Abstract

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 when extracting 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 and close to in practical applications.

Copyright

© 2016, the Authors. Published by Atlantis Press.

Open Access

This is an open access article distributed under the CC BY-NC license (http://creativecommons.org/licenses/by-nc/4.0/).

Download article (PDF)

TY  - CONF
AU  - Yonghong Qiu
AU  - Yongnian Zeng
AU  - Guoqing Sun
PY  - 2016/05
DA  - 2016/05
TI  - An Efficient GIS Algorithm for Detecting Topological Polygonal Chains
BT  - Proceedings of the 2016 International Conference on Computer and Information Technology Applications
PB  - Atlantis Press
SP  - 293
EP  - 298
SN  - 2352-538X
UR  - https://doi.org/10.2991/iccita-16.2016.54
DO  - 10.2991/iccita-16.2016.54
ID  - Qiu2016/05
ER  -