All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
Public Member Functions | Public Attributes | Friends | List of all members
NetworKit::QuadNodeCartesianEuclid< T > Class Template Reference

#include <QuadNodeCartesianEuclid.h>

Public Member Functions

 QuadNodeCartesianEuclid (Point< double > lower=Point< double >({0.0, 0.0}), Point< double > upper=Point< double >({1.0, 1.0}), unsigned capacity=1000, bool splitTheoretical=false)
 Construct a QuadNode for polar coordinates. More...
 
void split ()
 
void addContent (T input, Point< double > pos)
 Add a point at polar coordinates (angle, R) with content input. More...
 
bool removeContent (T input, Point< double > pos)
 Remove content at coordinate pos. More...
 
bool outOfReach (Point< double > query, double radius) const
 Check whether the region managed by this node lies outside of an Euclidean circle. More...
 
std::pair< double, double > EuclideanDistances (Point< double > query) const
 
bool responsible (Point< double > pos) const
 Does the point at (angle, r) fall inside the region managed by this QuadNode? More...
 
std::vector< T > getElements () const
 Get all Elements in this QuadNode or a descendant of it. More...
 
void getCoordinates (vector< Point< double > > &pointContainer) const
 
void getElementsInEuclideanCircle (Point< double > center, double radius, vector< T > &result) const
 Main query method, get points lying in a Euclidean circle around the center point. More...
 
count getElementsProbabilistically (Point< double > euQuery, std::function< double(double)> prob, vector< T > &result) const
 
void maybeGetKthElement (double upperBound, Point< double > euQuery, std::function< double(double)> prob, index k, vector< T > &circleDenizens) const
 
void trim ()
 Shrink all vectors in this subtree to fit the content. More...
 
count size () const
 Number of points lying in the region managed by this QuadNode. More...
 
void recount ()
 
count height () const
 Height of subtree hanging from this QuadNode. More...
 
count countLeaves () const
 Leaf cells in the subtree hanging from this QuadNode. More...
 
index getID () const
 
index indexSubtree (index nextID)
 
index getCellID (Point< double > pos) const
 
index getMaxIDInSubtree () const
 
count reindex (count offset)
 

Public Attributes

std::vector
< QuadNodeCartesianEuclid
children
 

Friends

class QuadTreeGTest
 

Constructor & Destructor Documentation

template<class T>
NetworKit::QuadNodeCartesianEuclid< T >::QuadNodeCartesianEuclid ( Point< double >  lower = Point<double>({0.0, 0.0}),
Point< double >  upper = Point<double>({1.0, 1.0}),
unsigned  capacity = 1000,
bool  splitTheoretical = false 
)
inline

Construct a QuadNode for polar coordinates.

Parameters
lowerMinimal coordinates of region
upperMaximal coordinates of region (excluded)
capacityNumber of points a leaf cell can store before splitting
splitTheoreticalWhether to split in a theoretically optimal way or in a way to decrease measured running times

Member Function Documentation

template<class T>
void NetworKit::QuadNodeCartesianEuclid< T >::addContent ( input,
Point< double >  pos 
)
inline

Add a point at polar coordinates (angle, R) with content input.

May split node if capacity is full

Parameters
inputarbitrary content, in our case an index
angleangular coordinate of point, between 0 and 2 pi.
Rradial coordinate of point, between 0 and 1.
template<class T>
count NetworKit::QuadNodeCartesianEuclid< T >::countLeaves ( ) const
inline

Leaf cells in the subtree hanging from this QuadNode.

template<class T>
std::pair<double, double> NetworKit::QuadNodeCartesianEuclid< T >::EuclideanDistances ( Point< double >  query) const
inline
Parameters
queryPosition of the query point

If the query point is not within the quadnode, the distance minimum is on the border. Need to check whether extremum is between corners.

