An Efficient Algorithm for Polygon Clipping
一个有效的多边形裁剪算法

Polygon clipping is more often used than line clipping in practice, so it is the main subject in clipping research now. An efficient algorithm for polygon clipping which processes general polygons including concave polygons and polygons with holes inside is presented in this paper. This algorithm can be used to calculate not only intersection (clipping) but also set-theoretic differences and union of two polygons. It is based on some new techniques proposed in this paper. Firstly, singly linked lists are used as the data structure of this algorithm rather than doubly linked lists or trees as other algorithms use, so less memory space and running time are required. Secondly, the relationship between the entry and exit points on the two polygons is found, which, with the reasonable operations on the lists, reduces the times that the lists are traversed and allows the polygon to be input clockwise or counterclockwise. Lastly, finding and computing of intersection points is a main procedure. An efficient technique for finding and computing intersection points is presented, which makes the speed of the algorithm higher. At the end of this paper, the new algorithm is compared with the existing algorithms and the result shows that it uses less memory space and has higher speed than others.