[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