如何用多条直线分割多边形？现有算法性能待优化

问题背景 #

我有一个由Vector2点列表定义的多边形，以及一系列用于分割它的直线（同样由Vector2点列表定义）。已实现Split()函数，可通过单条直线分割单个多边形并返回分割后的多边形列表，若未生成新多边形则返回null。

当前使用的SliceMany()函数用于处理单条直线对多多边形的分割，但存在以下问题：

• 速度极慢且不具备可扩展性
• 生成大量“冗余多边形”，即已被分割为更小多边形的无用原多边形

我使用Unity开发，还具备检测重叠多边形的函数，但尚未找到有效利用它的方法。目标是仅保留完全分割后的最终多边形，不保留任何原多边形，恳请提供优化建议。

当前实现的SliceMany()代码：

public static List<List<Vector2>> SliceMany(List<List<Vector2>> ps, Vector2 a, Vector2 b)
{
    List<List<Vector2>> result = new List<List<Vector2>>();
    for(int i = 0; i < ps.Count; i++)
    {
        List<List<Vector2>> sliced = Slice(ps[i], a, b);
        if(sliced != null)
        {
            if (sliced.Count > 1)
            {
                result.AddRange(sliced);
            }
            else
            {
                result.Add(ps[i]);
            }
        }
    }
    return result;
}

优化建议 #

1. 修复冗余多边形生成逻辑 #

当前代码中，当Slice()返回单元素列表时回退添加原多边形，这是冗余的核心来源。调整逻辑：只要Slice()返回非null结果，就直接添加分割后的所有多边形；若返回null（直线未分割该多边形），才保留原多边形。同时结合后续的冗余清理步骤，彻底移除已被分割的原多边形。

2. 性能优化措施 #

• 快速预过滤：用多边形包围盒做前置检测，若直线完全在包围盒外，直接跳过该多边形的分割操作，避免调用Slice()的不必要开销。
• 内存复用：在Unity中使用ListPool<T>复用列表对象，减少GC开销；预先分配结果列表的容量（比如按当前多边形数量的1.5倍预估），避免频繁内存扩容。
• 并行处理：若多边形数量较多，可使用Unity的Job System或C#的Parallel.For并行处理多个多边形的分割，充分利用多核CPU资源。

3. 利用重叠检测清理冗余 #

在所有分割步骤完成后，遍历多边形列表，结合已有重叠检测函数，移除被分割后的原多边形：

• 检测每个多边形是否被其他更小的多边形完全包含（通过面积对比+顶点包含检测）
• 倒序遍历列表，避免移除元素时的索引错乱问题

修改后的示例代码 #

public static List<List<Vector2>> SliceMany(List<List<Vector2>> polygons, Vector2 lineStart, Vector2 lineEnd)
{
    // 预分配结果列表容量，减少内存扩容
    List<List<Vector2>> result = new List<List<Vector2>>(polygons.Count);
    foreach (var poly in polygons)
    {
        // 快速包围盒检测，跳过不可能被分割的多边形
        Bounds polyBounds = GetPolygonBounds(poly);
        if (!LineIntersectsBounds(lineStart, lineEnd, polyBounds))
        {
            result.Add(poly);
            continue;
        }

        var sliced = Slice(poly, lineStart, lineEnd);
        if (sliced != null)
        {
            result.AddRange(sliced);
        }
        else
        {
            result.Add(poly);
        }
    }
    // 清理冗余多边形
    CleanRedundantPolygons(result);
    return result;
}

// 获取多边形的包围盒
private static Bounds GetPolygonBounds(List<Vector2> polygon)
{
    Bounds bounds = new Bounds(polygon[0], Vector2.zero);
    for (int i = 1; i < polygon.Count; i++)
    {
        bounds.Encapsulate(polygon[i]);
    }
    return bounds;
}

// 判断直线是否与包围盒相交（简化版分离轴定理）
private static bool LineIntersectsBounds(Vector2 a, Vector2 b, Bounds bounds)
{
    Vector2 center = bounds.center;
    Vector2 halfExtents = bounds.extents;
    Vector2 dir = b - a;
    Vector2 halfDir = dir * 0.5f;
    Vector2 centerToA = a - center;
    float maxDist = halfExtents.x + halfExtents.y;

    float dot = Mathf.Abs(Vector2.Dot(centerToA, Vector2.right)) + Mathf.Abs(Vector2.Dot(centerToA, Vector2.up));
    if (dot > maxDist + Mathf.Abs(Vector2.Dot(halfDir, Vector2.right)) + Mathf.Abs(Vector2.Dot(halfDir, Vector2.up)))
    {
        return false;
    }
    return true;
}

// 清理被分割后的原多边形
private static void CleanRedundantPolygons(List<List<Vector2>> polygons)
{
    // 倒序遍历避免索引错乱
    for (int i = polygons.Count - 1; i >= 0; i--)
    {
        var current = polygons[i];
        bool isRedundant = false;
        float currentArea = GetPolygonArea(current);
        
        for (int j = 0; j < polygons.Count; j++)
        {
            if (i == j) continue;
            var other = polygons[j];
            float otherArea = GetPolygonArea(other);
            
            // 若当前多边形面积更大，且所有顶点都在另一个多边形内部，判定为冗余
            if (currentArea > otherArea && CheckPolygonIsContained(current, other))
            {
                isRedundant = true;
                break;
            }
        }
        if (isRedundant)
        {
            polygons.RemoveAt(i);
        }
    }
}

// 计算多边形面积
private static float GetPolygonArea(List<Vector2> polygon)
{
    float area = 0;
    int count = polygon.Count;
    for (int i = 0; i < count; i++)
    {
        int j = (i + 1) % count;
        area += polygon[i].x * polygon[j].y - polygon[j].x * polygon[i].y;
    }
    return Mathf.Abs(area) * 0.5f;
}

// 检测一个多边形是否完全被另一个多边形包含
private static bool CheckPolygonIsContained(List<Vector2> inner, List<Vector2> outer)
{
    foreach (var point in inner)
    {
        if (!PointInPolygon(point, outer))
        {
            return false;
        }
    }
    return true;
}

// 点是否在多边形内部的检测函数
private static bool PointInPolygon(Vector2 point, List<Vector2> polygon)
{
    bool inside = false;
    int count = polygon.Count;
    for (int i = 0, j = count - 1; i < count; j = i++)
    {
        if (((polygon[i].y > point.y) != (polygon[j].y > point.y)) &&
            (point.x < (polygon[j].x - polygon[i].x) * (point.y - polygon[i].y) / (polygon[j].y - polygon[i].y) + polygon[i].x))
        {
            inside = !inside;
        }
    }
    return inside;
}

内容的提问来源于stack exchange，提问作者Finch Youngs