DOLFIN
DOLFIN C++ interface
Loading...
Searching...
No Matches
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
29namespace 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
Specialization of bounding box implementation to 1D.
Definition BoundingBoxTree1D.h:35
bool point_in_bbox(const double *x, unsigned int node) const
Check whether point (x) is in bounding box (node)
Definition BoundingBoxTree1D.h:67
std::size_t gdim() const
Return geometric dimension.
Definition BoundingBoxTree1D.h:58
double compute_squared_distance_bbox(const double *x, unsigned int node) const
Compute squared distance between point and bounding box.
Definition BoundingBoxTree1D.h:83
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
double compute_squared_distance_point(const double *x, unsigned int node) const
Compute squared distance between point and point.
Definition BoundingBoxTree1D.h:101
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
const double * get_bbox_coordinates(unsigned int node) const
Return bounding box coordinates for node.
Definition BoundingBoxTree1D.h:61
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
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 GenericBoundingBoxTree.h:41
std::vector< double > _bbox_coordinates
List of bounding box coordinates.
Definition GenericBoundingBoxTree.h:118
Definition adapt.h:30
void begin(std::string msg,...)
Begin task (increase indentation level)
Definition log.cpp:153
void end()
End task (decrease indentation level)
Definition log.cpp:168
Definition BoundingBoxTree1D.h:41
bool operator()(unsigned int i, unsigned int j)
Comparison operator.
Definition BoundingBoxTree1D.h:49
less_x(const std::vector< double > &bboxes)
Constructor.
Definition BoundingBoxTree1D.h:46
const std::vector< double > & bboxes
Bounding boxes.
Definition BoundingBoxTree1D.h:43