第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 清理规则

1. 重复点：距离小于阈值的连续点
2. 尖刺：前后点距离太近
3. 共线点：在直线上的中间点

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 库的辅助函数和工具方法：

1. 简化函数：SimplifyPolygon 消除自相交
2. 清理函数：CleanPolygon 移除冗余顶点
3. 闵可夫斯基运算：MinkowskiSum/MinkowskiDiff
4. 几何计算：Area、Orientation、PointInPolygon
5. 辅助工具：距离计算、四舍五入、交换等

这些工具方法在实际应用中非常有用，可以简化多边形处理流程。

上一章：偏移算法实现 | 返回目录 | 下一章：实际应用与最佳实践