An efficient algorithm for clipping operation based on trapezoidal meshes and sweep-line technique

摘要: This paper presents an efficient algorithm for clipping points, arcs and polygons, which is a common operation in geographic information system (GIS). By incorporating the sweep-line technique proposed algorithm, involved polygons are decomposed into collection of trapezoidal meshes. In this way, between to-be-clipped point, arc, polygon features subject transformed meshes, much easier to implement. Experimental results demonstrate that computational comparing existing methods, especially when input data contain large number polygons. addition, amount storage space required moderate. Furthermore, very flexible able handle concave those with holes.