这是一道10分的考博试题，请高手帮忙做一下：编写一段程序实现Weiler-Atherton多边形裁剪算法（C/ C++语言）。
一些应用需要涉及任意多边形窗口（含凹多边形窗口）的裁剪。Weiler-Atherton多边形裁剪算法正是满足这种要求的算法。 Weiler-Atherton又称双边裁剪法。 我找到了中国地质大的一个有关的教程，其中的算法过程具体如下： 1、算法在实现中，需要用到六个数组，分别用来存放：被裁剪多边形、裁剪窗口、交点数组、插入交点后的被裁剪多边形、插入交点后的裁剪窗口、输出多边形。 2、由于交点具有“入”、“出”标记，因此凡与交点有关的数组都要采用结构数组类型： struct point { double x； double y； int flag； }交点数组，数组3，数组4； 标记flag有三种状态： 0：非交点； 1：“入”点； -1：“出”点。 3、求交点时，利用被裁剪多边形的各边去对裁剪窗口的各边求交点： for（被裁剪多边形的各边） { …； for（裁剪窗口的各边） { 求有效交点；放入交点数组； …； } } 4、交点的顺序插入，意味着要对交点数组排序后再分别插入到数组1、数组2的相应位置上。 5、所谓找“入”点、“出”点，必须根据flag找寻满足条件的顶点位置。不光数组3中要找“入”点、“出”点，而且找到后还要转到数组4的相应顶点位置处。对数组4的处理也同上。这种处理在本算法中大量遇到。
|
|
