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

Jelle Feringa / EZCT Architecture & Design Research jelle.feringa at ezct.net
Thu Nov 16 08:18:19 CST 2006

By the way; have you heared of the python cgal project?

Jelle Feringa

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
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


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?


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

__________ Informacisn de NOD32, revisisn 1868 (20061115) __________

Este mensaje ha sido analizado con  NOD32 antivirus system

More information about the SciPy-user mailing list