DOLFIN
DOLFIN C++ interface
BoundingBoxTree1D.h
1 // Copyright (C) 2013 Anders Logg
2 //
3 // This file is part of DOLFIN.
4 //
5 // DOLFIN is free software: you can redistribute it and/or modify
6 // it under the terms of the GNU Lesser General Public License as published by
7 // the Free Software Foundation, either version 3 of the License, or
8 // (at your option) any later version.
9 //
10 // DOLFIN is distributed in the hope that it will be useful,
11 // but WITHOUT ANY WARRANTY; without even the implied warranty of
12 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 // GNU Lesser General Public License for more details.
14 //
15 // You should have received a copy of the GNU Lesser General Public License
16 // along with DOLFIN. If not, see <http://www.gnu.org/licenses/>.
17 //
18 // First added: 2013-05-02
19 // Last changed: 2014-02-24
20 
21 #ifndef __BOUNDING_BOX_TREE_1D_H
22 #define __BOUNDING_BOX_TREE_1D_H
23 
24 #include <algorithm>
25 #include <vector>
26 #include <dolfin/common/constants.h>
27 #include "GenericBoundingBoxTree.h"
28 
29 namespace dolfin
30 {
31 
33 
35  {
36  protected:
37 
40  struct less_x
41  {
43  const std::vector<double>& bboxes;
44 
46  less_x(const std::vector<double>& bboxes): bboxes(bboxes) {}
47 
49  inline bool operator()(unsigned int i, unsigned int j)
50  {
51  const double* bi = bboxes.data() + 2*i;
52  const double* bj = bboxes.data() + 2*j;
53  return bi[0] + bi[1] < bj[0] + bj[1];
54  }
55  };
56 
58  std::size_t gdim() const { return 1; }
59 
61  const double* get_bbox_coordinates(unsigned int node) const
62  {
63  return _bbox_coordinates.data() + 2*node;
64  }
65 
67  bool point_in_bbox(const double* x, unsigned int node) const
68  {
69  const double* b = _bbox_coordinates.data() + 2*node;
70  const double eps = DOLFIN_EPS_LARGE*(b[1] - b[0]);
71  return b[0] - eps <= x[0] && x[0] <= b[1] + eps;
72  }
73 
75  bool bbox_in_bbox(const double* a, unsigned int node) const
76  {
77  const double* b = _bbox_coordinates.data() + 2*node;
78  const double eps = DOLFIN_EPS_LARGE*(b[1] - b[0]);
79  return b[0] - eps <= a[1] && a[0] <= b[1] + eps;
80  }
81 
83  double compute_squared_distance_bbox(const double* x,
84  unsigned int node) const
85  {
86  // Note: Some else-if might be in order here but I assume the
87  // compiler can do a better job at optimizing/parallelizing this
88  // version. This is also the way the algorithm is presented in
89  // Ericsson.
90 
91  const double* b = _bbox_coordinates.data() + 2*node;
92  double r2 = 0.0;
93 
94  if (x[0] < b[0]) r2 += (x[0] - b[0])*(x[0] - b[0]);
95  if (x[0] > b[1]) r2 += (x[0] - b[1])*(x[0] - b[1]);
96 
97  return r2;
98  }
99 
101  double compute_squared_distance_point(const double* x,
102  unsigned int node) const
103  {
104  const double* p = _bbox_coordinates.data() + 2*node;
105  return (x[0] - p[0])*(x[0] - p[0]);
106  }
107 
109  void compute_bbox_of_bboxes(double* bbox,
110  std::size_t& axis,
111  const std::vector<double>& leaf_bboxes,
112  const std::vector<unsigned int>::iterator& begin,
113  const std::vector<unsigned int>::iterator& end)
114  {
115  typedef std::vector<unsigned int>::const_iterator iterator;
116 
117  // Get coordinates for first box
118  iterator it = begin;
119  const double* b = leaf_bboxes.data() + 2*(*it);
120  bbox[0] = b[0];
121  bbox[1] = b[1];
122 
123  // Compute min and max over remaining boxes
124  for (++it; it != end; ++it)
125  {
126  const double* b = leaf_bboxes.data() + 2*(*it);
127  if (b[0] < bbox[0]) bbox[0] = b[0];
128  if (b[1] > bbox[1]) bbox[1] = b[1];
129  }
130 
131  // Compute longest axis
132  axis = 0;
133  }
134 
136  void compute_bbox_of_points(double* bbox,
137  std::size_t& axis,
138  const std::vector<Point>& points,
139  const std::vector<unsigned int>::iterator& begin,
140  const std::vector<unsigned int>::iterator& end)
141  {
142  typedef std::vector<unsigned int>::const_iterator iterator;
143 
144  // Get coordinates for first point
145  iterator it = begin;
146  const double* p = points[*it].coordinates();
147  bbox[0] = p[0];
148  bbox[1] = p[0];
149 
150  // Compute min and max over remaining boxes
151  for (; it != end; ++it)
152  {
153  const double* p = points[*it].coordinates();
154  if (p[0] < bbox[0]) bbox[0] = p[0];
155  if (p[0] > bbox[1]) bbox[1] = p[0];
156  }
157 
158  // Compute longest axis
159  axis = 0;
160  }
161 
163  void sort_bboxes(std::size_t axis,
164  const std::vector<double>& leaf_bboxes,
165  const std::vector<unsigned int>::iterator& begin,
166  const std::vector<unsigned int>::iterator& middle,
167  const std::vector<unsigned int>::iterator& end)
168  {
169  std::nth_element(begin, middle, end, less_x(leaf_bboxes));
170  }
171 
172  };
173 
174 }
175 
176 #endif
void compute_bbox_of_bboxes(double *bbox, std::size_t &axis, const std::vector< double > &leaf_bboxes, const std::vector< unsigned int >::iterator &begin, const std::vector< unsigned int >::iterator &end)
Compute bounding box of bounding boxes.
Definition: BoundingBoxTree1D.h:109
Definition: adapt.h:29
Definition: GenericBoundingBoxTree.h:40
void begin(std::string msg,...)
Begin task (increase indentation level)
Definition: log.cpp:153
void sort_bboxes(std::size_t axis, const std::vector< double > &leaf_bboxes, const std::vector< unsigned int >::iterator &begin, const std::vector< unsigned int >::iterator &middle, const std::vector< unsigned int >::iterator &end)
Sort leaf bounding boxes along given axis.
Definition: BoundingBoxTree1D.h:163
const double * get_bbox_coordinates(unsigned int node) const
Return bounding box coordinates for node.
Definition: BoundingBoxTree1D.h:61
void compute_bbox_of_points(double *bbox, std::size_t &axis, const std::vector< Point > &points, const std::vector< unsigned int >::iterator &begin, const std::vector< unsigned int >::iterator &end)
Compute bounding box of points.
Definition: BoundingBoxTree1D.h:136
bool point_in_bbox(const double *x, unsigned int node) const
Check whether point (x) is in bounding box (node)
Definition: BoundingBoxTree1D.h:67
bool operator()(unsigned int i, unsigned int j)
Comparison operator.
Definition: BoundingBoxTree1D.h:49
void end()
End task (decrease indentation level)
Definition: log.cpp:168
less_x(const std::vector< double > &bboxes)
Constructor.
Definition: BoundingBoxTree1D.h:46
bool bbox_in_bbox(const double *a, unsigned int node) const
Check whether bounding box (a) collides with bounding box (node)
Definition: BoundingBoxTree1D.h:75
double compute_squared_distance_bbox(const double *x, unsigned int node) const
Compute squared distance between point and bounding box.
Definition: BoundingBoxTree1D.h:83
std::size_t gdim() const
Return geometric dimension.
Definition: BoundingBoxTree1D.h:58
const std::vector< double > & bboxes
Bounding boxes.
Definition: BoundingBoxTree1D.h:43
std::vector< double > _bbox_coordinates
List of bounding box coordinates.
Definition: GenericBoundingBoxTree.h:118
Specialization of bounding box implementation to 1D.
Definition: BoundingBoxTree1D.h:34
double compute_squared_distance_point(const double *x, unsigned int node) const
Compute squared distance between point and point.
Definition: BoundingBoxTree1D.h:101
Definition: BoundingBoxTree1D.h:40