精选_Weiler-Atherton多边形裁减算法展示程序_源码打包

# Weiler-Atherton多边形裁减算法展示程序 # 一、简介 计算机图形学的作业，实现Weiler-Atherton多边形裁减算法。这个程序允许用户点击画出多边形和裁减窗口，然后点按钮实现裁剪。 该算法的原理如下（摘自https://blog.csdn.net/liaojinyu282/article/details/6011177 ）：  *图中DCBA为裁剪窗口，dcba为要裁剪的多边形。在算法执行之前将多边形和裁剪窗口的交点分别加入他们的顶点序列。即图中的123456。* *则多边形序列为:a,6,5,d,4,3,c,2,b,1* *裁剪窗口序列为:A,5,4,D,C,1,B,2,3,6* *从多边形顶点a开始按逆时针方向遍历多边形顶点。到达多边形与裁剪边界的交点6，此时线段是从裁剪区的外部进入裁剪区内部。* *（即交点6是一个**入点**，entering intersection，因为从5到6，线段是指向多边形内的），则在多边形序列上继续遍历直到找到第一个从边界“出去”的点或者一个已经遍历过的点，图中所示为交点5（称交点5为一个**出点**，exiting intersection）；* *此时线段从裁剪区内出去，这时在裁剪窗口序列的当前顶点开始逆时针遍历（此时为交点5），到达交点4，线段d4指向多边形内部，交点4是一个entering intersection；* *转换到多边形序列继续遍历，到交点3,交点3是一个exiting intersection；* *转换到裁剪窗口序列逆时针遍历，到交点6，发现6已经访问过，得到顶点序列6543，即为一个要绘制的多边形；* *这时退回到最后一个exiting intersection，即顶点3，在多边形序列上遍历，找到一个   entering intersection，即点2，然后按照上述过程得到一个顶点序列2b1B，此时多边形所有的点均已访问，算法结束；* *整个算法就是先计算多边形和裁剪窗口的顶点序列，然后根据交点是一个entering intersection还是exiting intersection选择在不同的顶点序列上遍历，直到所有的点都访问完* 注：以上为内裁减，也就是保留裁减窗口内的图形。外裁减就是保留裁减窗口外的图形，其实现方法就是在按照上述方式遍历顶点时，把遍历方向反过来（上述为逆时针，所以改为顺时针就能实现外裁减）。大家画一画就能明白。 # 二、算法实现 Weiler-Atherton算法原理简单，但实际上写起来还是比较麻烦滴。我只粗暴地实现了基本功能，很多都是暴力实现的，效率之类的都没有太考虑，代码也有点乱。我的实现步骤基本如下： - 多边形的点按什么顺序存储会影响内裁减和外裁减时，遍历顶点的方向。把主多边形和裁剪窗口都按顺时针顺序排好 - 把主多边形和裁剪窗口的点存为两个顶点表。找出裁剪窗口与多边形的所有交点！然后把交点按顺序插入顶点表中！注意，不是把交点插在这条边的两个顶点即可，要考虑一下如果一条边上有两个交点，这两个交点的顺序 - 按照Weiler-Atherton算法的描述，在两个表之间来回按顺序找点，并生成新的多边形。 其实还是不难的，主要就是**麻烦**。 # 三、程序使用 左键点击，在面板上点出顶点。右键点击，则多边形自动闭合，完成一个多边形。 画完主多边形和裁减多边形（即裁减窗口）后，即可点击裁剪。 不要点得太快，有时会无法点上点。