是否有可以直接计算L_INF DELAUNAY三角剖分的最佳算法？

Question

我想编写一个C ++程序，该程序使用L_INF Metric绘制平面设置的点的Delaunay三角剖分。

我想知道是否有分歧＆amp;征服算法（来自Guibas和Stolfi）和增量算法（来自Bowyer-Watson）可以应用于L_INF度量。

有很多工作证明可以在O（nlogn）中完成L_P Delaunay三角剖分，但其中许多通过计算Voronoi图来间接证明了这一点。我想直接实现一个程序计算Delaunay三角剖分，而不是来自Voronoi图。

Answer 1

我是一个C ++的人，但在Python中，这可能是我的方法：

def delaunay(points):
    # Sort the points lexicographically (tuples are compared lexicographically).
    points = sorted(points)
    # Initialize the list of supertriangle(s).
    supertriangle = [[-2, -1, -2], [-1, -2, -2], [-2, -2, -2]]
    # Initialize the list of triangles.
    triangles = []
    # Initialize the list of edges.
    edges = []
    # For each point:
    for p in points:
        # Insert a point into the edge list.
        edges.append([p, p])
    # Create the supertriangle
    triangle = [[0, 1, 2], supertriangle]
    triangles.append(triangle)
    
    while True:
        # This is the end of the algorithm if no more edges are intersecting.
        if len(edges) == 0:
            break

        # Find the point of intersection of the smallest edge.
        edge = sorted(edges)[0]

        # Remove the edge from the edge list.
        edges.remove(edge)

        # Find the triangle containing the edge.
        triangle = None
        for t in triangles:
            if edge[0] in t[0] and edge[1] in t[0]:
                triangle = t
                break

        # Remove the triangle from the triangle list.
        triangles.remove(triangle)

        # Find the indices of the edge endpoints.
        index1 = triangle[0].index(edge[0])
        index2 = triangle[0].index(edge[1])

        # Form a new triangle for each endpoint.
        triangle1 = [
            [triangle[0][(index1 + 1) % 3], triangle[0][(index1 + 2) % 3], edge[1]],
            triangle[1],
        ]
        triangle2 = [
            [triangle[0][(index2 + 1) % 3], triangle[0][(index2 + 2) % 3], edge[0]],
            triangle[1],
        ]

        # Add the new
        triangles.append(triangle1)
        triangles.append(triangle2)

        # Form the new edges
        edges.append([triangle1[0][0], triangle2[0][0]])
        edges.append([triangle1[0][0], triangle1[0][1]])
        edges.append([triangle1[0][1], triangle2[0][0]])
        edges.append([triangle2[0][1], triangle2[0][0]])

    # Remove triangles that have a supertriangle vertex.
    triangles = [t for t in triangles if -1 not in t[0]]

    # Remove duplicate triangles.
    triangles = [dict(t) for t in set(tuple(t) for t in triangles)]

    # Return the list of triangles.
    return triangles

Answer 2

Jonathan Shewchuk的 triangle> triangle> cgal 2d三角剖分是C ++。我自己的 tinfour 实现在java中，所以这不是您想要的，但是该项目并不完全确实有一个设置的示例应用程序和一些实现说明，可以在“