Template Class QuadNode

Class Documentation

template<class T, bool poincare = true>
class QuadNode

Public Functions

inline QuadNode()
inline 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.

Parameters:
  • leftAngle – Minimal angular coordinate of region, in radians from 0 to 2\pi

  • minR – Minimal radial coordinate of region, between 0 and 1

  • rightAngle – Maximal angular coordinate of region, in radians from 0 to 2\pi

  • maxR – Maximal radial coordinate of region, between 0 and 1

  • capacity – Number of points a leaf cell can store before splitting

  • minDiameter – Minimal diameter of a quadtree node. If the node is already smaller, don’t split even if over capacity. Default is 0

  • splitTheoretical – Whether to split in a theoretically optimal way or in a way to decrease measured running times

  • alpha – dispersion Parameter of the point distribution. Only has an effect if theoretical split is true

  • diagnostics – Count how many necessary and unnecessary comparisons happen in leaf cells? Will cause race condition and false sharing in parallel use

inline void split()
inline void addContent(T input, double angle, double R)

Add a point at polar coordinates (angle, R) with content input. May split node if capacity is full

Parameters:
  • input – arbitrary content, in our case an index

  • angle – angular coordinate of point, between 0 and 2 pi.

  • R – radial coordinate of point, between 0 and 1.

inline bool removeContent(T input, double angle, double R)

Remove content at polar coordinates (angle, R). May cause coarsening of the quadtree

Parameters:
  • input – Content to be removed

  • angle – Angular coordinate

  • R – Radial coordinate

Returns:

True if content was found and removed, false otherwise

inline bool outOfReach(Point2DWithIndex<double> query, double radius) const

Check whether the region managed by this node lies outside of an Euclidean circle.

Parameters:
  • query – Center of the Euclidean query circle, given in Cartesian coordinates

  • radius – Radius of the Euclidean query circle

Returns:

True if the region managed by this node lies completely outside of the circle

inline 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. Functionality is the same as in the method above, but it takes polar coordinates instead of Cartesian ones

Parameters:
  • angle_c – Angular coordinate of the Euclidean query circle’s center

  • r_c – Radial coordinate of the Euclidean query circle’s center

  • radius – Radius of the Euclidean query circle

Returns:

True if the region managed by this node lies completely outside of the circle

inline std::pair<double, double> hyperbolicDistances(double phi, double r) const
Parameters:
  • phi – Angular coordinate of query point

  • r_h – radial coordinate of query point in poincare disk

inline bool responsible(double angle, double r) const

Does the point at (angle, r) fall inside the region managed by this QuadNode?

Parameters:
  • angle – Angular coordinate of input point

  • r – Radial coordinate of input points

Returns:

True if input point lies within the region of this QuadNode

inline std::vector<T> getElements() const

Get all Elements in this QuadNode or a descendant of it

Returns:

vector of content type T

inline void getCoordinates(vector<double> &anglesContainer, vector<double> &radiiContainer) const
inline QuadNode<T> &getAppropriateLeaf(double angle, double r)

Don’t use this! Code is still in here for a unit test.

Get copy of the leaf cell responsible for a point at (angle, r). Expensive because it copies the whole subtree, causes assertion failure if called with the wrong arguments

Parameters:
  • angle – Angular coordinate of point

  • r – Radial coordinate of point

Returns:

Copy of leaf cell containing point, or dummy cell not responsible for point

inline void getElementsInEuclideanCircle(Point2DWithIndex<double> center, double radius, vector<T> &result, double minAngle = 0, double maxAngle = 2 * PI, double lowR = 0, double highR = 1) const

Main query method, get points lying in a Euclidean circle around the center point. Optional limits can be given to get a different result or to reduce unnecessary comparisons

Elements are pushed onto a vector which is a required argument. This is done to reduce copying

Safe to call in parallel if diagnostics are disabled

Parameters:
  • center – Center of the query circle

  • radius – Radius of the query circle

  • result – Reference to the vector where the results will be stored

  • minAngle – Optional value for the minimum angular coordinate of the query region

  • maxAngle – Optional value for the maximum angular coordinate of the query region

  • lowR – Optional value for the minimum radial coordinate of the query region

  • highR – Optional value for the maximum radial coordinate of the query region

inline count getElementsProbabilistically(Point2DWithIndex<double> euQuery, std::function<double(double)> prob, bool suppressLeft, vector<T> &result) const
inline void maybeGetKthElement(double upperBound, Point2DWithIndex<double> euQuery, std::function<double(double)> prob, index k, vector<T> &circleDenizens) const
inline void trim()

Shrink all vectors in this subtree to fit the content. Call after quadtree construction is complete, causes better memory usage and cache efficiency

inline count size() const

Number of points lying in the region managed by this QuadNode

inline void recount()
inline count height() const

Height of subtree hanging from this QuadNode

inline count countLeaves() const

Leaf cells in the subtree hanging from this QuadNode

inline double getLeftAngle() const
inline double getRightAngle() const
inline double getMinR() const
inline double getMaxR() const
inline index getID() const
inline index indexSubtree(index nextID)
inline index getCellID(double phi, double r) const
inline index getMaxIDInSubtree() const
inline count reindex(count offset)

Public Members

std::vector<QuadNode> children