c# - 算法设计——寻找共享一个顶点的三角形集合的更好方法

Question

我正在尝试根据 Delaunay 三角剖分计算 Voronoi 图，我得到了顶点(图中的红色圆圈)和三角形(图中的蓝线)形式的三角剖分数据:

只需获取所有三角形的外心，我就能轻松计算出 Voronoi 图的顶点(红线的交点)。

但是，我需要导出每个红色多边形的“单元格”信息。为此，对于每个红色顶点，我需要找到一组共享相同顶点的三角形。所以对于带圆圈的顶点，我需要绿色三角形:

所以我的代码看起来像这样 (c#):

    foreach (Vertex3 vertex in DelaunayVertices)
    {
        VoronoiCell cell = new VoronoiCell();
        cell.Vertex = vertex;

        //seach all triangles for the ones that match this.
        foreach (Face3 face in DelaunayTriangles)
        {
            if (face.Vertices.Where(v => v.Equals(vertex)).Any())
            {
                //shares vertices, add it's circumcenter as an edge vertex of the cell
                cell.EdgeVertices.Add(face.Circumcenter);
            }
        }
    }

当然，这是非常低效的，因为它要搜索所有内容。然而，面孔或真实性的集合是完全未分类的(我不确定如何对它们进行分类，或者是否有帮助)。令人困惑的是，球体表面有 3 维顶点。

我唯一需要为每个三角形找到相邻的顶点或面的是相邻的，所以对于下面的橙色三角形，我知道三个绿色三角形:

我认为遍历此图可能更有效，但我正在努力想出一种算法方法来生成共享点的集合。

Answer 1

您可以尝试空间填充曲线，即沿希尔伯特曲线对顶点进行排序。您也可以尝试多边形点测试，但这非常困难。您也可以尝试使用暴力算法制作位图。