By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
444,050 Members | 1,009 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 444,050 IT Pros & Developers. It's quick & easy.

fast kd-tree or octree implementations for python

P: n/a
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.organd
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)

Nov 16 '06 #1
Share this question for a faster answer!
Share on Google+

This discussion thread is closed

Replies have been disabled for this discussion.