template<class T>
index NetworKit::QuadNodeCartesianEuclid< T >::getCellID ( Point< double >  pos) const
inline
template<class T>
void NetworKit::QuadNodeCartesianEuclid< T >::getCoordinates ( vector< Point< double > > &  pointContainer) const
inline
template<class T>
std::vector<T> NetworKit::QuadNodeCartesianEuclid< T >::getElements ( ) const
inline

Get all Elements in this QuadNode or a descendant of it.

Returns
vector of content type T
template<class T>
void NetworKit::QuadNodeCartesianEuclid< T >::getElementsInEuclideanCircle ( Point< double >  center,
double  radius,
vector< T > &  result 
) const
inline

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. (Maybe not necessary due to copy elisison)

Safe to call in parallel.

Parameters
centerCenter of the query circle
radiusRadius of the query circle
resultReference to the vector where the results will be stored
minAngleOptional value for the minimum angular coordinate of the query region
maxAngleOptional value for the maximum angular coordinate of the query region
lowROptional value for the minimum radial coordinate of the query region
highROptional value for the maximum radial coordinate of the query region
template<class T>
count NetworKit::QuadNodeCartesianEuclid< T >::getElementsProbabilistically ( Point< double >  euQuery,
std::function< double(double)>  prob,
vector< T > &  result 
) const
inline
template<class T>
index NetworKit::QuadNodeCartesianEuclid< T >::getID ( ) const
inline
template<class T>
index NetworKit::QuadNodeCartesianEuclid< T >::getMaxIDInSubtree ( ) const
inline
template<class T>
count NetworKit::QuadNodeCartesianEuclid< T >::height ( ) const
inline

Height of subtree hanging from this QuadNode.

template<class T>
index NetworKit::QuadNodeCartesianEuclid< T >::indexSubtree ( index  nextID)
inline
template<class T>
void NetworKit::QuadNodeCartesianEuclid< T >::maybeGetKthElement ( double  upperBound,
Point< double >  euQuery,
std::function< double(double)>  prob,
index  k,
vector< T > &  circleDenizens 
) const
inline
template<class T>
bool NetworKit::QuadNodeCartesianEuclid< T >::outOfReach ( Point< double >  query,
double  radius 
) const
inline

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

Parameters
queryCenter of the Euclidean query circle, given in Cartesian coordinates
radiusRadius of the Euclidean query circle
Returns
True if the region managed by this node lies completely outside of the circle
template<class T>
void NetworKit::QuadNodeCartesianEuclid< T >::recount ( )
inline
template<class T>
count NetworKit::QuadNodeCartesianEuclid< T >::reindex ( count  offset)
inline
template<class T>
bool NetworKit::QuadNodeCartesianEuclid< T >::removeContent ( input,
Point< double >  pos 
)
inline

Remove content at coordinate pos.

May cause coarsening of the quadtree

Parameters
inputContent to be removed
posCoordinate of content
Returns
True if content was found and removed, false otherwise
template<class T>
bool NetworKit::QuadNodeCartesianEuclid< T >::responsible ( Point< double >  pos) const
inline

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

Parameters
angleAngular coordinate of input point
rRadial coordinate of input points
Returns
True if input point lies within the region of this QuadNode
template<class T>
count NetworKit::QuadNodeCartesianEuclid< T >::size ( ) const
inline

Number of points lying in the region managed by this QuadNode.

template<class T>
void NetworKit::QuadNodeCartesianEuclid< T >::split ( )
inline
template<class T>
void NetworKit::QuadNodeCartesianEuclid< T >::trim ( )
inline

Shrink all vectors in this subtree to fit the content.

Call after quadtree construction is complete, causes better memory usage and cache efficiency

Friends And Related Function Documentation

template<class T>
friend class QuadTreeGTest
friend

Member Data Documentation

template<class T>
std::vector<QuadNodeCartesianEuclid> NetworKit::QuadNodeCartesianEuclid< T >::children

The documentation for this class was generated from the following file: