Line data    Source code

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