All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
QuadtreeCartesianEuclid.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 QUADTREECARTESIANEUCLID_H_
9 #define QUADTREECARTESIANEUCLID_H_
10 
11 #include <vector>
12 #include <memory>
13 #include <cmath>
14 #include <omp.h>
15 #include <functional>
17 
18 namespace NetworKit {
19 
20 template <class T>
23 public:
31  QuadtreeCartesianEuclid(Point<double> lower = Point<double>({0.0, 0.0}), Point<double> upper = Point<double>({1.0, 1.0}), bool theoreticalSplit=false, count capacity=1000) {
32  assert(lower.getDimensions() == upper.getDimensions());
33  root = QuadNodeCartesianEuclid<T>(lower, upper, capacity, theoreticalSplit);
34  this->lower = lower;
35  this->upper = upper;
36  }
37 
38  QuadtreeCartesianEuclid(const vector<Point<double> > &positions, const vector<T> &content, bool theoreticalSplit=false, count capacity=1000) {
39  const count n = positions.size();
40  assert(content.size() == n);
41  assert(n > 0);
42 
43  this->dimension = positions[0].getDimensions();
44  vector<double> lowerValue(dimension);
45  vector<double> upperValue(dimension);
46  for (index d = 0; d < dimension; d++) {
47  lowerValue[d] = positions[0].at(d);
48  upperValue[d] = positions[0].at(d);
49  }
50 
51  for (Point<double> pos : positions) {
52  assert(pos.getDimensions() == dimension);
53  for (index d = 0; d < dimension; d++) {
54  if (pos[d] < lowerValue[d]) lowerValue[d] = pos[d];
55  if (pos[d] > upperValue[d]) upperValue[d] = pos[d];
56  }
57  }
58 
59  //the upper limit is open, so it needs to be above the points
60  for (index d = 0; d < dimension; d++) {
61  upperValue[d] = std::nextafter(upperValue[d], std::numeric_limits<double>::max());
62  }
63  this->lower = Point<double>(lowerValue);
64  this->upper = Point<double>(upperValue);
65 
66  root = QuadNodeCartesianEuclid<T>(lower, upper, capacity, theoreticalSplit);
67  for (index i = 0; i < n; i++) {
68  assert(content[i] < n);
69  root.addContent(content[i], positions[i]);
70  }
71  }
72 
78  void addContent(T newcomer, Point<double> pos) {
79  root.addContent(newcomer, pos);
80  }
81 
87  bool removeContent(T toRemove, Point<double> pos) {
88  return root.removeContent(toRemove, pos);
89  }
90 
96  vector<T> getElements() const {
97  return root.getElements();
98  }
99 
100  void extractCoordinates(vector<Point<double> > &posContainer) const {
101  root.getCoordinates(posContainer);
102  }
103 
104  void getElementsInEuclideanCircle(const Point<double> circleCenter, const double radius, vector<T> &circleDenizens) const {
105  root.getElementsInEuclideanCircle(circleCenter, radius, circleDenizens);
106  }
107 
108  template<typename L>
109  count getElementsProbabilistically(Point<double> euQuery, L prob, vector<T> &circleDenizens) {
110  return root.getElementsProbabilistically(euQuery, prob, circleDenizens);
111  }
112 
113  void recount() {
114  root.recount();
115  }
116 
117  count size() const {
118  return root.size();
119  }
120 
121  count height() const {
122  return root.height();
123  }
124 
125  count countLeaves() const {
126  return root.countLeaves();
127  }
128 
130  return root.indexSubtree(nextID);
131  }
132 
134  return root.getCellID(pos);
135  }
136 
137  void reindex() {
138  #pragma omp parallel
139  {
140  #pragma omp single nowait
141  {
142  root.reindex(0);
143  }
144  }
145  }
146 
150  void trim() {
151  root.trim();
152  }
153 
154 private:
156  Point<double> lower;
157  Point<double> upper;
158  count dimension;
159 };
160 }
161 
162 #endif /* QUADTREE_H_ */
index indexSubtree(index nextID)
Definition: QuadtreeCartesianEuclid.h:129
uint64_t index
Typedefs.
Definition: Globals.h:20
count getElementsProbabilistically(Point< double > euQuery, L prob, vector< T > &circleDenizens)
Definition: QuadtreeCartesianEuclid.h:109
vector< T > getElements() const
Get all elements, regardless of position.
Definition: QuadtreeCartesianEuclid.h:96
QuadtreeCartesianEuclid(Point< double > lower=Point< double >({0.0, 0.0}), Point< double > upper=Point< double >({1.0, 1.0}), bool theoreticalSplit=false, count capacity=1000)
Definition: QuadtreeCartesianEuclid.h:31
void extractCoordinates(vector< Point< double > > &posContainer) const
Definition: QuadtreeCartesianEuclid.h:100
Definition: QuadNodeCartesianEuclid.h:28
bool removeContent(T toRemove, Point< double > pos)
Definition: QuadtreeCartesianEuclid.h:87
count countLeaves() const
Definition: QuadtreeCartesianEuclid.h:125
index getCellID(Point< double > pos) const
Definition: QuadtreeCartesianEuclid.h:133
friend class QuadTreeCartesianEuclidGTest
Definition: QuadtreeCartesianEuclid.h:22
Definition: QuadtreeCartesianEuclid.h:21
uint64_t count
Definition: Globals.h:21
void getElementsInEuclideanCircle(const Point< double > circleCenter, const double radius, vector< T > &circleDenizens) const
Definition: QuadtreeCartesianEuclid.h:104
void trim()
trims the vectors used to hold the content in the leaf cells.
Definition: QuadtreeCartesianEuclid.h:150
void reindex()
Definition: QuadtreeCartesianEuclid.h:137
void recount()
Definition: QuadtreeCartesianEuclid.h:113
QuadtreeCartesianEuclid(const vector< Point< double > > &positions, const vector< T > &content, bool theoreticalSplit=false, count capacity=1000)
Definition: QuadtreeCartesianEuclid.h:38
void addContent(T newcomer, Point< double > pos)
Definition: QuadtreeCartesianEuclid.h:78
count size() const
Definition: QuadtreeCartesianEuclid.h:117
count getDimensions() const
Definition: Point.h:50
count height() const
Definition: QuadtreeCartesianEuclid.h:121