第16章：填充规则详解

16.1 概述

填充规则决定了多边形的哪些区域被视为"内部"。Clipper 支持四种填充规则，不同的规则在处理自相交多边形时会产生不同的结果。

16.2 PolyFillType 枚举

public enum PolyFillType { 
    pftEvenOdd,   // 奇偶规则
    pftNonZero,   // 非零规则
    pftPositive,  // 正向规则
    pftNegative   // 负向规则
}

16.3 EvenOdd（奇偶规则）

16.3.1 原理

从任意点发出射线，计算与多边形边界的交点数：

• 奇数交点：点在多边形内部
• 偶数交点：点在多边形外部

16.3.2 图解

    ┌─────────────────────┐
    │        1            │  1个交点 → 内部
    │    ┌───────┐        │
    │    │   2   │        │  2个交点 → 外部
    │    │       │        │
    │    └───────┘        │
    │        1            │  1个交点 → 内部
    └─────────────────────┘
    0                        0个交点 → 外部

自相交情况：
        ╲
         ╲
    ┌─────╲────┐
    │      ╲   │
    │       ╲──┤
    │      ╱   │
    │     ╱    │
    └────╱─────┘
        ╱
交叉区域有 2 个交点 → 外部（空洞）

16.3.3 代码实现

private bool IsEvenOddFillType(TEdge edge)
{
    if (edge.PolyTyp == PolyType.ptSubject)
        return m_SubjFillType == PolyFillType.pftEvenOdd;
    else
        return m_ClipFillType == PolyFillType.pftEvenOdd;
}

// 在 IsContributing 中
case PolyFillType.pftEvenOdd:
    if (edge.WindDelta == 0 && edge.WindCnt != 1) 
        return false;
    break;

16.4 NonZero（非零规则）

16.4.1 原理

从任意点发出射线，计算缠绕数（Winding Number）：

• 向上穿过边界时 +1
• 向下穿过边界时 -1
• 缠绕数 ≠ 0：点在多边形内部
• 缠绕数 = 0：点在多边形外部

16.4.2 图解

方向向量 →

    ↓ -1      ↑ +1
    │         │
    │   W=0   │
    │  (外部) │
    ├─────────┤
    │         │
    │   W=+1  │
    │  (内部) │
    └─────────┘

自相交（同向）：
    ↓         ↓
    │         │
    │   W=+2  │  ← 重叠区域仍为内部
    │         │
    ├─────────┤
    │   W=+1  │
    └─────────┘

自相交（反向）：
    ↓         ↑
    │         │
    │   W=0   │  ← 重叠区域为外部
    │         │
    ├─────────┤
    │   W=+1  │
    └─────────┘

16.4.3 代码实现

case PolyFillType.pftNonZero:
    if (Math.Abs(edge.WindCnt) != 1) 
        return false;
    break;

16.5 Positive（正向规则）

16.5.1 原理

只有缠绕数 > 0 的区域被视为内部。

16.5.2 图解

    ↓ -1      ↑ +1      ↓ -1
    │         │         │
    │  W=-1   │  W=0    │  W=-1
    │  (外部) │ (外部)  │  (外部)
    ├─────────┼─────────┤
    │  W=0    │  W=+1   │  W=0
    │ (外部)  │ (内部)  │  (外部)
    └─────────┴─────────┘

16.5.3 代码实现

case PolyFillType.pftPositive:
    if (edge.WindCnt != 1) 
        return false;
    break;

16.6 Negative（负向规则）

16.6.1 原理

只有缠绕数 < 0 的区域被视为内部。

16.6.2 图解

    ↓ -1      ↑ +1      ↓ -1
    │         │         │
    │  W=-1   │  W=0    │  W=-1
    │  (内部) │ (外部)  │  (内部)
    ├─────────┼─────────┤
    │  W=0    │  W=+1   │  W=0
    │ (外部)  │ (外部)  │  (外部)
    └─────────┴─────────┘

16.6.3 代码实现

default: // pftNegative
    if (edge.WindCnt != -1) 
        return false; 
    break;

16.7 缠绕数计算

16.7.1 WindDelta

// 边的 WindDelta 取决于边的方向和多边形的方向
// 逆时针多边形：从下到上的边 WindDelta = +1
// 顺时针多边形：从下到上的边 WindDelta = -1
// 开放路径：WindDelta = 0

16.7.2 SetWindingCount

private void SetWindingCount(TEdge edge)
{
    TEdge e = edge.PrevInAEL;
    
    // 找到同类型的前一条边
    while (e != null && ((e.PolyTyp != edge.PolyTyp) || (e.WindDelta == 0))) 
        e = e.PrevInAEL;
    
    if (e == null)
    {
        // 第一条边
        if (edge.WindDelta == 0) 
            edge.WindCnt = (pft == PolyFillType.pftNegative ? -1 : 1);
        else 
            edge.WindCnt = edge.WindDelta;
        edge.WindCnt2 = 0;
    }
    else if (IsEvenOddFillType(edge))
    {
        // 奇偶规则：简单切换
        edge.WindCnt = edge.WindDelta;
        edge.WindCnt2 = e.WindCnt2;
    }
    else
    {
        // 非零规则：累加
        if (e.WindCnt * e.WindDelta < 0)
        {
            // 缠绕数正在减少
            if (Math.Abs(e.WindCnt) > 1)
            {
                if (e.WindDelta * edge.WindDelta < 0) 
                    edge.WindCnt = e.WindCnt;
                else 
                    edge.WindCnt = e.WindCnt + edge.WindDelta;
            }
            else
                edge.WindCnt = (edge.WindDelta == 0 ? 1 : edge.WindDelta);
        }
        else
        {
            // 缠绕数正在增加
            if (edge.WindDelta == 0)
                edge.WindCnt = (e.WindCnt < 0 ? e.WindCnt - 1 : e.WindCnt + 1);
            else if (e.WindDelta * edge.WindDelta < 0)
                edge.WindCnt = e.WindCnt;
            else 
                edge.WindCnt = e.WindCnt + edge.WindDelta;
        }
        edge.WindCnt2 = e.WindCnt2;
    }
    
    // 计算另一类多边形的缠绕数
    // ...
}

