GetFEM  5.5
bgeot_rtree.h
Go to the documentation of this file.
1 /* -*- c++ -*- (enables emacs c++ mode) */
2 /*===========================================================================
3 
4  Copyright (C) 2000-2026 Julien Pommier
5 
6  This file is a part of GetFEM
7 
8  GetFEM is free software; you can redistribute it and/or modify it
9  under the terms of the GNU Lesser General Public License as published
10  by the Free Software Foundation; either version 3 of the License, or
11  (at your option) any later version along with the GCC Runtime Library
12  Exception either version 3.1 or (at your option) any later version.
13  This program is distributed in the hope that it will be useful, but
14  WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
15  or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public
16  License and GCC Runtime Library Exception for more details.
17  You should have received a copy of the GNU Lesser General Public License
18  along with this program. If not, see https://www.gnu.org/licenses/.
19 
20  As a special exception, you may use this file as it is a part of a free
21  software library without restriction. Specifically, if other files
22  instantiate templates or use macros or inline functions from this file,
23  or you compile this file and link it with other files to produce an
24  executable, this file does not by itself cause the resulting executable
25  to be covered by the GNU Lesser General Public License. This exception
26  does not however invalidate any other reasons why the executable file
27  might be covered by the GNU Lesser General Public License.
28 
29 ===========================================================================*/
30 
31 #ifndef BGEOT_RTREE_H
32 #define BGEOT_RTREE_H
33 
34 /** @file bgeot_rtree.h
35  @author Julien Pommier <Julien.Pommier@insa-toulouse.fr>
36  @date January 2004.
37  @brief region-tree for window/point search on a set of rectangles.
38 */
39 
40 #include <set>
41 #include "bgeot_small_vector.h"
42 #include "bgeot_node_tab.h"
43 
44 namespace bgeot {
45 
46  struct box_index {
47  size_type id;
48  const base_node *min, *max;
49  };
50 
51  struct box_index_id_compare {
52  bool operator()(const box_index *plhs, const box_index *prhs) const {
53  return plhs->id < prhs->id;
54  }
55  };
56 
57  struct box_index_topology_compare {
58  const scalar_type EPS;
59  bool is_less(const base_node &lhs, const base_node &rhs) const {
60  GMM_ASSERT2(lhs.size() == rhs.size(), "size mismatch");
61  for (size_type i = 0; i < lhs.size(); ++i)
62  if (gmm::abs(lhs[i] - rhs[i]) > EPS) {
63  return lhs[i] < rhs[i];
64  }
65  return false;
66  }
67 
68  box_index_topology_compare(scalar_type EPS_) : EPS{EPS_} {}
69 
70  bool operator()(const box_index &lhs, const box_index &rhs) const {
71  if (EPS == scalar_type(0))
72  return lhs.id < rhs.id;
73  else
74  return is_less(*lhs.min, *rhs.min) ||
75  (!is_less(*rhs.min, *lhs.min) && is_less(*lhs.max, *rhs.max));
76  }
77  };
78 
79  struct rtree_elt_base {
80  enum { RECTS_PER_LEAF=8 };
81  bool isleaf_;
82  bool isleaf() const { return isleaf_; }
83  base_node rmin, rmax;
84  rtree_elt_base(bool leaf, const base_node& rmin_, const base_node& rmax_)
85  : isleaf_(leaf), rmin(rmin_), rmax(rmax_) {}
86  virtual ~rtree_elt_base() {}
87  };
88 
89  /** Balanced tree of n-dimensional rectangles.
90  *
91  * This is not a dynamic structure. Once a query has been made on the
92  * tree, new boxes should not be added.
93  *
94  * CAUTION : For EPS > 0, nearly identically boxes are eliminated
95  * For EPS = 0 all boxes are stored.
96  */
97  class rtree {
98  public:
99  using box_cont = std::set<box_index,box_index_topology_compare> ;
100  using pbox_cont = std::vector<const box_index*>;
101  using pbox_set = std::set<const box_index *, box_index_id_compare>;
102 
103  rtree(scalar_type EPS = 0);
104  rtree(const rtree&) = delete;
105  rtree& operator = (const rtree&) = delete;
106 
107  size_type add_box(const base_node &min, const base_node &max,
108  size_type id=size_type(-1));
109  size_type nb_boxes() const { return boxes.size(); }
110  void clear();
111 
112  void find_intersecting_boxes(const base_node& bmin, const base_node& bmax,
113  pbox_set& boxlst) const;
114  void find_containing_boxes(const base_node& bmin, const base_node& bmax,
115  pbox_set& boxlst) const;
116  void find_contained_boxes(const base_node& bmin, const base_node& bmax,
117  pbox_set& boxlst) const;
118  void find_boxes_at_point(const base_node& P, pbox_set& boxlst) const;
119  void find_line_intersecting_boxes(const base_node& org,
120  const base_small_vector& dirv,
121  pbox_set& boxlst) const;
122  void find_line_intersecting_boxes(const base_node& org,
123  const base_small_vector& dirv,
124  const base_node& bmin,
125  const base_node& bmax,
126  pbox_set& boxlst) const;
127 
128  void find_intersecting_boxes(const base_node& bmin, const base_node& bmax,
129  std::vector<size_type>& idvec) {
130  pbox_set bs;
131  find_intersecting_boxes(bmin, bmax, bs);
132  pbox_set_to_idvec(bs, idvec);
133  }
134  void find_containing_boxes(const base_node& bmin, const base_node& bmax,
135  std::vector<size_type>& idvec) {
136  pbox_set bs;
137  find_containing_boxes(bmin, bmax, bs);
138  pbox_set_to_idvec(bs, idvec);
139  }
140  void find_contained_boxes(const base_node& bmin,
141  const base_node& bmax,
142  std::vector<size_type>& idvec) {
143  pbox_set bs;
144  find_contained_boxes(bmin, bmax, bs);
145  pbox_set_to_idvec(bs, idvec);
146  }
147  void find_boxes_at_point(const base_node& P,
148  std::vector<size_type>& idvec) const
149  { pbox_set bs; find_boxes_at_point(P, bs); pbox_set_to_idvec(bs, idvec); }
150  void find_line_intersecting_boxes(const base_node& org,
151  const base_small_vector& dirv,
152  std::vector<size_type>& idvec) {
153  pbox_set bs;
154  find_line_intersecting_boxes(org, dirv, bs);
155  pbox_set_to_idvec(bs, idvec);
156  }
157  void find_line_intersecting_boxes(const base_node& org,
158  const base_small_vector& dirv,
159  const base_node& bmin,
160  const base_node& bmax,
161  std::vector<size_type>& idvec) {
162  pbox_set bs;
163  find_line_intersecting_boxes(org, dirv, bmin, bmax, bs);
164  pbox_set_to_idvec(bs, idvec);
165  }
166 
167  void dump();
168  void build_tree();
169  private:
170  void pbox_set_to_idvec(pbox_set bs, std::vector<size_type>& idvec) const {
171  idvec.reserve(bs.size()); idvec.resize(0);
172  for (pbox_set::const_iterator it=bs.begin(); it != bs.end(); ++it)
173  idvec.push_back((*it)->id);
174  }
175 
176  const scalar_type EPS;
177  node_tab nodes;
178  box_cont boxes;
179  std::unique_ptr<rtree_elt_base> root;
180  bool tree_built;
181  getfem::lock_factory locks_;
182  };
183 
184 }
185 
186 #endif
bgeot_node_tab.h
Structure which dynamically collects points identifying points that are nearer than a certain very sm...
bgeot_small_vector.h
Small (dim < 8) vectors.
bgeot::node_tab
Store a set of points, identifying points that are nearer than a certain very small distance.
Definition: bgeot_node_tab.h:51
bgeot::rtree
Balanced tree of n-dimensional rectangles.
Definition: bgeot_rtree.h:97
bgeot::small_vector< scalar_type >
bgeot
Basic Geometric Tools.
Definition: bgeot_convex_ref.cc:26
bgeot::size_type
size_t size_type
used as the common size type in the library
Definition: bgeot_poly.h:48