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_POINT_LOCATOR_TREE_H 21 #define LIBMESH_POINT_LOCATOR_TREE_H 22 23 // Local Includes 24 #include "libmesh/point_locator_base.h" 25 #include "libmesh/tree_base.h" 26 27 // C++ includes 28 #include <cstddef> 29 30 namespace libMesh 31 { 32 33 // Forward Declarations 34 class MeshBase; 35 class Point; 36 class Elem; 37 38 /** 39 * This is a point locator. It locates points in space 40 * using a tree: given a mesh they return the element 41 * and local coordinates for a given point in global coordinates. 42 * Use \p PointLocatorBase::build() to create objects of this 43 * type at run time. 44 * 45 * \author Daniel Dreyer 46 * \date 2003 47 */ 48 class PointLocatorTree : public PointLocatorBase 49 { 50 public: 51 /** 52 * Constructor. Needs the \p mesh in which the points 53 * should be located. Optionally takes a master 54 * interpolator. This master helps in saving memory 55 * by reducing the number of trees in use. Only the 56 * master locator holds a tree, the others simply 57 * use the master's tree. 58 */ 59 PointLocatorTree (const MeshBase & mesh, 60 const PointLocatorBase * master = nullptr); 61 62 63 /** 64 * Constructor. Needs the \p mesh in which the points 65 * should be located. Allows the user to specify the 66 * method to use when building the tree. 67 * Optionally takes a master interpolator. 68 * This master helps in saving memory 69 * by reducing the number of trees in use. Only the 70 * master locator holds a tree, the others simply 71 * use the master's tree. Allows the user to specify 72 * the build type. 73 */ 74 PointLocatorTree (const MeshBase & mesh, 75 const Trees::BuildType build_type, 76 const PointLocatorBase * master = nullptr); 77 78 /** 79 * Destructor. 80 */ 81 ~PointLocatorTree (); 82 83 /** 84 * Clears the locator. This function frees dynamic memory with "delete". 85 */ 86 virtual void clear() override; 87 88 /** 89 * Initializes the locator, so that the \p operator() methods can 90 * be used. This function allocates dynamic memory with "new". 91 */ 92 void init(Trees::BuildType build_type); 93 94 /** 95 * Initializes the locator, so that the \p operator() methods can 96 * be used. This function allocates dynamic memory with "new". 97 */ 98 virtual void init() override; 99 100 /** 101 * Locates the element in which the point with global coordinates 102 * \p p is located, optionally restricted to a set of allowed subdomains. 103 * The mutable _element member is used to cache 104 * the result and allow it to be used during the next call to 105 * operator(). 106 */ 107 virtual const Elem * operator() (const Point & p, 108 const std::set<subdomain_id_type> * allowed_subdomains = nullptr) const override; 109 110 /** 111 * Locates a set of elements in proximity to the point with global coordinates 112 * \p p Pure virtual. Optionally allows the user to restrict the subdomains searched. 113 */ 114 virtual void operator() (const Point & p, 115 std::set<const Elem *> & candidate_elements, 116 const std::set<subdomain_id_type> * allowed_subdomains = nullptr) const override; 117 118 /** 119 * As a fallback option, it's helpful to be able to do a linear 120 * search over the entire mesh. This can be used if operator() 121 * fails to find an element that contains \p p, for example. 122 * Optionally specify a "close to point" tolerance to use in 123 * the linear search. 124 * Return nullptr if no element is found. 125 */ 126 const Elem * perform_linear_search(const Point & p, 127 const std::set<subdomain_id_type> * allowed_subdomains, 128 bool use_close_to_point, 129 Real close_to_point_tolerance=TOLERANCE) const; 130 131 /** 132 * A method to check if "fat" point p is in multiple elements. This would happen 133 * if p is close to a face or node. This is important for evaluating MeshFunction 134 * on faces when discontinuous shape functions are used. 135 */ 136 std::set<const Elem *> perform_fuzzy_linear_search(const Point & p, 137 const std::set<subdomain_id_type> * allowed_subdomains, 138 Real close_to_point_tolerance=TOLERANCE) const; 139 140 /** 141 * Enables out-of-mesh mode. In this mode, if asked to find a point 142 * that is contained in no mesh at all, the point locator will 143 * return nullptr instead of crashing. Per default, this 144 * mode is off. 145 */ 146 virtual void enable_out_of_mesh_mode () override; 147 148 /** 149 * Disables out-of-mesh mode (default). If asked to find a point 150 * that is contained in no mesh at all, the point locator will now 151 * crash. 152 */ 153 virtual void disable_out_of_mesh_mode () override; 154 155 /** 156 * Set the target bin size. 157 */ 158 void set_target_bin_size(unsigned int target); 159 160 /** 161 * Get the target bin size. 162 */ 163 unsigned int get_target_bin_size() const; 164 165 protected: 166 /** 167 * Pointer to our tree. The tree is built at run-time 168 * through \p init(). For servant PointLocators (not master), 169 * this simply points to the tree of the master. 170 */ 171 TreeBase * _tree; 172 173 /** 174 * Pointer to the last element that was found by the tree. 175 * Chances are that this may be close to the next call to 176 * \p operator()... 177 */ 178 mutable const Elem * _element; 179 180 /** 181 * \p true if out-of-mesh mode is enabled. See \p 182 * enable_out_of_mesh_mode() for details. 183 */ 184 bool _out_of_mesh_mode; 185 186 /** 187 * Target bin size, which gets passed to the constructor of _tree. 188 */ 189 unsigned int _target_bin_size; 190 191 /** 192 * How the underlying tree is built. 193 */ 194 Trees::BuildType _build_type; 195 }; 196 197 } // namespace libMesh 198 199 #endif // LIBMESH_POINT_LOCATOR_TREE_H 200