All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
QuadNode.h
Go to the documentation of this file.
1 /*
2  * QuadNode.h
3  *
4  * Created on: 21.05.2014
5  * Author: Moritz v. Looz (moritz.looz-corswarem@kit.edu)
6  */
7 
8 #ifndef QUADNODE_H_
9 #define QUADNODE_H_
10 
11 #include <vector>
12 #include <algorithm>
13 #include <functional>
14 #include <assert.h>
15 #include "../../auxiliary/Log.h"
16 #include "../../auxiliary/Parallel.h"
17 #include "../../geometric/HyperbolicSpace.h"
18 
19 using std::vector;
20 using std::min;
21 using std::max;
22 using std::cos;
23 
24 namespace NetworKit {
25 
26 template <class T, bool poincare = true>
27 class QuadNode {
28  friend class QuadTreeGTest;
29 private:
30  double leftAngle;
31  double minR;
32  double rightAngle;
33  double maxR;
34  Point2D<double> a,b,c,d;
35  unsigned capacity;
36  static const unsigned coarsenLimit = 4;
37  count subTreeSize;
38  std::vector<T> content;
39  std::vector<Point2D<double> > positions;
40  std::vector<double> angles;
41  std::vector<double> radii;
42  bool isLeaf;
43  bool splitTheoretical;
44  double alpha;
45  double balance;
46  index ID;
47  double lowerBoundR;
48 
49 public:
50  std::vector<QuadNode> children;
51 
53  //This should never be called.
54  leftAngle = 0;
55  rightAngle = 0;
56  minR = 0;
57  maxR = 0;
58  capacity = 20;
59  isLeaf = true;
60  subTreeSize = 0;
61  balance = 0.5;
62  splitTheoretical = false;
63  alpha = 1;
64  lowerBoundR = maxR;
65  ID = 0;
66  }
67 
83  QuadNode(double leftAngle, double minR, double rightAngle, double maxR, unsigned capacity = 1000, bool splitTheoretical = false, double alpha = 1, double balance = 0.5) {
84  if (balance <= 0 || balance >= 1) throw std::runtime_error("Quadtree balance parameter must be between 0 and 1.");
85  if (poincare && maxR > 1) throw std::runtime_error("The Poincare disk has a radius of 1, cannot create quadtree larger than that!");
86  this->leftAngle = leftAngle;
87  this->minR = minR;
88  this->maxR = maxR;
89  this->rightAngle = rightAngle;
90  this->a = HyperbolicSpace::polarToCartesian(leftAngle, minR);
91  this->b = HyperbolicSpace::polarToCartesian(rightAngle, minR);
92  this->c = HyperbolicSpace::polarToCartesian(rightAngle, maxR);
93  this->d = HyperbolicSpace::polarToCartesian(leftAngle, maxR);
94  this->capacity = capacity;
95  this->alpha = alpha;
96  this->splitTheoretical = splitTheoretical;
97  this->balance = balance;
98  this->lowerBoundR = maxR;
99  this->ID = 0;
100  isLeaf = true;
101  subTreeSize = 0;
102  }
103 
104  void split() {
105  assert(isLeaf);
106  //heavy lifting: split up!
107  double middleAngle = (rightAngle - leftAngle) / 2 + leftAngle;
113  double middleR;
114 
115  if (poincare) {
116  if (splitTheoretical) {
117  double hyperbolicOuter = HyperbolicSpace::EuclideanRadiusToHyperbolic(maxR);
118  double hyperbolicInner = HyperbolicSpace::EuclideanRadiusToHyperbolic(minR);
119  double hyperbolicMiddle = acosh((1-balance)*cosh(alpha*hyperbolicOuter) + balance*cosh(alpha*hyperbolicInner))/alpha;
120  middleR = HyperbolicSpace::hyperbolicRadiusToEuclidean(hyperbolicMiddle);
121  } else {
122  double nom = maxR - minR;
123  double denom = pow((1-maxR*maxR)/(1-minR*minR), 0.5)+1;
124  middleR = nom/denom + minR;
125  }
126  } else {
127  middleR = acosh((1-balance)*cosh(alpha*maxR) + balance*cosh(alpha*minR))/alpha;
128  }
129 
130  //one could also use the median here. Results in worse asymptotical complexity, but maybe better runtime?
131 
132  assert(middleR < maxR);
133  assert(middleR > minR);
134 
135  QuadNode<index,poincare> southwest(leftAngle, minR, middleAngle, middleR, capacity, splitTheoretical, alpha, balance);
136  QuadNode<index,poincare> southeast(middleAngle, minR, rightAngle, middleR, capacity, splitTheoretical, alpha, balance);
137  QuadNode<index,poincare> northwest(leftAngle, middleR, middleAngle, maxR, capacity, splitTheoretical, alpha, balance);
138  QuadNode<index,poincare> northeast(middleAngle, middleR, rightAngle, maxR, capacity, splitTheoretical, alpha, balance);
139  children = {southwest, southeast, northwest, northeast};
140  isLeaf = false;
141  }
142 
150  void addContent(T input, double angle, double R) {
151  assert(this->responsible(angle, R));
152  if (lowerBoundR > R) lowerBoundR = R;
153  if (isLeaf) {
154  if (content.size() + 1 < capacity) {
155  content.push_back(input);
156  angles.push_back(angle);
157  radii.push_back(R);
159  positions.push_back(pos);
160  } else {
161 
162  split();
163 
164  for (index i = 0; i < content.size(); i++) {
165  this->addContent(content[i], angles[i], radii[i]);
166  }
167  assert(subTreeSize == content.size());//we have added everything twice
168  subTreeSize = content.size();
169  content.clear();
170  angles.clear();
171  radii.clear();
172  positions.clear();
173  this->addContent(input, angle, R);
174  }
175  }
176  else {
177  assert(children.size() > 0);
178  for (index i = 0; i < children.size(); i++) {
179  if (children[i].responsible(angle, R)) {
180  children[i].addContent(input, angle, R);
181  break;
182  }
183  }
184  subTreeSize++;
185  }
186  }
187 
197  bool removeContent(T input, double angle, double R) {
198  if (!responsible(angle, R)) return false;
199  if (isLeaf) {
200  index i = 0;
201  for (; i < content.size(); i++) {
202  if (content[i] == input) break;
203  }
204  if (i < content.size()) {
205  assert(angles[i] == angle);
206  assert(radii[i] == R);
207  //remove element
208  content.erase(content.begin()+i);
209  positions.erase(positions.begin()+i);
210  angles.erase(angles.begin()+i);
211  radii.erase(radii.begin()+i);
212  return true;
213  } else {
214  return false;
215  }
216  }
217  else {
218  bool removed = false;
219  bool allLeaves = true;
220  assert(children.size() > 0);
221  for (index i = 0; i < children.size(); i++) {
222  if (!children[i].isLeaf) allLeaves = false;
223  if (children[i].removeContent(input, angle, R)) {
224  assert(!removed);
225  removed = true;
226  }
227  }
228  if (removed) subTreeSize--;
229  //coarsen?
230  if (removed && allLeaves && size() < coarsenLimit) {
231  //coarsen!!
232  //why not assert empty containers and then insert directly?
233  vector<T> allContent;
234  vector<Point2D<double> > allPositions;
235  vector<double> allAngles;
236  vector<double> allRadii;
237  for (index i = 0; i < children.size(); i++) {
238  allContent.insert(allContent.end(), children[i].content.begin(), children[i].content.end());
239  allPositions.insert(allPositions.end(), children[i].positions.begin(), children[i].positions.end());
240  allAngles.insert(allAngles.end(), children[i].angles.begin(), children[i].angles.end());
241  allRadii.insert(allRadii.end(), children[i].radii.begin(), children[i].radii.end());
242  }
243  assert(subTreeSize == allContent.size());
244  assert(subTreeSize == allPositions.size());
245  assert(subTreeSize == allAngles.size());
246  assert(subTreeSize == allRadii.size());
247  children.clear();
248  content.swap(allContent);
249  positions.swap(allPositions);
250  angles.swap(allAngles);
251  radii.swap(allRadii);
252  isLeaf = true;
253  }
254 
255  return removed;
256  }
257  }
258 
259 
268  bool outOfReach(Point2D<double> query, double radius) const {
269  double phi, r;
270  HyperbolicSpace::cartesianToPolar(query, phi, r);
271  if (responsible(phi, r)) return false;
272 
273  //if using native coordinates, call distance calculation
274  if (!poincare) return hyperbolicDistances(phi, r).first > radius;
275 
276  //get four edge points
277  double topDistance, bottomDistance, leftDistance, rightDistance;
278 
279  if (phi < leftAngle || phi > rightAngle) {
280  topDistance = min(c.distance(query), d.distance(query));
281  } else {
282  topDistance = abs(r - maxR);
283  }
284  if (topDistance <= radius) return false;
285  if (phi < leftAngle || phi > rightAngle) {
286  bottomDistance = min(a.distance(query), b.distance(query));
287  } else {
288  bottomDistance = abs(r - minR);
289  }
290  if (bottomDistance <= radius) return false;
291 
292  double minDistanceR = r*cos(abs(phi-leftAngle));
293  if (minDistanceR > minR && minDistanceR < maxR) {
294  leftDistance = query.distance(HyperbolicSpace::polarToCartesian(phi, minDistanceR));
295  } else {
296  leftDistance = min(a.distance(query), d.distance(query));
297  }
298  if (leftDistance <= radius) return false;
299 
300  minDistanceR = r*cos(abs(phi-rightAngle));
301  if (minDistanceR > minR && minDistanceR < maxR) {
302  rightDistance = query.distance(HyperbolicSpace::polarToCartesian(phi, minDistanceR));
303  } else {
304  rightDistance = min(b.distance(query), c.distance(query));
305  }
306  if (rightDistance <= radius) return false;
307  return true;
308  }
309 
320  bool outOfReach(double angle_c, double r_c, double radius) const {
321  if (responsible(angle_c, r_c)) return false;
323  return outOfReach(query, radius);
324  }
325 
326 
331  std::pair<double, double> hyperbolicDistances(double phi, double r) const {
332  double minRHyper, maxRHyper, r_h;
333  if (poincare) {
334  minRHyper=HyperbolicSpace::EuclideanRadiusToHyperbolic(this->minR);
335  maxRHyper=HyperbolicSpace::EuclideanRadiusToHyperbolic(this->maxR);
337  } else {
338  minRHyper=this->minR;
339  maxRHyper=this->maxR;
340  r_h = r;
341  }
342 
343  double coshr = cosh(r_h);
344  double sinhr = sinh(r_h);
345  double coshMinR = cosh(minRHyper);
346  double coshMaxR = cosh(maxRHyper);
347  double sinhMinR = sinh(minRHyper);
348  double sinhMaxR = sinh(maxRHyper);
349  double cosDiffLeft = cos(phi - leftAngle);
350  double cosDiffRight = cos(phi - rightAngle);
351 
357  double coshMinDistance, coshMaxDistance;
358 
359  //Left border
360  double lowerLeftDistance = coshMinR*coshr-sinhMinR*sinhr*cosDiffLeft;
361  double upperLeftDistance = coshMaxR*coshr-sinhMaxR*sinhr*cosDiffLeft;
362  if (responsible(phi, r)) coshMinDistance = 1; //strictly speaking, this is wrong
363  else coshMinDistance = min(lowerLeftDistance, upperLeftDistance);
364 
365  coshMaxDistance = max(lowerLeftDistance, upperLeftDistance);
366  //double a = cosh(r_h);
367  double b = sinhr*cosDiffLeft;
368  double extremum = log((coshr+b)/(coshr-b))/2;
369  if (extremum < maxRHyper && extremum >= minRHyper) {
370  double extremeDistance = cosh(extremum)*coshr-sinh(extremum)*sinhr*cosDiffLeft;
371  coshMinDistance = min(coshMinDistance, extremeDistance);
372  coshMaxDistance = max(coshMaxDistance, extremeDistance);
373  }
378  assert(coshMaxDistance >= 1);
379  assert(coshMinDistance >= 1);
380 
381  //Right border
382  double lowerRightDistance = coshMinR*coshr-sinhMinR*sinhr*cosDiffRight;
383  double upperRightDistance = coshMaxR*coshr-sinhMaxR*sinhr*cosDiffRight;
384  coshMinDistance = min(coshMinDistance, lowerRightDistance);
385  coshMinDistance = min(coshMinDistance, upperRightDistance);
386  coshMaxDistance = max(coshMaxDistance, lowerRightDistance);
387  coshMaxDistance = max(coshMaxDistance, upperRightDistance);
388 
389  b = sinhr*cosDiffRight;
390  extremum = log((coshr+b)/(coshr-b))/2;
391  if (extremum < maxRHyper && extremum >= minRHyper) {
392  double extremeDistance = cosh(extremum)*coshr-sinh(extremum)*sinhr*cosDiffRight;
393  coshMinDistance = min(coshMinDistance, extremeDistance);
394  coshMaxDistance = max(coshMaxDistance, extremeDistance);
395  }
396 
397  assert(coshMaxDistance >= 1);
398  assert(coshMinDistance >= 1);
399 
400  //upper and lower borders
401  if (phi >= leftAngle && phi < rightAngle) {
402  double lower = cosh(abs(r_h-minRHyper));
403  double upper = cosh(abs(r_h-maxRHyper));
404  coshMinDistance = min(coshMinDistance, lower);
405  coshMinDistance = min(coshMinDistance, upper);
406  coshMaxDistance = max(coshMaxDistance, upper);
407  coshMaxDistance = max(coshMaxDistance, lower);
408  }
409 
410  assert(coshMaxDistance >= 1);
411  assert(coshMinDistance >= 1);
412 
413  //again with mirrored phi
414  double mirrorphi;
415  if (phi >= M_PI) mirrorphi = phi - M_PI;
416  else mirrorphi = phi + M_PI;
417  if (mirrorphi >= leftAngle && mirrorphi < rightAngle) {
418  double lower = coshMinR*coshr+sinhMinR*sinhr;
419  double upper = coshMaxR*coshr+sinhMaxR*sinhr;
420  coshMinDistance = min(coshMinDistance, lower);
421  coshMinDistance = min(coshMinDistance, upper);
422  coshMaxDistance = max(coshMaxDistance, upper);
423  coshMaxDistance = max(coshMaxDistance, lower);
424  }
425 
426  assert(coshMaxDistance >= 1);
427  assert(coshMinDistance >= 1);
428 
429  double minDistance, maxDistance;
430  minDistance = acosh(coshMinDistance);
431  maxDistance = acosh(coshMaxDistance);
432  assert(maxDistance >= 0);
433  assert(minDistance >= 0);
434  return std::pair<double, double>(minDistance, maxDistance);
435  }
436 
437 
446  bool responsible(double angle, double r) const {
447  return (angle >= leftAngle && angle < rightAngle && r >= minR && r < maxR);
448  }
449 
455  std::vector<T> getElements() const {
456  if (isLeaf) {
457  return content;
458  } else {
459  assert(content.size() == 0);
460  assert(angles.size() == 0);
461  assert(radii.size() == 0);
462  vector<T> result;
463  for (index i = 0; i < children.size(); i++) {
464  std::vector<T> subresult = children[i].getElements();
465  result.insert(result.end(), subresult.begin(), subresult.end());
466  }
467  return result;
468  }
469  }
470 
471  void getCoordinates(vector<double> &anglesContainer, vector<double> &radiiContainer) const {
472  assert(angles.size() == radii.size());
473  if (isLeaf) {
474  anglesContainer.insert(anglesContainer.end(), angles.begin(), angles.end());
475  radiiContainer.insert(radiiContainer.end(), radii.begin(), radii.end());
476  }
477  else {
478  assert(content.size() == 0);
479  assert(angles.size() == 0);
480  assert(radii.size() == 0);
481  for (index i = 0; i < children.size(); i++) {
482  children[i].getCoordinates(anglesContainer, radiiContainer);
483  }
484  }
485  }
486 
500  QuadNode<T>& getAppropriateLeaf(double angle, double r) {
501  assert(this->responsible(angle, r));
502  if (isLeaf) return *this;//will this return the reference to the subtree itself or to a copy?
503  else {
504  for (index i = 0; i < children.size(); i++) {
505  bool foundResponsibleChild = false;
506  if (children[i].responsible(angle, r)) {
507  assert(foundResponsibleChild == false);
508  foundResponsibleChild = true;
509  return children[i].getAppropriateLeaf(angle, r);
510  }
511  }
512  throw std::runtime_error("No responsible child found.");
513  }
514  }
515 
532  void getElementsInEuclideanCircle(Point2D<double> center, double radius, vector<T> &result, double minAngle=0, double maxAngle=2*M_PI, double lowR=0, double highR = 1) const {
533  if (!poincare) throw std::runtime_error("Euclidean query circles not yet implemented for native hyperbolic coordinates.");
534  if (minAngle >= rightAngle || maxAngle <= leftAngle || lowR >= maxR || highR < lowerBoundR) return;
535  if (outOfReach(center, radius)) {
536  return;
537  }
538 
539  if (isLeaf) {
540  const double rsq = radius*radius;
541  const double queryX = center[0];
542  const double queryY = center[1];
543  const count cSize = content.size();
544 
545  for (index i = 0; i < cSize; i++) {
546  const double deltaX = positions[i].getX() - queryX;
547  const double deltaY = positions[i].getY() - queryY;
548  if (deltaX*deltaX + deltaY*deltaY < rsq) {
549  result.push_back(content[i]);
550  }
551  }
552  } else {
553  for (index i = 0; i < children.size(); i++) {
554  children[i].getElementsInEuclideanCircle(center, radius, result, minAngle, maxAngle, lowR, highR);
555  }
556  }
557  }
558 
559  count getElementsProbabilistically(Point2D<double> euQuery, std::function<double(double)> prob, bool suppressLeft, vector<T> &result) const {
560  double phi_q, r_q;
561  HyperbolicSpace::cartesianToPolar(euQuery, phi_q, r_q);
562  if (suppressLeft && phi_q > rightAngle) return 0;
563  TRACE("Getting hyperbolic distances");
564  auto distancePair = hyperbolicDistances(phi_q, r_q);
565  double probUB = prob(distancePair.first);
566  double probLB = prob(distancePair.second);
567 #ifndef NDEBUG
568  assert(probLB <= probUB);
569 #else
570  ((void)(probLB));
571 #endif
572  if (probUB > 0.5) probUB = 1;//if we are going to take every second element anyway, no use in calculating expensive jumps
573  if (probUB == 0) return 0;
574  //TODO: return whole if probLB == 1
575  double probdenom = std::log(1-probUB);
576  if (probdenom == 0) {
577  DEBUG(probUB, " not zero, but too small too process. Ignoring.");
578  return 0;
579  }
580  TRACE("probUB: ", probUB, ", probdenom: ", probdenom);
581 
582  count expectedNeighbours = probUB*size();
583  count candidatesTested = 0;
584 
585  if (isLeaf) {
586  const count lsize = content.size();
587  TRACE("Leaf of size ", lsize);
588  for (index i = 0; i < lsize; i++) {
589  //jump!
590  if (probUB < 1) {
591  double random = Aux::Random::real();
592  double delta = std::log(random) / probdenom;
593  assert(delta == delta);
594  assert(delta >= 0);
595  i += delta;
596  if (i >= lsize) break;
597  TRACE("Jumped with delta ", delta, " arrived at ", i);
598  }
599 
600  //see where we've arrived
601  candidatesTested++;
602  double distance;
603  if (poincare) {
604  distance = HyperbolicSpace::poincareMetric(positions[i], euQuery);
605  } else {
606  distance = HyperbolicSpace::nativeDistance(angles[i], radii[i], phi_q, r_q);
607  }
608  assert(distance >= distancePair.first);
609 
610  double q = prob(distance);
611  q = q / probUB; //since the candidate was selected by the jumping process, we have to adjust the probabilities
612  assert(q <= 1);
613  assert(q >= 0);
614 
615  //accept?
616  double acc = Aux::Random::real();
617  if (acc < q) {
618  TRACE("Accepted node ", i, " with probability ", q, ".");
619  result.push_back(content[i]);
620  }
621  }
622  } else {
623  if (expectedNeighbours < 1) {//select candidates directly instead of calling recursively
624  TRACE("probUB = ", probUB, ", switching to direct candidate selection.");
625  assert(probUB < 1);
626  const count stsize = size();
627  for (index i = 0; i < stsize; i++) {
628  double delta = std::log(Aux::Random::real()) / probdenom;
629  assert(delta >= 0);
630  i += delta;
631  TRACE("Jumped with delta ", delta, " arrived at ", i, ". Calling maybeGetKthElement.");
632  if (i < size()) maybeGetKthElement(probUB, euQuery, prob, i, result);//this could be optimized. As of now, the offset is subtracted separately for each point
633  else break;
634  candidatesTested++;
635  }
636  } else {//carry on as normal
637  for (index i = 0; i < children.size(); i++) {
638  TRACE("Recursively calling child ", i);
639  candidatesTested += children[i].getElementsProbabilistically(euQuery, prob, suppressLeft, result);
640  }
641  }
642  }
643  //DEBUG("Expected at most ", expectedNeighbours, " neighbours, got ", result.size() - offset);
644  return candidatesTested;
645  }
646 
647 
648  void maybeGetKthElement(double upperBound, Point2D<double> euQuery, std::function<double(double)> prob, index k, vector<T> &circleDenizens) const {
649  TRACE("Maybe get element ", k, " with upper Bound ", upperBound);
650  assert(k < size());
651  if (isLeaf) {
652  double distance;
653  if (poincare) {
654  distance = HyperbolicSpace::poincareMetric(positions[k], euQuery);
655  } else {
656  double phi_q, r_q;
657  HyperbolicSpace::cartesianToPolar(euQuery, phi_q, r_q);
658  distance = HyperbolicSpace::nativeDistance(angles[k], radii[k], phi_q, r_q);
659  }
660  double acceptance = prob(distance)/upperBound;
661  TRACE("Is leaf, accept with ", acceptance);
662  if (Aux::Random::real() < acceptance) circleDenizens.push_back(content[k]);
663  } else {
664  TRACE("Call recursively.");
665  index offset = 0;
666  for (index i = 0; i < children.size(); i++) {
667  count childsize = children[i].size();
668  if (k - offset < childsize) {
669  children[i].maybeGetKthElement(upperBound, euQuery, prob, k - offset, circleDenizens);
670  break;
671  }
672  offset += childsize;
673  }
674  }
675  }
676 
681  void trim() {
682  content.shrink_to_fit();
683  positions.shrink_to_fit();
684  angles.shrink_to_fit();
685  radii.shrink_to_fit();
686  if (!isLeaf) {
687  for (index i = 0; i < children.size(); i++) {
688  children[i].trim();
689  }
690  }
691  }
692 
696  count size() const {
697  return isLeaf ? content.size() : subTreeSize;
698  }
699 
700  void recount() {
701  subTreeSize = 0;
702  for (index i = 0; i < children.size(); i++) {
703  children[i].recount();
704  subTreeSize += children[i].size();
705  }
706  }
707 
711  count height() const {
712  count result = 1;//if leaf node, the children loop will not execute
713  for (auto child : children) result = std::max(result, child.height()+1);
714  return result;
715  }
716 
720  count countLeaves() const {
721  if (isLeaf) return 1;
722  count result = 0;
723  for (index i = 0; i < children.size(); i++) {
724  result += children[i].countLeaves();
725  }
726  return result;
727  }
728 
729  double getLeftAngle() const {
730  return leftAngle;
731  }
732 
733  double getRightAngle() const {
734  return rightAngle;
735  }
736 
737  double getMinR() const {
738  return minR;
739  }
740 
741  double getMaxR() const {
742  return maxR;
743  }
744 
745  index getID() const {
746  return ID;
747  }
748 
750  index result = nextID;
751  assert(children.size() == 4 || children.size() == 0);
752  for (index i = 0; i < children.size(); i++) {
753  result = children[i].indexSubtree(result);
754  }
755  this->ID = result;
756  return result+1;
757  }
758 
759  index getCellID(double phi, double r) const {
760  if (!responsible(phi, r)) return NetworKit::none;
761  if (isLeaf) return getID();
762  else {
763  for (index i = 0; i < children.size(); i++) {
764  index childresult = children[i].getCellID(phi, r);
765  if (childresult != NetworKit::none) return childresult;
766  }
767  throw std::runtime_error("No responsible child node found even though this node is responsible.");
768  }
769  }
770 
772  if (isLeaf) return getID();
773  else {
774  index result = -1;
775  for (int i = 0; i < 4; i++) {
776  result = std::max(children[i].getMaxIDInSubtree(), result);
777  }
778  return std::max(result, getID());
779  }
780  }
781 
782  count reindex(count offset) {
783  if (isLeaf)
784  {
785  #pragma omp task
786  {
787  index p = offset;
788  std::generate(content.begin(), content.end(), [&p](){return p++;});
789  }
790  offset += size();
791  } else {
792  for (int i = 0; i < 4; i++) {
793  offset = children[i].reindex(offset);
794  }
795  }
796  return offset;
797  }
798 
799 };
800 }
801 
802 #endif /* QUADNODE_H_ */
void split()
Definition: QuadNode.h:104
static double poincareMetric(double firstangle, double firstR, double secondangle, double secondR)
This distance measure is taken from the Poincaré disc model.
Definition: HyperbolicSpace.cpp:44
bool responsible(double angle, double r) const
Does the point at (angle, r) fall inside the region managed by this QuadNode?
Definition: QuadNode.h:446
double real()
Definition: Random.cpp:77
void getElementsInEuclideanCircle(Point2D< double > center, double radius, vector< T > &result, double minAngle=0, double maxAngle=2 *M_PI, double lowR=0, double highR=1) const
Main query method, get points lying in a Euclidean circle around the center point.
Definition: QuadNode.h:532
index getCellID(double phi, double r) const
Definition: QuadNode.h:759
bool outOfReach(Point2D< double > query, double radius) const
Check whether the region managed by this node lies outside of an Euclidean circle.
Definition: QuadNode.h:268
std::vector< QuadNode > children
Definition: QuadNode.h:50
static double hyperbolicRadiusToEuclidean(double hyperbolicRadius)
Project radial coordinates of the hyperbolic plane into the Poincare disk model.
Definition: HyperbolicSpace.cpp:139
void log(const Location &loc, LogLevel p, const std::string msg)
Definition: Log.cpp:202
uint64_t index
Typedefs.
Definition: Globals.h:20
#define DEBUG(...)
Definition: Log.h:82
double getLeftAngle() const
Definition: QuadNode.h:729
T distance(const Point2D< T > &p) const
Definition: Point2D.h:96
QuadNode()
Definition: QuadNode.h:52
count getElementsProbabilistically(Point2D< double > euQuery, std::function< double(double)> prob, bool suppressLeft, vector< T > &result) const
Definition: QuadNode.h:559
count countLeaves() const
Leaf cells in the subtree hanging from this QuadNode.
Definition: QuadNode.h:720
static Point2D< double > polarToCartesian(double phi, double r)
Definition: HyperbolicSpace.cpp:98
bool removeContent(T input, double angle, double R)
Remove content at polar coordinates (angle, R).
Definition: QuadNode.h:197
count size() const
Number of points lying in the region managed by this QuadNode.
Definition: QuadNode.h:696
QuadNode< T > & getAppropriateLeaf(double angle, double r)
Don't use this! Code is still in here for a unit test.
Definition: QuadNode.h:500
static double EuclideanRadiusToHyperbolic(double EuclideanRadius)
Project radial coordinates of the Poincare model into the hyperbolic plane.
Definition: HyperbolicSpace.cpp:144
std::pair< double, double > hyperbolicDistances(double phi, double r) const
Definition: QuadNode.h:331
double getMaxR() const
Definition: QuadNode.h:741
bool outOfReach(double angle_c, double r_c, double radius) const
Check whether the region managed by this node lies outside of an Euclidean circle.
Definition: QuadNode.h:320
void addContent(T input, double angle, double R)
Add a point at polar coordinates (angle, R) with content input.
Definition: QuadNode.h:150
void recount()
Definition: QuadNode.h:700
friend class QuadTreeGTest
Definition: QuadNode.h:28
std::vector< T > getElements() const
Get all Elements in this QuadNode or a descendant of it.
Definition: QuadNode.h:455
Definition: QuadNode.h:27
uint64_t count
Definition: Globals.h:21
constexpr index none
Constants.
Definition: Globals.h:28
static double nativeDistance(double firstangle, double firstR, double secondangle, double secondR)
Definition: HyperbolicSpace.cpp:20
index indexSubtree(index nextID)
Definition: QuadNode.h:749
index getMaxIDInSubtree() const
Definition: QuadNode.h:771
index getID() const
Definition: QuadNode.h:745
void getCoordinates(vector< double > &anglesContainer, vector< double > &radiiContainer) const
Definition: QuadNode.h:471
count reindex(count offset)
Definition: QuadNode.h:782
void trim()
Shrink all vectors in this subtree to fit the content.
Definition: QuadNode.h:681
float distance
Definition: PubWebGenerator.h:25
QuadNode(double leftAngle, double minR, double rightAngle, double maxR, unsigned capacity=1000, bool splitTheoretical=false, double alpha=1, double balance=0.5)
Construct a QuadNode for polar coordinates.
Definition: QuadNode.h:83
double getMinR() const
Definition: QuadNode.h:737
static void cartesianToPolar(Point2D< double > a, double &phi, double &r)
Definition: HyperbolicSpace.cpp:113
double getRightAngle() const
Definition: QuadNode.h:733
#define TRACE(...)
Definition: Log.h:92
void maybeGetKthElement(double upperBound, Point2D< double > euQuery, std::function< double(double)> prob, index k, vector< T > &circleDenizens) const
Definition: QuadNode.h:648
count height() const
Height of subtree hanging from this QuadNode.
Definition: QuadNode.h:711