大规模等值线图的任意简单多边形窗口裁剪算法
小型微型计算机系统Journal of Chinese Computer Systems 2011年10月第10期Vol. 32No．102011
大规模等值线图的任意简单多边形窗口裁剪算法
李
12
1，212楠，吴信才，肖克炎
（中国地质大学（北京）地球科学与资源学院，北京100083）（中国地质科学院矿产资源研究所区划室，北京100037）
E-mail ：superln1980@yahoo．com．cn
摘
要：针对大规模等值线图裁剪算法面临的两个主要问题，如何减少线段求交次数和判别保留部分的起止点，提出一种针对大规模等值线图的任意多边形裁剪算法．该算法首先使用等网格分割方法，在等值线线段与裁剪多边形边之间建立网格索引，
减少线段求交次数；同时，在网格数据结构基础上，采用局部射线法，很好地解决了判断交点在裁剪多边形内外时间复杂度过大的问题，使得算法可以快速判断出需要保留（剔除）的等值线部分．本文算法的优点是能够在求出交点的基础上快速获得需要算法中裁剪多边形可以是包含任意多个洞的任意简单多边形，克服传统算法中对裁剪多边形保留（剔除）部分的起止点；同时，
的特定约束条件．本文算法易于实现且高效．关键词：局部拓扑；裁剪；线段求交中图分类号：TP391文献标识码：A
1220（2011）10-2068-06文章编号：1000-
Algorithm for Massive Contours Clipping Against General Polygon Window
2LI Nan 1，，WU Xin-cai 1，XIAO Ke-yan 212
（School of the Earth Sciences and Resources ，China University of GeoSciences ，Beijing 100083，China ）（Institute of Mineral Resources Chinese Academy of Geological Sciences ，Beijing 100037，China ）
Abstract ：Presented a new algorithm for massive Contour Clipping against General Polygon Window ．The algorithm builds relation-ship of local topology between massive disorder line segments and edges of clipping polygon windows by using uniform grid segmen-tation ，which reduces intersecting calculation among line segments．Secondly ，based on these topological relations ，using local ray method decreases time complexity generated by calculation of verifying point in general polygon windows．Thus ，it could rapidly dis-tinguish the reserve parts of contours that users needed．Furthermore ，the algorithm makes itself more universal as a result of modif-ying shortage of pre-algorithms that polygon window cannot be a general polygon．Key words ：local topology ；clipping ；segments intersections
1引言
顶点编码来快速实现凹多边形裁剪．以上算法主要针对简单
线段和特定裁剪多边形，而在实际应用中处理的数据可能是大规模等值线数据及裁剪多边形是任意简单多边形的情况，此时随着裁剪多边形数量、边数以及复杂程度的增加，以上算法均不能很好处理．孙春娟等提出基于凸片段分解的多边形窗口线裁剪算法，其算法复杂度在O （log N ） O （N ）之间，但该算法并没有讨论如何判断交点的出入属性问题．因为对于大规模等值线裁剪，上述问题是非常耗时的．所谓等值线图实质上就是由多条线段连接而成的折线或
［13］
者光滑曲线或任意多边形．等值线图的边界不一定局限于一个标准的矩形区域当中，而可能对应一个任意简单多边形边界；另外，对于一幅等值线图，各领域的研究人员仅仅会对它的不同部分产生兴趣，进而希望将它们提取出来，用于科学研究和成果的表达．这就产生了对已有等值线图进行裁剪的需求．然而，以上这些算法仅仅提到了针对单层窗口的剪切处理，并不适合带有洞的多边形裁剪．此外，大型的等值线图随
［16］
裁剪操作是计算机图形学的重要内容，是指识别指定图形在一组封闭折线所构成的区域内或区域外的部分的过程
［14］
．在实际生产中，其广泛应用于地质矿产，水文水利，工
程设计等工作．目前，对于矩形窗口的线剪裁国内外最著名的Sutherland 算法）［1］、算法有：分区编码剪取算法（Cohen-Sproull 和Sutherland 提出的便于硬件实现的中点分割算法
［2］
［3］
、我国学者梁友栋与Barsky 提出的参数方法，还有较
［4］
Lee-Nicholl 算法近期提出的Nicholl-法
［5］
、Andreev-Sofianska 算
、ELC 算法［6］、FLC 算法［7］等；对于多边形的裁剪，著名
的算法有：针对凸多边形裁剪提出的逐边裁剪法（Sutherland-Hodgman 算法）［8］、基于法向点积判断的参数化裁剪算法（Cyrus-Beck 算法）
［9］
；针对凹多边形裁剪提出的双边裁剪法
［10］
［11］
、刘勇奎等提出的延长裁剪线，
（Weiler-Atherton 算法）
12］通过通过计算斜率来快速判断直线与边是否相交、文献［
12-28收修改稿日期：2011-03-04基金项目：国家“八六三”收稿日期：2010-高技术研究发展计划项目（2006AA06Z114）资助；国家科技支
1980年生，撑计划项目（2006BAB01A01）资助；中央国家机关基本业务费基金项目资助．作者简介：李楠，男，博士研究生，工程师，主要研究
1953年生，1963年生，方向为地图制图与地理信息工程；吴信才，男，教授，博士生导师，研究方向为地理信息系统研究与应用；肖克炎，男，研究
员，博士生导师，研究方向为地球探测与信息技术．
着级数、范围、原始采样点密度和网格化密度的增加，等值线的数量以及线上的点都会成倍增加，上述这些传统的裁剪算13］结合法对于等值线的开窗和剪切就显得力不从心．文献［矩形网等值线追踪算法，在追踪等值线的同时，对裁剪矩形域抑制裁剪区域内的等值点，实现复杂矩形域的等值裁预处理，
剪．在实际应用中，裁剪等值线往往是对已有等值线数据且裁13］而文献［无法处理．剪区域可能是任意简单多边形的情况，
综上所述，结合等值线光滑后数据点比较密集的特点，提出大规模等值线图的任意多边形裁剪算法．该算法可以避免大量数据的求交运算和多边形内外点判断，实验表明算法稳定且效率高．
并记录下来；盒内等值线段的网格轨迹，
Step 4．根据网格记录进行求交计算，当且仅当网格记录符合条件时才进行求交判断和计算，其它网格均可跳过；Step 5．使用局部射线法，判断交点的出入属性并获得裁剪线
．
2算法涉及基本概念
定义1（任意简单多边形）．多边形是指一组封闭的折线．
多边形中具有共同端点的边称为相邻边．若多边形中不相邻且可以包含零或多个洞，就称为任意简单多边的边不相交，
形．在本文中，若多边形存在洞，则洞的顶点排列顺序与其它洞相同而与最外侧多边形顶点排列顺序相反．
定义2（裁剪多边形）．在二维平面上，任意的简单多边形均可以作为裁剪多边形．
定义3（网格轨迹）．线段在二维网格中所跨越的所有网格，该组网格称为线段的网格轨迹．如图1中线段AB 的网格轨迹为阴影网格所示
．
图2算法流程图Fig．2Algorithm flowchart
算法流程图如图2所示．3．2
建立裁剪多边形的初始包围盒
初始包围盒是由图中X 和Y 方向的最小值和最大值围
成的矩形框，如图3和图4（见下页）
所示的多边形初始包围
图1线段经过的网格轨迹
Fig．1Grid track passed by segment
定理1（射线法判断点在多边形内外）．根据从待判定点引出的一条射线与多边形边界交点数的奇偶性来判定该点是
则点在多边形内部；若否包含于多边形中．若交点数为奇数，交点数为偶数，则点在多边形外部．
3
3．1
算法思想
裁剪算法思想与步骤
本文算法研究的核心是避免大量数据的求交运算和点在
图3查找裁剪多边形的外包围盒
Fig．3External bounding box of polygon
盒．图4中所示的外包围盒，并不是严格按照裁剪多边形窗口
y 方向最小值），（x 方向最大值，y 方的范围（（x 方向最小值，
向最大值））得到的，而是将这个范围稍稍扩大了一些，这样
做的目的是便于算法1的编程实现，避免计算网格轨迹时边界网格的处理．
3．3对裁剪多边形的包围盒进行等网格分割
在求交和裁剪计算过程中，根据网格索引记录来判断当前等值线线段是否需要进行求交计算．在二维空间建立图形的网格索引结构方法有很多，例如：均匀条带分割、等格网分
减少裁剪多边形边界多边形内外的判断．首先利用网格索引，
与等值线段的求交次数；其次基于网格索引结构，提出基于等网格分割的“局部射线”法，该思想可以在求出交点的基础上，快速获得需要保留（剔除）等值线部分的起止点．
算法主要步骤：
Step 1．根据裁剪多边形窗口，生成多边形的外包围盒；Step 2．基于网格分割算法，构造包围盒网格；
Step 3．初始化所有网格记录，计算裁剪多边形边和包围
割、四叉树分割和自适应分块等方法．
由于文章主要处理的是
大规模等值线数据，为了方便计算网格轨迹，采用了等格网分
割的方法．基本思路是以包围盒为网格边界，将裁剪多边形和
［15］
等值线上的点放到大小相同的网格中．设格子的最大行列
iMaxColnum．如图5（a ）（b ）（c ）所示．数分别为iMaxRownum ，
此处还存在一个问题，即单元网格大小的确定．设当前包
含n 个离散点（包括裁剪多边形和等值线上的点）的矩形包则可以计算单位面积上点分布的平均密度ρ围盒的面积为s ，
=n /s．再利用离散点的平均密度就可以估计离散点间的平均
图4裁剪外包围盒的等网格分割
Uniform grid segmentation of external bounding box
在实际应用中，可将d 扩大适当倍数作为网距离d =格大小的参照，如取3倍平均距离为单元格的边长，则可以确定网格的期望大小为3d
ˑ
3
d ．
Fig．4
（a ）（a ）均匀条带分割法
Uniform strip segmentation
（b ）（b ）等格网分割法
Uniform grid segmentation
（c ）（c ）四叉树分割法Quadtree segmentation
图5空间云状图的分割法Fig．5Cloud form map segmentation
3．4
记录裁剪多边形和等值线线段的网格轨迹
｝；
采用基于均匀网格结构计算大规模等值线与裁剪多边形窗口的交点，首先需要在每一个网格上记录所有通过它的线并不需要实际计算网格线与线段．如图6中所示．上述过程，
段AB 的交点仅需计算线段AB 所跨越的网格（轨迹）．同时，获得网格轨迹不需要像图6中所示的那样将线段分割分别记录到网格中，而仅需在轨迹所包含的每个网格中记录线段
AB 的编号．
其中，成员变量pvecSegID 和
pvecEdgeID 均为整型堆栈
的指针．
图7网格化时出现的几种情况Fig．7Situations of gridding
（a ）任意一条线段与网格的位置情况如图7中所列出，
表示斜率k ＞0，但是不属于（c ）（d ）（f ）这类情况；（b ）表示斜率k ＜0；（c ）表示垂直；（d ）表示在同一列；（e ）表示水平；（f ）表示在同一行．对于裁剪多边形只要得到横向剪切（纵向剪切同理），所以只要单独特殊考虑情况（c ）即可，由以上分析得出算法1如下．
算法1（求得裁剪多边形和等值线上的线段网格轨迹并在单元网格中记录结果）
输入：线段AB （A．m _y ≤B．m _y ），当前网格结构Grids．输出：标记线段AB 网格轨迹的记录．
Step 1．计算A 点所在的行和列rowA ，colA ，B 点所在的
colB ；行和列rowB ，
Step 2．判断当前线段AB 与网格的位置关系，若垂直，转Step3；否则转Step4；
图6线段网格化
Fig．6Gridding segment
算法中格眼的数据结构如下（使用类似C ++语言的伪代码）：
struct Grid ｛
vector ＜线段编号＞*pvecSegID ；vector ＜多边形边的编号＞*pvecEdgeID ；
Step 3．AB 垂直于X 轴方向
遍历Grids 结构行范围大于等于rowA 并且小于等于rowB 同时列等于colA 的所有格子，标记存在线段AB 通过．转Step 5；
Step 4．线段AB 不垂直于X 轴方向，则计算线段AB 的斜
col1，col2］；率k ；由斜率k 得到列的范围［
遍历Grids 结构，行范围大于等于rowA 并且小于等于
rowB ，同时列范围大于等于col1并且小于等于col2的所有格子，标记存在线段AB 通过．
Step 5．结束．
colA ，rowB ，colB ，col1，其中，算法1中引入的变量rowA ，
col2均为整型．A．m_y和B．m_y分别为A 点和B 点在Y 方均为浮点型．向的坐标，
3．5等值线裁剪3．5．1
判断相交线段并计算交点由于建立网格索引，计算交点时，仅需要查找Grids 结构
由交点的个数判断点在分别与图8中多边形的8条边求交，
多边形的内外．按照图8所示的情况，总共需要进行求交（跨立）判断40次．但当我们已经知道灰格子位置的时候，求交运算仅需要在点所在的行中进行，需要进行的全部相交计算仅不到原算法求交次数的50%．如图9所示．为14次，
综上所述，局部射线法进行求交运算时，仅仅需要判断由端点引出的射线与其所在行中该端点右侧格子中记录的裁剪
就可以判断该点与裁剪多边形的关多边形线段的相交情况，
系．本质上算法使用某一局部判断的结果代替了与裁剪多边
形所有边求交判断内外的结果．该想法将极大地降低算法的时间复杂度．算法过程如图10所示
．
中既包含裁剪边界线段又包含等值线线段的那些格眼进行计算．若存在这种格眼，则遍历格眼中所有线段进行求交计算．3．5．2
基于等网格分割的局部射线法裁剪等值线
一般思想认为，剪切掉裁剪多边形以外（内）的多余等值
图10局部射线法
Fig．10Details of local ray method
线段AB 为等值线上的线段，线段CD 为裁剪多边形上的
RP 为交点，某条线段，分别以线段AB 的两个端点向右侧做射线，判断在射线所在行求到的交点的情况．按照定理1可知，
A 点在多边形外，B 点在多边形内．最终，等值线裁剪的结果如图11所示
．
线部分，由交点可以获得其所在等值线段的两个端点，通过判
以确定哪一部分断线段的哪一个端点在裁剪多边形内（外），
的等值线在裁剪多边形内（外），再根据线的顶点排列顺序，
最终获得裁剪多边形以内（外）的部分．但是显然上述算法还不够高效．
研究裁剪多边形的分割算法，我们可以发现，建立网格索引不仅将裁剪多边形的边控制在一个很小的区域范围之内
，
图11等值线裁剪结果Fig．11Clipping of contour
图8多边形边所经过的网格
Fig．8Grids passed by edges of polygon
同时，也将整个裁剪多边形分解为由其边的网格轨迹环绕的
灰格子标记了多边形所经过的网格
．图形．如图8所示，
算法2（基于网格和局部射线法的等值线裁剪）．
y1），（x2，y2））（y1＜=y2），输入：裁剪线段AB =（（x1，
当前网格结构Grids．
输出：返回裁剪多边形内（外）的等值线．Step 1．计算A 点所在的行和列rowA ，colA ，B 点所在的
colB ；行和列rowB ，
Step 2．获得在Grids ［rowA ］［colA ］到Grids ［rowA ］
［iMaxRownum ］之间与射线AA' 相交的裁剪多边形上线段的同时判断点A 在多边形的内外；数量，
Step 3．获得在Grids ［rowB ］［colB ］到Grids ［rowB ］［iMaxRownum ］之间与射线BB' 相交的裁剪多边形上线段的
图9利用局部射线法求交
Intersecting calculation by using local ray method
数量，同时判断点B 在多边形的内外；
Step 4．按照裁剪要求保留的部分以及裁剪多边形坐标点的顺序，获得需要保留（剔除）的部分；
Step 5．结束．
iMaxRownum 表示网格的最大行数．其中，
Fig．9
P 2，P 3，P 4，P 5五个点（如图9所示），此时，若存在P 1，判
断这些点是否在多边形内，一般射线法是将这五个点的射线
2072小型微型计算机系统2011年
4算法复杂度分析
设裁剪多边形的总边数为M ，等值线总线段数为N ，每条等值线平均包含m 条线段，在裁剪包围盒内的等值线的线段包围盒检测时数为n．首先计算包围盒时间复杂度为O （M ），
间复杂度为O （N ）；设每条等值线和裁剪边平均跨越k1个网
算法1的时间复杂度为O （k1*N ）；设平均网格每行存有格，
k2条裁剪多边形的边，则等值线与其所经过网格所在行的裁剪边求交的时间复杂度为O （k2*n ）；最后判断裁剪完等值线的内外关系的时间复杂度为O （k2*n /m）．综上分析，由于裁剪多边形的边数相对大规模等值线数据微乎其微，可以忽略不计，所以算法时间复杂度为T （n ）=O （k1*N +k2*n ）．结合研究对象，大规模等值线数据，包含的线段较密集且较短，k1和k2分别相对于N 和n 均极小（测试数据显示平均
因此我们认为，本文提出的新算法在时间复杂值均小于10），度方面应是线性的．
这一优点将会在算法的实际使用中充多边形中的检测问题，
分体现出来．因为，在实际应用中，随着裁剪多边形边数、个数以及复杂程度的增加，判断点在多边形内外将逐渐成为与求交运算同等严重的算法瓶颈．算法对西藏某地区大比例实际实验结果证明本文算法是高效并数据进行的裁剪算法测试，
且稳定的
．
5实验结果及分析
使用西藏某地的1：1万比例尺实际等值线数据作为实验数据，该图中的光滑等值线包含近300万条线段．为了便于与先前的算法进行比较，裁剪多边形选用了与参考文献中提到的相同的实验数据，同时，还提供了之前算法无法处理的任意如图12所示．硬件开发环境：CPU 简单多边形作为实验用例，
主频为2．16GHz 和内存为1G 的PC 机；软件开发环境：MS Windows XP 操作系统和Visual C ++7．
0．
图13实验数据的裁剪结果Fig．13The clipping results
12］中对为了进一步说明算法的优势，我们引用了文献［
在此基础上与本文提出的算法进行比比试验所提供的数据，
表1各算法在不同裁剪多边形下花费时间对比
Table 1Results of comparing among time
complexities of algorithms
时间（秒）
算法Cyrus-Beck LIU 陆国栋
凸六边形6．31875．82425．4945
凸八边形7．9676．53855．76925．625
凹十边形不能裁剪7．14296．15385．85
凹十五边形不能裁剪8．24186．86815．865
凹二十边形
不能裁剪9．56047．52755．865
任意简单多边形不能裁剪不能裁剪不能裁剪7．035
本文算法4．455
较（已经把文献中时间的单位由CPU 滴答转换为秒），如表1．从表中首先可以看出，本文提出的提高线段之间可见性，减
图12实验数据的裁剪多边形
Fig．12The testing clipping polygons
由实验结果可以看出，通过建立网格索引，我们可以将空间中两个完全不存在关联的大量图形对象联系起来．在裁剪计算时，将线段之间的求交计算限定在了一个很小的范围内进行，极大地提高了判断线段之间是否相交的算法效率．同
网格结构也不会与等值线的线段条数有关，其大小与密度时，
仅与裁剪多边形的边数和密度有关，这保证了构建网格结构仅会占用很小的时空复杂度，因为与等值线图所包含的线段数量相比，裁剪多边形的线段数量可以忽略不计．另外，利用已有的网格结构，我们还可以仅仅通过局部判断来解决点在
图14图示算法时间复杂度比较
Fig．14Map of comparing time complexity
少线段求交次数的方法是行之有效的，因为与前人所做的算
10期李楠等：大规模等值线图的任意简单多边形窗口裁剪算法2073
法时间复杂度处在同一数量级上；其次，更为重要地，从表中我们可以发现随着裁剪多边形边数和复杂程度的增加，算法的时间复杂度并没有显著增加，这一点与其它算法相比具有明显优势．例如，本文算法在使用凸八边形裁剪时的算法时间
［12］
但是当裁剪多边形边数增复杂度与陆国栋算法几乎相同，
加到37条并且多边形本身变得更加复杂时，本文算法的开销
如图14（见上页）所示．实验结果甚至低于以前算法近一倍，
［9］Cyrus M ，Beck J．Generalized two and three dimensional clipping
［J ］．Computers ＆Graphics ，1978，3（1）：23-28．
［10］Weiler K ，Atherton P．Hidden surface removal using polygon area
sorting ［J ］．ACM SIGGRAPH Computer Graphics ，1977，11（2）：214-222．
［11］Liu Yong-kui ，Yan Ye ，Shi Jiao-ying．An efficient algorithm for
the line clipping against a polygon ［J ］．Chinese Journal of Com-puters ，1999，22（11）：1210-1214．
［12］Lu Guo-dong ，Xing Shi-hai ，Peng Qun-sheng．An efficient algo-rithm of line clipping against polygonal window based on the vertex encodin ［J ］．Chinese Journal of Computers ，2002，25（9）：987-993．
［13］Zhao Hai-zhen ，Li Tong-lin ，Yu Guo-feng．Clipping of complex
grid contour ［J ］．Journal of Image and Graphics ，2002，7（4）：380-383．
［14］Donald Hearn ，M Pauline Baker．Computer graphics （second edi-tion ）［M ］．Beijing ：Publishing House of Electronics Industry ，2002．
［15］Liu Xiao-ping ，Zhu Xiao-qiang ，et al．Building algorithm of trian-gulation based on LiDAR point clouds ［J ］．Journal of Software ，2008，19（zk ）：1-9．
［16］Sun Chun-juan ，Wang Wen-cheng ，Li Jing ，et al．Line clipping a-gainst a polygon through convex segments ［J ］．Journal of Comput-er-Aided Design and Computer Graphics ，2006，18（12）：1799-1805．
再次证明了，与之前算法相比较，本文提出的算法更加具有实
际应用价值；最后，本文提出的算法可以处理上述算法无法处理的带洞的任意简单多边形情况．
6总结与展望
本文首先分析了目前裁剪算法研究领域提出的主要算
提出了一种新的二维空间法．在充分研究前人思想的基础上，
大规模线段多边形裁剪算法．本算法提出了利用等均匀网格
大大提高了线段求交算法效率，降低方法建立网格索引结构，
了点在多边内外判断的时间复杂度，实现了对大量线段数据
的快速任意简单多边形裁剪．应该可以认为是对大规模数据裁剪算法的有益推进和补充．本文算法稍作修改即可实现根据用户需要进行内（外）裁剪并得到裁剪结果．
本算法在如何建立合适的网格结构以及如何尽量减少网格结构带来的开销方面，还可以做进一步研究．References ：
［1］Newman W M ，Sproull R F．Principles of interactive computer
graphics ［M ］．McGraw -Hill ，New York ，1979．
［2］Sproull R F ，Southerland I E．A clipping divider ［M ］．FJCC ，
Thompson Books ，Washington D．C ，1968．
［3］Liang L D ，Barsky B A．A new concept and method for line clip-ping ［J ］．ACM Transactions on Graphics ，1984，3（1）：278-283．［4］Nicholl T M ，Lee D T ，Nicholl R A．An efficient new algorithm
for 2D line clipping ［J ］．SIGGRAPH' 87，Computer Graphics ，1987，21（4）：643-648．
［5］Andreev R ，Sofianska E．New algorithm for two dimensional line
clipping ［J ］．Computers ＆Graphics ，1991，15（4）：519-526．［6］Wang Hao-hong ，Wu Rui-xun ，Cai Shi-jie．A new efficient line
clipping algorithm based on geometric transformation ［J ］．Journal of Sofrware ，1998，9（10）：728-733．
［7］Wang Jun ，Liang You-dong ，Peng Qun-sheng．A 2-D line clipping
algorithm with the least arithmetic operations ［J ］．Chinese Journal of Computers ，1991，14（7）：495-504．
［8］Sutherland I E ，Hodgman G W．Reentrant polygon clipping ［J ］．
Communication of the ACM ，1994，17（1）：32-42．
附中文参考文献：
［6］汪灏泓，吴锐迅，蔡士杰．一种基于几何变换的高效的线裁剪新
J ］．软件学报，1998，9（10）：728-733．算法［［7］王
骏，梁友栋，彭群生．具有最少算术运算量的二维裁剪算法
叶，石教英．一个有效的多边形窗口的线裁剪算法
［J ］．计算机学报，1991，14（7）：495-504．［11］刘勇奎，颜
［J ］．计算机学报，1999，22（11）：1210-1214．
［12］陆国栋，刑世海，彭群生．基于顶点编码的多边形窗口线裁剪高
2002，25（9）：987-993．效算法［J ］．计算机学报，
［13］赵海珍，．中国李桐林，于国锋．复杂矩形网等值线图的剪切［J ］
2002，7（4）：380-383．图象图形学报，
［14］Donald Hearn ，M Pauline Baker．计算机图形学（第二版）［M ］．
2002．北京：电子工业出版社，
［15］刘晓平，朱晓强，等．基于LiDAR 点云数据的三角网构建算法
［J ］．软件学报，2008，19（zk ），1-9．［16］孙春娟，王文成，李
1799-1805．
静，等．基于凸片段分解的多边形窗口线
2006，18（12）：裁剪算法［J ］．计算机辅助设计与图形学学报，