Balanced tree over a set of points. More...

#include <bgeot_kdtree.h>

Inherits boost::noncopyable_::noncopyable.

Public Member Functions
void	clear ()
	reset the tree, remove all points

size_type	add_point (const base_node &n)
	insert a new point

void	add_point_with_id (const base_node &n, size_type i)
	insert a new point, with an associated number.

Detailed Description

Balanced tree over a set of points.

Once the tree have been built, it is possible to query very quickly for the list of points lying in a given box. Note that this is not a dynamic structure: once you start to call kdtree::points_in_box, you should not use anymore kdtree::add_point.

Here is an example of use (which tries to find the mapping between the dof of the mesh_fem and the node numbers of its mesh):

void dof_to_nodes(const getfem::mesh_fem &mf) {
  const getfem::getfem_mesh &m = mf.linked_mesh();
  bgeot::kdtree tree;
  for (dal::bv_visitor ip(m.points().index()); !ip.finished(); ++ip) {
    tree.add_point_with_id(m.points()[ip], ip);
  }
  bgeot::kdtree_tab_type t;
  for (size_type d = 0; d < mf.nb_dof(); ++d) {
    getfem::base_node P(mf.point_of_dof(d)), P2(P);
    for (unsigned i=0; i < P.size(); ++i) {
      P[i] -= 1e-12; P2[i]+= 1e-12;
    }
    tree.points_in_box(t, P, P2);
    if (t.size()) {
      assert(t.size() == 1);
      cout << " dof " << d << " maps to mesh node " << t[0].i << "\n";
    }
  }
}

Definition at line 103 of file bgeot_kdtree.h.

The documentation for this class was generated from the following files:

src/getfem/bgeot_kdtree.h
src/bgeot_kdtree.cc

Public Member Functions

Detailed Description