Voronoi算法中Delaunay三角形的处理列表

Question

给定 Delaunay 三角形列表，有必要获取将成为 Voronoi 曲面细分一部分的边的列表。

程序骨架的伪代码是：

getVoronoi(list<point> points) {
    list<triangle> triangles = delaunayTriangulation(points);
    list<edge> edges = voronoiTessellation(triangles);

    //Do something with "edges".
}

设 N 为 points 的大小，知道 delaunayTriangulation(points) 是 O(N log N) 和 triangles=<T1,T2,...TM>，那么，在 voronoiTessellation(triangles) 中，复杂度必须小于或等于等于 O(N log N).

一种计算曲面细分的方法是：

voronoiTessellation (list<Triangle> triangles) {
    list<Edge> edges;
    map<Triangle, Point> centers;

    foreach(Triangle triangle in triangles) {
        centers.add(triangle,triangle.calculateCircumcircle());
    }

    foreach(<Triangle triangle,Point point> in points) {
        list<edges> triangleEdges = triangle.getEdges();
        foreach (Edge edge in triangleEdges) {
            Triangle neighbor = searchNeighbor(edge);
            Point neighborCircumcenter = centers.get(neighbor);
            Line line(point, neighborCircumcenter);
            //todo only add this edge once
            edges.add(line);
        }
    }

    return edges;
}

我的问题是：voronoiTessellation(T) 的复杂度是多少？小于或等于 O(N log N)?

谢谢！

Answer 1

如果您可以在恒定时间内执行 searchNeighbor(edge) 和 centers.get()，则此算法为 O(N)，如果 searchNeighbor(edge) 为 O(log N)，则为 O(N log N)时间.

其中任何一个都应该很容易通过制作地图来满足：首先是边缘 - >（三角形，三角形），searchNeighbor() 会参考它。

如果您使用哈希映射，您将获得预期的 O(N) 时间。 N点的Delaunay三角剖分有O(N)个三角形，所以：

Building centers 增加O(N)个center，耗时O(N)
有O(N)个三角形，点对
每个三角形有3条边
您在 O(N) 时间内将 O(N) 条边添加到结果中

Voronoi算法中Delaunay三角形的处理列表

Process list of Delaunay triangles in Voronoi algorithm

algorithm

voronoi

delaunay

time-complexity

computational-geometry