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
equationattribute correctly? - Is there a tool out there already which does this for me?
- Can I compute the
equationparameter values given my orthogonal and mostly-equidistant case without going through Qhull?
