4 * Created on: May 12, 2014
7 * Modified by: Alfredo Morales Pinzón
10 #ifndef AIRWAYSNODE_H_
11 #define AIRWAYSNODE_H_
16 #include "../MathLib/vec3.h"
17 #include "airwaysEdge.h"
18 #include "Quaternion.h"
19 #include <appli/TempAirwaysAppli/AirwaysLib/AirwaysLib_Export.h>
31 * This class represents a node in a tree.
33 class AirwaysLib_EXPORT Node
39 typedef std::pair<Node*, Node*> pair_nodes;
42 typedef std::vector<Node*> vec_nodes;
44 // Map to link an id node to a list of nodes
45 typedef std::map< unsigned int, vec_nodes > map_id_vecnodes;
48 * This is the default constructor
53 * This is the alternative constructor
56 Node(const Vec3& coord);
59 * This is the alternative constructor (copy)
65 * This is the destructor
72 * This method returns the vector of the node children (const)
75 const std::vector<Node*>& GetChildren() const;
78 * Method that returns the node id
79 * @return the id of the node
81 const unsigned int GetId() const;
84 * This method returns the spatial position of a node
87 const Vec3& GetCoords() const;
90 * Method that returns the edge between the current node and its parent
93 Edge* GetEdge() const;
96 * Method that returns the father
99 Node* GetFather() const;
102 * This method returns the level of the node
103 * @return the level of the node
105 unsigned int GetLevel() const;
108 * Method that returns the depth of the node whose id is given by parameter
109 * @pre the node exist in the sub-tree
110 * @param idNode is the search node id
111 * @return the depth of the node up to the actual node
113 int GetDepthById(unsigned int idNode) const;
116 * Method that returns the weight of the tree
117 * @return the weight of the tree which is the number of nodes in the tree.
119 unsigned int GetWeight() const;
122 * Method that returns the height of the tree
123 * @return the height of the tree
125 unsigned int GetHeight() const;
128 * This method returns the size of the children vector
129 * @return the number of children
131 unsigned int GetNumberOfChildren() const;
134 * Method that returns the number of children non-marked
135 * @param depth is the depth up to which the non-marked child are taken into account
136 * @return the number of children non-marked
138 unsigned int GetNumberOfNonMarkedChildren( unsigned int depth ) const;
141 * Method that returns the number of leafs in the node and its children
142 * @return the number of leafs in the in the node and its children
144 unsigned int GetNumberOfLeafs( ) const;
147 * This method returns the node that has the requested id
148 * @param nId is the requested id
149 * @return is the node that has the requested id, NULL if the node is not found.
151 Node* GetNodeById(unsigned int nId);
154 * Method that returns the closest node to the givel voxel
155 * The closes node is the one whose path (skeleton) to the father has the closest point to the given point.
156 * @param voxel_x x componente of the voxel
157 * @param voxel_y y componente of the voxel
158 * @param voxel_z z componente of the voxel
159 * @param distance return the distance to the closest node
160 * @return the closest node to the given voxel
162 Node* GetClosestBranchNodeToPoint(float point_x, float point_y, float point_z, float &distance);
165 * Method that returns the closest node to the position given by parameter
166 * @param position is the position to be compares with
167 * @param distance is the minimum distance found
168 * return the closest node to the position given by parameter
170 Node* GetClosestNodeToPoint(Vec3 position, double& distance);
173 * Method that return the closest distance of the node skeleton
174 * @param voxel_x x componente of the voxel
175 * @param voxel_y y componente of the voxel
176 * @param voxel_z z componente of the voxel
177 * @return the closest distance of the node skeleton
179 float GetBranchDistanceToPoint(int voxel_x, int voxel_y, int voxel_z);
182 * Method that returns if the tree has a minimum of levels
183 * @return true if the tree has the minimum of levels, false otherwise
185 bool HasMinimumLevels(int levels);
189 * This method returns true if the node is a leaf
195 * This method returns true if the node is marked
198 bool IsMarked() const;
201 * Method that tells if a node has marked children
202 * @return true if the node has marked children, false otherwise
204 bool HasMarkedChildren() const;
207 * Method that returns if a node is in the descending set of nodes
208 * @return true is the given node is in the descending set of nodes, false otherwise
210 bool HasNode(Node* node_searched) const;
213 * Method that return if a node is in the tree
214 * @param id_node_searched id of the searched node
215 * @return true is the node is in the tree, false otherwise
217 bool HasNodeId(unsigned int id_node_searched) const;
220 * Method that returns if a voxel is influenced by a node, i.e. if the distance
221 * to the closest voxel of the edge is smaller than the radius on the closest voxel.
222 * @param x,y,z are the voxel positions in coordinates x, y, and z respectively.
223 * @return true is the voxel is influenced, false otherwise.
225 bool IsPointInfluencedByNode(float point_x, float point_y, float point_z) const;
228 * Method that returns the list of nodes that influence the given point
229 * @param point_x, point_y, point_z are the position of the point in real coordinates x, y, and z respectively.
230 * @param vec_nodes_influence vector to save the nodes
232 void GetBrancheNodesInfluencingPoint(float point_x, float point_y, float point_z, vec_nodes& vec_nodes_influence);
235 * Method that adds to a vector all the children with a maximum depth Q from actual node.
236 * If Q = 0, no nodes are added.
237 * @param Q the depth to find the children
238 * @param fathers vector to return the children
240 void GetChildrenUptoDepth(unsigned int Q, vec_nodes& fathers);
243 * This method compares the subtrees that start in this node and one given by parameter.
244 * @param nodeB is the stating node of the subtree to be compared with
245 * @param Q is the depth to select "fathers" nodes
246 * @param F is the depth to select "family" nodes
247 * @param commonA vector to save the common nodes for this subtree
248 * @param commonA vector to save the common nodes for the subtree given by parameter
249 * @param nonCommonA vector to save the non-common nodes for this subtree
250 * @param nonCommonB vector to save the non-common nodes for the subtree given by parameter
252 void CompareSubTreesOrkiszMorales(Node* nodeB, unsigned int Q, unsigned int F, vec_nodes& commonA, vec_nodes& commonB, vec_nodes& nonCommonA, vec_nodes& nonCommonB, map_id_vecnodes& map_A_to_B, map_id_vecnodes& map_B_to_A, std::vector< std::pair< pair_nodes, pair_nodes > >& vector_pair_edges);
255 * Method that returns the pair of branches (one node for each tree) that has the minimum distance after root overlapping.
256 * Valid branches for the actual node are the one level branches those the branches up to this child (height = 2).
257 * Root overlapping means the translation of branch so that root overlap.
258 * @pre: The actual branch is not marked.
259 * @param nodeB is the subtree root node to be compared with
260 * @return the pair of branches (one node for each tree) that has the minimum distance after root overlapping
262 std::pair< std::pair<Node*, Node*>, double> GetBestBranches_ActualTranslatedOneLevelBranches_To_AllPossibleBranches(Node* nodeB);
265 * Method that returns all the distances to all the non-marked branches, i.e., the end node of the branch is non-marked,
266 * inside a multimap (key, value) structure where the value elementent corresponds to the compared branches.
267 * @param node_gradfather is the grandfather node to be compared
268 * @param Q is the depth to select "fathers"
269 * @param F is the depth to select "family" nodes
270 * @return multimap where the key is the distance between branches and the value is the pair of compared branches end-nodes.
272 std::multimap< double, std::pair<Node*, Node*> > CalculateDistanceToAllBranches_FatherAndFamily(Node* node_gradfather, unsigned int Q, unsigned int F);
275 * Method is executed by grandfather nodes. It returns the closest pair of nodes,
276 * one must be my child and the other one of the relatives given node.
277 * The closest pair is the one that has the minimal distance between the children and the families.
278 * The distance is the sum of fathers distances and family distances.
279 * @param nodeB is the node to be compared with
280 * @return the closest pair of nodes, one must be my child and the other on of the relatives given node.
282 //std::pair< std::pair<Node*, Node*>, double> GetClosestBranch_FatherAndFamily(Node* nodeB);
285 * Method that returns the closest relative node, all the nodes but this, whose position is the closest to the point given by parameter
286 * @param position is the point to be compared with
287 * @param distance is the minimum distance found in the relatives
288 * @return the closest relative node, all the nodes but this, whose position is the closest to the point given by parameter
290 Node* GetClosestRelativeToPoint(Vec3 position, double& distance);
293 Node* GetClosestRelativeToBranch(Edge* branch, Vec3 vector_translation, double& distance);
296 * Method that returns the closest node to the given by node.
297 * Closest involve the distance between fathers and family.
298 * @param node_grandfather is the father of the "node_father" which can be different from the direct father.
299 * this is the case when the father distance is the algorithm, given by Q, is greater than 1.
300 * @param node_father is the node to be compared with
301 * @param F is the depth to select "family" nodes
302 * @param vector_translation is the translation vector to translate the "father" branch
303 * @param distance is the distance to be returned by parameter
304 * @return the closest node to the given by node.
306 Node* GetClosestRelativeFatherAndFamily(Node* node_grandfather, Node* node_father, unsigned int F, Vec3 vector_translation, double& distance);
308 Node* GetClosestBranchToTranslatedBranch(Edge* branch, Vec3 vector_translation, double& distance, Edge* edgeSuperior);
311 * This method returns the closest father and family, in this subtree, that is the closest to the subtree given by parameter
312 * The returned node represents the father.
313 * @param node_grandfather is the father of the "node_father" which can be different from the direct father.
314 * this is the case when the father distance is the algorithm, given by Q, is greater than 1.
315 * @param node_father is the node father to be compared with
316 * @param F is the depth to select "family" nodes
317 * @param vector_translation is the translation vector to translation the father given by parameter
318 * @param distance is the closest distances to be returned by parameter
319 * @param edgeSuperior is a superior edge where the actual edge must be attached
320 * @returns the closest father and family, in this subtree, that is the closest to the subtree given by parameter
322 Node* GetClosestFatherAndFamilyToTranslatedFatherAndFamily(Node* node_grandfather, Node* node_father, unsigned int F, Vec3 vector_translation, double& distance, Edge* edgeSuperior);
325 * Method that return the closest ascending node that is marked as common.
326 * A common node may common if:
327 * (1) it is marked or (2) one of their descendants is marked
328 * return the closest ascending common node. NULL is there is no such node.
330 const Node* GetClosestCommonAscendingNode() const;
333 * Method that marks all nodes between this node and the one given by parameter. If the searched node is not found then all nodes are marked.
334 * @param nodeB is the searched node
335 * @return true is the node was found, false otherwise
337 bool MarkNodesUntilNode(Node* nodeB);
339 Node* GetNextNodeInPathToNode(Node* node_searched);
342 * Method that returns the path from the actual node to the searched node
343 * @param node_end is the searched node
344 * @param vector_pathNodes vector_pathNodesis the vector to return the path
346 void GetPathToNode(Node* node_end, vec_nodes& vector_pathNodes);
348 void MarkPathFromNodeToNode(Node* node_begin, Node* node_end);
350 void MarkPathNodesToNode(Node* node_end);
353 * Method that returns a root with a copy of this node as single child
354 * @return a root with a copy of this node as single child
356 Node* GetDetachedRootCopy();
359 * This method return true if two nodes are equals
363 bool CompareNodes(Node* nodeTreeB);
366 * Method that returns a new composed edge from this node to the searched node.
367 * @param idNode is the searched id node
368 * @return the edge to the searched node. Null if the node is not found.
370 Edge* GetComposedEdge(unsigned int idNode);
373 * Method that composes the actual edge with the edge given by parameter
374 * @param nEdge edge to be composed with
375 * @return final composed edge
377 Edge* AddChildEdgeInformation(Edge* nEdge);
380 * Method that returns a "composed edge" up to the ancestor
381 * @pre the ancesto node must be a real ancestor
382 * @param node_ancestor is the ancestor node to with the edge must be composed
383 * @param edge is the actual composed edge. NULL if the fist iteration
384 * @return the composed edge up to the ancesto node
386 Edge* GetEdgeToAncestor(Node* node_ancestor, Edge* edge);
389 * Method that concatenates the actual edge to a superior edge given by parameter.
390 * As the given edge is superior then the actual edge must be concatenate at the end of the superior edge,
391 * this means that superiorEdge.target must equal to the actualEdge.source.
392 * @param superiorEdge is the superior edge where the actual edge must be added
393 * @return - a copy of the actual edge if the superior edge is NULL
394 * - if superiorEdge.target == actualEdge.source the the superior edge with the actual edge concatenated
395 * - NULL otherwise (superiorEdge.target != actualEdge.source)
397 Edge* ConcatenateEdgeToSuperiorEdge(Edge* superiorEdge);
400 * This method returns true if the accumulation of a set of nodes are equals
401 * (in tolerance) to the compared node (this). This method tries to find
402 * edges in the case of edge losses.
403 * When this method returns true, NodeB pointer is replaced to the node (target)
404 * found by accumulation (See the report to understand what this means).
405 * @param nodeB - Current node to compare
406 * @param nodeBAcc - Accumulator Node (Optional)
409 bool FindSimilarEdgeByAccumulation(Node* nodeB, Node* nodeBAcc = NULL);
412 * This method returns true if there is a marked node along the hierarchy
416 bool FindMarked(Node* result);
419 * This method marks the path between two nodes and returns true if a path
424 bool MarkPath(Node* nodeB);
427 * This method returns the cost between two nodes.
431 unsigned int GetCost(Node* nodeB);
433 //Setters and Modifiers
436 * Method that sets the id of the node
437 * @param nM_id is the new id
439 void SetId(unsigned int nM_id);
442 * This method adds a node in the children vector
443 * @param node is the node to be added
445 void AddChild(Node* node);
448 * This method sets the children vector
451 void SetChildren(std::vector<Node*>& children);
454 * Method that sets the father
455 * @param nFather is the father
457 void SetFather(Node* nFather);
460 * This method sets an edge between the current node and its parent
463 void SetEdge(Edge* edge);
466 * This method sets the coordinates of the node
469 void SetCoords(const Vec3& coords);
472 * Method that sets the level of the node
473 * @param level is the level of the node
475 void SetLevel(const int& level);
478 * Method that deleted a node and all his children, from the tree
479 * @return true if the node was deleted (found), false otherwise
481 bool DeleteNodeById(unsigned int nId);
484 * This method merges the nodeB into this
487 void MergeNodes(Node* nodeB);
490 * This method marks a node
495 * This method unmarks a node
500 * This method update all levels along the hierarchy
503 void UpdateLevels(unsigned int level = 0);
507 * Method that prints the tree up to a given level
508 * @param level where the print must finish
510 void printUpToLevel(int level);
512 void printNodeAndChildrenIds( );
514 void printChildrenIds( );
517 * Method that creates the quaternions of the airways up the maxLevel
518 * @param level is the level where the extraction must end
519 * @param requiredLevel is the required level until the extraction must be done
522 void createQuaternionsUpToLevel(int level, int requiredLevel);
525 * Method that returns the closest pair node, based on their distance, having the first node of the pair as non-marked.
526 * The pair is found on the given a multimap of distances and pair of nodes. It is supposed that the multimap sorts
527 * the elements by its key. In this case the key corresponds to the distance.
528 * @param map_dist_pairNodes is the map containing the distances (keys) and the pair of nodes (value)
529 * @return the closest pair nodes, based on their distance, given a multimap of distances and pair of nodes. If
530 * no pair was found with the pair node nonmaked, a null pair is returned.
531 * Actually the method returns the pair and its distances in a pair <distance, pair>
533 std::pair<double, std::pair<Node*, Node*> > GetPairWithClosestDistance_FirstNodeNonMarked(std::multimap<double, pair_nodes> map_dist_pairNodes);
536 * Add the statistics of number of bifurcations in the tree to the array given by parameter
537 * @param p array to save the statistics
539 void getStasticsBifurcations(int* p);
543 Node& operator=(Node& node);
545 const Node& operator=(const Node& node);
547 bool operator ==(const Node& node);
549 bool operator !=(const Node& node);
551 bool operator <(const Node& node);
553 bool operator >(const Node& node);
563 * Children nodes vector
565 vec_nodes m_children;
573 * Edge between the current node and its parent.
574 * The source of the edge corresponds to the parent en the target to the child,
575 * in this case to "this" node.
580 * Spatial 3D position of the node in real coordinates of the image
595 } /* namespace airways */
597 #endif /* AIRWAYSNODE_H_ */