Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

LinearQuadtree.h
Go to the documentation of this file.
1 
32 #pragma once
33 
36 
37 #define OGDF_LQ_M2L_MIN_BOUND 8
38 #define OGDF_LQ_WSPD_BRANCH_BOUND 16
39 #define OGDF_LQ_WSPD_BOUND 25
40 
41 namespace ogdf {
42 namespace fast_multipole_embedder {
43 
44 class LinearQuadtreeBuilder;
45 class WSPD;
46 
48 {
49  friend class LinearQuadtreeBuilder;
51 public:
52  using NodeID = unsigned int;
53  using PointID = unsigned int;
54 
55  struct LQPoint // 16 byte
56  {
57  MortonNR mortonNr; // 8 byte
58  uint32_t node; // 4 byte
59  uint32_t ref; // 4 byte
60  };
61 
62  struct LQNode // 27 byte
63  {
64  uint32_t level; // 4 byte
65  NodeID next; // 4 byte
66  NodeID child[4]; // 4 byte *4 = 16 byte
67  uint32_t numChilds; // 4 byte
68  PointID firstPoint; // 4 byte
69  uint32_t numPoints; // 4 byte
70  bool fence; // 1 byte
71  };
72 
73  struct LQWSPair
74  {
75  LQWSPair(NodeID c, NodeID d) : a(c), b(d) {};
76  NodeID a;
78  };
79 
81  {
84  inline bool operator()(NodeID u) { return tree.isFence(u); }
85  };
86 
89 
90 
92  {
95  inline bool operator()(NodeID u) { return tree.isLeaf(u); }
96  };
97 
100 
101 
103  template<typename F>
105  {
107  F func;
109  uint32_t numNodes;
110 
111  forall_tree_nodes_functor(const LinearQuadtree& t, F f, NodeID b, uint32_t num) : tree(t), func(f), begin(b), numNodes(num) { }
112 
113  inline void operator()()
114  {
115  NodeID it = begin;
116  for (uint32_t i=0; i<numNodes; i++)
117  {
118  func(it);
119  it = tree.nextNode(it);
120  }
121  }
122  };
123 
125  template<typename F>
126  inline forall_tree_nodes_functor<F> forall_tree_nodes(F f, NodeID begin, uint32_t num) const
127  {
128  return forall_tree_nodes_functor<F>(*this, f, begin, num);
129  }
130 
132  template<typename F>
134  {
136  F func;
137 
138  forall_children_functor(const LinearQuadtree& t, F f) : tree(t), func(f) { }
139 
140  inline void operator()(NodeID u)
141  {
142  if (tree.isLeaf(u)) return;
143  for (uint32_t i = 0; i < tree.numberOfChilds(u); i++) func(tree.child(u, i));
144  }
145  };
146 
148  template<typename F>
150  {
151  return forall_children_functor<F>(*this, f);
152  }
153 
154 
156  template<typename Func>
158  {
160  Func func;
161 
162  forall_points_functor(const LinearQuadtree& t, const Func& f) : tree(t), func(f) { }
163 
164  inline void operator()(NodeID u)
165  {
168  for (PointID i = firstPoint; i < end; i++)
169  func(i);
170  }
171  };
172 
174  template<typename Func>
175  inline forall_points_functor<Func> forall_points(const Func& func) const
176  {
177  return forall_points_functor<Func>(*this, func);
178  }
179 
181  template<typename F>
183  {
185  F func;
186 
188 
189  inline void operator()(NodeID u)
190  {
191  if (tree.isLeaf(u)) return;
192  for (uint32_t i = 0; i < tree.numberOfChilds(u); i++)
193  for (uint32_t j = i+1; j < tree.numberOfChilds(u); j++)
194  func(tree.child(u, i), tree.child(u, j));
195  }
196  };
197 
199  template<typename F>
201  {
203  }
204 
206  template<typename F, typename CondType = true_condition>
208  {
210  F func;
211  CondType cond;
212 
214  top_down_traversal_functor(const LinearQuadtree& t, F f, CondType c) : tree(t), func(f), cond(c) { }
215 
216  inline void operator()(NodeID u)
217  {
218  if (cond(u)) { func(u); tree.forall_children(*this)(u); };
219  }
220  };
221 
223  template<typename F>
225  {
226  return top_down_traversal_functor<F>(*this, f);
227  }
228 
230  template<typename F, typename Cond>
232  {
233  return top_down_traversal_functor<F, Cond>(*this, f, cond);
234  }
235 
236 
238  template<typename F, typename CondType = true_condition>
240  {
242  F func;
243  CondType cond;
244 
246  bottom_up_traversal_functor(const LinearQuadtree& t, F f, CondType c) : tree(t), func(f), cond(c) { }
247 
248  inline void operator()(NodeID u)
249  {
250  if (cond(u)) { tree.forall_children(*this)(u); func(u); };
251  }
252  };
253 
255  template<typename F>
257  {
258  return bottom_up_traversal_functor<F>(*this, f);
259  }
260 
262  template<typename F, typename Cond>
264  {
265  return bottom_up_traversal_functor<F, Cond>(*this, f, cond);
266  }
267 
268 
269  template<typename WSPairFuncType, typename DPairFuncType, typename DNodeFuncType, typename BranchCondType = true_condition>
271  {
273  WSPairFuncType WSFunction;
274  DPairFuncType DPairFunction;
275  DNodeFuncType DNodeFunction;
276  BranchCondType BranchCondFunction;
277 
278  wspd_functor(const LinearQuadtree& t, WSPairFuncType& wsf, DPairFuncType& dpf, DNodeFuncType& dnf)
279  : tree(t), WSFunction(wsf), DPairFunction(dpf), DNodeFunction(dnf) { }
280 
281  wspd_functor(const LinearQuadtree& t, WSPairFuncType& wsf, DPairFuncType& dpf, DNodeFuncType& dnf, BranchCondType& bc)
282  : tree(t), WSFunction(wsf), DPairFunction(dpf), DNodeFunction(dnf), BranchCondFunction(bc) { }
283 
284  inline void operator()(NodeID u)
285  {
286  if (BranchCondFunction(u))
287  {
289  {
290  if (tree.numberOfPoints(u) > 1)
291  DNodeFunction(u);
292  } else
293  {
294  tree.forall_children(*this)(u);
296  }
297  }
298  }
299 
300 
301  inline void operator()(NodeID u, NodeID v)
302  {
303  if (tree.isWS(u, v))
304  {
306  DPairFunction(u, v);
307  else
308  WSFunction(u, v);
309  }
310  else
311  {
313  tree.isLeaf(u) || tree.isLeaf(v))
314  {
315  DPairFunction(u, v);
316  }
317  else
318  {
319  if (tree.level(u) >= tree.level(v))
320  tree.forall_children(pair_call(*this, v))(u);
321  else
322  tree.forall_children(pair_call(*this, u))(v);
323  }
324  }
325  }
326  };
327 
328  template<typename A, typename B, typename C, typename ConditionType>
329  inline wspd_functor<A, B, C, ConditionType> forall_well_separated_pairs(A a, B b, C c, ConditionType cond)
330  {
331  return wspd_functor<A, B, C, ConditionType>(*this, a, b, c, cond);
332  }
333 
334  template<typename A, typename B, typename C>
336  {
337  return wspd_functor<A, B, C>(*this, a, b, c);
338  }
339 
341  {
344  inline void operator()(NodeID a, NodeID b) { tree.addWSPD(a, b); }
345  };
346 
348 
349 
351  {
354  inline void operator()(NodeID a, NodeID b) { tree.addDirectPair(a, b); }
355  };
356 
358 
359 
361  {
364  inline void operator()(NodeID a) { tree.addDirect(a); }
365  };
366 
368 
369  inline NodeID level(NodeID nodeID) const
370  {
371  return m_tree[nodeID].level;
372  }
373 
374  inline NodeID nextNode(NodeID nodeID) const
375  {
376  return m_tree[nodeID].next;
377  }
378 
379  inline void setNextNode(NodeID nodeID, NodeID next)
380  {
381  m_tree[nodeID].next = next;
382  }
383 
384  inline void setLevel(NodeID nodeID, uint32_t level)
385  {
386  m_tree[nodeID].level = level;
387  }
388 
389  inline PointID firstPoint(NodeID nodeID) const
390  {
391  return m_tree[nodeID].firstPoint;
392  }
393 
394  inline void setFirstPoint(NodeID nodeID, PointID firstPoint)
395  {
396  m_tree[nodeID].firstPoint = firstPoint;
397  }
398 
399  inline LQPoint& point(PointID pointID)
400  {
401  return m_points[pointID];
402  }
403 
404  inline const LQPoint& point(PointID pointID) const
405  {
406  return m_points[pointID];
407  }
408 
410  {
411  return m_points[point].mortonNr;
412  }
413 
417  inline uint32_t numberOfChilds(NodeID nodeID) const
418  {
419  return m_tree[nodeID].numChilds;
420  }
421 
423  inline void setNumberOfChilds(NodeID nodeID, uint32_t numChilds)
424  {
425  m_tree[nodeID].numChilds = numChilds;
426  }
427 
429  inline NodeID child(NodeID nodeID, uint32_t i) const
430  {
431  return m_tree[nodeID].child[i];
432  }
433 
435  inline void setChild(NodeID nodeID, uint32_t i, NodeID c)
436  {
437  m_tree[nodeID].child[i] = c;
438  }
439 
441  inline bool isLeaf(NodeID nodeID) const
442  {
443  return !m_tree[nodeID].numChilds;
444  }
445 
447  inline bool isFence(NodeID nodeID) const
448  {
449  return m_tree[nodeID].fence;
450  }
451 
453  inline uint32_t numberOfPoints(NodeID nodeID) const
454  {
455  return m_tree[nodeID].numPoints;
456  }
457 
459  inline void setNumberOfPoints(NodeID nodeID, uint32_t numPoints)
460  {
461  m_tree[nodeID].numPoints = numPoints;
462  }
463 
465  inline NodeID root() const
466  {
467  return m_root;
468  }
469 
471  inline uint32_t numberOfPoints() const
472  {
473  return m_numPoints;
474  }
475 
477  inline uint32_t numberOfNodes() const
478  {
479  return m_numInnerNodes + m_numLeaves;
480  }
481 
483  inline uint32_t maxNumberOfNodes() const
484  {
485  return m_maxNumNodes;
486  }
487 
489  void clear();
490 
492  LinearQuadtree(uint32_t n, float* origXPos, float* origYPos, float* origSize);
493 
495  ~LinearQuadtree(void);
496 
497  uint64_t sizeInBytes() const;
498 
500  {
501  return m_points[point].node;
502  }
503 
504  inline void setPointLeaf(PointID point, NodeID leaf)
505  {
506  m_points[point].node = leaf;
507  }
508 
509  inline float pointX(PointID point) const { return m_pointXPos[point]; }
510 
511  inline float pointY(PointID point) const { return m_pointYPos[point]; }
512 
513  inline float pointSize(PointID point) const { return m_pointSize[point]; }
514 
515  inline float* pointX() const { return m_pointXPos; }
516 
517  inline float* pointY() const { return m_pointYPos; }
518 
519  inline float* pointSize() const { return m_pointSize; }
520 
521  inline float nodeX(NodeID nodeID) const { return m_nodeXPos[nodeID]; }
522 
523  inline void setNodeX(NodeID nodeID, float x) { m_nodeXPos[nodeID] = x; }
524 
525  inline float nodeY(NodeID nodeID) const { return m_nodeYPos[nodeID]; }
526 
527  inline void setNodeY(NodeID nodeID, float y) { m_nodeYPos[nodeID] = y; }
528 
529  inline float nodeSize(NodeID nodeID) const { return m_nodeSize[nodeID]; }
530 
531  inline void setNodeSize(NodeID nodeID, float size) { m_nodeSize[nodeID] = size; }
532 
533  void setPoint(PointID id, float x, float y, uint32_t ref)
534  {
535  m_pointXPos[id] = x;
536  m_pointYPos[id] = y;
537  m_points[id].ref = ref;
538  }
539 
541  {
542  uint32_t ref = m_points[id].ref;
543  m_pointXPos[id] = m_origXPos[ref];
544  m_pointYPos[id] = m_origYPos[ref];
545  m_pointSize[id] = m_origSize[ref];
546  }
547 
548  void setPoint(PointID id, float x, float y, float r, uint32_t ref)
549  {
550  m_pointXPos[id] = x;
551  m_pointYPos[id] = y;
552  m_pointSize[id] = r;
553  m_points[id].ref = ref;
554  }
555 
556  void setPoint(PointID id, float x, float y, float r)
557  {
558  m_pointXPos[id] = x;
559  m_pointYPos[id] = y;
560  m_pointSize[id] = r;
561  }
562 
563  inline uint32_t refOfPoint(PointID id) const
564  {
565  return m_points[id].ref;
566  }
567 
568  inline NodeID nodeOfPoint(PointID id) const
569  {
570  return m_points[id].node;
571  }
572 
573  inline void nodeFence(NodeID nodeID)
574  {
575  m_tree[nodeID].fence = true;
576  }
577 
578  inline bool isWS(NodeID a, NodeID b) const
579  {
580  float s = 0.00000001f;
581  float dx = nodeX(a) - nodeX(b);
582  float dy = nodeY(a) - nodeY(b);
583  float d_sq = dx*dx+dy*dy;
584  float size = max(nodeSize(a), nodeSize(b));
585  return d_sq > (s * 0.5 + 1) * (s * 0.5 + 1) * 2 * size * size;
586  }
587 
588  void computeWSPD();
589 
590  void computeWSPD(NodeID n);
591 
592  inline NodeID firstInnerNode() const { return m_firstInner; }
593 
594  inline uint32_t numberOfInnerNodes() const { return m_numInnerNodes; }
595 
596  inline NodeID firstLeaf() const { return m_firstLeaf; }
597 
598  inline uint32_t numberOfLeaves() const { return m_numLeaves; }
599 
600 
601  uint32_t numberOfWSP() const { return m_numWSP; }
602 
603  uint32_t numberOfDirectPairs() const { return m_numNotWSP; }
604 
605  uint32_t numberOfDirectNodes() const { return m_numDirectNodes; }
606 
607  inline NodeID directNode(uint32_t i) const { return m_directNodes[i]; }
608 
609  inline NodeID directNodeA(uint32_t i) const { return m_notWspd[i].a; }
610 
611  inline NodeID directNodeB(uint32_t i) const { return m_notWspd[i].b; }
612 
613 
614  WSPD* wspd() const{ return m_WSPD; };
615 
616  void init(float min_x, float min_y, float max_x, float max_y);
617  inline float minX() const { return m_min_x; }
618  inline float minY() const { return m_min_y; }
619  inline float maxX() const { return m_max_x; }
620  inline float maxY() const { return m_max_y; }
621  inline double scaleInv() const { return m_scaleInv; }
622 
623 
624  inline void computeCoords(NodeID nodeIndex)
625  {
626  uint32_t ix, iy;
627  uint32_t level = this->level(nodeIndex);
628  float s = (float)(m_cellSize * (1 << level));
629  this->setNodeSize(nodeIndex, s);
630  MortonNR mnr = this->mortonNr(this->firstPoint(nodeIndex));
631  mnr = mnr >> (level * 2);
632  mnr = mnr << (level * 2);
633  mortonNumberInv<uint64_t, uint32_t>(mnr, ix, iy);
634  this->setNodeX(nodeIndex, (float)((m_sideLengthPoints*((float)ix)-0.5)/m_sideLengthGrid + (float)m_min_x + (float)s*0.5f));
635  this->setNodeY(nodeIndex, (float)((m_sideLengthPoints*((float)iy)-0.5)/m_sideLengthGrid + (float)m_min_y + (float)s*0.5f));
636  }
637 
638  LQPoint* pointArray() { return m_points; }
639 
640  PointID findFirstPointInCell(PointID somePointInCell) const;
641 
642 private:
644  void allocate(uint32_t n);
645 
647  void deallocate();
648 
649  inline void initLeaf(NodeID leaf, PointID firstPoint, uint32_t numPoints, NodeID next)
650  {
651  m_tree[leaf].numChilds = 0;
652  m_tree[leaf].next = next;
653  m_tree[leaf].fence = 0;
654  m_tree[leaf].level = 0;
655  m_tree[leaf].firstPoint = firstPoint;
656  m_tree[leaf].numPoints = numPoints;
657  }
658 
659  inline void initInnerNode(NodeID nodeID, NodeID leftChild, NodeID rightChild, uint32_t level, NodeID next)
660  {
661  m_tree[nodeID].numChilds = 2;
662  m_tree[nodeID].child[0] = leftChild;
663  m_tree[nodeID].child[1] = rightChild;
664  m_tree[nodeID].next = next;
665  m_tree[nodeID].fence = 0;
666  m_tree[nodeID].level = level;
667  m_tree[nodeID].firstPoint = leftChild;
668  m_tree[nodeID].numPoints = rightChild - leftChild;
669  }
670 
672  inline void nodeAppendChild(NodeID nodeID, NodeID child)
673  {
674  m_tree[nodeID].child[m_tree[nodeID].numChilds++] = child;
675  m_tree[nodeID].numPoints += m_tree[child].numPoints;
676  }
677 
679  inline void leafAppendPoint(NodeID leaf, PointID point)
680  {
681  m_points[point].node = leaf;
682  m_tree[leaf].numPoints++;
683  }
684 
686  void addWSPD(NodeID s, NodeID t);
687 
689  void addDirectPair(NodeID s, NodeID t);
690 
692  void addDirect(NodeID s);
693 
695  float m_min_x;
696 
698  float m_min_y;
699 
701  float m_max_x;
702 
704  float m_max_y;
705 
707  double m_cellSize;
708 
710  double m_scaleInv;
711 
714 
717 
719  float* m_origXPos;
720 
722  float* m_origYPos;
723 
725  float* m_origSize;
726 
728  float* m_pointXPos;
729 
731  float* m_pointYPos;
732 
734  float* m_pointSize;
735 
737  float* m_nodeXPos;
738 
739 
741  float* m_nodeYPos;
742 
744  float* m_nodeSize;
745 
748 
750  uint32_t m_maxNumNodes;
751 
754 
756  uint32_t m_numPoints;
757 
758  uint32_t m_numWSP;
759 
761  uint32_t m_numNotWSP;
762 
765 
768 
771 
774 
776  uint32_t m_numLeaves;
777 
780 
782  uint32_t m_numInnerNodes;
783 
784 };
785 
787 {
788  return a.mortonNr < b.mortonNr;
789 }
790 
791 }
792 }
ogdf::fast_multipole_embedder::LinearQuadtree::forall_ordered_pairs_of_children_functor::func
F func
Definition: LinearQuadtree.h:185
ogdf::fast_multipole_embedder::LinearQuadtree::minX
float minX() const
Definition: LinearQuadtree.h:617
ogdf
The namespace for all OGDF objects.
Definition: AugmentationModule.h:36
ogdf::fast_multipole_embedder::LinearQuadtree::StoreDirectNodeFunctor::operator()
void operator()(NodeID a)
Definition: LinearQuadtree.h:364
ogdf::fast_multipole_embedder::LinearQuadtree::StoreDirectPairFunctor
Definition: LinearQuadtree.h:350
ogdf::fast_multipole_embedder::LinearQuadtree::forall_ordered_pairs_of_children_functor::tree
const LinearQuadtree & tree
Definition: LinearQuadtree.h:184
ogdf::fast_multipole_embedder::LinearQuadtree::top_down_traversal_functor
top down traversal of the subtree of a given node
Definition: LinearQuadtree.h:207
ogdf::fast_multipole_embedder::LinearQuadtree::numberOfNodes
uint32_t numberOfNodes() const
returns the number of nodes in this tree
Definition: LinearQuadtree.h:477
ogdf::fast_multipole_embedder::LinearQuadtree::top_down_traversal_functor::operator()
void operator()(NodeID u)
Definition: LinearQuadtree.h:216
ogdf::fast_multipole_embedder::LinearQuadtree::NodeID
unsigned int NodeID
Definition: LinearQuadtree.h:52
ogdf::fast_multipole_embedder::LinearQuadtree::m_notWspd
LQWSPair * m_notWspd
Definition: LinearQuadtree.h:760
ogdf::fast_multipole_embedder::LinearQuadtree::findFirstPointInCell
PointID findFirstPointInCell(PointID somePointInCell) const
ogdf::fast_multipole_embedder::LinearQuadtree::numberOfDirectNodes
uint32_t numberOfDirectNodes() const
Definition: LinearQuadtree.h:605
ogdf::fast_multipole_embedder::LinearQuadtree::setNumberOfPoints
void setNumberOfPoints(NodeID nodeID, uint32_t numPoints)
sets the number of nodes containted in node nodeID
Definition: LinearQuadtree.h:459
ogdf::fast_multipole_embedder::LinearQuadtree::StoreWSPairFunction
StoreWSPairFunctor StoreWSPairFunction()
Definition: LinearQuadtree.h:347
ogdf::fast_multipole_embedder::LinearQuadtree::top_down_traversal
top_down_traversal_functor< F > top_down_traversal(F f) const
creator
Definition: LinearQuadtree.h:224
ogdf::fast_multipole_embedder::LinearQuadtree::LQNode::fence
bool fence
Definition: LinearQuadtree.h:70
ogdf::fast_multipole_embedder::LinearQuadtree::bottom_up_traversal_functor::bottom_up_traversal_functor
bottom_up_traversal_functor(const LinearQuadtree &t, F f, CondType c)
Definition: LinearQuadtree.h:246
ogdf::fast_multipole_embedder::LinearQuadtree::forall_ordered_pairs_of_children_functor::operator()
void operator()(NodeID u)
Definition: LinearQuadtree.h:189
ogdf::fast_multipole_embedder::LinearQuadtree::forall_points_functor::forall_points_functor
forall_points_functor(const LinearQuadtree &t, const Func &f)
Definition: LinearQuadtree.h:162
ogdf::fast_multipole_embedder::LinearQuadtree::directNode
NodeID directNode(uint32_t i) const
Definition: LinearQuadtree.h:607
ogdf::fast_multipole_embedder::LinearQuadtree::bottom_up_traversal_functor::tree
const LinearQuadtree & tree
Definition: LinearQuadtree.h:241
ogdf::fast_multipole_embedder::LinearQuadtree::forall_children
forall_children_functor< F > forall_children(F f) const
creator
Definition: LinearQuadtree.h:149
ogdf::fast_multipole_embedder::LinearQuadtree::nodeOfPoint
NodeID nodeOfPoint(PointID id) const
Definition: LinearQuadtree.h:568
ogdf::fast_multipole_embedder::LinearQuadtree::wspd_functor
Definition: LinearQuadtree.h:270
ogdf::fast_multipole_embedder::LinearQuadtree::firstInnerNode
NodeID firstInnerNode() const
Definition: LinearQuadtree.h:592
ogdf::fast_multipole_embedder::LinearQuadtree::wspd_functor::operator()
void operator()(NodeID u, NodeID v)
Definition: LinearQuadtree.h:301
ogdf::fast_multipole_embedder::LinearQuadtree::addWSPD
void addWSPD(NodeID s, NodeID t)
adds a well-separated pair to the wspd
ogdf::fast_multipole_embedder::LinearQuadtree::m_tree
LQNode * m_tree
the main tree array containing all nodes (including leaves)
Definition: LinearQuadtree.h:747
ogdf::fast_multipole_embedder::LinearQuadtree::forall_points_functor
simple functor for iterating over all points of a node
Definition: LinearQuadtree.h:157
ogdf::fast_multipole_embedder::LinearQuadtree::forall_children_functor::operator()
void operator()(NodeID u)
Definition: LinearQuadtree.h:140
ogdf::fast_multipole_embedder::WSPD
Class for the Well-Separated-Pairs-Decomposition (WSPD)
Definition: WSPD.h:41
ogdf::fast_multipole_embedder::LinearQuadtree::numberOfInnerNodes
uint32_t numberOfInnerNodes() const
Definition: LinearQuadtree.h:594
ogdf::fast_multipole_embedder::LinearQuadtree::forall_well_separated_pairs
wspd_functor< A, B, C, ConditionType > forall_well_separated_pairs(A a, B b, C c, ConditionType cond)
Definition: LinearQuadtree.h:329
ogdf::fast_multipole_embedder::LinearQuadtree::nodeX
float nodeX(NodeID nodeID) const
Definition: LinearQuadtree.h:521
ogdf::fast_multipole_embedder::LinearQuadtree::scaleInv
double scaleInv() const
Definition: LinearQuadtree.h:621
ogdf::fast_multipole_embedder::LinearQuadtree::is_leaf_condition_functor::operator()
bool operator()(NodeID u)
Definition: LinearQuadtree.h:95
ogdf::fast_multipole_embedder::LinearQuadtree::computeCoords
void computeCoords(NodeID nodeIndex)
Definition: LinearQuadtree.h:624
ogdf::fast_multipole_embedder::pair_call
static pair_call_functor< F, A > pair_call(F f, A a)
creates a pair call resulting in a call f(a, *)
Definition: FMEFunctional.h:141
ogdf::fast_multipole_embedder::LinearQuadtree::LQWSPair::LQWSPair
LQWSPair(NodeID c, NodeID d)
Definition: LinearQuadtree.h:75
ogdf::fast_multipole_embedder::LinearQuadtree::numberOfDirectPairs
uint32_t numberOfDirectPairs() const
Definition: LinearQuadtree.h:603
ogdf::fast_multipole_embedder::LinearQuadtree::isFence
bool isFence(NodeID nodeID) const
sets the fence flag for node nodeID
Definition: LinearQuadtree.h:447
ogdf::fast_multipole_embedder::LinearQuadtree::setNumberOfChilds
void setNumberOfChilds(NodeID nodeID, uint32_t numChilds)
sets the number of children of a node
Definition: LinearQuadtree.h:423
ogdf::fast_multipole_embedder::LinearQuadtree::wspd_functor::operator()
void operator()(NodeID u)
Definition: LinearQuadtree.h:284
ogdf::fast_multipole_embedder::LinearQuadtree::top_down_traversal_functor::func
F func
Definition: LinearQuadtree.h:210
ogdf::fast_multipole_embedder::LinearQuadtree::nextNode
NodeID nextNode(NodeID nodeID) const
Definition: LinearQuadtree.h:374
ogdf::fast_multipole_embedder::LinearQuadtree::m_pointSize
float * m_pointSize
point size in tree order
Definition: LinearQuadtree.h:734
ogdf::fast_multipole_embedder::LinearQuadtree::is_leaf_condition_functor
Definition: LinearQuadtree.h:91
ogdf::fast_multipole_embedder::LinearQuadtree::m_numNotWSP
uint32_t m_numNotWSP
Definition: LinearQuadtree.h:761
ogdf::fast_multipole_embedder::LinearQuadtree::sizeInBytes
uint64_t sizeInBytes() const
ogdf::fast_multipole_embedder::LinearQuadtree::forall_tree_nodes
forall_tree_nodes_functor< F > forall_tree_nodes(F f, NodeID begin, uint32_t num) const
creator
Definition: LinearQuadtree.h:126
ogdf::fast_multipole_embedder::LinearQuadtree::LinearQuadtreeBuilderList
friend class LinearQuadtreeBuilderList
Definition: LinearQuadtree.h:50
ogdf::fast_multipole_embedder::LinearQuadtree::top_down_traversal_functor::cond
CondType cond
Definition: LinearQuadtree.h:211
ogdf::fast_multipole_embedder::LinearQuadtree::StoreDirectNodeFunctor::StoreDirectNodeFunctor
StoreDirectNodeFunctor(LinearQuadtree &t)
Definition: LinearQuadtree.h:363
ogdf::fast_multipole_embedder::LinearQuadtreeBuilder
the builder for the LinearQuadtree
Definition: LinearQuadtreeBuilder.h:41
ogdf::fast_multipole_embedder::LinearQuadtree::forall_tree_nodes_functor::tree
const LinearQuadtree & tree
Definition: LinearQuadtree.h:106
ogdf::fast_multipole_embedder::LinearQuadtree::pointSize
float pointSize(PointID point) const
Definition: LinearQuadtree.h:513
ogdf::fast_multipole_embedder::LinearQuadtree::forall_tree_nodes_functor::operator()
void operator()()
Definition: LinearQuadtree.h:113
ogdf::fast_multipole_embedder::LinearQuadtree::addDirect
void addDirect(NodeID s)
add a direct node to the array list of direct nodes
ogdf::fast_multipole_embedder::LinearQuadtree::LQNode::numChilds
uint32_t numChilds
Definition: LinearQuadtree.h:67
ogdf::fast_multipole_embedder::LinearQuadtree::numberOfLeaves
uint32_t numberOfLeaves() const
Definition: LinearQuadtree.h:598
ogdf::fast_multipole_embedder::LinearQuadtree::nodeY
float nodeY(NodeID nodeID) const
Definition: LinearQuadtree.h:525
ogdf::fast_multipole_embedder::LinearQuadtree::top_down_traversal_functor::top_down_traversal_functor
top_down_traversal_functor(const LinearQuadtree &t, F f, CondType c)
Definition: LinearQuadtree.h:214
ogdf::fast_multipole_embedder::LinearQuadtree::forall_tree_nodes_functor::func
F func
Definition: LinearQuadtree.h:107
ogdf::fast_multipole_embedder::LinearQuadtree::wspd_functor::WSFunction
WSPairFuncType WSFunction
Definition: LinearQuadtree.h:273
ogdf::fast_multipole_embedder::LinearQuadtree::initLeaf
void initLeaf(NodeID leaf, PointID firstPoint, uint32_t numPoints, NodeID next)
Definition: LinearQuadtree.h:649
ogdf::fast_multipole_embedder::LinearQuadtree::StoreWSPairFunctor::StoreWSPairFunctor
StoreWSPairFunctor(LinearQuadtree &t)
Definition: LinearQuadtree.h:343
ogdf::fast_multipole_embedder::LinearQuadtree::numberOfPoints
uint32_t numberOfPoints(NodeID nodeID) const
returns the number of points contained in the subtree of node nodeID
Definition: LinearQuadtree.h:453
ogdf::fast_multipole_embedder::LinearQuadtree::allocate
void allocate(uint32_t n)
helper function for allocating the array's
ogdf::fast_multipole_embedder::LinearQuadtree::StoreDirectNodeFunction
StoreDirectNodeFunctor StoreDirectNodeFunction()
Definition: LinearQuadtree.h:367
ogdf::fast_multipole_embedder::LinearQuadtree::LQPoint::mortonNr
MortonNR mortonNr
Definition: LinearQuadtree.h:57
ogdf::fast_multipole_embedder::LinearQuadtree::setPointLeaf
void setPointLeaf(PointID point, NodeID leaf)
Definition: LinearQuadtree.h:504
ogdf::fast_multipole_embedder::LinearQuadtree::StoreDirectNodeFunctor::tree
LinearQuadtree & tree
Definition: LinearQuadtree.h:362
ogdf::fast_multipole_embedder::LinearQuadtree::m_nodeXPos
float * m_nodeXPos
node x coord
Definition: LinearQuadtree.h:737
FastUtils.h
Definition of utility functions for FME layout.
ogdf::fast_multipole_embedder::LinearQuadtree::m_origSize
float * m_origSize
point size in graph order
Definition: LinearQuadtree.h:725
ogdf::fast_multipole_embedder::LinearQuadtree::isWS
bool isWS(NodeID a, NodeID b) const
Definition: LinearQuadtree.h:578
ogdf::fast_multipole_embedder::LinearQuadtree::setFirstPoint
void setFirstPoint(NodeID nodeID, PointID firstPoint)
Definition: LinearQuadtree.h:394
ogdf::fast_multipole_embedder::LinearQuadtree::setPoint
void setPoint(PointID id, float x, float y, float r, uint32_t ref)
Definition: LinearQuadtree.h:548
ogdf::fast_multipole_embedder::LinearQuadtree::m_origXPos
float * m_origXPos
point x coord in graph order
Definition: LinearQuadtree.h:719
ogdf::fast_multipole_embedder::LinearQuadtree::firstPoint
PointID firstPoint(NodeID nodeID) const
Definition: LinearQuadtree.h:389
ogdf::fast_multipole_embedder::LinearQuadtree::is_fence_condition
is_fence_condition_functor is_fence_condition() const
creator
Definition: LinearQuadtree.h:88
ogdf::fast_multipole_embedder::LinearQuadtree::pointLeaf
NodeID pointLeaf(PointID point) const
Definition: LinearQuadtree.h:499
ogdf::fast_multipole_embedder::LinearQuadtree::forall_ordered_pairs_of_children_functor::forall_ordered_pairs_of_children_functor
forall_ordered_pairs_of_children_functor(const LinearQuadtree &t, F f)
Definition: LinearQuadtree.h:187
ogdf::fast_multipole_embedder::LinearQuadtree::bottom_up_traversal
bottom_up_traversal_functor< F, Cond > bottom_up_traversal(F f, Cond cond) const
creator
Definition: LinearQuadtree.h:263
ogdf::fast_multipole_embedder::LinearQuadtree::is_leaf_condition_functor::is_leaf_condition_functor
is_leaf_condition_functor(const LinearQuadtree &t)
Definition: LinearQuadtree.h:94
ogdf::fast_multipole_embedder::LinearQuadtree::forall_points_functor::operator()
void operator()(NodeID u)
Definition: LinearQuadtree.h:164
ogdf::fast_multipole_embedder::LinearQuadtree::m_scaleInv
double m_scaleInv
the inverse scale to transform
Definition: LinearQuadtree.h:710
ogdf::fast_multipole_embedder::LinearQuadtree::LQPoint::node
uint32_t node
Definition: LinearQuadtree.h:58
ogdf::fast_multipole_embedder::LinearQuadtree::nodeSize
float nodeSize(NodeID nodeID) const
Definition: LinearQuadtree.h:529
OGDF_LQ_WSPD_BOUND
#define OGDF_LQ_WSPD_BOUND
Definition: LinearQuadtree.h:39
ogdf::fast_multipole_embedder::LinearQuadtree::child
NodeID child(NodeID nodeID, uint32_t i) const
returns the i th child index of node nodeID
Definition: LinearQuadtree.h:429
ogdf::fast_multipole_embedder::LinearQuadtree::m_maxNumNodes
uint32_t m_maxNumNodes
the maximum number of nodes (2*n here instead of 2*n-1)
Definition: LinearQuadtree.h:750
ogdf::fast_multipole_embedder::LinearQuadtree::forall_children_functor::func
F func
Definition: LinearQuadtree.h:136
ogdf::fast_multipole_embedder::LinearQuadtree::pointY
float * pointY() const
Definition: LinearQuadtree.h:517
ogdf::fast_multipole_embedder::LinearQuadtree::bottom_up_traversal_functor::cond
CondType cond
Definition: LinearQuadtree.h:243
ogdf::fast_multipole_embedder::LinearQuadtree::LQPoint::ref
uint32_t ref
Definition: LinearQuadtree.h:59
r
int r[]
Definition: hierarchical-ranking.cpp:8
ogdf::fast_multipole_embedder::LinearQuadtree::m_nodeSize
float * m_nodeSize
node size
Definition: LinearQuadtree.h:744
ogdf::fast_multipole_embedder::LinearQuadtree::is_leaf_condition
is_leaf_condition_functor is_leaf_condition() const
creator
Definition: LinearQuadtree.h:99
ogdf::fast_multipole_embedder::LinearQuadtree::pointX
float pointX(PointID point) const
Definition: LinearQuadtree.h:509
ogdf::fast_multipole_embedder::LinearQuadtree::m_nodeYPos
float * m_nodeYPos
node y coord
Definition: LinearQuadtree.h:741
ogdf::fast_multipole_embedder::LinearQuadtree::LQNode::numPoints
uint32_t numPoints
Definition: LinearQuadtree.h:69
ogdf::fast_multipole_embedder::LinearQuadtree::m_min_y
float m_min_y
the y coordinate of the bottom most point
Definition: LinearQuadtree.h:698
ogdf::fast_multipole_embedder::LinearQuadtree::StoreDirectPairFunction
StoreDirectPairFunctor StoreDirectPairFunction()
Definition: LinearQuadtree.h:357
OGDF_LQ_M2L_MIN_BOUND
#define OGDF_LQ_M2L_MIN_BOUND
Definition: LinearQuadtree.h:37
ogdf::fast_multipole_embedder::LinearQuadtree::forall_tree_nodes_functor::forall_tree_nodes_functor
forall_tree_nodes_functor(const LinearQuadtree &t, F f, NodeID b, uint32_t num)
Definition: LinearQuadtree.h:111
ogdf::fast_multipole_embedder::LinearQuadtree::is_leaf_condition_functor::tree
const LinearQuadtree & tree
Definition: LinearQuadtree.h:93
ogdf::fast_multipole_embedder::MortonNR
uint64_t MortonNR
Definition: FastUtils.h:69
ogdf::fast_multipole_embedder::LinearQuadtree::top_down_traversal
top_down_traversal_functor< F, Cond > top_down_traversal(F f, Cond cond) const
creator
Definition: LinearQuadtree.h:231
ogdf::fast_multipole_embedder::LinearQuadtree::init
void init(float min_x, float min_y, float max_x, float max_y)
ogdf::fast_multipole_embedder::LinearQuadtree::m_numPoints
uint32_t m_numPoints
number of points this quadtree is based on
Definition: LinearQuadtree.h:756
ogdf::fast_multipole_embedder::LinearQuadtree::firstLeaf
NodeID firstLeaf() const
Definition: LinearQuadtree.h:596
ogdf::fast_multipole_embedder::LinearQuadtree::is_fence_condition_functor::is_fence_condition_functor
is_fence_condition_functor(const LinearQuadtree &t)
Definition: LinearQuadtree.h:83
ogdf::fast_multipole_embedder::LinearQuadtree::top_down_traversal_functor::tree
const LinearQuadtree & tree
Definition: LinearQuadtree.h:209
ogdf::fast_multipole_embedder::LinearQuadtree::wspd_functor::BranchCondFunction
BranchCondType BranchCondFunction
Definition: LinearQuadtree.h:276
ogdf::fast_multipole_embedder::LinearQuadtree::point
const LQPoint & point(PointID pointID) const
Definition: LinearQuadtree.h:404
ogdf::fast_multipole_embedder::LinearQuadtree::m_max_x
float m_max_x
the x coordinate of the right most point
Definition: LinearQuadtree.h:701
ogdf::fast_multipole_embedder::LinearQuadtree::setNodeX
void setNodeX(NodeID nodeID, float x)
Definition: LinearQuadtree.h:523
ogdf::fast_multipole_embedder::LinearQuadtree::leafAppendPoint
void leafAppendPoint(NodeID leaf, PointID point)
appends an successing point by simply increasing childcount of a leaf. Assumes isLeaf
Definition: LinearQuadtree.h:679
ogdf::fast_multipole_embedder::LinearQuadtree::LQWSPair
Definition: LinearQuadtree.h:73
ogdf::fast_multipole_embedder::LinearQuadtree::m_numLeaves
uint32_t m_numLeaves
number of leaves in the chain
Definition: LinearQuadtree.h:776
ogdf::fast_multipole_embedder::LinearQuadtree::forall_points
forall_points_functor< Func > forall_points(const Func &func) const
creator
Definition: LinearQuadtree.h:175
ogdf::fast_multipole_embedder::LinearQuadtree::LQPoint
Definition: LinearQuadtree.h:55
ogdf::fast_multipole_embedder::LinearQuadtree::pointY
float pointY(PointID point) const
Definition: LinearQuadtree.h:511
ogdf::fast_multipole_embedder::LinearQuadtree::top_down_traversal_functor::top_down_traversal_functor
top_down_traversal_functor(const LinearQuadtree &t, F f)
Definition: LinearQuadtree.h:213
ogdf::fast_multipole_embedder::LinearQuadtree::pointArray
LQPoint * pointArray()
Definition: LinearQuadtree.h:638
ogdf::fast_multipole_embedder::LinearQuadtree::point
LQPoint & point(PointID pointID)
Definition: LinearQuadtree.h:399
ogdf::fast_multipole_embedder::LinearQuadtree::level
NodeID level(NodeID nodeID) const
Definition: LinearQuadtree.h:369
ogdf::fast_multipole_embedder::LinearQuadtree::setNodeY
void setNodeY(NodeID nodeID, float y)
Definition: LinearQuadtree.h:527
ogdf::fast_multipole_embedder::LinearQuadtree::wspd
WSPD * wspd() const
Definition: LinearQuadtree.h:614
ogdf::fast_multipole_embedder::LinearQuadtree::LQNode::firstPoint
PointID firstPoint
Definition: LinearQuadtree.h:68
ogdf::fast_multipole_embedder::LinearQuadtree::bottom_up_traversal_functor::operator()
void operator()(NodeID u)
Definition: LinearQuadtree.h:248
ogdf::fast_multipole_embedder::LinearQuadtree::bottom_up_traversal
bottom_up_traversal_functor< F > bottom_up_traversal(F f) const
creator
Definition: LinearQuadtree.h:256
ogdf::fast_multipole_embedder::LinearQuadtree::m_numWSP
uint32_t m_numWSP
Definition: LinearQuadtree.h:758
ogdf::fast_multipole_embedder::LinearQuadtree::initInnerNode
void initInnerNode(NodeID nodeID, NodeID leftChild, NodeID rightChild, uint32_t level, NodeID next)
Definition: LinearQuadtree.h:659
ogdf::fast_multipole_embedder::LinearQuadtree::nodeAppendChild
void nodeAppendChild(NodeID nodeID, NodeID child)
appends one child index. Assumes childCount < 4 and not leaf
Definition: LinearQuadtree.h:672
ogdf::fast_multipole_embedder::LinearQuadtree::StoreDirectPairFunctor::tree
LinearQuadtree & tree
Definition: LinearQuadtree.h:352
ogdf::fast_multipole_embedder::LinearQuadtree::minY
float minY() const
Definition: LinearQuadtree.h:618
ogdf::fast_multipole_embedder::LinearQuadtree::forall_children_functor::forall_children_functor
forall_children_functor(const LinearQuadtree &t, F f)
Definition: LinearQuadtree.h:138
ogdf::fast_multipole_embedder::LQPointComparer
bool LQPointComparer(const LinearQuadtree::LQPoint &a, const LinearQuadtree::LQPoint &b)
Definition: LinearQuadtree.h:786
ogdf::fast_multipole_embedder::LinearQuadtree::LQWSPair::a
NodeID a
Definition: LinearQuadtree.h:75
ogdf::fast_multipole_embedder::LinearQuadtree::m_numInnerNodes
uint32_t m_numInnerNodes
number of inner nodes in the chain
Definition: LinearQuadtree.h:782
ogdf::fast_multipole_embedder::LinearQuadtree::maxY
float maxY() const
Definition: LinearQuadtree.h:620
ogdf::fast_multipole_embedder::LinearQuadtree::m_cellSize
double m_cellSize
the height and width of a grid cell
Definition: LinearQuadtree.h:707
ogdf::fast_multipole_embedder::LinearQuadtree::setChild
void setChild(NodeID nodeID, uint32_t i, NodeID c)
sets the i th child index of node nodeID
Definition: LinearQuadtree.h:435
ogdf::fast_multipole_embedder::LinearQuadtree::m_directNodes
NodeID * m_directNodes
Definition: LinearQuadtree.h:763
ogdf::fast_multipole_embedder::LinearQuadtree::m_firstInner
NodeID m_firstInner
first inner node in the inner node chain
Definition: LinearQuadtree.h:779
ogdf::fast_multipole_embedder::LinearQuadtree::wspd_functor::wspd_functor
wspd_functor(const LinearQuadtree &t, WSPairFuncType &wsf, DPairFuncType &dpf, DNodeFuncType &dnf)
Definition: LinearQuadtree.h:278
ogdf::fast_multipole_embedder::LinearQuadtree::forall_tree_nodes_functor
simple functor for iterating over all nodes
Definition: LinearQuadtree.h:104
ogdf::fast_multipole_embedder::LinearQuadtree::StoreWSPairFunctor
Definition: LinearQuadtree.h:340
ogdf::fast_multipole_embedder::LinearQuadtree::addDirectPair
void addDirectPair(NodeID s, NodeID t)
add a direct pair to the array list of direct pairs
ogdf::fast_multipole_embedder::LinearQuadtree::is_fence_condition_functor::operator()
bool operator()(NodeID u)
Definition: LinearQuadtree.h:84
ogdf::fast_multipole_embedder::LinearQuadtree::forall_tree_nodes_functor::numNodes
uint32_t numNodes
Definition: LinearQuadtree.h:109
ogdf::fast_multipole_embedder::LinearQuadtree::forall_ordered_pairs_of_children_functor
functor for iterating over all ordered pairs of children of a node
Definition: LinearQuadtree.h:182
ogdf::fast_multipole_embedder::LinearQuadtree::setNextNode
void setNextNode(NodeID nodeID, NodeID next)
Definition: LinearQuadtree.h:379
ogdf::fast_multipole_embedder::LinearQuadtree::wspd_functor::DPairFunction
DPairFuncType DPairFunction
Definition: LinearQuadtree.h:274
ogdf::fast_multipole_embedder::LinearQuadtree
Definition: LinearQuadtree.h:47
ogdf::fast_multipole_embedder::LinearQuadtree::PointID
unsigned int PointID
Definition: LinearQuadtree.h:53
ogdf::fast_multipole_embedder::LinearQuadtree::m_max_y
float m_max_y
the y coordinate of the top most point
Definition: LinearQuadtree.h:704
ogdf::fast_multipole_embedder::LinearQuadtree::~LinearQuadtree
~LinearQuadtree(void)
destructor. tree mem will be released
ogdf::fast_multipole_embedder::LinearQuadtree::StoreWSPairFunctor::operator()
void operator()(NodeID a, NodeID b)
Definition: LinearQuadtree.h:344
ogdf::fast_multipole_embedder::LinearQuadtree::forall_points_functor::tree
const LinearQuadtree & tree
Definition: LinearQuadtree.h:159
ogdf::fast_multipole_embedder::LinearQuadtree::m_origYPos
float * m_origYPos
point y coord in graph order
Definition: LinearQuadtree.h:722
ogdf::fast_multipole_embedder::LinearQuadtree::pointX
float * pointX() const
Definition: LinearQuadtree.h:515
ogdf::fast_multipole_embedder::LinearQuadtree::computeWSPD
void computeWSPD()
ogdf::fast_multipole_embedder::LinearQuadtree::numberOfWSP
uint32_t numberOfWSP() const
Definition: LinearQuadtree.h:601
ogdf::fast_multipole_embedder::LinearQuadtree::is_fence_condition_functor
Definition: LinearQuadtree.h:80
ogdf::fast_multipole_embedder::LinearQuadtree::m_sideLengthPoints
double m_sideLengthPoints
the maximum of height and width
Definition: LinearQuadtree.h:713
ogdf::fast_multipole_embedder::LinearQuadtree::isLeaf
bool isLeaf(NodeID nodeID) const
returns true if the given node index is a leaf
Definition: LinearQuadtree.h:441
ogdf::fast_multipole_embedder::LinearQuadtree::LQWSPair::b
NodeID b
Definition: LinearQuadtree.h:77
ogdf::fast_multipole_embedder::LinearQuadtree::wspd_functor::tree
const LinearQuadtree & tree
Definition: LinearQuadtree.h:272
ogdf::fast_multipole_embedder::LinearQuadtree::m_pointXPos
float * m_pointXPos
point x coord in tree order
Definition: LinearQuadtree.h:728
ogdf::fast_multipole_embedder::LinearQuadtree::bottom_up_traversal_functor::bottom_up_traversal_functor
bottom_up_traversal_functor(const LinearQuadtree &t, F f)
Definition: LinearQuadtree.h:245
OGDF_LQ_WSPD_BRANCH_BOUND
#define OGDF_LQ_WSPD_BRANCH_BOUND
Definition: LinearQuadtree.h:38
ogdf::fast_multipole_embedder::LinearQuadtree::deallocate
void deallocate()
helper function for releasing memory
ogdf::fast_multipole_embedder::LinearQuadtree::LQNode
Definition: LinearQuadtree.h:62
ogdf::fast_multipole_embedder::LinearQuadtree::root
NodeID root() const
returns the index of the root
Definition: LinearQuadtree.h:465
ogdf::fast_multipole_embedder::LinearQuadtree::refOfPoint
uint32_t refOfPoint(PointID id) const
Definition: LinearQuadtree.h:563
ogdf::fast_multipole_embedder::LinearQuadtree::m_pointYPos
float * m_pointYPos
point y coord in tree order
Definition: LinearQuadtree.h:731
FMEFunctional.h
Definitions of functors used in FME layout.
ogdf::fast_multipole_embedder::LinearQuadtree::forall_tree_nodes_functor::begin
NodeID begin
Definition: LinearQuadtree.h:108
ogdf::fast_multipole_embedder::LinearQuadtree::bottom_up_traversal_functor::func
F func
Definition: LinearQuadtree.h:242
ogdf::fast_multipole_embedder::LinearQuadtree::mortonNr
MortonNR mortonNr(PointID point) const
Definition: LinearQuadtree.h:409
ogdf::fast_multipole_embedder::LinearQuadtree::nodeFence
void nodeFence(NodeID nodeID)
Definition: LinearQuadtree.h:573
ogdf::fast_multipole_embedder::LinearQuadtree::m_points
LQPoint * m_points
the point order in tree order
Definition: LinearQuadtree.h:753
ogdf::fast_multipole_embedder::LinearQuadtree::m_min_x
float m_min_x
the x coordinate of the left most point
Definition: LinearQuadtree.h:695
ogdf::fast_multipole_embedder::LinearQuadtree::setPoint
void setPoint(PointID id, float x, float y, float r)
Definition: LinearQuadtree.h:556
ogdf::fast_multipole_embedder::LinearQuadtree::StoreDirectPairFunctor::StoreDirectPairFunctor
StoreDirectPairFunctor(LinearQuadtree &t)
Definition: LinearQuadtree.h:353
ogdf::fast_multipole_embedder::LinearQuadtree::m_sideLengthGrid
double m_sideLengthGrid
the resulting side length of the grid (constant)
Definition: LinearQuadtree.h:716
ogdf::fast_multipole_embedder::LinearQuadtree::directNodeB
NodeID directNodeB(uint32_t i) const
Definition: LinearQuadtree.h:611
ogdf::fast_multipole_embedder::LinearQuadtree::wspd_functor::DNodeFunction
DNodeFuncType DNodeFunction
Definition: LinearQuadtree.h:275
ogdf::fast_multipole_embedder::LinearQuadtree::updatePointPositionSize
void updatePointPositionSize(PointID id)
Definition: LinearQuadtree.h:540
ogdf::fast_multipole_embedder::LinearQuadtree::StoreWSPairFunctor::tree
LinearQuadtree & tree
Definition: LinearQuadtree.h:342
ogdf::fast_multipole_embedder::LinearQuadtree::LinearQuadtree
LinearQuadtree(uint32_t n, float *origXPos, float *origYPos, float *origSize)
constructor. required tree mem will be allocated
ogdf::fast_multipole_embedder::LinearQuadtree::setLevel
void setLevel(NodeID nodeID, uint32_t level)
Definition: LinearQuadtree.h:384
ogdf::fast_multipole_embedder::LinearQuadtree::directNodeA
NodeID directNodeA(uint32_t i) const
Definition: LinearQuadtree.h:609
ogdf::fast_multipole_embedder::LinearQuadtree::m_firstLeaf
NodeID m_firstLeaf
first leaf in the leaf chain
Definition: LinearQuadtree.h:773
ogdf::fast_multipole_embedder::LinearQuadtree::StoreDirectPairFunctor::operator()
void operator()(NodeID a, NodeID b)
Definition: LinearQuadtree.h:354
ogdf::fast_multipole_embedder::LinearQuadtree::numberOfPoints
uint32_t numberOfPoints() const
returns the number of points in this tree
Definition: LinearQuadtree.h:471
ogdf::fast_multipole_embedder::LinearQuadtree::LQNode::level
uint32_t level
Definition: LinearQuadtree.h:64
ogdf::fast_multipole_embedder::LinearQuadtree::clear
void clear()
resets the tree
ogdf::fast_multipole_embedder::LinearQuadtree::StoreDirectNodeFunctor
Definition: LinearQuadtree.h:360
ogdf::fast_multipole_embedder::LinearQuadtree::m_root
NodeID m_root
the root of the tree
Definition: LinearQuadtree.h:770
ogdf::fast_multipole_embedder::LinearQuadtree::setPoint
void setPoint(PointID id, float x, float y, uint32_t ref)
Definition: LinearQuadtree.h:533
ogdf::fast_multipole_embedder::LinearQuadtree::is_fence_condition_functor::tree
const LinearQuadtree & tree
Definition: LinearQuadtree.h:82
ogdf::fast_multipole_embedder::LinearQuadtree::forall_children_functor::tree
const LinearQuadtree & tree
Definition: LinearQuadtree.h:135
ogdf::fast_multipole_embedder::LinearQuadtree::maxX
float maxX() const
Definition: LinearQuadtree.h:619
ogdf::fast_multipole_embedder::LinearQuadtree::pointSize
float * pointSize() const
Definition: LinearQuadtree.h:519
ogdf::fast_multipole_embedder::LinearQuadtree::bottom_up_traversal_functor
bottom up traversal of the subtree of a given node
Definition: LinearQuadtree.h:239
ogdf::fast_multipole_embedder::LinearQuadtree::forall_children_functor
simple functor for iterating over all children of a node
Definition: LinearQuadtree.h:133
ogdf::fast_multipole_embedder::LinearQuadtree::maxNumberOfNodes
uint32_t maxNumberOfNodes() const
the upper bound for a compressed quadtree (2*numPoints)
Definition: LinearQuadtree.h:483
ogdf::fast_multipole_embedder::LinearQuadtree::forall_ordered_pairs_of_children
forall_ordered_pairs_of_children_functor< F > forall_ordered_pairs_of_children(F f) const
creator
Definition: LinearQuadtree.h:200
ogdf::fast_multipole_embedder::LinearQuadtree::wspd_functor::wspd_functor
wspd_functor(const LinearQuadtree &t, WSPairFuncType &wsf, DPairFuncType &dpf, DNodeFuncType &dnf, BranchCondType &bc)
Definition: LinearQuadtree.h:281
ogdf::fast_multipole_embedder::LinearQuadtree::LQNode::child
NodeID child[4]
Definition: LinearQuadtree.h:66
ogdf::fast_multipole_embedder::LinearQuadtree::setNodeSize
void setNodeSize(NodeID nodeID, float size)
Definition: LinearQuadtree.h:531
ogdf::fast_multipole_embedder::LinearQuadtree::m_WSPD
WSPD * m_WSPD
the wspd of this quadtree
Definition: LinearQuadtree.h:767
ogdf::fast_multipole_embedder::LinearQuadtree::LQNode::next
NodeID next
Definition: LinearQuadtree.h:65
ogdf::fast_multipole_embedder::LinearQuadtree::forall_points_functor::func
Func func
Definition: LinearQuadtree.h:160
ogdf::fast_multipole_embedder::LinearQuadtree::m_numDirectNodes
uint32_t m_numDirectNodes
Definition: LinearQuadtree.h:764
ogdf::fast_multipole_embedder::LinearQuadtree::forall_well_separated_pairs
wspd_functor< A, B, C > forall_well_separated_pairs(A a, B b, C c)
Definition: LinearQuadtree.h:335
ogdf::fast_multipole_embedder::LinearQuadtree::numberOfChilds
uint32_t numberOfChilds(NodeID nodeID) const
returns the number of children of node nodeID. for an inner node this is 1..4 and can be accessed by ...
Definition: LinearQuadtree.h:417