第15章：孔洞检测与处理

15.1 概述

在多边形布尔运算中，正确识别和处理孔洞是至关重要的。本章将分析 Clipper 如何确定多边形是外轮廓还是孔洞，以及如何维护它们之间的层次关系。

15.2 孔洞的定义

15.2.1 几何定义

• 外轮廓：逆时针方向的闭合路径，包围"内部"区域
• 孔洞：顺时针方向的闭合路径，从外轮廓中"挖出"区域

外轮廓（逆时针）        孔洞（顺时针）
    ┌───────────┐         ┌───────┐
    │           │         │ ┌───┐ │
    │           │         │ │   │ │
    │           │         │ └───┘ │
    └───────────┘         └───────┘
         ↺                    ↻

15.2.2 面积符号

public static double Area(Path poly)
{
    int cnt = (int)poly.Count;
    if (cnt < 3) return 0;
    double a = 0;
    for (int i = 0, j = cnt - 1; i < cnt; ++i)
    {
        a += ((double)poly[j].X + poly[i].X) * 
             ((double)poly[j].Y - poly[i].Y);
        j = i;
    }
    return -a * 0.5;
}

• 正面积：逆时针（外轮廓）
• 负面积：顺时针（孔洞）

15.3 SetHoleState

在创建新输出记录时设置孔洞状态：

private void SetHoleState(TEdge e, OutRec outRec)
{
    TEdge e2 = e.PrevInAEL;
    TEdge eTmp = null;
    
    while (e2 != null)
    {
        if (e2.OutIdx >= 0 && e2.WindDelta != 0)
        {
            if (eTmp == null)
                eTmp = e2;
            else if (eTmp.OutIdx == e2.OutIdx)
                eTmp = null;  // 配对边，不计入
        }
        e2 = e2.PrevInAEL;
    }

    if (eTmp == null)
    {
        outRec.FirstLeft = null;
        outRec.IsHole = false;
    }
    else
    {
        outRec.FirstLeft = m_PolyOuts[eTmp.OutIdx];
        outRec.IsHole = !outRec.FirstLeft.IsHole;
    }
}

15.3.1 算法原理

从当前边向左遍历 AEL，计算经过的边数：

• 偶数边：外轮廓
• 奇数边：孔洞

        e1     e2     e3     e4
AEL: ───│──────│──────│──────│──── 
        │      │      │      │
        ▼      ▼      ▼      ▼
      外轮廓  孔洞   外轮廓  孔洞

新边从 e4 右侧开始：
经过 e4（1）→ e3（2）→ e2（3）→ e1（4）
4 条边，偶数 → 新边是孔洞

15.3.2 配对边处理

if (eTmp.OutIdx == e2.OutIdx)
    eTmp = null;  // 配对边

如果遇到属于同一输出记录的两条边，它们相互抵消。

15.4 FixHoleLinkage

修复孔洞链接：

private void FixHoleLinkage(OutRec outRec)
{
    // 确保 FirstLeft 指向有效的外轮廓
    if (outRec.FirstLeft == null ||                
        (outRec.IsHole != outRec.FirstLeft.IsHole &&
        outRec.FirstLeft.Pts != null)) 
        return;

    OutRec orfl = outRec.FirstLeft;
    while (orfl != null && 
           ((orfl.IsHole == outRec.IsHole) || orfl.Pts == null))
        orfl = orfl.FirstLeft;
    outRec.FirstLeft = orfl;
}

15.4.1 修复逻辑

确保孔洞的 FirstLeft 指向一个：

1. 有效的输出记录（Pts != null）
2. 不同类型的记录（孔洞的 FirstLeft 应该是外轮廓）

15.5 FirstLeft 链

FirstLeft 建立了输出记录之间的父子关系：

PolyTree 结构：
Root
├── OutRec1 (外轮廓)
│   ├── OutRec2 (孔洞, FirstLeft = OutRec1)
│   │   └── OutRec3 (岛屿, FirstLeft = OutRec2)
│   └── OutRec4 (孔洞, FirstLeft = OutRec1)
└── OutRec5 (外轮廓)

