[Scipy-tickets] [SciPy] #1728: Scipy.spatial.Delaunay fail to produce the tetrahedron for all particles
SciPy Trac
scipy-tickets@scipy....
Sun Sep 30 10:04:05 CDT 2012
#1728: Scipy.spatial.Delaunay fail to produce the tetrahedron for all particles
---------------------------+------------------------------------------------
Reporter: ilaudy | Owner: somebody
Type: defect | Status: new
Priority: normal | Milestone: Unscheduled
Component: scipy.spatial | Version: 0.10.0
Keywords: |
---------------------------+------------------------------------------------
Comment(by pv):
This is a Qhull option issue: it omits coplanar points from the
triangulation.
The main problem appears to be the offset in the data: you get the
expected results by using centered data as input: `points -
points.mean(axis=0)`.
It seems that the `Qz` option significantly worsens the precision error
issue. I suppose the additional "point-at-infinity" is added at the origin
of the coordinate system, which brings up precision error issues if the
points reside far from the origin. The scaling + translation can be done
inside Qhull with the `QbB` option. You can try playing with the Qhull
command line utility:
{{{
qhull d Qz Qbb Qt Fv < Problem_centers.txt | wc -l
}}}
However, even adding `QbB` or removing `Qz` from Scipy's default option
list will not *guarantee* that some points are not omitted.
AFAIK, the only way to guarantee that all points are included in the
triangulation is to randomly perturb the points, until by chance the
desired triangulation is obtained. Qhull can do this random perturbation
internally if the `QJ` parameter is supplied.
The "correct fix" seems to be:
- allow passing in custom options to Qhull
- add a check for no coplanar points (enabled by default), as the behavior
of Qhull seems to confuse users. alternatively, make it default to off,
and explain this clearly in the documentation.
- expose coplanar points in the API. Qhull knows in which simplex each of
these nearly incident extra points belongs to.
- drop the Qz option (i.e. use exactly the same default option list as the
command-line qdelaunay)
--
Ticket URL: <http://projects.scipy.org/scipy/ticket/1728#comment:2>
SciPy <http://www.scipy.org>
SciPy is open-source software for mathematics, science, and engineering.
More information about the Scipy-tickets
mailing list