How to instantiate a scipy Delaunay triangulation from vertices and simplices

Question

Given a list of vertices and simplices, I would like to instantiate a scipy.spatial.Delaunay object such that I can use its Delaunay.find_simplex method on my triangulation. I did not find any way to do so. The only option I found is to to instantiate the object from the vertices only but this approach:

1. does not preserve my original simplices
2. it seems unnecessary slow as it has to recompute the triangulation.

I would expect the Delaunay class to implement a class method:

class scipy.spatial.Delaunay:

    @classmethod
    def from_vertices_and_simplices(cls, vertices, simplices):
        ...

that allows me to instantiate a triangulation from its vertices and simplices such that I can do

triangulation = scipy.spatial.Delaunay.from_vertices_and_simplices(vertices=vertices, simplices=simplices)
simplex_index = triangulation.find_simplex(point_to_locate)

Any thought?

Answer 1

scipy.spatial.Delaunay is a Delaunay triangulation that is based on the Qhull library. It computes the Delaunay triangulation by computing the (n+1 dimensional) convex hull of the points lifted to a paraboloid (see, for example, in wikipedia or slide 16 of this presentation, or other web references on the lifting algorithm). This means that it's algorithms depend on its inner qhull representation and data-structures and a construction from vertices-and-simplices isn't sufficient.

Therefore, in order to use its find_simplex method you have no choice but to reconstruct the Delaunay triangulation from the vertices you have.

As for 1 in your question, the fact that the constructed simplices do not preserve your initial simplices may indicate that your initial triangulation was not a Delaunay or that it is a degenerate (or near-degenerate) point configuration (since Delaunay triangulations are unique up to degenerate configurations). Another possibility is that it just doesn't preserve the order of your simplices, in which case you can map the simplex-tuples between your ordering and the constructed one (assuming you preserved the ordering of the initial vertices).