[SciPy-user] fast kd-tree or octree implementations for python

[Jelle Feringa / EZCT Architecture & Design Research]

By the way; have you heared of the python cgal project?
http://cgal-python.gforge.inria.fr/



Jelle Feringa
EZCT ARCHITECTURE & DESIGN RESEARCH

Office:  +33 (0) 1 42 40 19 81
Fax:     +33 (0) 1 43 14 94 61
Cell Nl:  +31 (0) 6 44 02 10 15
Cell Fr:  +33 (0) 6 63 51 27 46
www.ezct.net
jelle.feringa at ezct.net


-----Original Message-----
From: scipy-user-bounces at scipy.org [mailto:scipy-user-bounces at scipy.org] On
Behalf Of Neilen Marais
Sent: Thursday, November 16, 2006 2:48 PM
To: scipy-user at scipy.org
Cc: python-list at python.org
Subject: [SciPy-user] fast kd-tree or octree implementations for python

Hi.

I'm doing a FEM (Finite Elements) code in python. It uses a tetrahedral
mesh to represent the geometry. For post-processing one specifies a list
of 3D coordinates to calculate field values at, which requires the tet
that contains a given point. Right now I'm brute-forcing it checking each
tet for each point, which is very slow on large meshes since the number of
points you are looking for also tend to increase with mesh size.

It seems a kd-tree or octree data-structure will allow me to do lookups in
O(logN) time at the cost of building the data structure in O(N*logN) time.
I am looking for preferably a fast kd-tree implementation with a
GPL-compatible license that is already wrapped for Python, but I'd be
willing to make my own wrappers if needed.

So far I've found CGAL - <http://www.cgal.org> and 
GTS -- The GNU Triangulated Surface Library - <http://gts.sourceforge.net/>
.

CGAL has python wrappers but the tree code is under the QPL license (not
GPL compat) while GTS doesn't come with ready-made python wrappers. What
are other good choices?

Thanks
Neilen

-- 
you know its kind of tragic 
we live in the new world
but we've lost the magic
-- Battery 9 (www.battery9.co.za)

_______________________________________________
SciPy-user mailing list
SciPy-user at scipy.org
http://projects.scipy.org/mailman/listinfo/scipy-user


__________ Informacisn de NOD32, revisisn 1868 (20061115) __________

Este mensaje ha sido analizado con  NOD32 antivirus system
http://www.nod32.com