[SciPy-Dev] PR 377: Convex hulls and Voronoi diagrams via Qhull

[Pauli Virtanen]

Hi,

08.12.2012 11:09, Matt Terry kirjoitti:
[clip]
> It would be nice to be able to add points to an existing triangulation. 
> I looked into this briefly, and it looked like qhull has the needed
> functions, but it does some strange things with globals that would make
> retaining the needed data structures tricky.

I also looked at this: there's some code here:

	https://github.com/pv/scipy-work/tree/incremental-qhull

This works fine as long as the triangulation has no geometrical
degeneracies.

However, Qhull seems to not be really designed for this, and I so far
I've had some difficulties with this feature. For instance:

import numpy as np
from scipy.spatial import Delaunay
points = [(0,0), (0,1), (1,0), (1,1)]
tri = Delaunay(points, incremental=True, qhull_options="Qt Q11 Qz")
tri.add_points([(1, 1 + 1e-3)])
print tri.vertices

Despite the "Qt Q11" options and calling qh_triangulate, Qhull seems to
generate a non-simplical facet here, so the triangulation has to be
re-done from scratch.

Moreover, if you hit a case in which Qhull makes a longjmp() out from
the middle of the code (or, aborts the process, if error handling is not
enabled), the internal state is apparently left inconsistent.
Interestingly, this seems to also happens in qh_new_qhull, so in fact
the Qhull code probably leaks memory on failures.

-- 
Pauli Virtanen