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

[Cantwell Carson]

Are there other ideas for what could ship with scipy? I have tried CGAL and
mayavi and they function, but no better than Qhull (IMHO). Matplotlib also
has a routine, but I doubt the redundancy in algorithm would be beneficial.
For example, here is a CGAL wrapper that I tried, along with associated
comments about the speed:

def Delaunay_wrapper(points):
    ## Designed for integer point coordinates.

    from CGAL.CGAL_Kernel import Point_3
    from CGAL.CGAL_Triangulation_3 import Delaunay_triangulation_3

    ## Carry out the triangulation (very fast)
    L=[]
    for coordinates in points:
        L.append(Point_3(*coordinates))

    T=Delaunay_triangulation_3(L)

    ## Read the information at the pointers T into pts_dict (very slow)
    pts_dict = {}
    for idx in range(4):
        pts_dict[idx] = []
        for cell in T.finite_cells():
            pts_dict[idx].append((cell.vertex(idx).point()))
        pts_dict[idx] = [map(float, str(x).split(' ')) for x in
pts_dict[idx]]

    ## reslice the list to group the cells together
    cell_list = zip(pts_dict[0],pts_dict[1],pts_dict[2],pts_dict[3])

    ## return a list of n cells comprised of 4 points with 3 coords
    return cell_list

I was using the SWIG wrapper to expose the CGAL methods to Python. The
triangulation is very fast, but writing them into a Python object is very
slow. If this could be sped up, there might be a benefit to making it an
option in Scipy. As for the number of points, I recommend that we insert a
warning or error when the number of points in Qhull algorithm exceeds 2**24
so that the method can exit without crashing, instead of killing the whole
process as it does now.


On Mon, Jun 22, 2015 at 2:54 PM, Pauli Virtanen <pav at iki.fi> wrote:

> 22.06.2015, 19:48, Cantwell Carson kirjoitti:
> [clip]
> > 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.
>
> I can't immediately help you with the Qhull internals, but other comment:
>
> Your best bet with that would probably be to try to get your patch
> included in Qhull itself. The Qhull code is shipped with Scipy only for
> convenience, and is unmodified from the 2012.1 version --- shipping a
> patched version might not be a very good thing if the Qhull upstream is
> still responsive.
>
> Of course, Qhull is not the only game in town, at least for
> low-dimensional triangulations, and it could be interesting to have more
> featureful alternatives for those cases.
>
>
> _______________________________________________
> SciPy-Dev mailing list
> SciPy-Dev at scipy.org
> http://mail.scipy.org/mailman/listinfo/scipy-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/scipy-dev/attachments/20150622/423312cd/attachment.html>