A New Algorithm for Polygon Intersection Operation

Author

Ya, Zhou

Author_Institution

Coll. of Geogr., Nanjing Normal Univ., Nanjing, China

Volume

1

fYear

2009

fDate

28-30 Dec. 2009

Firstpage

12

Lastpage

15

Abstract

Polygon Intersection is among the most fundamental operations in Computer Graphics, which is also broadly applied in GIS. The existing algorithms for polygon intersection may fail because of being specified ambiguously, or can not handling the concave polygons or those with holes. In this paper, introducing the concept of Monotone chain from Geometry, a rapid polygon intersection algorithm has been addressed. This algorithm could be adapted to any general polygons, with no need to process abnormal conditions; moreover, it could tolerate arithmetic errors. The algorithm has already been applied in GIS platform software, and proved of great stability and reliability.

Keywords

computational geometry; computer graphics; geographic information systems; GIS platform software; arithmetic errors; computer graphics; geometry; monotone chain; rapid polygon intersection operation algorithm; Algorithm design and analysis; Arithmetic; Cities and towns; Computational geometry; Computer graphics; Data structures; Educational institutions; Geographic Information Systems; Geography; Software algorithms; GIS; Monotone chain; Polygon intersection algorithm; Spatial analysis;

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.19

Filename

5380680