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

Question

我正在尝试从Delaunay三角剖分计算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);
            }
        }
    }

当然，这样做非常低效，因为它在搜索所有内容。但是，面或变化的集合完全未排序（我不确定如何对其进行排序，或者是否有帮助）。为了混淆事情，球体表面有三维顶点。

我唯一需要找到每个三角形相邻的顶点或面的东西就是它的邻接性，因此对于下面的橙色三角形，我知道三个绿色三角形：

我在思考遍历这个图可能更有效，但我很难想出一个算法的方法来产生共享点的集合。

- Joe

---

我担心由于这个问题特定领域的本质，可能存在隐藏的需求/限制，这将使得很难提出一个符合您要求的答案。不过，我建议你简单地维护一个字典，其中每个顶点是一个键，而该键对应的值是使用该顶点的所有三角形的列表。你可以通过枚举三角形并将该三角形添加到与三角形顶点相对应的三个列表中，来填充字典。一旦数据结构被创建，检索给定顶点的三角形时间复杂度为 O(n)，其中 n 是发现的三角形数目。 - Peter Duniho

听起来像是个不错的计划，应该考虑尝试类似的东西。我会尝试实现它，看看它的表现如何。 - Joe

Answer 1

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

- Micromega

Answer 2

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

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

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

- Darren Engwirda

---

完美运行，非常感谢。我觉得我应该想到这个。 - Joe

它的构建难道不也需要时间吗？ - Micromega

是的，但它只是通过循环一次，然后再次循环，所以是2 * O(n)，相比我之前的做法来说速度要快，我认为那是O(n^2)或者类似的。(一个循环里还有一个循环)? - Joe