/* * airwaysNode.h * * Created on: May 12, 2014 * Author: caceres * * Modified by: Alfredo Morales Pinzón */ #ifndef AIRWAYSNODE_H_ #define AIRWAYSNODE_H_ #include #include #include "../MathLib/vec3.h" #include "airwaysEdge.h" #include "Quaternion.h" #include // Namespaces using namespace std; namespace airways { class AirwaysTree; class Edge; /* * This class represents a node in a tree. */ class AirwaysLib_EXPORT Node { public: // Pair of nodes typedef std::pair pair_nodes; // Vector of nodes typedef std::vector vec_nodes; // Map to link an id node to a list of nodes typedef std::map< unsigned int, vec_nodes > map_id_vecnodes; /*! * This is the default constructor */ Node(); /*! * This is the alternative constructor * @param coord */ Node(const Vec3& coord); /*! * This is the alternative constructor (copy) * @param node */ Node(Node* node); /*! * This is the destructor */ virtual ~Node(); //Getters /*! * This method returns the vector of the node children (const) * @return */ const std::vector& GetChildren() const; /** * Method that returns the node id * @return the id of the node */ const unsigned int GetId() const; /*! * This method returns the spatial position of a node * @return */ const Vec3& GetCoords() const; /* * Method that returns the edge between the current node and its parent * @return the edge */ Edge* GetEdge() const; /* * Method that returns the father * @return the father */ Node* GetFather() const; /* * This method returns the level of the node * @return the level of the node */ unsigned int GetLevel() const; /** * Method that returns the depth of the node whose id is given by parameter * @pre the node exist in the sub-tree * @param idNode is the search node id * @return the depth of the node up to the actual node */ int GetDepthById(unsigned int idNode) const; /** * Method that returns the weight of the tree * @return the weight of the tree which is the number of nodes in the tree. */ unsigned int GetWeight() const; /** * Method that returns the height of the tree * @return the height of the tree */ unsigned int GetHeight() const; /*! * This method returns the size of the children vector * @return the number of children */ unsigned int GetNumberOfChildren() const; /** * Method that returns the number of children non-marked * @param depth is the depth up to which the non-marked child are taken into account * @return the number of children non-marked */ unsigned int GetNumberOfNonMarkedChildren( unsigned int depth ) const; /** * Method that returns the number of leafs in the node and its children * @return the number of leafs in the in the node and its children */ unsigned int GetNumberOfLeafs( ) const; /** * This method returns the node that has the requested id * @param nId is the requested id * @return is the node that has the requested id, NULL if the node is not found. */ Node* GetNodeById(unsigned int nId); /** * Method that returns the closest node to the givel voxel * The closes node is the one whose path (skeleton) to the father has the closest point to the given point. * @param voxel_x x componente of the voxel * @param voxel_y y componente of the voxel * @param voxel_z z componente of the voxel * @param distance return the distance to the closest node * @return the closest node to the given voxel */ Node* GetClosestBranchNodeToPoint(float point_x, float point_y, float point_z, float &distance); /** * Method that returns the closest node to the position given by parameter * @param position is the position to be compares with * @param distance is the minimum distance found * return the closest node to the position given by parameter */ Node* GetClosestNodeToPoint(Vec3 position, double& distance); /** * Method that return the closest distance of the node skeleton * @param voxel_x x componente of the voxel * @param voxel_y y componente of the voxel * @param voxel_z z componente of the voxel * @return the closest distance of the node skeleton */ float GetBranchDistanceToPoint(int voxel_x, int voxel_y, int voxel_z); /** * Method that returns if the tree has a minimum of levels * @return true if the tree has the minimum of levels, false otherwise */ bool HasMinimumLevels(int levels); /*! * This method returns true if the node is a leaf * @return */ bool IsLeaf() const; /*! * This method returns true if the node is marked * @return */ bool IsMarked() const; /** * Method that tells if a node has marked children * @return true if the node has marked children, false otherwise */ bool HasMarkedChildren() const; /** * Method that returns if a node is in the descending set of nodes * @return true is the given node is in the descending set of nodes, false otherwise */ bool HasNode(Node* node_searched) const; /** * Method that return if a node is in the tree * @param id_node_searched id of the searched node * @return true is the node is in the tree, false otherwise */ bool HasNodeId(unsigned int id_node_searched) const; /** * Method that returns if a voxel is influenced by a node, i.e. if the distance * to the closest voxel of the edge is smaller than the radius on the closest voxel. * @param x,y,z are the voxel positions in coordinates x, y, and z respectively. * @return true is the voxel is influenced, false otherwise. */ bool IsPointInfluencedByNode(float point_x, float point_y, float point_z) const; /** * Method that returns the list of nodes that influence the given point * @param point_x, point_y, point_z are the position of the point in real coordinates x, y, and z respectively. * @param vec_nodes_influence vector to save the nodes */ void GetBrancheNodesInfluencingPoint(float point_x, float point_y, float point_z, vec_nodes& vec_nodes_influence); /** * Method that adds to a vector all the children with a maximum depth Q from actual node. * If Q = 0, no nodes are added. * @param Q the depth to find the children * @param fathers vector to return the children */ void GetChildrenUptoDepth(unsigned int Q, vec_nodes& fathers); /** * This method compares the subtrees that start in this node and one given by parameter. * @param nodeB is the stating node of the subtree to be compared with * @param Q is the depth to select "fathers" nodes * @param F is the depth to select "family" nodes * @param commonA vector to save the common nodes for this subtree * @param commonA vector to save the common nodes for the subtree given by parameter * @param nonCommonA vector to save the non-common nodes for this subtree * @param nonCommonB vector to save the non-common nodes for the subtree given by parameter */ 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); /** * Method that returns the pair of branches (one node for each tree) that has the minimum distance after root overlapping. * Valid branches for the actual node are the one level branches those the branches up to this child (height = 2). * Root overlapping means the translation of branch so that root overlap. * @pre: The actual branch is not marked. * @param nodeB is the subtree root node to be compared with * @return the pair of branches (one node for each tree) that has the minimum distance after root overlapping */ std::pair< std::pair, double> GetBestBranches_ActualTranslatedOneLevelBranches_To_AllPossibleBranches(Node* nodeB); /** * Method that returns all the distances to all the non-marked branches, i.e., the end node of the branch is non-marked, * inside a multimap (key, value) structure where the value elementent corresponds to the compared branches. * @param node_gradfather is the grandfather node to be compared * @param Q is the depth to select "fathers" * @param F is the depth to select "family" nodes * @return multimap where the key is the distance between branches and the value is the pair of compared branches end-nodes. */ std::multimap< double, std::pair > CalculateDistanceToAllBranches_FatherAndFamily(Node* node_gradfather, unsigned int Q, unsigned int F); /** * Method is executed by grandfather nodes. It returns the closest pair of nodes, * one must be my child and the other one of the relatives given node. * The closest pair is the one that has the minimal distance between the children and the families. * The distance is the sum of fathers distances and family distances. * @param nodeB is the node to be compared with * @return the closest pair of nodes, one must be my child and the other on of the relatives given node. */ //std::pair< std::pair, double> GetClosestBranch_FatherAndFamily(Node* nodeB); /** * Method that returns the closest relative node, all the nodes but this, whose position is the closest to the point given by parameter * @param position is the point to be compared with * @param distance is the minimum distance found in the relatives * @return the closest relative node, all the nodes but this, whose position is the closest to the point given by parameter */ Node* GetClosestRelativeToPoint(Vec3 position, double& distance); Node* GetClosestRelativeToBranch(Edge* branch, Vec3 vector_translation, double& distance); /** * Method that returns the closest node to the given by node. * Closest involve the distance between fathers and family. * @param node_grandfather is the father of the "node_father" which can be different from the direct father. * this is the case when the father distance is the algorithm, given by Q, is greater than 1. * @param node_father is the node to be compared with * @param F is the depth to select "family" nodes * @param vector_translation is the translation vector to translate the "father" branch * @param distance is the distance to be returned by parameter * @return the closest node to the given by node. */ Node* GetClosestRelativeFatherAndFamily(Node* node_grandfather, Node* node_father, unsigned int F, Vec3 vector_translation, double& distance); Node* GetClosestBranchToTranslatedBranch(Edge* branch, Vec3 vector_translation, double& distance, Edge* edgeSuperior); /** * This method returns the closest father and family, in this subtree, that is the closest to the subtree given by parameter * The returned node represents the father. * @param node_grandfather is the father of the "node_father" which can be different from the direct father. * this is the case when the father distance is the algorithm, given by Q, is greater than 1. * @param node_father is the node father to be compared with * @param F is the depth to select "family" nodes * @param vector_translation is the translation vector to translation the father given by parameter * @param distance is the closest distances to be returned by parameter * @param edgeSuperior is a superior edge where the actual edge must be attached * @returns the closest father and family, in this subtree, that is the closest to the subtree given by parameter */ Node* GetClosestFatherAndFamilyToTranslatedFatherAndFamily(Node* node_grandfather, Node* node_father, unsigned int F, Vec3 vector_translation, double& distance, Edge* edgeSuperior); /** * Method that return the closest ascending node that is marked as common. * A common node may common if: * (1) it is marked or (2) one of their descendants is marked * return the closest ascending common node. NULL is there is no such node. */ const Node* GetClosestCommonAscendingNode() const; /** * 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. * @param nodeB is the searched node * @return true is the node was found, false otherwise */ bool MarkNodesUntilNode(Node* nodeB); Node* GetNextNodeInPathToNode(Node* node_searched); /** * Method that returns the path from the actual node to the searched node * @param node_end is the searched node * @param vector_pathNodes vector_pathNodesis the vector to return the path */ void GetPathToNode(Node* node_end, vec_nodes& vector_pathNodes); void MarkPathFromNodeToNode(Node* node_begin, Node* node_end); void MarkPathNodesToNode(Node* node_end); /** * Method that returns a root with a copy of this node as single child * @return a root with a copy of this node as single child */ Node* GetDetachedRootCopy(); /*! * This method return true if two nodes are equals * @param nodeTreeB * @return */ bool CompareNodes(Node* nodeTreeB); /** * Method that returns a new composed edge from this node to the searched node. * @param idNode is the searched id node * @return the edge to the searched node. Null if the node is not found. */ Edge* GetComposedEdge(unsigned int idNode); /** * Method that composes the actual edge with the edge given by parameter * @param nEdge edge to be composed with * @return final composed edge */ Edge* AddChildEdgeInformation(Edge* nEdge); /** * Method that returns a "composed edge" up to the ancestor * @pre the ancesto node must be a real ancestor * @param node_ancestor is the ancestor node to with the edge must be composed * @param edge is the actual composed edge. NULL if the fist iteration * @return the composed edge up to the ancesto node */ Edge* GetEdgeToAncestor(Node* node_ancestor, Edge* edge); /** * Method that concatenates the actual edge to a superior edge given by parameter. * As the given edge is superior then the actual edge must be concatenate at the end of the superior edge, * this means that superiorEdge.target must equal to the actualEdge.source. * @param superiorEdge is the superior edge where the actual edge must be added * @return - a copy of the actual edge if the superior edge is NULL * - if superiorEdge.target == actualEdge.source the the superior edge with the actual edge concatenated * - NULL otherwise (superiorEdge.target != actualEdge.source) */ Edge* ConcatenateEdgeToSuperiorEdge(Edge* superiorEdge); /*! * This method returns true if the accumulation of a set of nodes are equals * (in tolerance) to the compared node (this). This method tries to find * edges in the case of edge losses. * When this method returns true, NodeB pointer is replaced to the node (target) * found by accumulation (See the report to understand what this means). * @param nodeB - Current node to compare * @param nodeBAcc - Accumulator Node (Optional) * @return */ bool FindSimilarEdgeByAccumulation(Node* nodeB, Node* nodeBAcc = NULL); /*! * This method returns true if there is a marked node along the hierarchy * @param result * @return */ bool FindMarked(Node* result); /*! * This method marks the path between two nodes and returns true if a path * has found. * @param nodeB * @return */ bool MarkPath(Node* nodeB); /*! * This method returns the cost between two nodes. * @param nodeB * @return */ unsigned int GetCost(Node* nodeB); //Setters and Modifiers /* * Method that sets the id of the node * @param nM_id is the new id */ void SetId(unsigned int nM_id); /*! * This method adds a node in the children vector * @param node is the node to be added */ void AddChild(Node* node); /*! * This method sets the children vector * @param children */ void SetChildren(std::vector& children); /** * Method that sets the father * @param nFather is the father */ void SetFather(Node* nFather); /*! * This method sets an edge between the current node and its parent * @param edge */ void SetEdge(Edge* edge); /*! * This method sets the coordinates of the node * @param coords */ void SetCoords(const Vec3& coords); /** * Method that sets the level of the node * @param level is the level of the node */ void SetLevel(const int& level); /** * Method that deleted a node and all his children, from the tree * @return true if the node was deleted (found), false otherwise */ bool DeleteNodeById(unsigned int nId); /*! * This method merges the nodeB into this * @param nodeB */ void MergeNodes(Node* nodeB); /*! * This method marks a node */ void Mark(); /*! * This method unmarks a node */ void UnMark(); /*! * This method update all levels along the hierarchy * @param level */ void UpdateLevels(unsigned int level = 0); /** * Method that prints the tree up to a given level * @param level where the print must finish */ void printUpToLevel(int level); void printNodeAndChildrenIds( ); void printChildrenIds( ); /** * Method that creates the quaternions of the airways up the maxLevel * @param level is the level where the extraction must end * @param requiredLevel is the required level until the extraction must be done * @pre level >= 2 */ void createQuaternionsUpToLevel(int level, int requiredLevel); /** * Method that returns the closest pair node, based on their distance, having the first node of the pair as non-marked. * The pair is found on the given a multimap of distances and pair of nodes. It is supposed that the multimap sorts * the elements by its key. In this case the key corresponds to the distance. * @param map_dist_pairNodes is the map containing the distances (keys) and the pair of nodes (value) * @return the closest pair nodes, based on their distance, given a multimap of distances and pair of nodes. If * no pair was found with the pair node nonmaked, a null pair is returned. * Actually the method returns the pair and its distances in a pair */ std::pair > GetPairWithClosestDistance_FirstNodeNonMarked(std::multimap map_dist_pairNodes); /** * Add the statistics of number of bifurcations in the tree to the array given by parameter * @param p array to save the statistics */ void getStasticsBifurcations(int* p); //Operator Overloads Node& operator=(Node& node); const Node& operator=(const Node& node); bool operator ==(const Node& node); bool operator !=(const Node& node); bool operator <(const Node& node); bool operator >(const Node& node); protected: /** * Node id */ unsigned int m_id; /** * Children nodes vector */ vec_nodes m_children; /** * Father node */ Node* father; /** * Edge between the current node and its parent. * The source of the edge corresponds to the parent en the target to the child, * in this case to "this" node. */ Edge* m_edge; /** * Spatial 3D position of the node in real coordinates of the image */ Vec3 m_coords; /** * Node level */ int m_level; /** * Node mark */ bool m_mark; }; } /* namespace airways */ #endif /* AIRWAYSNODE_H_ */