Regularly spaced orthogonal grid Delaunay triangulation (Computing the paraboloid coeficients)

Question

I'm trying to construct a Delaunay triangulation for the very specific case where the input x and y coordinates are orthogonal and relatively equidistant.

Given the data size is relatively large (1000x1200 triangulation points) and that the Qhull algorithm doesn't know about my extra orthogonal condition, the triangulation is relatively slow (25 seconds on my machine).

As such, I'd like to manually construct a Delaunay triangulation with each of my known quads subdivided into two triangles. I appreciate that this won't always result in a valid Delaunay triangulation (e.g. when the x and y step are significantly different), but in my case I'm fairly confident that the subdivision approach will produce a good triangulation.

In the following plot, I have labelled each of the triangles with an index, the initial vertex and vertex definition direction:

In this case I have and x and y coordinates of [-1, 1.33, 3.67, 6] and [2, 4.5, 7, 9.5, 12] respectively.

I'm currently using the SciPy wrappers to Qhull, and have been able to construct vertices and appropriate neighbor information, but am having difficulty defining the equations attribute (as briefly mentioned at http://docs.scipy.org/doc/scipy-dev/reference/generated/scipy.spatial.ConvexHull.html).

Essentially, I believe these values are parameters of each triangle's normal to the paraboloid defined by the paraboloid_scale and paraboloid_shift attributes, but cannot come up with the magic numbers suitable for interpretation by Qhull. There should be n_dimensions + 1 values per vertex and there is code in SciPy which computes the distance of each vertex from a given point:

dist = d.equations[isimplex*(d.ndim+2) + d.ndim+1]
for k in xrange(d.ndim+1):
    dist += d.equations[isimplex*(d.ndim+2) + k] * point[k]

So my questions are:

• Have I interpreted the equation attribute correctly?
• Is there a tool out there already which does this for me?
• Can I compute the equation parameter values given my orthogonal and mostly-equidistant case without going through Qhull?

Answer 1

To compute a 2D Delaunay triangulation, qhull lifts the 2D points in 3D, onto a paraboloid, then compute the lower convex hull of those 3D points, and the 2D Delaunay triangulation is the projection in the 2D plane of that 3D lower convex hull.

See that image taken from here:

For each face of the 2D Delaunay triangulation, the corresponding 3D hyperplane is the 3D plane that passes through the three lifted 3D points. If the triangulation is Delaunay, that hyperplane corresponds to an empty circle in 2D. See that image taken from here: