[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