1 // The libMesh Finite Element Library. 2 // Copyright (C) 2002-2020 Benjamin S. Kirk, John W. Peterson, Roy H. Stogner 3 4 // This library is free software; you can redistribute it and/or 5 // modify it under the terms of the GNU Lesser General Public 6 // License as published by the Free Software Foundation; either 7 // version 2.1 of the License, or (at your option) any later version. 8 9 // This library is distributed in the hope that it will be useful, 10 // but WITHOUT ANY WARRANTY; without even the implied warranty of 11 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 12 // Lesser General Public License for more details. 13 14 // You should have received a copy of the GNU Lesser General Public 15 // License along with this library; if not, write to the Free Software 16 // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA 17 18 19 20 #ifndef LIBMESH_TREE_H 21 #define LIBMESH_TREE_H 22 23 // Local includes 24 #include "libmesh/tree_node.h" 25 #include "libmesh/tree_base.h" 26 27 // C++ includes 28 29 namespace libMesh 30 { 31 32 // Forward Declarations 33 class MeshBase; 34 35 /** 36 * This class defines a tree that may be used for fast point 37 * location in space. 38 * 39 * \author Benjamin S. Kirk 40 * \date 2002 41 * \brief Tree class templated on the number of leaves on each node. 42 */ 43 template <unsigned int N> 44 class Tree : public TreeBase 45 { 46 public: 47 /** 48 * Constructor. Requires a mesh and the target bin size. Optionally takes the build method. 49 */ 50 Tree (const MeshBase & m, 51 unsigned int target_bin_size, 52 Trees::BuildType bt = Trees::NODES); 53 54 /** 55 * Copy-constructor. Not currently implemented. 56 */ 57 Tree (const Tree<N> & other_tree); 58 59 /** 60 * Destructor. 61 */ 62 ~Tree() = default; 63 64 /** 65 * Prints the nodes. 66 */ 67 virtual void print_nodes(std::ostream & my_out=libMesh::out) const override; 68 69 /** 70 * Prints the nodes. 71 */ 72 virtual void print_elements(std::ostream & my_out=libMesh::out) const override; 73 74 /** 75 * \returns The number of active bins. 76 */ n_active_bins()77 virtual unsigned int n_active_bins() const override 78 { return root.n_active_bins(); } 79 80 /** 81 * \returns A pointer to the element containing point p, 82 * optionally restricted to a set of allowed subdomains, 83 * optionally using a non-zero relative tolerance for searches. 84 */ 85 virtual const Elem * find_element(const Point & p, 86 const std::set<subdomain_id_type> * allowed_subdomains = nullptr, 87 Real relative_tol = TOLERANCE) const override; 88 89 /** 90 * Fills \p candidate_elements with any elements containing the 91 * specified point \p p, 92 * optionally restricted to a set of allowed subdomains, 93 * optionally using a non-zero relative tolerance for searches. 94 */ 95 virtual void find_elements(const Point & p, 96 std::set<const Elem *> & candidate_elements, 97 const std::set<subdomain_id_type> * allowed_subdomains = nullptr, 98 Real relative_tol = TOLERANCE) const override; 99 100 /** 101 * \returns A pointer to the element containing point p, 102 * optionally restricted to a set of allowed subdomains, 103 * optionally using a non-zero relative tolerance for searches. 104 */ 105 const Elem * operator() (const Point & p, 106 const std::set<subdomain_id_type> * allowed_subdomains = nullptr, 107 Real relative_tol = TOLERANCE) const; 108 109 private: 110 /** 111 * The tree root. 112 */ 113 TreeNode<N> root; 114 115 /** 116 * How the tree is built. 117 */ 118 const Trees::BuildType build_type; 119 }; 120 121 122 123 /** 124 * For convenience we define QuadTrees and OctTrees 125 * explicitly. 126 */ 127 namespace Trees 128 { 129 /** 130 * A BinaryTree is a tree appropriate 131 * for 1D meshes. 132 */ 133 typedef Tree<2> BinaryTree; 134 135 /** 136 * A QuadTree is a tree appropriate 137 * for 2D meshes. 138 */ 139 typedef Tree<4> QuadTree; 140 141 /** 142 * An OctTree is a tree appropriate 143 * for 3D meshes. 144 */ 145 typedef Tree<8> OctTree; 146 } 147 148 } // namespace libMesh 149 150 151 #endif // LIBMESH_TREE_H 152