#include <ogdf/energybased/fast_multipole_embedder/LinearQuadtree.h>
Classes | |
struct | bottom_up_traversal_functor |
bottom up traversal of the subtree of a given node More... | |
struct | forall_children_functor |
simple functor for iterating over all children of a node More... | |
struct | forall_ordered_pairs_of_children_functor |
functor for iterating over all ordered pairs of children of a node More... | |
struct | forall_points_functor |
simple functor for iterating over all points of a node More... | |
struct | forall_tree_nodes_functor |
simple functor for iterating over all nodes More... | |
struct | is_fence_condition_functor |
struct | is_leaf_condition_functor |
struct | LQNode |
struct | LQPoint |
struct | LQWSPair |
struct | StoreDirectNodeFunctor |
struct | StoreDirectPairFunctor |
struct | StoreWSPairFunctor |
struct | top_down_traversal_functor |
top down traversal of the subtree of a given node More... | |
struct | wspd_functor |
Public Types | |
using | NodeID = unsigned int |
using | PointID = unsigned int |
Private Member Functions | |
void | addDirect (NodeID s) |
add a direct node to the array list of direct nodes | |
void | addDirectPair (NodeID s, NodeID t) |
add a direct pair to the array list of direct pairs | |
void | addWSPD (NodeID s, NodeID t) |
adds a well-separated pair to the wspd | |
void | allocate (uint32_t n) |
helper function for allocating the array's | |
void | deallocate () |
helper function for releasing memory | |
void | initInnerNode (NodeID nodeID, NodeID leftChild, NodeID rightChild, uint32_t level, NodeID next) |
void | initLeaf (NodeID leaf, PointID firstPoint, uint32_t numPoints, NodeID next) |
void | leafAppendPoint (NodeID leaf, PointID point) |
appends an successing point by simply increasing childcount of a leaf. Assumes isLeaf | |
void | nodeAppendChild (NodeID nodeID, NodeID child) |
appends one child index. Assumes childCount < 4 and not leaf | |
Private Attributes | |
double | m_cellSize |
the height and width of a grid cell | |
NodeID * | m_directNodes |
NodeID | m_firstInner |
first inner node in the inner node chain | |
NodeID | m_firstLeaf |
first leaf in the leaf chain | |
float | m_max_x |
the x coordinate of the right most point | |
float | m_max_y |
the y coordinate of the top most point | |
uint32_t | m_maxNumNodes |
the maximum number of nodes (2*n here instead of 2*n-1) | |
float | m_min_x |
the x coordinate of the left most point | |
float | m_min_y |
the y coordinate of the bottom most point | |
float * | m_nodeSize |
node size | |
float * | m_nodeXPos |
node x coord | |
float * | m_nodeYPos |
node y coord | |
LQWSPair * | m_notWspd |
uint32_t | m_numDirectNodes |
uint32_t | m_numInnerNodes |
number of inner nodes in the chain | |
uint32_t | m_numLeaves |
number of leaves in the chain | |
uint32_t | m_numNotWSP |
uint32_t | m_numPoints |
number of points this quadtree is based on | |
uint32_t | m_numWSP |
float * | m_origSize |
point size in graph order | |
float * | m_origXPos |
point x coord in graph order | |
float * | m_origYPos |
point y coord in graph order | |
LQPoint * | m_points |
the point order in tree order | |
float * | m_pointSize |
point size in tree order | |
float * | m_pointXPos |
point x coord in tree order | |
float * | m_pointYPos |
point y coord in tree order | |
NodeID | m_root |
the root of the tree | |
double | m_scaleInv |
the inverse scale to transform | |
double | m_sideLengthGrid |
the resulting side length of the grid (constant) | |
double | m_sideLengthPoints |
the maximum of height and width | |
LQNode * | m_tree |
the main tree array containing all nodes (including leaves) | |
WSPD * | m_WSPD |
the wspd of this quadtree | |
Friends | |
class | LinearQuadtreeBuilder |
class | LinearQuadtreeBuilderList |
Definition at line 47 of file LinearQuadtree.h.
Definition at line 52 of file LinearQuadtree.h.
Definition at line 53 of file LinearQuadtree.h.
ogdf::fast_multipole_embedder::LinearQuadtree::LinearQuadtree | ( | uint32_t | n, |
float * | origXPos, | ||
float * | origYPos, | ||
float * | origSize | ||
) |
constructor. required tree mem will be allocated
ogdf::fast_multipole_embedder::LinearQuadtree::~LinearQuadtree | ( | void | ) |
destructor. tree mem will be released
add a direct node to the array list of direct nodes
add a direct pair to the array list of direct pairs
adds a well-separated pair to the wspd
helper function for allocating the array's
|
inline |
creator
Definition at line 259 of file LinearQuadtree.h.
|
inline |
creator
Definition at line 265 of file LinearQuadtree.h.
|
inline |
returns the i
th child index of node nodeID
Definition at line 403 of file LinearQuadtree.h.
void ogdf::fast_multipole_embedder::LinearQuadtree::clear | ( | ) |
resets the tree
Definition at line 552 of file LinearQuadtree.h.
void ogdf::fast_multipole_embedder::LinearQuadtree::computeWSPD | ( | ) |
|
private |
helper function for releasing memory
Definition at line 532 of file LinearQuadtree.h.
Definition at line 534 of file LinearQuadtree.h.
Definition at line 536 of file LinearQuadtree.h.
PointID ogdf::fast_multipole_embedder::LinearQuadtree::findFirstPointInCell | ( | PointID | somePointInCell | ) | const |
|
inline |
Definition at line 518 of file LinearQuadtree.h.
|
inline |
Definition at line 522 of file LinearQuadtree.h.
Definition at line 380 of file LinearQuadtree.h.
|
inline |
creator
Definition at line 151 of file LinearQuadtree.h.
|
inline |
creator
Definition at line 201 of file LinearQuadtree.h.
|
inline |
creator
Definition at line 174 of file LinearQuadtree.h.
|
inline |
creator
Definition at line 127 of file LinearQuadtree.h.
|
inline |
Definition at line 334 of file LinearQuadtree.h.
|
inline |
Definition at line 328 of file LinearQuadtree.h.
void ogdf::fast_multipole_embedder::LinearQuadtree::init | ( | float | min_x, |
float | min_y, | ||
float | max_x, | ||
float | max_y | ||
) |
|
inlineprivate |
Definition at line 589 of file LinearQuadtree.h.
|
inlineprivate |
Definition at line 580 of file LinearQuadtree.h.
|
inline |
creator
Definition at line 88 of file LinearQuadtree.h.
|
inline |
creator
Definition at line 101 of file LinearQuadtree.h.
sets the fence flag for node nodeID
Definition at line 412 of file LinearQuadtree.h.
returns true if the given node index is a leaf
Definition at line 409 of file LinearQuadtree.h.
Definition at line 505 of file LinearQuadtree.h.
|
inlineprivate |
appends an successing point by simply increasing childcount of a leaf. Assumes isLeaf
Definition at line 608 of file LinearQuadtree.h.
Definition at line 372 of file LinearQuadtree.h.
|
inline |
the upper bound for a compressed quadtree (2*numPoints)
Definition at line 432 of file LinearQuadtree.h.
|
inline |
Definition at line 546 of file LinearQuadtree.h.
|
inline |
Definition at line 548 of file LinearQuadtree.h.
|
inline |
Definition at line 542 of file LinearQuadtree.h.
|
inline |
Definition at line 544 of file LinearQuadtree.h.
Definition at line 390 of file LinearQuadtree.h.
Definition at line 374 of file LinearQuadtree.h.
|
inlineprivate |
appends one child index. Assumes childCount < 4 and not leaf
Definition at line 602 of file LinearQuadtree.h.
Definition at line 503 of file LinearQuadtree.h.
Definition at line 501 of file LinearQuadtree.h.
Definition at line 469 of file LinearQuadtree.h.
Definition at line 461 of file LinearQuadtree.h.
Definition at line 465 of file LinearQuadtree.h.
|
inline |
returns the number of children of node nodeID
. for an inner node this is 1..4 and can be accessed by child(i). For a leaf the number of points in this leaf is returned starting with point child(0)
Definition at line 395 of file LinearQuadtree.h.
|
inline |
Definition at line 530 of file LinearQuadtree.h.
|
inline |
Definition at line 528 of file LinearQuadtree.h.
|
inline |
Definition at line 520 of file LinearQuadtree.h.
|
inline |
Definition at line 524 of file LinearQuadtree.h.
|
inline |
returns the number of nodes in this tree
Definition at line 429 of file LinearQuadtree.h.
|
inline |
returns the number of points in this tree
Definition at line 426 of file LinearQuadtree.h.
|
inline |
returns the number of points contained in the subtree of node nodeID
Definition at line 415 of file LinearQuadtree.h.
|
inline |
Definition at line 526 of file LinearQuadtree.h.
Definition at line 386 of file LinearQuadtree.h.
|
inline |
Definition at line 388 of file LinearQuadtree.h.
|
inline |
Definition at line 569 of file LinearQuadtree.h.
Definition at line 445 of file LinearQuadtree.h.
|
inline |
Definition at line 459 of file LinearQuadtree.h.
Definition at line 453 of file LinearQuadtree.h.
|
inline |
Definition at line 455 of file LinearQuadtree.h.
Definition at line 449 of file LinearQuadtree.h.
|
inline |
Definition at line 457 of file LinearQuadtree.h.
Definition at line 451 of file LinearQuadtree.h.
Definition at line 499 of file LinearQuadtree.h.
|
inline |
returns the index of the root
Definition at line 423 of file LinearQuadtree.h.
|
inline |
Definition at line 550 of file LinearQuadtree.h.
|
inline |
sets the i
th child index of node nodeID
Definition at line 406 of file LinearQuadtree.h.
|
inline |
Definition at line 382 of file LinearQuadtree.h.
|
inline |
Definition at line 378 of file LinearQuadtree.h.
|
inline |
Definition at line 376 of file LinearQuadtree.h.
|
inline |
Definition at line 471 of file LinearQuadtree.h.
Definition at line 463 of file LinearQuadtree.h.
Definition at line 467 of file LinearQuadtree.h.
|
inline |
sets the number of children of a node
Definition at line 398 of file LinearQuadtree.h.
|
inline |
sets the number of nodes containted in node nodeID
Definition at line 418 of file LinearQuadtree.h.
|
inline |
Definition at line 493 of file LinearQuadtree.h.
|
inline |
Definition at line 486 of file LinearQuadtree.h.
|
inline |
Definition at line 473 of file LinearQuadtree.h.
|
inline |
Definition at line 447 of file LinearQuadtree.h.
uint64_t ogdf::fast_multipole_embedder::LinearQuadtree::sizeInBytes | ( | ) | const |
|
inline |
Definition at line 368 of file LinearQuadtree.h.
|
inline |
Definition at line 356 of file LinearQuadtree.h.
|
inline |
Definition at line 346 of file LinearQuadtree.h.
|
inline |
creator
Definition at line 227 of file LinearQuadtree.h.
|
inline |
creator
Definition at line 233 of file LinearQuadtree.h.
Definition at line 479 of file LinearQuadtree.h.
|
inline |
Definition at line 538 of file LinearQuadtree.h.
|
friend |
Definition at line 48 of file LinearQuadtree.h.
Definition at line 49 of file LinearQuadtree.h.
|
private |
the height and width of a grid cell
Definition at line 635 of file LinearQuadtree.h.
|
private |
Definition at line 691 of file LinearQuadtree.h.
|
private |
first inner node in the inner node chain
Definition at line 707 of file LinearQuadtree.h.
|
private |
first leaf in the leaf chain
Definition at line 701 of file LinearQuadtree.h.
|
private |
the x coordinate of the right most point
Definition at line 629 of file LinearQuadtree.h.
|
private |
the y coordinate of the top most point
Definition at line 632 of file LinearQuadtree.h.
|
private |
the maximum number of nodes (2*n here instead of 2*n-1)
Definition at line 678 of file LinearQuadtree.h.
|
private |
the x coordinate of the left most point
Definition at line 623 of file LinearQuadtree.h.
|
private |
the y coordinate of the bottom most point
Definition at line 626 of file LinearQuadtree.h.
|
private |
node size
Definition at line 672 of file LinearQuadtree.h.
|
private |
node x coord
Definition at line 665 of file LinearQuadtree.h.
|
private |
node y coord
Definition at line 669 of file LinearQuadtree.h.
|
private |
Definition at line 688 of file LinearQuadtree.h.
|
private |
Definition at line 692 of file LinearQuadtree.h.
|
private |
number of inner nodes in the chain
Definition at line 710 of file LinearQuadtree.h.
|
private |
number of leaves in the chain
Definition at line 704 of file LinearQuadtree.h.
|
private |
Definition at line 689 of file LinearQuadtree.h.
|
private |
number of points this quadtree is based on
Definition at line 684 of file LinearQuadtree.h.
|
private |
Definition at line 686 of file LinearQuadtree.h.
|
private |
point size in graph order
Definition at line 653 of file LinearQuadtree.h.
|
private |
point x coord in graph order
Definition at line 647 of file LinearQuadtree.h.
|
private |
point y coord in graph order
Definition at line 650 of file LinearQuadtree.h.
|
private |
the point order in tree order
Definition at line 681 of file LinearQuadtree.h.
|
private |
point size in tree order
Definition at line 662 of file LinearQuadtree.h.
|
private |
point x coord in tree order
Definition at line 656 of file LinearQuadtree.h.
|
private |
point y coord in tree order
Definition at line 659 of file LinearQuadtree.h.
|
private |
the root of the tree
Definition at line 698 of file LinearQuadtree.h.
|
private |
the inverse scale to transform
Definition at line 638 of file LinearQuadtree.h.
|
private |
the resulting side length of the grid (constant)
Definition at line 644 of file LinearQuadtree.h.
|
private |
the maximum of height and width
Definition at line 641 of file LinearQuadtree.h.
|
private |
the main tree array containing all nodes (including leaves)
Definition at line 675 of file LinearQuadtree.h.
|
private |
the wspd of this quadtree
Definition at line 695 of file LinearQuadtree.h.