1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
|
/**
*
* This file is part of Tulip (https://tulip.labri.fr)
*
* Authors: David Auber and the Tulip development Team
* from LaBRI, University of Bordeaux
*
* Tulip is free software; you can redistribute it and/or modify
* it under the terms of the GNU Lesser General Public License
* as published by the Free Software Foundation, either version 3
* of the License, or (at your option) any later version.
*
* Tulip is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
* See the GNU General Public License for more details.
*
*/
#ifndef __OCTTREE_H__
#define __OCTTREE_H__
#include <tulip/Node.h>
#include <tulip/Coord.h>
#include <tulip/DoubleProperty.h>
#include <vector>
namespace tlp {
/**
* Octtree for graph nodes with positions in 3D space.
* Contains all graph nodes that are located in a given cuboid in 3D space.
* From Andreas Noack's java implementation.
*/
class OctTree {
friend class LinLogLayout;
protected:
bool isLeaf;
bool firstNode;
// Maximum depth of tree nodes.
unsigned int MAX_DEPTH; // = 18;
unsigned int MAX_CHILDREN;
// For leafs, the corresponding graph node; for non-leafs <code>null</code>.
tlp::node node;
// Children of this tree node.
// std::vector<OctTree*>* children ;//= new OctTree[8];
OctTree **_children;
// Number of children of this tree node.
unsigned int childCount; // = 0;
// unsigned int childrenSize;
// Barycenter of the contained graph nodes.
Coord position;
// Total weight of the contained graph nodes.
double weight;
// Minimum coordinates of the cuboid in each of the 3 dimensions.
Coord minPos;
// Maximum coordinates of the cuboid in each of the 3 dimensions.
Coord maxPos;
// The weight metric
tlp::DoubleProperty *linLogWeight;
public:
// constructor
OctTree(tlp::node node, Coord position, Coord minPos, Coord maxPos,
tlp::DoubleProperty *_linLogWeight, bool _fistNode);
// destructor
~OctTree();
// Adds a graph node to the octtree
void addNode(tlp::node newNode, Coord newPos, unsigned int depth);
// Adds a graph node to the OctTree, without changing the position and weight of the root
void addNode2(tlp::node newNode, Coord newPos, unsigned int depth);
// Removes a graph node from the octtree
void removeNode(tlp::node oldNode, Coord oldPos, unsigned int depth);
// Returns the maximum extension of the octtree
double width();
// Returns the height of the octtree
int getHeight();
// Returns the current node
tlp::node getNode();
// Sets the maximum number of children for a branch of the octtree
void setMaxChildren(unsigned int);
// Prints the tree on a console output
void printTree(unsigned int);
};
} // namespace tlp
#endif // __OCTTREE_H__
|
