appli/TempAirwaysAppli/AirwaysLib/airwaysNode.h

   1 /*
   2  * airwaysNode.h
   3  *
   4  *  Created on: May 12, 2014
   5  *  Author: caceres
   6  *
   7  *  Modified by: Alfredo Morales Pinzón
   8  */
   9
  10 #ifndef AIRWAYSNODE_H_
  11 #define AIRWAYSNODE_H_
  12
  13 #include <vector>
  14 #include <map>
  15
  16 #include "../MathLib/vec3.h"
  17 #include "airwaysEdge.h"
  18 #include "Quaternion.h"
  19 #include <appli/TempAirwaysAppli/AirwaysLib/AirwaysLib_Export.h>
  20
  21 // Namespaces
  22 using namespace std;
  23
  24 namespace airways
  25 {
  26
  27 class AirwaysTree;
  28 class Edge;
  29
  30 /*
  31  * This class represents a node in a tree.
  32  */
  33 class AirwaysLib_EXPORT Node
  34 {
  35
  36 public:
  37
  38         // Pair of nodes
  39         typedef std::pair<Node*, Node*> pair_nodes;
  40
  41         // Vector of nodes
  42         typedef std::vector<Node*> vec_nodes;
  43
  44         // Map to link an id node to a list of nodes
  45         typedef std::map< unsigned int, vec_nodes > map_id_vecnodes;
  46
  47         /*!
  48          * This is the default constructor
  49          */
  50         Node();
  51
  52         /*!
  53          * This is the alternative constructor
  54          * @param coord
  55          */
  56         Node(const Vec3& coord);
  57
  58         /*!
  59          * This is the alternative constructor (copy)
  60          * @param node
  61          */
  62         Node(Node* node);
  63
  64         /*!
  65          * This is the destructor
  66          */
  67         virtual ~Node();
  68
  69         //Getters
  70
  71         /*!
  72          * This method returns the vector of the node children (const)
  73          * @return
  74          */
  75         const std::vector<Node*>& GetChildren() const;
  76
  77         /**
  78          * Method that returns the node id
  79          * @return the id of the node
  80          */
  81         const unsigned int GetId() const;
  82
  83         /*!
  84          * This method returns the spatial position of a node
  85          * @return
  86          */
  87         const Vec3&     GetCoords() const;
  88
  89         /*
  90          * Method that returns the edge between the current node and its parent
  91          * @return the edge
  92          */
  93         Edge* GetEdge() const;
  94
  95         /*
  96          * Method that returns the father
  97          * @return the father
  98          */
  99         Node* GetFather() const;
 100
 101         /*
 102          * This method returns the level of the node
 103          * @return the level of the node
 104          */
 105         unsigned int GetLevel() const;
 106
 107         /**
 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
 112          */
 113         int GetDepthById(unsigned int idNode) const;
 114
 115         /**
 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.
 118          */
 119         unsigned int GetWeight() const;
 120
 121         /**
 122          * Method that returns the height of the tree
 123          * @return the height of the tree
 124          */
 125         unsigned int GetHeight() const;
 126
 127         /*!
 128          * This method returns the size of the children vector
 129          * @return the number of children
 130          */
 131         unsigned int GetNumberOfChildren() const;
 132
 133         /**
 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
 137          */
 138         unsigned int GetNumberOfNonMarkedChildren( unsigned int depth ) const;
 139
 140         /**
 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
 143          */
 144         unsigned int GetNumberOfLeafs( ) const;
 145
 146         /**
 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.
 150          */
 151         Node* GetNodeById(unsigned int nId);
 152
 153         /**
 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
 161          */
 162         Node* GetClosestBranchNodeToPoint(float point_x, float point_y, float point_z, float &distance);
 163
 164         /**
 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
 169          */
 170         Node* GetClosestNodeToPoint(Vec3 position, double& distance);
 171
 172         /**
 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
 178          */
 179         float GetBranchDistanceToPoint(int voxel_x, int voxel_y, int voxel_z);
 180
 181         /**
 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
 184          */
 185         bool HasMinimumLevels(int levels);
 186
 187
 188         /*!
 189          * This method returns true if the node is a leaf
 190          * @return
 191          */
 192         bool IsLeaf() const;
 193
 194         /*!
 195          * This method returns true if the node is marked
 196          * @return
 197          */
 198         bool IsMarked() const;
 199
 200         /**
 201          * Method that tells if a node has marked children
 202          * @return true if the node has marked children, false otherwise
 203          */
 204         bool HasMarkedChildren() const;
 205
 206         /**
 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
 209          */
 210         bool HasNode(Node* node_searched) const;
 211
 212         /**
 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
 216          */
 217         bool HasNodeId(unsigned int id_node_searched) const;
 218
 219         /**
 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.
 224          */
 225         bool IsPointInfluencedByNode(float point_x, float point_y, float point_z) const;
 226
 227         /**
 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
 231          */
 232         void GetBrancheNodesInfluencingPoint(float point_x, float point_y, float point_z, vec_nodes& vec_nodes_influence);
 233
 234         /**
 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
 239          */
 240         void GetChildrenUptoDepth(unsigned int Q, vec_nodes& fathers);
 241
 242         /**
 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
 251          */
 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);
 253
 254         /**
 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
 261          */
 262         std::pair< std::pair<Node*, Node*>, double> GetBestBranches_ActualTranslatedOneLevelBranches_To_AllPossibleBranches(Node* nodeB);
 263
 264         /**
 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.
 271          */
 272         std::multimap< double, std::pair<Node*, Node*> > CalculateDistanceToAllBranches_FatherAndFamily(Node* node_gradfather, unsigned int Q, unsigned int F);
 273
 274         /**
 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.
 281          */
 282         //std::pair< std::pair<Node*, Node*>, double> GetClosestBranch_FatherAndFamily(Node* nodeB);
 283
 284         /**
 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
 289          */
 290         Node* GetClosestRelativeToPoint(Vec3 position, double& distance);
 291
 292
 293         Node* GetClosestRelativeToBranch(Edge* branch, Vec3 vector_translation, double& distance);
 294
 295         /**
 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.
 305          */
 306         Node* GetClosestRelativeFatherAndFamily(Node* node_grandfather, Node* node_father, unsigned int F, Vec3 vector_translation, double& distance);
 307
 308         Node* GetClosestBranchToTranslatedBranch(Edge* branch, Vec3 vector_translation, double& distance, Edge* edgeSuperior);
 309
 310         /**
 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
 321          */
 322         Node* GetClosestFatherAndFamilyToTranslatedFatherAndFamily(Node* node_grandfather, Node* node_father, unsigned int F, Vec3 vector_translation, double& distance, Edge* edgeSuperior);
 323
 324         /**
 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.
 329          */
 330         const Node* GetClosestCommonAscendingNode() const;
 331
 332         /**
 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
 336          */
 337         bool MarkNodesUntilNode(Node* nodeB);
 338
 339         Node* GetNextNodeInPathToNode(Node* node_searched);
 340
 341         /**
 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
 345          */
 346         void GetPathToNode(Node* node_end, vec_nodes& vector_pathNodes);
 347
 348         void MarkPathFromNodeToNode(Node* node_begin, Node* node_end);
 349
 350         void MarkPathNodesToNode(Node* node_end);
 351
 352         /**
 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
 355          */
 356         Node* GetDetachedRootCopy();
 357
 358         /*!
 359          * This method return true if two nodes are equals
 360          * @param nodeTreeB
 361          * @return
 362          */
 363         bool CompareNodes(Node* nodeTreeB);
 364
 365         /**
 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.
 369          */
 370         Edge* GetComposedEdge(unsigned int idNode);
 371
 372         /**
 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
 376          */
 377         Edge* AddChildEdgeInformation(Edge* nEdge);
 378
 379         /**
 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
 385          */
 386         Edge* GetEdgeToAncestor(Node* node_ancestor, Edge* edge);
 387
 388         /**
 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)
 396          */
 397         Edge* ConcatenateEdgeToSuperiorEdge(Edge* superiorEdge);
 398
 399         /*!
 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)
 407          * @return
 408          */
 409         bool FindSimilarEdgeByAccumulation(Node* nodeB, Node* nodeBAcc = NULL);
 410
 411         /*!
 412          * This method returns true if there is a marked node along the hierarchy
 413          * @param result
 414          * @return
 415          */
 416         bool FindMarked(Node* result);
 417
 418         /*!
 419          * This method marks the path between two nodes and returns true if a path
 420          * has found.
 421          * @param nodeB
 422          * @return
 423          */
 424         bool MarkPath(Node* nodeB);
 425
 426         /*!
 427          * This method returns the cost between two nodes.
 428          * @param nodeB
 429          * @return
 430          */
 431         unsigned int GetCost(Node* nodeB);
 432
 433         //Setters and Modifiers
 434
 435         /*
 436          * Method that sets the id of the node
 437          * @param nM_id is the new id
 438          */
 439         void SetId(unsigned int nM_id);
 440
 441         /*!
 442          * This method adds a node in the children vector
 443          * @param node is the node to be added
 444          */
 445         void AddChild(Node* node);
 446
 447         /*!
 448          * This method sets the children vector
 449          * @param children
 450          */
 451         void SetChildren(std::vector<Node*>& children);
 452
 453         /**
 454          * Method that sets the father
 455          * @param nFather is the father
 456          */
 457         void SetFather(Node* nFather);
 458
 459         /*!
 460          * This method sets an edge between the current node and its parent
 461          * @param edge
 462          */
 463         void SetEdge(Edge* edge);
 464
 465         /*!
 466          * This method sets the coordinates of the node
 467          * @param coords
 468          */
 469         void SetCoords(const Vec3& coords);
 470
 471         /**
 472          * Method that sets the level of the node
 473          * @param level is the level of the node
 474          */
 475         void SetLevel(const int& level);
 476
 477         /**
 478          * Method that deleted a node and all his children, from the tree
 479          * @return true if the node was deleted (found), false otherwise
 480          */
 481         bool DeleteNodeById(unsigned int nId);
 482
 483         /*!
 484          * This method merges the nodeB into this
 485          * @param nodeB
 486          */
 487         void MergeNodes(Node* nodeB);
 488
 489         /*!
 490          * This method marks a node
 491          */
 492         void Mark();
 493
 494         /*!
 495          * This method unmarks a node
 496          */
 497         void UnMark();
 498
 499         /*!
 500          * This method update all levels along the hierarchy
 501          * @param level
 502          */
 503         void UpdateLevels(unsigned int level = 0);
 504
 505
 506         /**
 507          * Method that prints the tree up to a given level
 508          * @param level where the print must finish
 509          */
 510         void printUpToLevel(int level);
 511
 512         void printNodeAndChildrenIds( );
 513
 514         void printChildrenIds( );
 515
 516         /**
 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
 520          * @pre level >= 2
 521          */
 522         void createQuaternionsUpToLevel(int level, int requiredLevel);
 523
 524         /**
 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>
 532          */
 533         std::pair<double, std::pair<Node*, Node*> > GetPairWithClosestDistance_FirstNodeNonMarked(std::multimap<double, pair_nodes> map_dist_pairNodes);
 534
 535         /**
 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
 538          */
 539         void getStasticsBifurcations(int* p);
 540
 541         //Operator Overloads
 542
 543         Node& operator=(Node& node);
 544
 545         const Node& operator=(const Node& node);
 546
 547         bool operator ==(const Node& node);
 548
 549         bool operator !=(const Node& node);
 550
 551         bool operator <(const Node& node);
 552
 553         bool operator >(const Node& node);
 554
 555 protected:
 556
 557         /**
 558          * Node id
 559          */
 560         unsigned int m_id;
 561
 562         /**
 563          * Children nodes vector
 564          */
 565         vec_nodes m_children;
 566
 567         /**
 568          * Father node
 569          */
 570         Node* father;
 571
 572         /**
 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.
 576          */
 577         Edge* m_edge;
 578
 579         /**
 580          * Spatial 3D position of the node in real coordinates of the image
 581          */
 582         Vec3 m_coords;
 583
 584         /**
 585          * Node level
 586          */
 587         int m_level;
 588
 589         /**
 590          * Node mark
 591          */
 592         bool m_mark;
 593 };
 594
 595 } /* namespace airways */
 596
 597 #endif /* AIRWAYSNODE_H_ */