关键词: 等值线, 包围盒, 链式结构, 行扫描, 线段求交

Abstract: This paper presents a new fast algorithm for contour clipping against general complex polygon windows. The new algorithm builds the bounding box of the clipping polygons and creates the grid structure. And the algorithm uses the grid structure to pre-clip the contours quickly. Through linked structure to clip the contours, it could get the final clipping result. This paper can realize the method of row scanning to judge the inside and outside attribute by building the linked structure and reduce the counts of segments intersection. Through many experiments, the new algorithm is proved to be very effective and stable. Additionally, the algorithm can resolve various special cases which contain complex nested polygons and overcome the constraint conditions presented by previous algorithms. The algorithm can be implemented by programs easily, and can accord with requirements of the project.

Key words: contours, bounding box, linked structure, row scanning, segments intersection