OutRec与OutPt输出结构是什么？
摘要：layout: default title: 第11章：OutRec 与 OutPt 输出结构 第11章：OutRec 与 OutPt 输出结构 11.1 概述 当 Clipper2 的扫描线算法处理多边形时，需要构建输出多边形。OutRe
第11章：OutRec 与 OutPt 输出结构
11.1 概述
当 Clipper2 的扫描线算法处理多边形时，需要构建输出多边形。OutRec（输出记录）和 OutPt（输出点）是用于存储和构建输出多边形的核心数据结构。
11.2 OutPt 类
11.2.1 类定义
internal class OutPt
{
public Point64 pt; // 点坐标
public OutPt? next; // 下一个输出点
public OutPt? prev; // 上一个输出点
public OutRec outrec; // 所属的输出记录
public Joiner? joiner; // 连接器（用于处理自相交）
}
11.2.2 双向循环链表
与 Vertex 类似，OutPt 形成双向循环链表：
op1 ←→ op2 ←→ op3 ←→ op4 ←→ op1
│ │
└─────────────────────────┘
11.2.3 OutPt vs Vertex
特性
Vertex
OutPt
用途
输入多边形
输出多边形
内容
pt, flags
pt, outrec, joiner
创建时机
预处理阶段
扫描线处理中
数量
与输入相同
可能更多（交点）
11.3 OutRec 类
11.3.1 类定义
internal class OutRec
{
public int idx; // 索引
public OutRec? owner; // 所有者（外轮廓）
public Active? frontEdge; // 前边
public Active? backEdge; // 后边
public OutPt? pts; // 输出点链表
public PolyPath64? polypath; // 多边形树路径
public Rect64 bounds; // 边界矩形
public Path64? path; // 最终路径
public bool isOpen; // 是否开放路径
public List<OutRec?>? splits; // 分割记录
public OutRec? recursiveSplit; // 递归分割
}
11.3.2 成员详解
成员
类型
说明
idx
int
在 outrecList 中的索引
owner
OutRec?
父轮廓（包含此轮廓的外轮廓）
frontEdge
Active?
当前构建的前边
backEdge
Active?
当前构建的后边
pts
OutPt?
输出点链表的头
bounds
Rect64
计算后的边界框
isOpen
bool
是否为开放路径
11.3.3 Owner 关系
外轮廓 (OutRec A, owner = null)
├── 孔洞 (OutRec B, owner = A)
│ └── 岛屿 (OutRec C, owner = B)
└── 孔洞 (OutRec D, owner = A)
11.4 创建 OutRec
11.4.1 CreateOutRec 方法
[MethodImpl(MethodImplOptions.AggressiveInlining)]
private OutRec CreateOutRec()
{
OutRec result = _outRecPool.Get();
result.idx = _outrecList.Count;
result.owner = null;
result.frontEdge = null;
result.backEdge = null;
result.pts = null;
result.polypath = null;
result.isOpen = false;
result.splits = null;
result.recursiveSplit = null;
_outrecList.Add(result);
return result;
}
11.4.2 对象池使用
// 获取
OutRec outrec = _outRecPool.Get();
// 归还
_outRecPool.Return(outrec);
11.5 创建 OutPt
11.5.1 AddOutPt 方法
private OutPt AddOutPt(Active ae, Point64 pt)
{
OutPt newOp = _outPtPool.Get();
newOp.pt = pt;
newOp.joiner = null;
newOp.outrec = ae.outrec!;
OutPt? op = ae.outrec!.pts;
if (op == null)
{
// 第一个点
newOp.next = newOp;
newOp.prev = newOp;
ae.outrec.pts = newOp;
}
else if (ae == ae.outrec.frontEdge)
{
// 添加到前端
newOp.next = op;
newOp.prev = op.prev;
op.prev!.next = newOp;
op.prev = newOp;
ae.outrec.pts = newOp;
}
else
{
// 添加到后端
newOp.prev = op;
newOp.next = op.next;
op.next!.prev = newOp;
op.next = newOp;
}
return newOp;
}
11.5.2 插入位置示意
前端插入 (frontEdge):
新点 → pts → op2 → op3 → ...
后端插入 (backEdge):
pts → 新点 → op2 → op3 → ...
11.6 构建输出多边形
11.6.1 StartOutRec 方法
private void StartOutRec(Active ae1, Active ae2)
{
OutRec outrec = CreateOutRec();
// 设置边关联
ae1.outrec = outrec;
ae2.outrec = outrec;
SetOwner(outrec, ae1, ae2);
// 确定前后边
if (ae1.curX <= ae2.curX)
{
outrec.frontEdge = ae1;
outrec.backEdge = ae2;
}
else
{
outrec.frontEdge = ae2;
outrec.backEdge = ae1;
}
}
11.6.2 AddLocalMinPoly
private OutPt? AddLocalMinPoly(Active ae1, Active ae2, Point64 pt,
bool isNew = false)
{
OutRec outrec;
if (isNew)
{
outrec = CreateOutRec();
outrec.isOpen = IsOpen(ae1);
// 设置边
if (ae1.curX <= ae2.curX)
{
outrec.frontEdge = ae1;
outrec.backEdge = ae2;
}
else
{
outrec.frontEdge = ae2;
outrec.backEdge = ae1;
}
ae1.outrec = outrec;
ae2.outrec = outrec;
}
else
{
outrec = ae1.outrec!;
}
OutPt op = AddOutPt(ae1, pt);
if (!isNew)
{
// 处理合并情况
AddOutPt(ae2, pt);
}
return op;
}
11.6.3 AddLocalMaxPoly
private void AddLocalMaxPoly(Active ae1, Active ae2, Point64 pt)
{
AddOutPt(ae1, pt);
if (ae1.outrec == ae2.outrec)
{
// 同一个 OutRec，闭合多边形
ae1.outrec!.frontEdge = null;
ae1.outrec.backEdge = null;
ae1.outrec = null;
ae2.outrec = null;
}
else
{
// 合并两个 OutRec
MergeOutRecs(ae1, ae2);
}
}
11.7 Owner 设置
11.7.1 SetOwner 方法
private void SetOwner(OutRec outrec, Active ae1, Active ae2)
{
// 查找有效的 owner
OutRec? owner = null;
// 尝试从 ae1 的左侧边找 owner
Active? ae = ae1.prevInAEL;
while (ae != null)
{
if (ae.outrec != null && !ae.outrec.isOpen)
{
owner = ae.outrec;
break;
}
ae = ae.prevInAEL;
}
outrec.owner = GetRealOwner(owner);
}
11.7.2 确定嵌套关系
private OutRec? GetRealOwner(OutRec? outrec)
{
while (outrec != null && outrec.pts == null)
outrec = outrec.owner;
return outrec;
}
11.8 OutRec 合并
11.8.1 MergeOutRecs 方法
private void MergeOutRecs(Active ae1, Active ae2)
{
OutRec? outrec1 = ae1.outrec;
OutRec? outrec2 = ae2.outrec;
if (outrec1 == null || outrec2 == null) return;
if (outrec1 == outrec2) return;
// 确定哪个是 owner
OutRec? keepRec, discardRec;
if (outrec1.idx < outrec2.idx)
{
keepRec = outrec1;
discardRec = outrec2;
}
else
{
keepRec = outrec2;
discardRec = outrec1;
}
// 合并点链表
MergePaths(keepRec, discardRec);
// 更新引用
discardRec.pts = null;
discardRec.owner = keepRec;
ae2.outrec = keepRec;
}
11.8.2 MergePaths 合并点链表
private void MergePaths(OutRec keep, OutRec discard)
{
OutPt op1 = keep.pts!;
OutPt op2 = discard.pts!;
// 连接两个环
OutPt op1Last = op1.prev!;
OutPt op2Last = op2.prev!;
op1Last.next = op2;
op2.prev = op1Last;
op2Last.next = op1;
op1.prev = op2Last;
// 更新所有点的 outrec
OutPt op = op2;
do
{
op.outrec = keep;
op = op.next!;
} while (op != op2);
}
11.9 边界计算
11.9.1 GetBounds 方法
internal static Rect64 GetBounds(OutPt op)
{
Rect64 result = new Rect64(
long.MaxValue, long.MaxValue,
long.MinValue, long.MinValue);
OutPt op2 = op;
do
{
if (op2.pt.X < result.left) result.left = op2.pt.X;
if (op2.pt.X > result.right) result.right = op2.pt.X;
if (op2.pt.Y < result.top) result.top = op2.pt.Y;
if (op2.pt.Y > result.bottom) result.bottom = op2.pt.Y;
op2 = op2.next!;
} while (op2 != op);
return result;
}
11.10 Joiner 连接器
11.10.1 Joiner 类
internal class Joiner
{
public int idx;
public OutPt op1;
public OutPt? op2;
public Joiner? next1;
public Joiner? next2;
}
11.10.2 用途
Joiner 用于处理自相交多边形的连接：
●───────●
╱ ╲ ╱
╱ ╲ ╱
╱ ╲ ╱
●───────●──────●
交点需要 Joiner 处理
11.10.3 创建 Joiner
private void AddJoin(OutPt op1, OutPt op2)
{
Joiner joiner = new Joiner
{
idx = _joinerList.Count,
op1 = op1,
op2 = op2,
next1 = op1.joiner,
next2 = op2.joiner
};
op1.joiner = joiner;
op2.joiner = joiner;
_joinerList.Add(joiner);
}
11.11 路径构建
11.11.1 BuildPath 方法
private Path64? BuildPath(OutPt op, bool reverse, bool isOpen)
{
int cnt = CountOutPts(op);
if (cnt < 2) return null;
if (!isOpen && cnt < 3) return null;
Path64 result = new Path64(cnt);
OutPt op2 = op;
if (reverse)
{
do
{
result.Add(op2.pt);
op2 = op2.prev!;
} while (op2 != op);
}
else
{
do
{
result.Add(op2.pt);
op2 = op2.next!;
} while (op2 != op);
}
return result;
}
11.11.2 CountOutPts
[MethodImpl(MethodImplOptions.AggressiveInlining)]
private static int CountOutPts(OutPt op)
{
int result = 0;
OutPt op2 = op;
do
{
result++;
op2 = op2.next!;
} while (op2 != op);
return result;
}
11.12 清理输出点
11.12.1 CleanCollinear 方法
private void CleanCollinear(OutRec outrec)
{
OutPt? op = outrec.pts;
if (op == null) return;
OutPt startOp = op;
OutPt? op2;
do
{
op2 = op;
// 跳过重复点
while (op2.next != startOp && op2.pt == op2.next!.pt)
{
DisposeOutPt(op2.next);
}
// 移除共线点
if (op2.prev != op2.next &&
InternalClipper.IsCollinear(op2.prev!.pt, op2.pt, op2.next!.pt))
{
if (op2 == outrec.pts)
outrec.pts = op2.prev;
DisposeOutPt(op2);
op2 = op2.prev;
if (op2 == outrec.pts) startOp = op2;
}
else
{
op2 = op2.next;
}
} while (op2 != startOp);
}
11.12.2 DisposeOutPt
[MethodImpl(MethodImplOptions.AggressiveInlining)]
private void DisposeOutPt(OutPt op)
{
op.prev!.next = op.next;
op.next!.prev = op.prev;
_outPtPool.Return(op);
}
11.13 分割处理
11.13.1 splits 列表
public List<OutRec?>? splits;
当一个 OutRec 因为自相交而分割时，splits 记录子记录。
11.13.2 CheckSplitOwner
private void CheckSplitOwner(OutRec outrec)
{
if (outrec.splits == null) return;
foreach (OutRec? split in outrec.splits)
{
if (split != null && split.pts != null)
{
// 处理分割后的多边形
ProcessSplit(split);
}
}
}
11.14 本章小结
OutRec 和 OutPt 是 Clipper2 输出多边形的核心结构：
OutPt：
输出点，形成双向循环链表
包含坐标、链接和所属 OutRec
使用对象池管理
OutRec：
输出记录，表示一个输出多边形
维护点链表和边界信息
owner 字段建立嵌套关系
关键操作：
创建和添加输出点
合并和分割 OutRec
清理共线点
构建最终路径
Joiner：
处理自相交情况
连接需要合并的点
理解输出结构是理解 Clipper2 如何生成最终结果的关键。
上一章：Vertex与LocalMinima | 返回目录 | 下一章：Clipper64裁剪类详解