RaPC:A Rasterization-based Polygon Clipping Algorithm and Its Error Analysis

Acta Geodaetica et Cartographica Sinica

ZHOU Yuke¹  FAN Junfu²  MA Ting²  ZHOU Chenghu³  JI Min³  KONG Weihua³ 

[1] College of Geomatics, Shandong University of Science and Technology, Qingdao 266590, China;School of Civil and Architectural Engineering, Shandong University of Technology, Zibo 255049, China;State Key Laboratory of Resources and Environmental Information System, Institute of Geographic and Nature Resources Research, Chinese Academy of Sciences, Beijing 100101, China;

关键词: rasterization;    polygon clipping;    point in polygon;    winding and tracing;    area error;   

DOI  :  10.11947/j.AGCS.2015.20140017

来源: DOAJ

【 摘 要 】

Computational efficiencies of traditional vector computing-based polygon clipping algorithms will decrease rapidly when handling polygons contain large amount of vertices. The computing flows of traditional polygon clipping algorithms are tightly coupled with special data structures, which difficult to be optimized in the underlying of them. Under the premise of meeting a certain degree of area errors, the polygon clipping problem can be solved by introducing the idea of rasterization processing. In this research, we proposed a new rasterization processing-based polygon clipping algorithm: the RaPC algorithm, on the basis of analyzing the characteristics of existing algorithms. The area errors of results of the new algorithm are also analyzed and discussed. Experimental results show that the efficiencies of the RaPC algorithm can be enhanced significantly when using large grid cells, and it shows a linear trend growth with the increase of amount of polygon vertices. Compared with the Vatti algorithm, the RaPC algorithm represents more efficiencies on dealing clipping issues between polygons with large amount of vertices, the former shows lower time costs when handling polygons with less vertices. The area error of computing results of the RaPC algorithm is closely related with the grid size, and errors can be reduced using smaller grid sizes. Therefore the RaPC algorithm showed higher efficiencies on processing polygons with large amount of vertices than the Vatti algorithm and presented practical values to some degree.

【 授权许可】

Unknown