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

Question

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

我只需获取所有三角形的外心即可轻松计算出 Voronoi 图的顶点（红线的交点）。

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

所以我的代码看起来像这样 (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

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

Answer 2

如果您愿意存储辅助的顶点到三角形数据结构，您可以首先遍历三角形列表，将每个三角形推入与其三个顶点关联的邻接列表中：

for (all tria's ti)
    for (all nodes ni in tria ti)
        v2t[ni] <- ti
    end for
end for

这只是一次 O(n) 扫描。

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

Algorithm design - a better way of finding sets of triangles that share a vertex

c#

algorithm

delaunay

voronoi