c# - 对 voronoi 单元顶点进行排序以计算多边形

Question

我目前正在尝试从 Polygon-Voronoi-Intersection 中获取剪裁后的单元格。

这是我到目前为止所得到的:

我有一个多边形并计算了其中的一些点来计算 voronoi 图，下图中的红线是 voronoi 边。然后我使用一种算法从每个单元格获取角点，现在我需要在正确的方向(顺时针)获取角点以生成单元格多边形。

为一个单元格找到角落

首先我使用的是这种方法:

private List<Vector> sortClockwise(List<Vector> points)
    {
        points = points.OrderBy(x => Math.Atan2(x.X, x.Y)).ToList();
        return points;
    }

但是在一些特殊的凹多边形中这不起作用并且正确的顺序会混淆。

有没有人建议或暗示如何以最简单的方式做到这一点？考虑到多边形点的顺序已经正确，并且 voronoi 角混合在一起，需要对多边形点进行排序。

我的想法:

• 在单元角找到第一个多边形点
• 沿着多边形方向看 voronoi 顶点的点是否在那条线上。
• 如果是:获取找到的 voronoi 边的端点并寻找共享的 voronoi 边。
• 如果找到共享边，总是选择最右边的边
• 做直到你到达拳头点

这是我能做到的唯一方法吗？

编辑 - 更新

好吧，我现在有一些一半的答案。

正如我所说，我拥有属于 voronoi 单元格之一的所有顶点，但顺序仍然困惑，所以我想我可以像这样从质心按角度对它们进行排序:

private List<Vector> sortClockwiseBySentroid(List<Vector> points, Vector center)
    {
        points = points.OrderBy(x => Math.Atan2(x.X - center.X, x.Y - center.Y)).ToList();
        return points;
    }

但这并不总是有效。以下是其工作时和不工作时的示例。问题是在凹边上，从质心到角的角度有时比我真正需要的要小。关于如何解决这个问题有什么建议吗？

这里是它的工作

这里不起作用...

Answer 1

这就是我的 Voronoi 生成中的单元格的顶点列表按顺时针顺序排序的方式。假设您知道需要对哪些顶点进行排序，此代码就可以完成这项工作。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;


public class ConvexHull
{
private List<Vector2> vertices;

public ConvexHull()
{
    vertices = new List<Vector2>();
}

public ConvexHull(Vector2[] vertices)
{
    this.vertices = new List<Vector2>(vertices);
}

public void AddVertices(Vector2[] vertices)
{
    this.vertices.AddRange(new List<Vector2>(vertices));
}

public Vector2[] Generate()
{
    if (vertices.Count > 1)
    {
        int k = 0;
        Vector2[] hull = new Vector2[2 * vertices.Count];

        // Make the list distinct and sorted
        vertices = vertices.Distinct().OrderBy(v => v.x).ToList();
        //vertices.Sort();
        //Array.Sort(vertices);

        // Build lower hull
        for (int i = 0; i < vertices.Count; ++i)
        {
            while (k >= 2 && Cross(hull[k - 2], hull[k - 1], vertices[i]) <= 0)
                k--;
            hull[k++] = vertices[i];
        }

        // Build upper hull
        for (int i = vertices.Count - 2, t = k + 1; i >= 0; i--)
        {
            while (k >= t && Cross(hull[k - 2], hull[k - 1], vertices[i]) <= 0)
                k--;
            hull[k++] = vertices[i];
        }
        if (k > 1)
        {
            hull = hull.Take(k - 1).ToArray();
        }
        return hull;
    }
    if (vertices.Count <= 1)
    {
        return vertices.ToArray();
    }

    return null;
}

private float Cross(Vector2 p1, Vector2 p2, Vector2 p3)
{
    return (p2.x - p1.x) * (p3.y - p1.y) - (p2.y - p1.y) * (p3.x - p1.x);
}
}