[SciPy-Dev] Qhull Delaunay triangulation "equations" attribute

[Pauli Virtanen]

20.02.2014 16:00, Phil Elson kirjoitti:
> I'm trying to manually construct a Delaunay triangulation for an orthogonal
> 2d grid as described in
> http://stackoverflow.com/questions/21888546<http://stackoverflow.com/questions/21888546/regularly-spaced-orthogonal-grid-delaunay-triangulation-computing-the-paraboloi>and
> wonder if anybody can help provide some interpretation of the
> "equations" values of a scipy.spatial.Delaunay instance.
> Essentially I'm working off the premise that it is possible to construct a
> Delaunay triangulation from a regular grid without going through the
> expensive triangulation stage, does anybody know if that is true or not?

Yes, it should be possible to construct the equations manually.

For Delaunay, "equations" contains the hyperplane equation defining the
convex hull facets in ndim+1 dimensions corresponding to the simplices
of the triangulation.

You get the ndim+1 dim coordinates for each simplex from the ndim
coordinates by adding an additional last coordinate to the vertices of
the simplices. The routine Delaunay.lift_points maps points in ndim dims
onto the paraboloid in ndim+1.

The hyperplane equations should be constructed for the so transformed
coordinates, in the form

	sum([equations[j,k]*x[k] for k in range(ndim+1)])
	+
	equations[j,ndim+1]
	==
	0

Here, x is the coordinate "lifted" to ndim+1 dims.

Geometrically, equations[j,:ndim+1] contains the normal vector of the
facet j, and equations[j,ndim+1] the offset scalar.

-- 
Pauli Virtanen