第14章：输出多边形构建
14.1 概述
在 Clipper 处理过程中，输出多边形通过 OutRec 和 OutPt 数据结构逐步构建。本章将详细分析这些结构及其相关方法。
14.2 OutRec 结构
internal class OutRec
{internal int Idx; // 在 m_PolyOuts 中的索引internal bool IsHole; // 是否为孔洞internal bool IsOpen; // 是否为开放路径internal OutRec FirstLeft; // 第一个左侧轮廓（父轮廓）internal OutPt Pts; // 输出点链表头internal OutPt BottomPt; // 最底部的点internal PolyNode PolyNode; // 对应的 PolyNode（用于 PolyTree）
}
14.3 OutPt 结构
internal class OutPt
{internal int Idx; // 所属 OutRec 的索引internal IntPoint Pt; // 点坐标internal OutPt Next; // 下一个点internal OutPt Prev; // 上一个点
}
14.3.1 OutPt 链表结构
环形双向链表：┌──────────────────────────┐│ │▼ │OutPt1 ←──→ OutPt2 ←──→ OutPt3 ─┘▲ │└───────────┘Pts（入口点）
14.4 CreateOutRec
创建新的输出记录：
internal OutRec CreateOutRec()
{OutRec result = new OutRec();result.Idx = Unassigned;result.IsHole = false;result.IsOpen = false;result.FirstLeft = null;result.Pts = null;result.BottomPt = null;result.PolyNode = null;m_PolyOuts.Add(result);result.Idx = m_PolyOuts.Count - 1;return result;
}
14.5 AddOutPt
向输出多边形添加点：
internal OutPt AddOutPt(TEdge e, IntPoint pt)
{if (e.OutIdx < 0){// 创建新的输出记录OutRec outRec = CreateOutRec();outRec.IsOpen = (e.WindDelta == 0);OutPt newOp = new OutPt();outRec.Pts = newOp;newOp.Idx = outRec.Idx;newOp.Pt = pt;newOp.Next = newOp;newOp.Prev = newOp;if (!outRec.IsOpen)SetHoleState(e, outRec);e.OutIdx = outRec.Idx;return newOp;}else{// 添加到已有输出记录OutRec outRec = m_PolyOuts[e.OutIdx];OutPt op = outRec.Pts;bool ToFront = (e.Side == EdgeSide.esLeft);if (ToFront && pt == op.Pt) return op;else if (!ToFront && pt == op.Prev.Pt) return op.Prev;OutPt newOp = new OutPt();newOp.Idx = outRec.Idx;newOp.Pt = pt;newOp.Next = op;newOp.Prev = op.Prev;newOp.Prev.Next = newOp;op.Prev = newOp;if (ToFront) outRec.Pts = newOp;return newOp;}
}
14.5.1 添加点的两种情况
情况1: 新建输出记录边 e 没有关联的 OutRec→ 创建新 OutRec→ 创建第一个 OutPt→ 形成单点的循环链表情况2: 添加到已有记录边 e 已有关联的 OutRec→ 根据边的 Side 决定添加到头部还是尾部→ 插入新 OutPt 到链表
14.5.2 ToFront 判断
Side == esLeft → 添加到前面（Pts）
Side == esRight → 添加到后面（Pts.Prev）Pts│▼●───►●───►●───►●│ │└────◄────◄────◄─┘▲│Pts.Prev
14.6 AddLocalMinPoly
在局部极小值处创建新的输出多边形：
private OutPt AddLocalMinPoly(TEdge e1, TEdge e2, IntPoint pt)
{OutPt result;TEdge e, prevE;if (IsHorizontal(e2) || (e1.Dx > e2.Dx)){result = AddOutPt(e1, pt);e2.OutIdx = e1.OutIdx;e1.Side = EdgeSide.esLeft;e2.Side = EdgeSide.esRight;e = e1;if (e.PrevInAEL == e2)prevE = e2.PrevInAEL; elseprevE = e.PrevInAEL;}else{result = AddOutPt(e2, pt);e1.OutIdx = e2.OutIdx;e1.Side = EdgeSide.esRight;e2.Side = EdgeSide.esLeft;e = e2;if (e.PrevInAEL == e1)prevE = e1.PrevInAEL;elseprevE = e.PrevInAEL;}if (prevE != null && prevE.OutIdx >= 0 && prevE.Top.Y < pt.Y && e.Top.Y < pt.Y){cInt xPrev = TopX(prevE, pt.Y);cInt xE = TopX(e, pt.Y);if ((xPrev == xE) && (e.WindDelta != 0) && (prevE.WindDelta != 0) &&SlopesEqual(new IntPoint(xPrev, pt.Y), prevE.Top, new IntPoint(xE, pt.Y), e.Top, m_UseFullRange)){OutPt outPt = AddOutPt(prevE, pt);AddJoin(result, outPt, e.Top);}}return result;
}
14.6.1 局部极小值图解
╲ ╱╲ pt ╱╲ ╱e1 ╲ ╱ e2╲╱极小值点创建 OutRec:
- e1 设为左边界（Side = esLeft）
- e2 设为右边界（Side = esRight）
- 两边共享同一个 OutIdx
14.7 AddLocalMaxPoly
在局部极大值处关闭输出多边形：
private void AddLocalMaxPoly(TEdge e1, TEdge e2, IntPoint pt)
{AddOutPt(e1, pt);if (e2.WindDelta == 0) AddOutPt(e2, pt);if (e1.OutIdx == e2.OutIdx){e1.OutIdx = Unassigned;e2.OutIdx = Unassigned;}else if (e1.OutIdx < e2.OutIdx) AppendPolygon(e1, e2);else AppendPolygon(e2, e1);
}
14.7.1 局部极大值图解
╱╲╱ ╲e1 ╱ ╲ e2╱ pt ╲╱ ╲极大值点处理:
- 添加点 pt 到输出
- 如果两边属于同一输出，关闭多边形
- 如果属于不同输出，合并它们
14.8 AppendPolygon
合并两个输出多边形：
private void AppendPolygon(TEdge e1, TEdge e2)
{OutRec outRec1 = m_PolyOuts[e1.OutIdx];OutRec outRec2 = m_PolyOuts[e2.OutIdx];OutRec holeStateRec;if (OutRec1RightOfOutRec2(outRec1, outRec2)) holeStateRec = outRec2;else if (OutRec1RightOfOutRec2(outRec2, outRec1)) holeStateRec = outRec1;else holeStateRec = GetLowermostRec(outRec1, outRec2);// 获取两个输出的点OutPt p1_lft = outRec1.Pts;OutPt p1_rt = p1_lft.Prev;OutPt p2_lft = outRec2.Pts;OutPt p2_rt = p2_lft.Prev;// 根据边的 Side 连接if (e1.Side == EdgeSide.esLeft){if (e2.Side == EdgeSide.esLeft){// 反转 p2 并连接ReversePolyPtLinks(p2_lft);p2_lft.Next = p1_lft;p1_lft.Prev = p2_lft;p1_rt.Next = p2_rt;p2_rt.Prev = p1_rt;outRec1.Pts = p2_rt;}else{// 直接连接p2_rt.Next = p1_lft;p1_lft.Prev = p2_rt;p2_lft.Prev = p1_rt;p1_rt.Next = p2_lft;outRec1.Pts = p2_lft;}}else{if (e2.Side == EdgeSide.esRight){ReversePolyPtLinks(p2_lft);p1_rt.Next = p2_rt;p2_rt.Prev = p1_rt;p2_lft.Next = p1_lft;p1_lft.Prev = p2_lft;}else{p1_rt.Next = p2_lft;p2_lft.Prev = p1_rt;p1_lft.Prev = p2_rt;p2_rt.Next = p1_lft;}}outRec1.BottomPt = null;// 更新孔洞状态if (holeStateRec == outRec2){if (outRec2.FirstLeft != outRec1)outRec1.FirstLeft = outRec2.FirstLeft;outRec1.IsHole = outRec2.IsHole;}// 清理 outRec2outRec2.Pts = null;outRec2.BottomPt = null;outRec2.FirstLeft = outRec1;int OKIdx = e1.OutIdx;int ObsoleteIdx = e2.OutIdx;e1.OutIdx = Unassigned;e2.OutIdx = Unassigned;// 更新所有引用 ObsoleteIdx 的边TEdge e = m_ActiveEdges;while (e != null){if (e.OutIdx == ObsoleteIdx){e.OutIdx = OKIdx;e.Side = e1.Side;}e = e.NextInAEL;}outRec2.Idx = outRec1.Idx;
}
14.9 ReversePolyPtLinks
反转点链表的方向：
private void ReversePolyPtLinks(OutPt pp)
{if (pp == null) return;OutPt pp1;OutPt pp2;pp1 = pp;do{pp2 = pp1.Next;pp1.Next = pp1.Prev;pp1.Prev = pp2;pp1 = pp2;} while (pp1 != pp);
}
14.10 FixupOutPolygon
清理输出多边形（移除重复点和共线边）：
private void FixupOutPolygon(OutRec outRec)
{OutPt lastOK = null;outRec.BottomPt = null;OutPt pp = outRec.Pts;bool preserveCol = PreserveCollinear || StrictlySimple;for (;;){if (pp.Prev == pp || pp.Prev == pp.Next){outRec.Pts = null;return;}// 检查重复点和共线边if ((pp.Pt == pp.Next.Pt) || (pp.Pt == pp.Prev.Pt) ||(SlopesEqual(pp.Prev.Pt, pp.Pt, pp.Next.Pt, m_UseFullRange) &&(!preserveCol || !Pt2IsBetweenPt1AndPt3(pp.Prev.Pt, pp.Pt, pp.Next.Pt)))){lastOK = null;// 移除当前点pp.Prev.Next = pp.Next;pp.Next.Prev = pp.Prev;pp = pp.Prev;}else if (pp == lastOK) break;else{if (lastOK == null) lastOK = pp;pp = pp.Next;}}outRec.Pts = pp;
}
14.11 GetOutRec
获取最终的输出记录（处理合并情况）：
private OutRec GetOutRec(int idx)
{OutRec outrec = m_PolyOuts[idx];while (outrec != m_PolyOuts[outrec.Idx])outrec = m_PolyOuts[outrec.Idx];return outrec;
}
14.12 UpdateOutPtIdxs
更新输出点的索引：
private void UpdateOutPtIdxs(OutRec outrec)
{ OutPt op = outrec.Pts;do{op.Idx = outrec.Idx;op = op.Prev;}while (op != outrec.Pts);
}
14.13 PointCount
计算输出多边形的点数：
private int PointCount(OutPt pts)
{if (pts == null) return 0;int result = 0;OutPt p = pts;do{result++;p = p.Next;}while (p != pts);return result;
}
14.14 输出构建流程
1. 局部极小值 → AddLocalMinPoly创建新的 OutRec 和初始点2. 边处理 → AddOutPt逐步添加点到输出多边形3. 局部极大值 → AddLocalMaxPoly关闭多边形或合并多边形4. 后处理 → FixupOutPolygon清理重复点和共线边5. 构建结果 → BuildResult/BuildResult2转换为最终的 Paths 或 PolyTree
14.15 本章小结
本章详细分析了 Clipper 的输出多边形构建：
-
数据结构：
- OutRec：输出记录
- OutPt：输出点链表
-
核心方法：
- AddOutPt：添加点
- AddLocalMinPoly：极小值创建
- AddLocalMaxPoly：极大值关闭
- AppendPolygon：合并多边形
-
后处理：
- FixupOutPolygon：清理输出
- BuildResult：构建最终结果
理解输出构建对于理解 Clipper 的完整工作流程至关重要。
上一章：水平边处理 | 返回目录 | 下一章：孔洞检测与处理