多边形正交化Python脚本转Unity C#及代码修复求助

1. 优先解决重复顶点问题 #

输出多边形变成三角形的核心原因大概率是顶点重复导致有效顶点数不足。Unity的Vector2/Vector3是浮点数类型，不能直接用==判断相等，必须加精度阈值：

// 移除重复顶点（含首尾闭合重复）
private List<Vector2> RemoveDuplicateVertices(List<Vector2> vertices)
{
    List<Vector2> uniqueVertices = new List<Vector2>();
    foreach (var v in vertices)
    {
        bool isDuplicate = false;
        foreach (var uv in uniqueVertices)
        {
            // 用1e-6作为精度阈值，避免浮点误差误判
            if (Vector2.Distance(v, uv) < 1e-6)
            {
                isDuplicate = true;
                break;
            }
        }
        if (!isDuplicate) uniqueVertices.Add(v);
    }
    // 处理闭合多边形的首尾重复
    if (uniqueVertices.Count >= 2 && Vector2.Distance(uniqueVertices[0], uniqueVertices[^1]) < 1e-6)
    {
        uniqueVertices.RemoveAt(uniqueVertices.Count - 1);
    }
    return uniqueVertices;
}

所有算法步骤（凸包、角点检测、正交化）前后都要调用这个方法去重。

2. 凸包算法适配Unity坐标系 #

Python常用的图像坐标系Y轴向下，而Unity Y轴向上，直接移植凸包算法会导致方向错误，进而引发后续顶点异常。以下是适配Unity的Graham扫描法实现：

private List<Vector2> ConvexHull(List<Vector2> points)
{
    if (points.Count <= 1) return points.ToList();

    // 找到最左下角的点（Unity Y轴向上，优先取最小Y，再取最小X）
    int lowestIndex = 0;
    for (int i = 1; i < points.Count; i++)
    {
        if (points[i].y < points[lowestIndex].y || 
            (points[i].y == points[lowestIndex].y && points[i].x < points[lowestIndex].x))
        {
            lowestIndex = i;
        }
    }
    Vector2 lowestPoint = points[lowestIndex];
    points.RemoveAt(lowestIndex);

    // 按极角逆时针排序（适配Unity坐标系）
    points.Sort((a, b) =>
    {
        float cross = CrossProduct(lowestPoint, a, b);
        if (cross > 0) return -1;
        if (cross < 0) return 1;
        // 极角相同时，距离近的排前面
        return Vector2.Distance(lowestPoint, a).CompareTo(Vector2.Distance(lowestPoint, b));
    });

    List<Vector2> hull = new List<Vector2> { lowestPoint };
    foreach (var p in points)
    {
        // 移除凹点
        while (hull.Count >= 2 && CrossProduct(hull[hull.Count - 2], hull[hull.Count - 1], p) <= 0)
        {
            hull.RemoveAt(hull.Count - 1);
        }
        hull.Add(p);
    }
    return hull;
}

// 计算叉乘，判断三点的转向
private float CrossProduct(Vector2 a, Vector2 b, Vector2 c)
{
    return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}

3. 角点检测的可靠实现 #

角点检测要避免浮点误差导致的异常，计算夹角时必须做值范围钳制：

private List<int> DetectCornerPoints(List<Vector2> hull)
{
    List<int> cornerIndices = new List<int>();
    int n = hull.Count;
    if (n < 3) return cornerIndices;

    for (int i = 0; i < n; i++)
    {
        Vector2 prev = hull[(i - 1 + n) % n];
        Vector2 curr = hull[i];
        Vector2 next = hull[(i + 1) % n];

        Vector2 v1 = prev - curr;
        Vector2 v2 = next - curr;

        // 计算夹角余弦值，钳制范围避免Acos报错
        float dot = Vector2.Dot(v1.normalized, v2.normalized);
        float angle = Mathf.Acos(Mathf.Clamp(dot, -1f, 1f)) * Mathf.Rad2Deg;

        // 角度小于160度视为角点（可根据需求调整阈值）
        if (angle < 160f) cornerIndices.Add(i);
    }
    return cornerIndices;
}

4. 正交化步骤的容错处理 #

正交化后容易产生新的重复顶点，必须再次去重：

private List<Vector2> OrthogonalizePolygon(List<Vector2> corners)
{
    List<Vector2> orthogonal = new List<Vector2>(corners);
    int n = orthogonal.Count;
    if (n < 3) return orthogonal;

    for (int i = 0; i < n; i++)
    {
        int prevIdx = (i - 1 + n) % n;
        int nextIdx = (i + 1) % n;
        Vector2 prev = orthogonal[prevIdx];
        Vector2 curr = orthogonal[i];
        Vector2 next = orthogonal[nextIdx];

        Vector2 dirPrev = prev - curr;
        Vector2 dirNext = next - curr;

        // 优先保留水平/垂直方向，调整相邻顶点
        if (Mathf.Abs(dirPrev.x) > Mathf.Abs(dirPrev.y))
        {
            orthogonal[nextIdx] = new Vector2(curr.x, next.y);
        }
        else
        {
            orthogonal[nextIdx] = new Vector2(next.x, curr.y);
        }
    }

    // 正交化后再次去重
    return RemoveDuplicateVertices(orthogonal);
}

5. 调试验证方法 #

• 分步绘制：分别绘制原始多边形（绿）、凸包（蓝）、角点（红圆点）、正交化结果（洋红），定位哪一步出现异常。
• 打印顶点数据：对比Python脚本每一步的顶点输出，看Unity版本在哪个步骤开始出现差异（重点检查坐标系方向是否转换正确）。
• 坐标系转换：如果原始Python脚本是基于图像坐标系（Y向下），需要将输入顶点的Y坐标取反：new Vector2(vertex.x, -vertex.y)。

内容的提问来源于stack exchange，提问作者Sphelele Sphesihle Lubanyana