范华燃-杨杰-李晨辉-罗宗铭-刘强1

任意多边形裁剪算法研究

范华燃, 刘强, 罗宗铭, 李辰辉, 杨杰

(成都理工大学, 空间信息技术系)

摘要:多边形裁剪算法被广泛应用于空间叠置分析、图像处理等各个领域，具有非常大的价

值和研究意义。在多边形裁剪的诸多算法中，主要有 Sutherland-Hodman 算法,梁友栋-Braian

算法等，但是这些算法在裁剪多边形后均不能消除多余边和边的自身相交。梁－Braian 算法针

对这一问题作了解决，但该算法需作很多的乘除法，不利于计算机内部实现。因此本文主要学习

研究了一种基于出入点判断的任意多边形裁剪算法，即 Weiler-Atherton 裁剪算法，该算法利于

快速简洁、计算机实现，且具有一般性。

clipping Sutherland - Hodman algorithm, main Liang Youdong - Braian algorithm, etc., but these

algorithms are not eliminate redundant after cutting polygon edge and the edge of the intersection.

Beam - Braian algorithm to solve the problem in order to solve this problem, but the algorithm requires

a lot of, method, is not conducive to internal computer implementation. So this paper mainly studies a

kind of arbitrary polygon clipping algorithm based on the access point judgement, namely Weiler

Atherton - cutting algorithm, the algorithm for fast computer .

Keywords: Polygon clipping、vector、Arbitrary polygon、Time complexity

1 引言

原有的多边形裁剪算法，例如 Sutherland-Hodman 算法，梁友栋－-Braian 算法，在裁剪多

边形后均不能消除多余边和边的自身相交。Weiler-Atherton 裁剪算法基于上述问题提出了一种

从被裁剪多边形离开裁剪窗口的交点，称为“出点”。

算法从被裁剪多边形的一个入点开始，碰到入点，沿着被裁剪多边形按顺时针方向搜集顶点

序列；而当遇到出点时，则沿着裁剪窗口按顺时针方向搜集顶点序列。

按上述规则，如此交替地沿着两个多边形的边线行进，直到回到起始点。这时，收集到的全