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