3.qt-图解Weiler-Atherton任意多边形剪裁算法

1.Weiler-Atherton多边形剪裁算法

Weiler-Atherton剪裁算法是一个适用于凸的、凹的和带孔的多边形的裁剪算法。

裁剪窗口可以是矩形、任意凸多边形、任意凹多边形。

与 Sutherland – Hodgman 多边形裁剪算法不同，该算法能够裁剪凹多边形而不会留下任何残留物。

需要注意的是保证两个多边形的端点是顺时针的.当然也可以通过函数进行判断一下,从而进行反转:

WeilerAtherton::ClockWiseType WeilerAtherton::isClockWise(QVector points)
{
    if (points.length() < 3)    // 错误,points是一个点或者一条线
        return  ClockWiseUnknown;
 
    // Shoelace formula算法来计算多边形面积判断顺和逆
    qreal area = 0;
    for (int i = 0; i < points.length(); i++) {
        int j = (i + 1) % points.length();
        area += points[i].x() * points[j].y();
        area -= points[j].x() * points[i].y();
    }
 
    if(area / 2.0 > 0)
        return Anticlockwise;
    return ClockWise;
}

2.算法图解-简单示例1

找到所有交点,下图所示:

通过规律可以看出如果主多边形与裁剪多边形有交点,交点成对出现,然后我们可以将相交点规定为进点和出点(enter和exit)、然后找到所有的近点和出点相交点.如下图所示:

制作两个列表:

一个是裁剪多边形(VWXYZ)，一个主多边形(ABCD):

找到第一个进点:

从裁剪多边形的列表(VWXYZ)开始,找到第一个进点为i1,然后我们就可以开始在ABCD区域绘制子方形,直到遇到第一个出点i2(出点代表另一个列表的入点).然后再次在ABCD列表中从i2开始,直到绘制到开始点i1为止(避免被漏掉).

 

然后继续往后遍历,得到:

3.算法图解-简单示例2

设P1 P2 P3 P4 P5 P6为裁剪多边形, V1 V2 V3 V4 V5 V6为主多边形

从裁剪多边形开始,找到第一个入点i2后,直到绘制到终点i2为止,遍历如下所示:

i2 –> i3(列表1的出点,相当于是列表2的入点)

跳转到列表2的入点i3遍历:

i3->i8(列表2的出点)

跳转到列表1的入点i8遍历:

i8->i1(列表1的出点)

继续跳到列表2的入口i1遍历:

i1->i2(遇到开始的入点则停止)

最后重复往后遍历,直到最后得到:

 

实现效果如下所示,代码很乱,后续整理后发出来(主多边形是一个带内环多边形)