15.6 FixupFirstLefts 方法系列

15.6.1 FixupFirstLefts1

private void FixupFirstLefts1(OutRec OldOutRec, OutRec NewOutRec)
{ 
    foreach (OutRec outRec in m_PolyOuts)
    {
        OutRec firstLeft = ParseFirstLeft(outRec.FirstLeft);
        if (outRec.Pts != null && firstLeft == OldOutRec)
        {
            if (Poly2ContainsPoly1(outRec.Pts, NewOutRec.Pts))
                outRec.FirstLeft = NewOutRec;
        }
    }
}

当一个多边形被分割时，更新子多边形的 FirstLeft。

15.6.2 FixupFirstLefts2

private void FixupFirstLefts2(OutRec innerOutRec, OutRec outerOutRec)
{
    OutRec orfl = outerOutRec.FirstLeft;
    foreach (OutRec outRec in m_PolyOuts)
    {
        if (outRec.Pts == null || outRec == outerOutRec || outRec == innerOutRec) 
            continue;
        OutRec firstLeft = ParseFirstLeft(outRec.FirstLeft);
        if (firstLeft != orfl && firstLeft != innerOutRec && firstLeft != outerOutRec) 
            continue;
        if (Poly2ContainsPoly1(outRec.Pts, innerOutRec.Pts))
            outRec.FirstLeft = innerOutRec;
        else if (Poly2ContainsPoly1(outRec.Pts, outerOutRec.Pts))
            outRec.FirstLeft = outerOutRec;
        else if (outRec.FirstLeft == innerOutRec || outRec.FirstLeft == outerOutRec) 
            outRec.FirstLeft = orfl;
    }
}

当一个多边形被分割成内外两部分时使用。

15.6.3 FixupFirstLefts3

private void FixupFirstLefts3(OutRec OldOutRec, OutRec NewOutRec)
{
    foreach (OutRec outRec in m_PolyOuts)
    {
        OutRec firstLeft = ParseFirstLeft(outRec.FirstLeft);
        if (outRec.Pts != null && firstLeft == OldOutRec) 
            outRec.FirstLeft = NewOutRec;
    }
}

简单替换 FirstLeft 引用。

15.7 Poly2ContainsPoly1

判断一个多边形是否包含另一个：

private static bool Poly2ContainsPoly1(OutPt outPt1, OutPt outPt2)
{
    OutPt op = outPt1;
    do
    {
        int res = PointInPolygon(op.Pt, outPt2);
        if (res >= 0) return res > 0;
        op = op.Next;
    }
    while (op != outPt1);
    return true;
}

遍历第一个多边形的所有点，检查是否在第二个多边形内部。

15.8 PointInPolygon

点在多边形内判断：

public static int PointInPolygon(IntPoint pt, Path path)
{
    // returns 0 if false, +1 if true, -1 if pt ON polygon boundary
    int result = 0, cnt = path.Count;
    if (cnt < 3) return 0;
    IntPoint ip = path[0];
    
    for (int i = 1; i <= cnt; ++i)
    {
        IntPoint ipNext = (i == cnt ? path[0] : path[i]);
        
        if (ipNext.Y == pt.Y)
        {
            if ((ipNext.X == pt.X) || (ip.Y == pt.Y &&
                ((ipNext.X > pt.X) == (ip.X < pt.X)))) 
                return -1;  // 在边界上
        }
        
        if ((ip.Y < pt.Y) != (ipNext.Y < pt.Y))
        {
            if (ip.X >= pt.X)
            {
                if (ipNext.X > pt.X) 
                    result = 1 - result;
                else
                {
                    double d = (double)(ip.X - pt.X) * (ipNext.Y - pt.Y) -
                               (double)(ipNext.X - pt.X) * (ip.Y - pt.Y);
                    if (d == 0) return -1;
                    else if ((d > 0) == (ipNext.Y > ip.Y)) 
                        result = 1 - result;
                }
            }
            else
            {
                if (ipNext.X > pt.X)
                {
                    double d = (double)(ip.X - pt.X) * (ipNext.Y - pt.Y) -
                               (double)(ipNext.X - pt.X) * (ip.Y - pt.Y);
                    if (d == 0) return -1;
                    else if ((d > 0) == (ipNext.Y > ip.Y)) 
                        result = 1 - result;
                }
            }
        }
        ip = ipNext;
    }
    return result;
}

