对Voronoi单元顶点进行排序以计算多边形

Question

我目前在尝试从多边形 Voronoi 交集中获取剪切的单元格。

以下是我现在所拥有的：

我有一个多边形，并计算了其中的一些点以计算 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;
    }

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

这里是有效的

这里无效...

- GeoGecco

---

在我看来，按角度排序几乎总是错误的选择。此外，由于您的多边形是凹多边形，因此 Voronoi 单元格和多边形的交点可能会导致多个多边形。您当前的算法没有考虑到这一点。最佳方法是使用众多多边形剪辑库之一，跳过重新发明轮子的步骤。 - Nicko Po

你能给我一些建议吗？实际上，我想将它分成多个多边形，但这个例子只展示了一个单元格的步骤。 - GeoGecco

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);
}
}

- Adam H

---

每当 k <= 1 时，最终的返回值不应该是：return hull.Take(vertices.count).ToArray() 吗？ - Spi