Question

请教一道计算机图形学的编程题

这是一道10分的考博试题，请高手帮忙做一下：
编写一段程序实现Weiler-Atherton多边形裁剪算法（C/ C++语言）。

Answer 1

一些应用需要涉及任意多边形窗口（含凹多边形窗口）的裁剪。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的处理也同上。这种处理在本算法中大量遇到。