A Novel Algorithm for Union between Complex Polygons

Author

Cui Can ; Shen Dingtao ; Wu Wenzhou ; Wang Jiechen

Author_Institution

Dept. of Geographic Inf. Sci., Nanjing Univ., Nanjing, China

Volume

1

fYear

2009

fDate

28-30 Dec. 2009

Firstpage

8

Lastpage

11

Abstract

The union operation, one of the spatial analysis operations, plays an important role in the capability of GIS software. At present, many algorithms for this operation have been put forward; however, most of them have limitation on handling general polygons. In this paper, introducing the trapezoidal-mesh data structure and the split-and-merge technique, an efficient union algorithm has been ad-dressed, which is suitable for general polygons. The trapezoidal data structure is simple and the operations based on it are easily to be implemented. Being applied in GIS platform software, this algorithm has been proved of high efficiency and occupying less memory.

Keywords

computer graphics; geographic information systems; GIS software; spatial analysis operations; split-and-merge technique; trapezoidal-mesh data structure; union operation; Algorithm design and analysis; Computer graphics; Data structures; Geographic Information Systems; Information analysis; Information science; Performance analysis; Software algorithms; Software performance; Geographic information system; Polygon union operation; Split-Merge technique; Trapezoidal-mesh;

fLanguage

English

Publisher

ieee

Conference_Titel

Computer and Electrical Engineering, 2009. ICCEE '09. Second International Conference on

Conference_Location

Dubai

Print_ISBN

978-1-4244-5365-8

Electronic_ISBN

978-0-7695-3925-6

Type

conf

DOI

10.1109/ICCEE.2009.11

Filename

5380721