我正在尝试实现以下Bowyer-Watson算法以实现Delaunay三角剖分。
function BowyerWatson (pointList)
// pointList is a set of coordinates defining the points to be triangulated
triangulation := empty triangle mesh data structure
add super-triangle to triangulation // must be large enough to completely contain all the points in pointList
for each point in pointList do // add all the points one at a time to the triangulation
badTriangles := empty set
for each triangle in triangulation do // first find all the triangles that are no longer valid due to the insertion
if point is inside circumcircle of triangle
add triangle to badTriangles
polygon := empty set
for each triangle in badTriangles do // find the boundary of the polygonal hole
for each edge in triangle do
if edge is not shared by any other triangles in badTriangles
add edge to polygon
for each triangle in badTriangles do // remove them from the data structure
remove triangle from triangulation
for each edge in polygon do // re-triangulate the polygonal hole
newTri := form a triangle from edge to point
add newTri to triangulation
for each triangle in triangulation // done inserting points, now clean up
if triangle contains a vertex from original super-triangle
remove triangle from triangulation
return triangulation
如前所述,该算法声称三角化N个点需要O(NlogN)次操作。但是是否有任何方式可以从上述算法中计算它呢?我的意思是上述算法的哪一部分需要log N次,这导致n个点的结果为(N log N)?维基百科写道,存在特殊退化情况,其中这个时间复杂度会增加到O(N2)。那么这个退化案例的意义是什么?