GIS矩形网格中任意多边形裁剪算法

An Algorithm of Clipping General Polygons in Rectangle Grids of GIS

从提高任意多边形裁剪效能的要求出发,提出以矩形网格来裁剪任意多边形的思想,该算法省去传统裁剪方式中一些重复运算步骤和数据访问、直线求交的工作量,同时也考虑了节省内存的需求,裁剪性能比传统的逐一单元格裁剪方式有所提高.

The application of general clipping algorithm occurs frequently in geographical information systems （GIS）, which is designed usually as general polygon clipping against single general or rectangle polygon. And the high-performance computer and long-time running of program are the common solutions for pretreatment of huge spatial data in GIS, also in this condition the pretreatment program needs validate, low-memory usage and low-CPU requiring clipping algorithm. An algbrithm of clipping general polygon in rectangle grids in GIS is presented in this paper, which is designed for the demand of improving clipping general polygon performance. This algorithm has skipped some repeated operation and some workload of reading raw data and computing intersection point between lines, at one time, it considers the requirement of saving memory. According to the result of algorithm analysis and experiment, it is valid and has better performance in the aspects of memory application, total memory, reading times of spatial data, computing times of intersection points, etc, so the total clipping time of this algorithm is less than common clipping algorithm in GIS, which clips polygon cell by cell in grids.