GetFEM++  5.3
bgeot_rtree.h
Go to the documentation of this file.
1 /* -*- c++ -*- (enables emacs c++ mode) */
2 /*===========================================================================
3 
4  Copyright (C) 2000-2017 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 
44 namespace bgeot {
45 
46  struct box_index {
47  size_type id;
48  base_node min, max;
49  };
50 
51  struct rtree_elt_base {
52  enum { RECTS_PER_LEAF=8 };
53  bool isleaf_;
54  bool isleaf() const { return isleaf_; }
55  base_node rmin, rmax;
56  rtree_elt_base(bool leaf, const base_node& rmin_, const base_node& rmax_)
57  : isleaf_(leaf), rmin(rmin_), rmax(rmax_) {}
58  virtual ~rtree_elt_base() {}
59  };
60 
61  /** Balanced tree of n-dimensional rectangles.
62  *
63  * This is not a dynamic structure. Once a query has been made on the
64  * tree, new boxes should not be added.
65  */
66  class rtree : public boost::noncopyable {
67  public:
68  typedef std::deque<box_index> box_cont;
69  typedef std::vector<const box_index*> pbox_cont;
70  typedef std::set<const box_index*> pbox_set;
71 
72  void add_box(base_node min, base_node max, size_type id=size_type(-1)) {
73  box_index bi; bi.min = min; bi.max = max;
74  bi.id = (id + 1) ? id : boxes.size();
75  boxes.push_back(bi);
76  }
77  size_type nb_boxes() const { return boxes.size(); }
78  void clear() { root = std::unique_ptr<rtree_elt_base>(); boxes.clear(); }
79 
80  void find_intersecting_boxes(const base_node& bmin, const base_node& bmax,
81  pbox_set& boxlst);
82  void find_containing_boxes(const base_node& bmin, const base_node& bmax,
83  pbox_set& boxlst);
84  void find_contained_boxes(const base_node& bmin, const base_node& bmax,
85  pbox_set& boxlst);
86  void find_boxes_at_point(const base_node& P, pbox_set& boxlst);
87  void find_line_intersecting_boxes(const base_node& org,
88  const base_small_vector& dirv,
89  pbox_set& boxlst);
90  void find_line_intersecting_boxes(const base_node& org,
91  const base_small_vector& dirv,
92  const base_node& bmin,
93  const base_node& bmax,
94  pbox_set& boxlst);
95 
96  void find_intersecting_boxes(const base_node& bmin, const base_node& bmax,
97  std::vector<size_type>& idvec) {
98  pbox_set bs;
99  find_intersecting_boxes(bmin, bmax, bs);
100  pbox_set_to_idvec(bs, idvec);
101  }
102  void find_containing_boxes(const base_node& bmin, const base_node& bmax,
103  std::vector<size_type>& idvec) {
104  pbox_set bs;
105  find_containing_boxes(bmin, bmax, bs);
106  pbox_set_to_idvec(bs, idvec);
107  }
108  void find_contained_boxes(const base_node& bmin,
109  const base_node& bmax,
110  std::vector<size_type>& idvec) {
111  pbox_set bs;
112  find_contained_boxes(bmin, bmax, bs);
113  pbox_set_to_idvec(bs, idvec);
114  }
115  void find_boxes_at_point(const base_node& P, std::vector<size_type>& idvec)
116  { pbox_set bs; find_boxes_at_point(P, bs); pbox_set_to_idvec(bs, idvec); }
117  void find_line_intersecting_boxes(const base_node& org,
118  const base_small_vector& dirv,
119  std::vector<size_type>& idvec) {
120  pbox_set bs;
121  find_line_intersecting_boxes(org, dirv, bs);
122  pbox_set_to_idvec(bs, idvec);
123  }
124  void find_line_intersecting_boxes(const base_node& org,
125  const base_small_vector& dirv,
126  const base_node& bmin,
127  const base_node& bmax,
128  std::vector<size_type>& idvec) {
129  pbox_set bs;
130  find_line_intersecting_boxes(org, dirv, bmin, bmax, bs);
131  pbox_set_to_idvec(bs, idvec);
132  }
133 
134  void dump();
135  void build_tree();
136  private:
137  static void pbox_set_to_idvec(pbox_set bs, std::vector<size_type>& idvec) {
138  idvec.reserve(bs.size()); idvec.resize(0);
139  for (pbox_set::const_iterator it=bs.begin(); it != bs.end(); ++it)
140  idvec.push_back((*it)->id);
141  }
142 
143  box_cont boxes;
144  std::unique_ptr<rtree_elt_base> root;
145  getfem::lock_factory locks_;
146  };
147 
148 }
149 
150 #endif
bgeot_small_vector.h
Small (dim < 8) vectors.
bgeot::small_vector< scalar_type >
bgeot::size_type
size_t size_type
used as the common size type in the library
Definition: bgeot_poly.h:49
bgeot
Basic Geometric Tools.
Definition: bgeot_convex_ref.cc:27
bgeot::rtree
Balanced tree of n-dimensional rectangles.
Definition: bgeot_rtree.h:66