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) -- http://mail.python.org/mailman/listinfo/python-list
