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

給定Delaunay三角形的列表，有必要獲取將成爲Voronoi細分的一部分的邊緣列表。Voronoi算法中Delaunay三角形的處理列表

程序的骨架的僞代碼是：

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

    //Do something with "edges". 
}

設N是的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)？

謝謝！

來源

2016-01-03 Valentina Ramirez

如果您可以在常量時間內執行searchNeighbor（edge）和centers.get（），或者如果searchNeighbor（edge）需要O（log N）時間，則此算法爲O（N）。

其中之一應該很容易通過製作一個地圖來滿足：邊緣 - >（三角形，三角形）首先，searchNeighbor（）會參考。

如果使用哈希映射，您會得到預期的O（N）時間。有O（N）個三角形的N個點的Delaunay三角，所以：

大廈中心增加了O（N）中心和需要O（N）時間
有O（N）三角形，點對
有每個三角形3個邊緣
您添加O（N）的邊緣到結果，在O（N）時間

來源

2016-01-03 01:59:32

問題是，我必須知道N =＃點的最壞情況，有相同數量的三角和三點嗎？ –

是的。 2D Delauney三角測量具有O（#points）三角形數量 –

您有文檔或證明嗎？謝謝！ –

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

回答

相關問題