多边形裁剪算法

修剪多边形的SutherlandHodgman算法1 1.SutherlandHodgman多边形裁剪算法思想此算法的基本思想是使用窗口的边界和延长线每次修剪多边形的边。多边形通常表示为其顶点序列，通过修剪规则对边界进行修剪，然后创建新的顶点序列，修剪下一个边界，直到窗口的所有边界都被修剪。算法形成了可以构成一个或多个多边形的最后一个顶点序列。多边形的顶点交点相对于窗口的边界和延伸线进行修剪时，以下四种情况(即修剪规则)除外：1、如果顶点Pi在内部，并且旧顶点Pi-1也在内部，则Pi包含在新顶点序列中。2，如果顶点IP在内部，旧顶点IP-1在外部，则首先查找相交q，然后将q、Pi包含在新顶点顺序中。3、如果顶点IP位于外部，而旧顶点Pi-1位于内部，则首先查找交点q，然后在新顶点序列中包含q。4、“顶点Pi”和“旧顶点Pi-1”都在外部时，不会将新顶点添加到顶点序列中。2 2.SutherlandHodgman多边形修剪算法步骤考虑基于边界和延长线修剪多边形的算法。1.从主函数中获取要剪切的多边形的顶点序列P2、顶点序列n、窗口边界参数XL(矩形窗口的左边界)。2.指定初始值：将顶点序列中的最后一个顶点指定给上一个顶点s。设置初始标志flag:If(S在边界内部)flag=0；else flag=1；设置新的顶点序列数j=0。3.系统会针对多边形的每个顶点处理裁剪规则，并将结果放置在新多边形顶点序列Q2上。For(从第一个顶点到最后一个顶点逐一处理)If(交点位于边界内部)If(flag！=0)flag=0；找到交点，然后将其放置在新的多边形顶点序列Qj中。j；将当前顶点放入新的多边形顶点序列Qj中。QJ=pij；ElseIf(flag=0)flag=1；找到交点，然后将其放置在新的多边形顶点序列Qj中。j；将当前顶点指定给s: s=pi。4.准备返回：将新的多边形顶点序列q返回到原始多边形顶点序列p:p=q；将新多边形顶点数j放回原始多边形顶点数n。n=j；/修剪多边形的SutherlandHodgman算法- /void cmy clip _ a view 3363603360 clippedgel(cpoint poly point，cpoint clip window ，uint polynum)/*其中参数polypoint表示多边形顶点，clipwindow表示修剪窗口顶点，polynum表示多边形顶点数*/寻找裁剪视窗边界Long xl、xr、yt、Yb；UINT I；Xl=clipwindow0。x；Xr=clipwindow0。x；Yt=clipwindow0。y；Yb=clipwindow0。y；for(I=1)；I=4；I)If (xlclipbindow I)。x)Xl=clipwindowi。x；If (xrclipbindow I)。y)Yb=clipwindowi。y；If(yt=xl polypointi 1)。x=xl) /*边的两个端点都在内部，*/*每个保留点在阵列中仅出现一次，并且保留的两个点中的第一个*/Bm_nB。x=polypointi。x；Bm_nB。y=polypointi。y；m _ nB=m _ nB 1；ContinueIf(polypointi)。x=xl)/*边的两个终点起点在外侧，终点在内侧，找到交点，然后找到交点。端点都是临时阵列*/*保持交点*/X=xlTem1=(xl-polypointi)。x)；/tem 2=(XL-x1)* dy/dx y1；/y/x=dy/dx - y=x*dy/dxTem2=tem1 * (polypoint I 1)。y-polypoint I。y)/polypoint I 1。x-polypoint I。x) polypoint I。y；Y=tem2Bm_nB。x=xBm_nB。y=ym _ nB=m _ nB 1；ContinueIf (polypoint I)。x=xlpolypoint I 1。x=ybb I 1。y=Yb)/p1，p2均位于Yb上方Cm_nA。x=Bi。x；Cm_nA。y=Bi。y；M _ nAContinueIf(Bi)。y=yb)/p1位于下方，P2位于上方，保留交点，外部-内部Y=ybTem1=yb-Bi。y；/tem2=x1 (yb-y1)*dx/dyTem2=tem1 * (b I 1)。x-b I。x)/(b I 1)。y-b I。y) b I。x；X=tem2Cm_nA。x=xCm_nA。y=yM _ nAContinueIf(Bi)。y=yb Bi 1。yxr Ci 1。xxr)/P1，P2均向右- go nextContinueIf(Ci)。x=xr C