[SciPy-user] Memory leak in delaunay interpolator

Robert Kern robert.kern@gmail....
Thu Jan 17 15:21:20 CST 2008


Pauli Virtanen wrote:
> Thu, 17 Jan 2008 14:35:50 -0500, william ratcliff wrote:
> 
>> Does it still crash if you give it a degenerate list of points?
> 
> It removes duplicate points prior to triangulation, and I think the 
> segfault associated with this is now patched by Robert Kern.

Well, you patched it; I checked it in.

> But there 
> are still datasets that it can't diagonalize (raises KeyError now instead 
> of a hard segfault); I managed to reduce the problematic example in #376 
> to a simpler one:
> 
>>>> import scikits.delaunay as d
>>>> import numpy as np
>>>> data = np.array([
> ...     [-1, -1                          ], [-1, 0], [-1, 1],
> ...     [ 0, -1                          ], [ 0, 0], [ 0, 1],
> ...     [ 1, -1 - np.finfo(np.float_).eps], [ 1, 0], [ 1, 1],
> ... ])
>>>> tri = d.Triangulation(data[:,0], data[:,1])
> Traceback (most recent call last):
>   File "<stdin>", line 1, in <module>
>   File "/home/pauli/koodi/proj/delaunay/main/scikits/delaunay/
> triangulate.py", line 90, in __init__
>     self.hull = self._compute_convex_hull()
>   File "/home/pauli/koodi/proj/delaunay/main/scikits/delaunay/
> triangulate.py", line 125, in _compute_convex_hull
>     hull.append(edges.pop(hull[-1]))
> KeyError: 6
>>>> data[6,1] = -1
>>>> tri = d.Triangulation(data[:,0], data[:,1])
>>>> data[6,1] = -1 - 1e6*np.finfo(np.float_).eps
>>>> tri = d.Triangulation(data[:,0], data[:,1])
> 
> That is, it works only after rounding off the epsilon. Also, it seems to 
> work if instead of eps, 1e6*eps is subtracted from data[6,1].

This may be a fundamental limitation of the underlying implementation/algorithm 
being used here. Steve Fortune's sweepline algorithm cannot be made to use exact 
geometric predicates with floating point numbers. Other Delaunay triangulation 
algorithms like the incremental construction and divide-and-conquer can. I have 
been (slowly) working on implementing these myself using Jon Shewchuk's exact 
geometric predicates, but this is a low-priority project for me.

-- 
Robert Kern

"I have come to believe that the whole world is an enigma, a harmless enigma
  that is made terrible by our own mad attempt to interpret it as though it had
  an underlying truth."
   -- Umberto Eco


More information about the SciPy-user mailing list