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_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. Class cannot be default copy constructed
      56             :    * because TreeNode cannot be default copy constructed.
      57             :    */
      58             :   Tree (const Tree<N> &) = delete;
      59             : 
      60             :   /**
      61             :    * Destructor.
      62             :    */
      63       12547 :   ~Tree() = default;
      64             : 
      65             :   /**
      66             :    * Prints the nodes.
      67             :    */
      68             :   virtual void print_nodes(std::ostream & my_out=libMesh::out) const override;
      69             : 
      70             :   /**
      71             :    * Prints the nodes.
      72             :    */
      73             :   virtual void print_elements(std::ostream & my_out=libMesh::out) const override;
      74             : 
      75             :   /**
      76             :    * \returns The number of active bins.
      77             :    */
      78           0 :   virtual unsigned int n_active_bins() const override
      79           0 :   { return root.n_active_bins(); }
      80             : 
      81             :   /**
      82             :    * \returns A pointer to the element containing point p,
      83             :    * optionally restricted to a set of allowed subdomains,
      84             :    * optionally using a non-zero relative tolerance for searches.
      85             :    */
      86             :   virtual const Elem * find_element(const Point & p,
      87             :                                     const std::set<subdomain_id_type> * allowed_subdomains = nullptr,
      88             :                                     Real relative_tol = TOLERANCE) const override;
      89             : 
      90             :   /**
      91             :    * Adds to \p candidate_elements any elements containing the
      92             :    * specified point \p p,
      93             :    * optionally restricted to a set of allowed subdomains,
      94             :    * optionally using a non-zero relative tolerance for searches.
      95             :    */
      96             :   virtual void find_elements(const Point & p,
      97             :                              std::set<const Elem *> & candidate_elements,
      98             :                              const std::set<subdomain_id_type> * allowed_subdomains = nullptr,
      99             :                              Real relative_tol = TOLERANCE) const override;
     100             : 
     101             :   /**
     102             :    * \returns A pointer to the element containing point p,
     103             :    * optionally restricted to a set of allowed subdomains,
     104             :    * optionally using a non-zero relative tolerance for searches.
     105             :    */
     106             :   const Elem * operator() (const Point & p,
     107             :                            const std::set<subdomain_id_type> * allowed_subdomains = nullptr,
     108             :                            Real relative_tol = TOLERANCE) const;
     109             : 
     110             : private:
     111             :   /**
     112             :    * The tree root.
     113             :    */
     114             :   TreeNode<N> root;
     115             : 
     116             :   /**
     117             :    * How the tree is built.
     118             :    */
     119             :   const Trees::BuildType build_type;
     120             : };
     121             : 
     122             : 
     123             : 
     124             : /**
     125             :  * For convenience we define QuadTrees and OctTrees
     126             :  * explicitly.
     127             :  */
     128             : namespace Trees
     129             : {
     130             : /**
     131             :  * A BinaryTree is a tree appropriate
     132             :  * for 1D meshes.
     133             :  */
     134             : typedef Tree<2> BinaryTree;
     135             : 
     136             : /**
     137             :  * A QuadTree is a tree appropriate
     138             :  * for 2D meshes.
     139             :  */
     140             : typedef Tree<4> QuadTree;
     141             : 
     142             : /**
     143             :  * An OctTree is a tree appropriate
     144             :  * for 3D meshes.
     145             :  */
     146             : typedef Tree<8> OctTree;
     147             : }
     148             : 
     149             : } // namespace libMesh
     150             : 
     151             : 
     152             : #endif // LIBMESH_TREE_H