第19章：辅助函数与工具方法
19.1 概述
Clipper 库提供了许多辅助函数和工具方法，用于简化多边形操作和处理。本章将分析这些实用功能。
19.2 SimplifyPolygon/SimplifyPolygons
简化多边形，消除自相交：
public static Paths SimplifyPolygon(Path poly,
PolyFillType fillType = PolyFillType.pftEvenOdd)
{
Paths result = new Paths();
Clipper c = new Clipper();
c.StrictlySimple = true;
c.AddPath(poly, PolyType.ptSubject, true);
c.Execute(ClipType.ctUnion, result, fillType, fillType);
return result;
}
public static Paths SimplifyPolygons(Paths polys,
PolyFillType fillType = PolyFillType.pftEvenOdd)
{
Paths result = new Paths();
Clipper c = new Clipper();
c.StrictlySimple = true;
c.AddPaths(polys, PolyType.ptSubject, true);
c.Execute(ClipType.ctUnion, result, fillType, fillType);
return result;
}
19.2.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));
// 简化为两个独立的三角形
Paths simplified = Clipper.SimplifyPolygon(figure8);
// 结果：两个三角形
19.3 CleanPolygon/CleanPolygons
清理多边形，移除冗余顶点：
public static Path CleanPolygon(Path path, double distance = 1.415)
{
int cnt = path.Count;
if (cnt == 0) return new Path();
OutPt[] outPts = new OutPt[cnt];
for (int i = 0; i < cnt; ++i)
outPts[i] = new OutPt();
// 建立链表
for (int i = 0; i < cnt; ++i)
{
outPts[i].Pt = path[i];
outPts[i].Next = outPts[(i + 1) % cnt];
outPts[i].Next.Prev = outPts[i];
outPts[i].Idx = 0;
}
double distSqrd = distance * distance;
OutPt op = outPts[0];
while (op.Idx == 0 && op.Next != op.Prev)
{
if (PointsAreClose(op.Pt, op.Prev.Pt, distSqrd))
{
op = ExcludeOp(op);
cnt--;
}
else if (PointsAreClose(op.Prev.Pt, op.Next.Pt, distSqrd))
{
ExcludeOp(op.Next);
op = ExcludeOp(op);
cnt -= 2;
}
else if (SlopesNearCollinear(op.Prev.Pt, op.Pt, op.Next.Pt, distSqrd))
{
op = ExcludeOp(op);
cnt--;
}
else
{
op.Idx = 1;
op = op.Next;
}
}
if (cnt < 3) cnt = 0;
Path result = new Path(cnt);
for (int i = 0; i < cnt; ++i)
{
result.Add(op.Pt);
op = op.Next;
}
return result;
}
19.3.1 清理规则
- 重复点：距离小于阈值的连续点
- 尖刺：前后点距离太近
- 共线点：在直线上的中间点
19.3.2 使用示例
Path noisy = new Path();
noisy.Add(new IntPoint(0, 0));
noisy.Add(new IntPoint(1, 0)); // 太近
noisy.Add(new IntPoint(100, 0));
noisy.Add(new IntPoint(100, 100));
noisy.Add(new IntPoint(50, 50)); // 共线的中间点
noisy.Add(new IntPoint(0, 0));
Path cleaned = Clipper.CleanPolygon(noisy, 2.0);
// 结果：移除冗余点后的简化多边形
19.4 MinkowskiSum/MinkowskiDiff
闵可夫斯基和与差：
public static Paths MinkowskiSum(Path pattern, Path path, bool pathIsClosed)
{
Paths paths = Minkowski(pattern, path, true, pathIsClosed);
Clipper c = new Clipper();
c.AddPaths(paths, PolyType.ptSubject, true);
c.Execute(ClipType.ctUnion, paths,
PolyFillType.pftNonZero, PolyFillType.pftNonZero);
return paths;
}
public static Paths MinkowskiDiff(Path poly1, Path poly2)
{
Paths paths = Minkowski(poly1, poly2, false, true);
Clipper c = new Clipper();
c.AddPaths(paths, PolyType.ptSubject, true);
c.Execute(ClipType.ctUnion, paths,
PolyFillType.pftNonZero, PolyFillType.pftNonZero);
return paths;
}
19.4.1 Minkowski 核心方法
private static Paths Minkowski(Path pattern, Path path, bool IsSum, bool IsClosed)
{
int delta = (IsClosed ? 1 : 0);
int polyCnt = pattern.Count;
int pathCnt = path.Count;
Paths result = new Paths(pathCnt);
if (IsSum)
for (int i = 0; i < pathCnt; i++)
{
Path p = new Path(polyCnt);
foreach (IntPoint ip in pattern)
p.Add(new IntPoint(path[i].X + ip.X, path[i].Y + ip.Y));
result.Add(p);
}
else
for (int i = 0; i < pathCnt; i++)
{
Path p = new Path(polyCnt);
foreach (IntPoint ip in pattern)
p.Add(new IntPoint(path[i].X - ip.X, path[i].Y - ip.Y));
result.Add(p);
}
// 构建四边形连接
Paths quads = new Paths((pathCnt + delta) * (polyCnt + 1));
for (int i = 0; i < pathCnt - 1 + delta; i++)
for (int j = 0; j < polyCnt; j++)
{
Path quad = new Path(4);
quad.Add(result[i % pathCnt][j % polyCnt]);
quad.Add(result[(i + 1) % pathCnt][j % polyCnt]);
quad.Add(result[(i + 1) % pathCnt][(j + 1) % polyCnt]);
quad.Add(result[i % pathCnt][(j + 1) % polyCnt]);
if (!Orientation(quad)) quad.Reverse();
quads.Add(quad);
}
return quads;
}
19.4.2 闵可夫斯基和的应用
// 圆形膨胀效果
Path circle = CreateCircle(0, 0, 10, 16);
Path shape = CreateSquare(50, 50, 100);
Paths expanded = Clipper.MinkowskiSum(circle, shape, true);
// 结果：圆角正方形
19.5 Area 方法
计算有符号面积：
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;
}
19.5.1 鞋带公式
面积 = (1/2) * |Σ(x[i]*y[i+1] - x[i+1]*y[i])|
简化形式（代码使用）：
面积 = -(1/2) * Σ((x[j]+x[i])*(y[j]-y[i]))
19.5.2 使用示例
Path triangle = new Path();
triangle.Add(new IntPoint(0, 0));
triangle.Add(new IntPoint(100, 0));
triangle.Add(new IntPoint(50, 100));
double area = Clipper.Area(triangle);
// 结果：5000（正值=逆时针）
triangle.Reverse();
area = Clipper.Area(triangle);
// 结果：-5000（负值=顺时针）
19.6 Orientation 方法
判断多边形方向：
public static bool Orientation(Path poly)
{
return Area(poly) >= 0;
}
true：逆时针（外轮廓）false：顺时针（孔洞）
19.7 ReversePath/ReversePaths
反转路径方向：
public static void ReversePath(Path p)
{
p.Reverse();
}
public static void ReversePaths(Paths polys)
{
foreach (var poly in polys)
{
poly.Reverse();
}
}
19.8 PointInPolygon
点在多边形内判断：
public static int PointInPolygon(IntPoint pt, Path path)
{
// 返回值：
// 0 = 外部
// 1 = 内部
// -1 = 在边界上
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;
}
19.9 DistanceSqrd 和 DistanceFromLineSqrd
距离计算辅助函数：
private static double DistanceSqrd(IntPoint pt1, IntPoint pt2)
{
double dx = ((double)pt1.X - pt2.X);
double dy = ((double)pt1.Y - pt2.Y);
return (dx * dx + dy * dy);
}
private static double DistanceFromLineSqrd(IntPoint pt, IntPoint ln1, IntPoint ln2)
{
// 点到线段的距离的平方
double A = ln1.Y - ln2.Y;
double B = ln2.X - ln1.X;
double C = A * ln1.X + B * ln1.Y;
C = A * pt.X + B * pt.Y - C;
return (C * C) / (A * A + B * B);
}
19.10 Round 函数
安全的四舍五入：
internal static cInt Round(double value)
{
return value < 0 ? (cInt)(value - 0.5) : (cInt)(value + 0.5);
}
19.11 Swap 方法
交换两个值：
private static void Swap(ref cInt val1, ref cInt val2)
{
cInt tmp = val1;
val1 = val2;
val2 = tmp;
}
19.12 near_zero
浮点数零值判断：
internal static bool near_zero(double val)
{
return (val > -tolerance) && (val < tolerance);
}
19.13 使用示例集合
19.13.1 完整的工作流程
// 1. 创建多边形
Path polygon = new Path();
polygon.Add(new IntPoint(0, 0));
polygon.Add(new IntPoint(100, 0));
polygon.Add(new IntPoint(100, 100));
polygon.Add(new IntPoint(0, 100));
// 2. 清理
polygon = Clipper.CleanPolygon(polygon);
// 3. 检查方向
if (!Clipper.Orientation(polygon))
polygon.Reverse();
// 4. 计算面积
double area = Clipper.Area(polygon);
Console.WriteLine($"面积: {area}");
// 5. 点在多边形内测试
IntPoint testPt = new IntPoint(50, 50);
int result = Clipper.PointInPolygon(testPt, polygon);
Console.WriteLine($"点在内部: {result == 1}");
19.13.2 批量处理
// 处理多个多边形
Paths polygons = LoadPolygons();
// 清理所有
for (int i = 0; i < polygons.Count; i++)
polygons[i] = Clipper.CleanPolygon(polygons[i]);
// 简化（消除自相交）
polygons = Clipper.SimplifyPolygons(polygons);
// 计算总面积
double totalArea = 0;
foreach (var poly in polygons)
totalArea += Math.Abs(Clipper.Area(poly));
19.14 本章小结
本章介绍了 Clipper 库的辅助函数和工具方法：
- 简化函数：SimplifyPolygon 消除自相交
- 清理函数：CleanPolygon 移除冗余顶点
- 闵可夫斯基运算：MinkowskiSum/MinkowskiDiff
- 几何计算：Area、Orientation、PointInPolygon
- 辅助工具：距离计算、四舍五入、交换等
这些工具方法在实际应用中非常有用，可以简化多边形处理流程。
| 上一章：偏移算法实现 | 返回目录 | 下一章：实际应用与最佳实践 |