All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
QuadtreePolarEuclid.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 QUADTREEPOLAREUCLID_H_
9 #define QUADTREEPOLAREUCLID_H_
10 
11 #include <vector>
12 #include <memory>
13 #include <cmath>
14 #include <omp.h>
15 #include <functional>
16 #include "QuadNodePolarEuclid.h"
17 
18 namespace NetworKit {
19 
20 template <class T>
23 public:
25  root = QuadNodePolarEuclid<T>();
26  this->maxRadius = 1;
27  }
28 
36  QuadtreePolarEuclid(double maxR,bool theoreticalSplit=false, double alpha=1, count capacity=1000, double balance = 0.5) {
37  root = QuadNodePolarEuclid<T>(0, 0, 2*M_PI, maxR, capacity, 0,theoreticalSplit,alpha,balance);
38  this->maxRadius = maxR;
39  }
40 
41  QuadtreePolarEuclid(const vector<double> &angles, const vector<double> &radii, const vector<T> &content, bool theoreticalSplit=false, count capacity=1000, double balance = 0.5) {
42  const count n = angles.size();
43  assert(angles.size() == radii.size());
44  assert(radii.size() == content.size());
45  maxRadius = 0;
46  for (double radius : radii) {
47  if (radius > maxRadius) maxRadius = radius;
48  }
49  maxRadius = std::nextafter(maxRadius, std::numeric_limits<double>::max());
50  root = QuadNodePolarEuclid<T>(0, 0, 2*M_PI, maxRadius, capacity, theoreticalSplit,balance);
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 
88  void getElementsInEuclideanCircle(const Point2D<double> circleCenter, const double radius, vector<T> &circleDenizens) const {
89  root.getElementsInEuclideanCircle(circleCenter, radius, false, circleDenizens);
90  }
91 
92  count getElementsProbabilistically(Point2D<double> euQuery, std::function<double(double)> prob, vector<T> &circleDenizens) {
93  return root.getElementsProbabilistically(euQuery, prob, false, circleDenizens);
94  }
95 
96  count getElementsProbabilistically(Point2D<double> euQuery, std::function<double(double)> prob, bool suppressLeft, vector<T> &circleDenizens) {
97  return root.getElementsProbabilistically(euQuery, prob, suppressLeft, circleDenizens);
98  }
99 
100  void recount() {
101  root.recount();
102  }
103 
104  count size() const {
105  return root.size();
106  }
107 
108  count height() const {
109  return root.height();
110  }
111 
112  count countLeaves() const {
113  return root.countLeaves();
114  }
115 
117  return root.indexSubtree(nextID);
118  }
119 
120  index getCellID(double phi, double r) const {
121  return root.getCellID(phi, r);
122  }
123 
124  double getMaxRadius() const {
125  return maxRadius;
126  }
127 
128  void reindex() {
129  #pragma omp parallel
130  {
131  #pragma omp single nowait
132  {
133  root.reindex(0);
134  }
135  }
136  }
137 
141  void trim() {
142  root.trim();
143  }
144 
145 private:
147  double maxRadius;
148 };
149 }
150 
151 #endif /* QUADTREE_H_ */
void reindex()
Definition: QuadtreePolarEuclid.h:128
QuadtreePolarEuclid(const vector< double > &angles, const vector< double > &radii, const vector< T > &content, bool theoreticalSplit=false, count capacity=1000, double balance=0.5)
Definition: QuadtreePolarEuclid.h:41
count countLeaves() const
Definition: QuadtreePolarEuclid.h:112
count getElementsProbabilistically(Point2D< double > euQuery, std::function< double(double)> prob, bool suppressLeft, vector< T > &circleDenizens)
Definition: QuadtreePolarEuclid.h:96
QuadtreePolarEuclid(double maxR, bool theoreticalSplit=false, double alpha=1, count capacity=1000, double balance=0.5)
Definition: QuadtreePolarEuclid.h:36
index indexSubtree(index nextID)
Definition: QuadtreePolarEuclid.h:116
count size() const
Definition: QuadtreePolarEuclid.h:104
uint64_t index
Typedefs.
Definition: Globals.h:20
bool removeContent(T toRemove, double angle, double r)
Definition: QuadtreePolarEuclid.h:71
void recount()
Definition: QuadtreePolarEuclid.h:100
vector< T > getElements() const
Get all elements, regardless of position.
Definition: QuadtreePolarEuclid.h:80
void addContent(T newcomer, double angle, double r)
Definition: QuadtreePolarEuclid.h:62
void trim()
trims the vectors used to hold the content in the leaf cells.
Definition: QuadtreePolarEuclid.h:141
index getCellID(double phi, double r) const
Definition: QuadtreePolarEuclid.h:120
void extractCoordinates(vector< double > &anglesContainer, vector< double > &radiiContainer) const
Definition: QuadtreePolarEuclid.h:84
Definition: QuadtreePolarEuclid.h:21
count getElementsProbabilistically(Point2D< double > euQuery, std::function< double(double)> prob, vector< T > &circleDenizens)
Definition: QuadtreePolarEuclid.h:92
count height() const
Definition: QuadtreePolarEuclid.h:108
uint64_t count
Definition: Globals.h:21
void getElementsInEuclideanCircle(const Point2D< double > circleCenter, const double radius, vector< T > &circleDenizens) const
Definition: QuadtreePolarEuclid.h:88
double getMaxRadius() const
Definition: QuadtreePolarEuclid.h:124
Definition: QuadNodePolarEuclid.h:28
friend class QuadTreePolarEuclidGTest
Definition: QuadtreePolarEuclid.h:22
QuadtreePolarEuclid()
Definition: QuadtreePolarEuclid.h:24