RaPC:A Rasterization-based Polygon Clipping Algorithm and Its Error Analysis
Fan Junf · DOAJ (DOAJ: Directory of Open Access Journals) · 2015
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.