[Scipy-tickets] [SciPy] #376: [PATCH] sandbox.delaunay crashes on duplicate points

SciPy scipy-tickets@scipy....
Sun Mar 4 08:46:20 CST 2007

#376: [PATCH] sandbox.delaunay crashes on duplicate points
 Reporter:  pv      |        Owner:  somebody
     Type:  defect  |       Status:  new     
 Priority:  normal  |    Milestone:          
Component:  Other   |      Version:  0.5.2   
 Severity:  normal  |   Resolution:          
 Keywords:          |  
Changes (by pv):

  * summary:  sandbox.delaunay crash on eps-perturbed data => [PATCH]
              sandbox.delaunay crashes on duplicate points


 Some info:

 Crash occurs in _delaunay.cpp:getMesh, because vdg.getNumbers returns
 ``length``, which differs from what results in the list walking in
 vdg.getNextDelaunay. Hence, edge_db_ptr overflows.  Attached patch
 delaunay-fix-crashes.patch fixes this by allocating a sufficiently large

 However, the algorithm apparently produces garbage if there are duplicate
 points. The attached patch delaunay-hack-duplicate-points.patch makes
 Triangulation to pass only unique points to _delaunay.delaunay(). This is
 of course only a work-around, it'd be nicer to fix the actual algorithm.
 However, as of now I don't understand how it works and can't fix it.

 The third attached patch adds some test cases to the package.

 CAVEAT: I'm not completely certain that passing only unique points makes
 the algorithm to always work, but at least now Triangulate seems to work
 in the cases I tested. Also, when interpolating, it might be nicer to use
 average values at duplicate points.

Ticket URL: <http://projects.scipy.org/scipy/scipy/ticket/376#comment:3>
SciPy <http://www.scipy.org/>
SciPy is open-source software for mathematics, science, and engineering.

More information about the Scipy-tickets mailing list