GetFEM  5.4.2
bgeot::kdtree Class Reference

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

#include <bgeot_kdtree.h>

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();
for (dal::bv_visitor ip(m.points().index()); !ip.finished(); ++ip) {
tree.add_point_with_id(m.points()[ip], ip);
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 102 of file bgeot_kdtree.h.

The documentation for this class was generated from the following files:
std::vector< index_node_pair > kdtree_tab_type
store a set of points with associated indexes.
Definition: bgeot_kdtree.h:68
size_t size_type
used as the common size type in the library
Definition: bgeot_poly.h:49
Describe a finite element method linked to a mesh.
Definition: getfem_mesh_fem.h:148
Balanced tree over a set of points.
Definition: bgeot_kdtree.h:102
const mesh & linked_mesh() const
Return a reference to the underlying mesh.
Definition: getfem_mesh_fem.h:279
virtual size_type nb_dof() const
Return the total number of degrees of freedom.
Definition: getfem_mesh_fem.h:562
void add_point_with_id(const base_node &n, size_type i)
insert a new point, with an associated number.
Definition: bgeot_kdtree.h:120