All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
Quadtree.h
Go to the documentation of this file.
1 /*
2  * Quadtree.h
3  *
4  * Created on: 21.05.2014
5  * Author: Moritz v. Looz (moritz.looz-corswarem@kit.edu)
6  */
7 
8 #ifndef QUADTREE_H_
9 #define QUADTREE_H_
10 
11 #include <vector>
12 #include <memory>
13 #include <cmath>
14 #include <omp.h>
15 #include <functional>
16 #include "QuadNode.h"
17 #include "../../geometric/HyperbolicSpace.h"
18 #include "../../auxiliary/Parallel.h"
19 
20 namespace NetworKit {
21 
22 template <class T, bool poincare=true>
23 class Quadtree {
24  friend class QuadTreeGTest;
25 public:
27  root = QuadNode<T, poincare>();
28  this->maxRadius = 1;
29  }
30 
38  Quadtree(double maxR,bool theoreticalSplit=false, double alpha=1, count capacity=1000, double balance = 0.5) {
39  root = QuadNode<T,poincare>(0, 0, 2*M_PI, maxR, capacity, theoreticalSplit,alpha,balance);
40  this->maxRadius = maxR;
41  }
42 
43  Quadtree(const vector<double> &angles, const vector<double> &radii, const vector<T> &content, double stretch, bool theoreticalSplit=false, double alpha=1, count capacity=1000, double balance = 0.5) {
44  const count n = angles.size();
45  assert(angles.size() == radii.size());
46  assert(radii.size() == content.size());
47  double R = stretch*HyperbolicSpace::hyperbolicAreaToRadius(n);
49  root = QuadNode<T>(0, 0, 2*M_PI, r, capacity, theoreticalSplit,alpha,balance);
50  maxRadius = r;
51  for (index i = 0; i < n; i++) {
52  assert(content[i] < n);
53  root.addContent(content[i], angles[i], radii[i]);
54  }
55  }
56 
62  void addContent(T newcomer, double angle, double r) {
63  root.addContent(newcomer, angle, r);
64  }
65 
71  bool removeContent(T toRemove, double angle, double r) {
72  return root.removeContent(toRemove, angle, r);
73  }
74 
80  vector<T> getElements() const {
81  return root.getElements();
82  }
83 
84  void extractCoordinates(vector<double> &anglesContainer, vector<double> &radiiContainer) const {
85  root.getCoordinates(anglesContainer, radiiContainer);
86  }
87 
95  vector<T> getElementsInHyperbolicCircle(Point2D<double> circleCenter, double hyperbolicRadius) const {
96  vector<T> circleDenizens;
97  getElementsInHyperbolicCircle(circleCenter, hyperbolicRadius, circleDenizens);
98  return circleDenizens;
99  }
100 
101  void getElementsInHyperbolicCircle(const Point2D<double> circleCenter, const double hyperbolicRadius, const bool suppressLeft, vector<T> &circleDenizens) const {
102  assert(circleDenizens.empty());
103  double cc_phi, cc_r;
104  HyperbolicSpace::cartesianToPolar(circleCenter, cc_phi, cc_r);
105  //Transform hyperbolic circle into Euclidean circle
106  double minPhi, maxPhi, radius, r_e;
107  HyperbolicSpace::getEuclideanCircle(cc_r, hyperbolicRadius, r_e, radius);
109  double minR = r_e - radius;
110  double maxR = r_e + radius;
111  //assert(maxR < 1);//this looks fishy
112  if (maxR > 1) maxR = 1;
113  if (minR < 0) {
114  maxR = std::max(abs(minR), maxR);
115  minR = 0;
116  minPhi = 0;
117  maxPhi = 2*M_PI;
118  } else {
119  double spread = asin(radius / r_e);
120  //double phi_c, r_c;
121  //HyperbolicSpace::cartesianToPolar(center, phi_c, r_c);
122  minPhi = cc_phi - spread;
123  maxPhi = cc_phi + spread;
127  }
128 
129  if (suppressLeft) minPhi = cc_phi;
134  bool wraparound = false;
135  root.getElementsInEuclideanCircle(center, radius, circleDenizens, minPhi, maxPhi, minR, maxR);
136  if (minPhi < 0) {
137  root.getElementsInEuclideanCircle(center, radius, circleDenizens, 2*M_PI+minPhi, 2*M_PI, minR, maxR);
138  wraparound = true;
139  }
140  if (maxPhi > 2*M_PI) {
141  root.getElementsInEuclideanCircle(center, radius, circleDenizens, 0, maxPhi - 2*M_PI, minR, maxR);
142  wraparound = true;
143  }
144 
145  for (T denizen : circleDenizens) {
146  if (denizen >= size()) {
147  DEBUG("Content ", denizen, " found in quadtree of size ", size(), ", as one of ", circleDenizens.size(), " neighbours.");
148  }
149  assert(denizen < size());//TODO: remove this after debugging, in general the quadtree should handle arbitrary contents
150  }
151 
152  //we have sort(deg(v)) here! This is not good, but does not make the asymptotical complexity of O(deg(v) log n) worse.
153  if (wraparound) {
154  Aux::Parallel::sort(circleDenizens.begin(), circleDenizens.end());
155  auto newend = unique(circleDenizens.begin(), circleDenizens.end());
156  count toRemove = circleDenizens.end() - newend;
157  count remaining = newend - circleDenizens.begin();
158  if (toRemove > 0) {
159  DEBUG("Removing, ", toRemove, " duplicate entries, keeping ", remaining);
160  circleDenizens.resize(remaining);
161  }
162  }
163 
164  for (T denizen : circleDenizens) {
165  if (denizen >= size()) DEBUG("Content ", denizen, " found in quadtree of size ", size(), ", as one of ", circleDenizens.size(), " neighbours, after sorting");
166  assert(denizen < size());//TODO: remove this after debugging, in general the quadtree should handle arbitrary contents
167  }
168  }
169 
170  void getElementsInHyperbolicCircle(const Point2D<double> circleCenter, const double hyperbolicRadius, vector<T> &circleDenizens) const {
171  getElementsInHyperbolicCircle(circleCenter, hyperbolicRadius, false, circleDenizens);
172  }
173 
174  count getElementsProbabilistically(Point2D<double> euQuery, std::function<double(double)> prob, vector<T> &circleDenizens) {
175  return root.getElementsProbabilistically(euQuery, prob, false, circleDenizens);
176  }
177 
178  count getElementsProbabilistically(Point2D<double> euQuery, std::function<double(double)> prob, bool suppressLeft, vector<T> &circleDenizens) {
179  return root.getElementsProbabilistically(euQuery, prob, suppressLeft, circleDenizens);
180  }
181 
182  void recount() {
183  root.recount();
184  }
185 
186  count size() const {
187  return root.size();
188  }
189 
190  count height() const {
191  return root.height();
192  }
193 
194  count countLeaves() const {
195  return root.countLeaves();
196  }
197 
199  return root.indexSubtree(nextID);
200  }
201 
202  index getCellID(double phi, double r) const {
203  return root.getCellID(phi, r);
204  }
205 
206  double getMaxRadius() const {
207  return maxRadius;
208  }
209 
210  void reindex() {
211  #pragma omp parallel
212  {
213  #pragma omp single nowait
214  {
215  root.reindex(0);
216  }
217  }
218  }
219 
223  void trim() {
224  root.trim();
225  }
226 
227 private:
229  double maxRadius;
230 };
231 }
232 
233 #endif /* QUADTREE_H_ */
void recount()
Definition: Quadtree.h:182
static double hyperbolicAreaToRadius(double area)
Definition: HyperbolicSpace.h:128
Quadtree(const vector< double > &angles, const vector< double > &radii, const vector< T > &content, double stretch, bool theoreticalSplit=false, double alpha=1, count capacity=1000, double balance=0.5)
Definition: Quadtree.h:43
static double hyperbolicRadiusToEuclidean(double hyperbolicRadius)
Project radial coordinates of the hyperbolic plane into the Poincare disk model.
Definition: HyperbolicSpace.cpp:139
vector< T > getElements() const
Get all elements, regardless of position.
Definition: Quadtree.h:80
double getMaxRadius() const
Definition: Quadtree.h:206
friend class QuadTreeGTest
Definition: Quadtree.h:24
uint64_t index
Typedefs.
Definition: Globals.h:20
#define DEBUG(...)
Definition: Log.h:82
Quadtree()
Definition: Quadtree.h:26
static Point2D< double > polarToCartesian(double phi, double r)
Definition: HyperbolicSpace.cpp:98
vector< T > getElementsInHyperbolicCircle(Point2D< double > circleCenter, double hyperbolicRadius) const
Get elements whose hyperbolic distance to the query point is less than the hyperbolic distance...
Definition: Quadtree.h:95
void addContent(T newcomer, double angle, double r)
Definition: Quadtree.h:62
static void getEuclideanCircle(Point2D< double > hyperbolicCenter, double hyperbolicRadius, Point2D< double > &euclideanCenter, double &euclideanRadius)
Converts a hyperbolic circle to a Euclidean circle.
Definition: HyperbolicSpace.cpp:124
void extractCoordinates(vector< double > &anglesContainer, vector< double > &radiiContainer) const
Definition: Quadtree.h:84
Definition: QuadNode.h:27
uint64_t count
Definition: Globals.h:21
void getElementsInHyperbolicCircle(const Point2D< double > circleCenter, const double hyperbolicRadius, const bool suppressLeft, vector< T > &circleDenizens) const
Definition: Quadtree.h:101
count height() const
Definition: Quadtree.h:190
void trim()
trims the vectors used to hold the content in the leaf cells.
Definition: Quadtree.h:223
index getCellID(double phi, double r) const
Definition: Quadtree.h:202
bool removeContent(T toRemove, double angle, double r)
Definition: Quadtree.h:71
count getElementsProbabilistically(Point2D< double > euQuery, std::function< double(double)> prob, bool suppressLeft, vector< T > &circleDenizens)
Definition: Quadtree.h:178
static void cartesianToPolar(Point2D< double > a, double &phi, double &r)
Definition: HyperbolicSpace.cpp:113
count getElementsProbabilistically(Point2D< double > euQuery, std::function< double(double)> prob, vector< T > &circleDenizens)
Definition: Quadtree.h:174
count countLeaves() const
Definition: Quadtree.h:194
void reindex()
Definition: Quadtree.h:210
count size() const
Definition: Quadtree.h:186
void getElementsInHyperbolicCircle(const Point2D< double > circleCenter, const double hyperbolicRadius, vector< T > &circleDenizens) const
Definition: Quadtree.h:170
index indexSubtree(index nextID)
Definition: Quadtree.h:198
Definition: Quadtree.h:23
Quadtree(double maxR, bool theoreticalSplit=false, double alpha=1, count capacity=1000, double balance=0.5)
Definition: Quadtree.h:38