[SciPy-dev] St9bad_alloc

[Pauli Virtanen]

Maik Trömel wrote:
> I've got some problems with Scipy/sandbox/delaunay.
> Everytime I run my script the following error occures:
> terminate called after throwing an instance of 'std::bad_alloc'
>   what():  St9bad_alloc
> 
> Does anybody know what this means? And what I can do to avoid this
> error?
> 
> I have postet in several forums, but nowbody could help me.

The delaunay module as in SVN does have a couple of bugs. I've filed bug
tickets for these, but probably people aren't aware of them:

http://projects.scipy.org/scipy/scipy/ticket/382
        Memory leak, patch included

http://projects.scipy.org/scipy/scipy/ticket/376
        Algorithm failure + crash on special types of data. Partial
        workaround + test cases included

The latter problem is more difficult, since the errors are apparently
related to the robustness of the algorithm itself. The patches I
included for #376 plug one crasher bug, but the error manifests instead
like this (which is better than segfaulting):

        Traceback (most recent call last):
          File "tests/test_triangulate.py", line 105, in test_ticket_376_2
            tri = dlny.Triangulation(data[:,0], data[:,1])
          File "/home/pauli/tmp/scipy/Lib/sandbox/delaunay/build/lib.linux-x86_64-2.4/delaunay/triangulate.py", line 83, in __init__
            self.hull = self._compute_convex_hull()
          File "/home/pauli/tmp/scipy/Lib/sandbox/delaunay/build/lib.linux-x86_64-2.4/delaunay/triangulate.py", line 118, in _compute_convex_hull
            hull.append(edges.pop(hull[-1]))
        KeyError: 0

Most of the time these errors can be fixed by rounding off a few least
significant digits of the input data; like this

	xscale, yscale = x.ptp(), y.ptp()
	Triangulation(around(x/xscale, 13)*xscale, 
                      around(y/yscale, 13)*yscale)

A "bad" dataset inducing this type of bug is included in the testcases.
Really fixing this problem probably would need good understanding of the
algorithm, though. Nonetheless, with these fixes, I've been able to
hobble along using delaunay, without further problems.

-- 
Pauli Virtanen