[SciPy-Dev] Fwd: Increasing the maximum number of points in the spatial.Delaunay triangulation

[Cantwell Carson]

I originally wrote this to the scipy-user group, but I think it might be
more appropriate here. I am working on an image processing algorithm that
relies on the Delaunay triangulation of a 3d image. Unfortunately, I need
to work on images with more than 2**24 points that go into the Delaunay
triangulation. This is problematic because the Qhull routine labels the
input vertices with a 24-bit label.  I have tried editing the source code
for qhull here in libqhull.h, lines 352, 380 and 663 - 664:

  unsigned id:32;       /* unique identifier, =>room for 8 flags, bit field
matches qh.ridge_id */
  ...
  unsigned id:32;       /* unique identifier, bit field matches
qh.vertex_id */
  ...
  unsigned ridge_id:32;   /* ID of next, new ridge from newridge() */
  unsigned vertex_id:32;  /* ID of next, new vertex from newvertex() */


poly.c, lines 569, 1019 - 1023:

  long ridgeid;
  ...
  if (qh ridge_id == 0xFFFFFFFF) {
    qh_fprintf(qh ferr, 7074, "\
qhull warning: more than %d ridges.  ID field overflows and two ridges\n\
may have the same identifier.  Otherwise output ok.\n", 0xFFFFFFFF);

and poly2.c, lines 2277 - 2279:

  if (qh vertex_id == 0xFFFFFFFF) {
    qh_fprintf(qh ferr, 6159, "qhull error: more than %d vertices.  ID
field overflows and two vertices\n\
may have the same identifier.  Vertices will not be sorted correctly.\n",
0xFFFFFFFF);

This compiles fine, but so far, this produces a memory leak (as far as I
can tell) when I put more than 2**24 points into the algorithm. I have
emailed Brad Barber, who indicated that this changing the ridgeid field was
possible. I am also working on a divide and conquer approach, but am having
trouble deleting the old Delaunay object before instantiating the next one.
I can send that code along if there is no good way to increase the number
of points in the algorithm.

I think it would be useful to have an algorithm that can accept more
points, given the increased speed and processing power of modern computers.
Thanks for your help.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/scipy-dev/attachments/20150622/9a294ff5/attachment.html>