16.8 IsContributing 中的填充规则

private bool IsContributing(TEdge edge)
{
    PolyFillType pft, pft2;
    if (edge.PolyTyp == PolyType.ptSubject)
    {
        pft = m_SubjFillType;
        pft2 = m_ClipFillType;
    }
    else
    {
        pft = m_ClipFillType;
        pft2 = m_SubjFillType;
    }

    // 检查自身类型的缠绕数
    switch (pft)
    {
        case PolyFillType.pftEvenOdd:
            if (edge.WindDelta == 0 && edge.WindCnt != 1) 
                return false;
            break;
        case PolyFillType.pftNonZero:
            if (Math.Abs(edge.WindCnt) != 1) 
                return false;
            break;
        case PolyFillType.pftPositive:
            if (edge.WindCnt != 1) 
                return false;
            break;
        default: // pftNegative
            if (edge.WindCnt != -1) 
                return false; 
            break;
    }

    // 检查与另一类多边形的关系（根据 ClipType）
    // ...
}

16.9 填充规则与布尔运算的结合

16.9.1 交集（Intersection）

case ClipType.ctIntersection:
    switch (pft2)
    {
        case PolyFillType.pftEvenOdd:
        case PolyFillType.pftNonZero:
            return (edge.WindCnt2 != 0);  // 在另一多边形内部
        case PolyFillType.pftPositive:
            return (edge.WindCnt2 > 0);
        default:
            return (edge.WindCnt2 < 0);
    }

16.9.2 并集（Union）

case ClipType.ctUnion:
    switch (pft2)
    {
        case PolyFillType.pftEvenOdd:
        case PolyFillType.pftNonZero:
            return (edge.WindCnt2 == 0);  // 不在另一多边形内部
        case PolyFillType.pftPositive:
            return (edge.WindCnt2 <= 0);
        default:
            return (edge.WindCnt2 >= 0);
    }

16.9.3 差集（Difference）

case ClipType.ctDifference:
    if (edge.PolyTyp == PolyType.ptSubject)
        // Subject 边：不在 Clip 内部
        switch (pft2)
        {
            case PolyFillType.pftEvenOdd:
            case PolyFillType.pftNonZero:
                return (edge.WindCnt2 == 0);
            // ...
        }
    else
        // Clip 边：在 Subject 内部
        switch (pft2)
        {
            case PolyFillType.pftEvenOdd:
            case PolyFillType.pftNonZero:
                return (edge.WindCnt2 != 0);
            // ...
        }

16.10 使用示例

16.10.1 自相交多边形

// 创建 8 字形多边形
Path figure8 = new Path();
figure8.Add(new IntPoint(0, 0));
figure8.Add(new IntPoint(100, 100));
figure8.Add(new IntPoint(100, 0));
figure8.Add(new IntPoint(0, 100));

Clipper clipper = new Clipper();
clipper.AddPath(figure8, PolyType.ptSubject, true);

// 使用奇偶规则
Paths resultEvenOdd = new Paths();
clipper.Execute(ClipType.ctUnion, resultEvenOdd, 
    PolyFillType.pftEvenOdd, PolyFillType.pftEvenOdd);
// 结果：交叉区域为空洞

// 使用非零规则
clipper.Clear();
clipper.AddPath(figure8, PolyType.ptSubject, true);
Paths resultNonZero = new Paths();
clipper.Execute(ClipType.ctUnion, resultNonZero, 
    PolyFillType.pftNonZero, PolyFillType.pftNonZero);
// 结果：取决于边的方向

16.10.2 重叠多边形

// 两个重叠的正方形
Path square1 = CreateSquare(0, 0, 100);
Path square2 = CreateSquare(50, 50, 100);

Clipper clipper = new Clipper();
clipper.AddPath(square1, PolyType.ptSubject, true);
clipper.AddPath(square2, PolyType.ptSubject, true);

// 奇偶规则：重叠区域变成空洞
Paths resultEO = new Paths();
clipper.Execute(ClipType.ctUnion, resultEO, 
    PolyFillType.pftEvenOdd);

// 非零规则：重叠区域保持填充
clipper.Clear();
clipper.AddPath(square1, PolyType.ptSubject, true);
clipper.AddPath(square2, PolyType.ptSubject, true);
Paths resultNZ = new Paths();
clipper.Execute(ClipType.ctUnion, resultNZ, 
    PolyFillType.pftNonZero);

16.11 选择填充规则的建议

16.12 本章小结

本章详细分析了 Clipper 的四种填充规则：

1. EvenOdd：基于交点奇偶性
2. NonZero：基于缠绕数符号
3. Positive：只填充正缠绕区域
4. Negative：只填充负缠绕区域

不同的填充规则会影响：

• 自相交多边形的处理
• 重叠区域的处理
• 边的贡献判断

选择合适的填充规则取决于具体应用场景。

上一章：孔洞检测与处理 | 返回目录 | 下一章：ClipperOffset详解