15.8.1 算法：射线法

从点发出水平射线，计算与多边形边的交叉次数：

• 奇数：内部
• 偶数：外部
• 在边上：返回 -1

15.9 方向修正

在 ExecuteInternal 的后处理阶段：

foreach (OutRec outRec in m_PolyOuts)
{
    if (outRec.Pts == null || outRec.IsOpen) continue;
    if ((outRec.IsHole ^ ReverseSolution) == (Area(outRec) > 0))
        ReversePolyPtLinks(outRec.Pts);
}

15.9.1 正确方向

15.10 BuildResult2 中的层次构建

private void BuildResult2(PolyTree polytree)
{
    polytree.Clear();

    // 第一遍：创建所有 PolyNode
    polytree.m_AllPolys.Capacity = m_PolyOuts.Count;
    for (int i = 0; i < m_PolyOuts.Count; i++)
    {
        OutRec outRec = m_PolyOuts[i];
        // ...
        FixHoleLinkage(outRec);
        PolyNode pn = new PolyNode();
        polytree.m_AllPolys.Add(pn);
        outRec.PolyNode = pn;
        // ... 填充顶点 ...
    }

    // 第二遍：建立父子关系
    polytree.m_Childs.Capacity = m_PolyOuts.Count;
    for (int i = 0; i < m_PolyOuts.Count; i++)
    {
        OutRec outRec = m_PolyOuts[i];
        if (outRec.PolyNode == null) continue;
        else if (outRec.IsOpen)
        {
            outRec.PolyNode.IsOpen = true;
            polytree.AddChild(outRec.PolyNode);
        }
        else if (outRec.FirstLeft != null && 
                 outRec.FirstLeft.PolyNode != null)
            outRec.FirstLeft.PolyNode.AddChild(outRec.PolyNode);
        else
            polytree.AddChild(outRec.PolyNode);
    }
}

15.11 使用示例

Clipper clipper = new Clipper();

// 添加带孔的多边形
Path outer = new Path();
outer.Add(new IntPoint(0, 0));
outer.Add(new IntPoint(200, 0));
outer.Add(new IntPoint(200, 200));
outer.Add(new IntPoint(0, 200));

Path hole = new Path();
hole.Add(new IntPoint(50, 50));
hole.Add(new IntPoint(50, 150));
hole.Add(new IntPoint(150, 150));
hole.Add(new IntPoint(150, 50));

clipper.AddPath(outer, PolyType.ptSubject, true);
clipper.AddPath(hole, PolyType.ptSubject, true);

// 使用 PolyTree 获取层次结构
PolyTree tree = new PolyTree();
clipper.Execute(ClipType.ctUnion, tree);

// 遍历结果
void ProcessNode(PolyNode node, int depth)
{
    string indent = new string(' ', depth * 2);
    if (node.Contour.Count > 0)
    {
        string type = node.IsHole ? "孔洞" : "外轮廓";
        Console.WriteLine($"{indent}{type}: {node.Contour.Count}点");
    }
    foreach (var child in node.Childs)
        ProcessNode(child, depth + 1);
}

ProcessNode(tree, 0);

15.12 本章小结

本章详细分析了 Clipper 的孔洞处理：

1. 孔洞识别：

   • 基于面积符号判断方向
   • SetHoleState 使用 AEL 计数

2. 层次关系：

   • FirstLeft 链建立父子关系
   • FixupFirstLefts 系列修复链接

3. 包含测试：

   • Poly2ContainsPoly1 判断包含
   • PointInPolygon 点在多边形内

4. 方向修正：

   • 确保外轮廓逆时针
   • 确保孔洞顺时针

5. 结果构建：

   • BuildResult2 构建 PolyTree
   • 保留完整的层次结构

上一章：输出多边形构建 | 返回目录 | 下一章：填充规则详解