fast kd-tree or octree implementations for python

[Neilen Marais]

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