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

[Phil Elson]

Thanks Pauli,

Based on what you said, I've simply used the Delaunay.lift_points method to
take my vertices to the paraboloid. Though I arbitrarily picked a
paraboloid of scale 1 and shift of 0.

Is it worth submitting a PR to add a static method for the creation of a
Delaunay instance from 2 orthogonal 1D coordinates (I've only implemented
it for the 2D case) in this way? I've found that for reasonably large
regular grids (800, 1200), manually constructing the triangulation can cut
~25s from the ~31s overall execution time.

Additionally, I've been using LinearNDInterplator which I would like to be
able to construct with an already computed triangulation instance, would
there be interest in me submitting a PR for that also?

Thanks,

Phil



On 20 February 2014 17:18, Pauli Virtanen <pav at iki.fi> wrote:

> 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
>
> _______________________________________________
> SciPy-Dev mailing list
> SciPy-Dev at scipy.org
> http://mail.scipy.org/mailman/listinfo/scipy-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/scipy-dev/attachments/20140226/e6bad420/attachment.html>