CODEWITHSUNDEEP
triangulationvoronoidelaunay
user18926311
user18926311

Reputation: 1

Is there an optimal algorithm which can be compute a L_inf Delaunay triangulation directly?

I want to write a C++ program which draws a Delaunay triangulation of a point set in the plane using L_inf metric.

I wonder if a Divide & Conquer algorithm (from Guibas and Stolfi) and an incremental algorithm (from Bowyer-Watson) can be applied to L_inf metric.

There have been a lot of works which prove that L_p Delaunay triangulation can be done in O(nlogn), but many of them proved it indirectly by computing Voronoi diagram. I want to implement a program computing Delaunay triangulation directly, not from a Voronoi diagram.

Upvotes: 0

Views: 124

Answers (2)

Gary Lucas
Gary Lucas

Reputation: 478

Jonathan Shewchuk's Triangle is a well regarded implementation in C and there is also the CGAL 2D Triangulation which is C++. My own Tinfour implementation is in Java, so it's not quite what you're looking for, but the project does have a set example applications and some implementation notes that may be of use at Tinfour Algorithms

Upvotes: 0

PCDSandwichMan
PCDSandwichMan

Reputation: 2120

I'm much of a C++ guy but in Python this would probably be my approach:

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

Upvotes: 0

Related Questions