4 * Created on: May 12, 2014
5 * Author: Diego Cáceres
7 * Modified by: Alfredo Morales Pinzón
12 #include "airwaysNode.h"
17 Node::Node() : m_id(0), m_children(), m_edge(NULL), m_coords(0, 0, 0), m_level(-1), m_mark(false)
21 Node::Node(const Vec3& coord) : m_id(0), m_children(), m_edge(NULL), m_level(-1), m_mark(false)
23 this->m_coords = coord;
27 Node::Node(Node* node) : m_id(0), m_children(), m_mark(false)
29 this->m_coords = node->m_coords;
30 this->m_level = node->m_level;
31 this->m_edge = new Edge(node->m_edge);
40 const std::vector<Node*>& Node::GetChildren() const
42 return this->m_children;
45 const unsigned int Node::GetId() const
50 const Vec3& Node::GetCoords() const
52 return this->m_coords;
55 Edge* Node::GetEdge() const
60 Node* Node::GetFather() const
65 unsigned int Node::GetLevel() const
70 int Node::GetDepthById(unsigned int idNode) const
72 if( this->m_id == idNode)
75 vec_nodes::const_iterator it = this->m_children.begin();
76 for( ; it != this->m_children.end(); ++it)
78 if((*it)->HasNodeId(idNode))
79 return 1 + (*it)->GetDepthById(idNode);
82 std::cout << "GetDepthById - The idNode: " << idNode << "does not exist" << std::endl;
87 unsigned int Node::GetWeight() const
92 unsigned int weight = 0;
94 vec_nodes::const_iterator it = this->m_children.begin();
95 for( ; it != this->m_children.end(); ++it)
96 weight += (*it)->GetWeight();
101 unsigned int Node::GetHeight() const
103 unsigned int heightChildren = 0;
105 vec_nodes::const_iterator it=this->m_children.begin();
106 for( ; it != this->m_children.end(); ++it)
108 unsigned int actualHeight = (*it)->GetHeight();
109 if(actualHeight > heightChildren)
110 heightChildren = actualHeight;
113 // Return my heigh plus my children height
114 return 1 + heightChildren;
117 unsigned int Node::GetNumberOfChildren() const
119 return this->m_children.size();
122 unsigned int Node::GetNumberOfNonMarkedChildren( unsigned int depth ) const
126 unsigned int nonMarked = 0;
128 for(vec_nodes::const_iterator it = this->m_children.begin(); it != this->m_children.end(); ++it)
132 nonMarked += (*it)->GetNumberOfNonMarkedChildren( depth - 1 );
139 unsigned int Node::GetNumberOfLeafs() const
144 unsigned int leafs = 0;
145 vec_nodes::const_iterator it = this->m_children.begin();
146 for( ; it != this->m_children.end(); ++it)
147 leafs += (*it)->GetNumberOfLeafs();
152 Node* Node::GetNodeById(unsigned int nId)
158 Node* node_searched = NULL;
160 // Search in the children
161 vec_nodes::iterator it_children = m_children.begin();
162 for( ; it_children != m_children.end() && node_searched == NULL; ++it_children)
163 node_searched = (*it_children)->GetNodeById(nId);
165 return node_searched;
168 Node* Node::GetClosestBranchNodeToPoint(float point_x, float point_y, float point_z, float &distance)
170 // Get the actual distance
171 distance = GetBranchDistanceToPoint(point_x, point_y, point_z);
173 // Make as closest "this" node
174 Node* node_closest = this;
176 // Iterate over the children
177 vec_nodes::iterator it_children = m_children.begin();
178 for( ; it_children != m_children.end(); ++it_children)
180 // Get actual child distance
181 float distance_actual = 0;
182 Node* bestNodeChild = (*it_children)->GetClosestBranchNodeToPoint(point_x, point_y, point_z, distance_actual);
184 // If the child distance is smaller then switch
185 if(distance_actual < distance)
187 node_closest = bestNodeChild;
188 distance = distance_actual;
195 Node* Node::GetClosestNodeToPoint(Vec3 position, double& distance)
197 // Calculate actual distance to point
198 Vec3 vector_diff = position - this->m_coords;
199 distance = vector_diff.Norm();
205 double actualDistance = -1;
206 Node* node_Best = this;
207 Node* node_Actual = NULL;
209 // Check the children and get the best
210 for(vec_nodes::const_iterator it = this->m_children.begin(); it != this->m_children.end(); ++it)
212 node_Actual = (*it)->GetClosestNodeToPoint(position, actualDistance);
214 if(actualDistance < distance)
216 node_Best = node_Actual;
217 distance = actualDistance;
221 if(actualDistance == -1)
222 std::cout << "GetClosestNodeToPoint NOT FOUND!" << std::endl;
227 float Node::GetBranchDistanceToPoint(int voxel_x, int voxel_y, int voxel_z)
229 Vec3 voxel(voxel_x,voxel_y, voxel_z);
230 if(this->m_edge != NULL)
231 return this->m_edge->GetSmallestDistanceToPoint(voxel);
234 Vec3 vector_diff = this->m_coords - voxel;
235 return vector_diff.Norm();
239 bool Node::HasMinimumLevels(int levels)
244 bool minimum = false;
246 vec_nodes::iterator it=this->m_children.begin();
247 for( ; it != this->m_children.end() && !minimum; ++it)
248 if((*it)->HasMinimumLevels(levels-1))
254 bool Node::IsLeaf() const
256 return this->m_children.empty();
259 bool Node::IsMarked() const
264 bool Node::HasMarkedChildren() const
269 // Check the children
270 vec_nodes::const_iterator it = this->m_children.begin();
271 for( ; it != this->m_children.end(); ++it)
272 if( (*it)->IsMarked() || (*it)->HasMarkedChildren())
278 bool Node::HasNode(Node* node_searched) const
280 if(this->m_id == node_searched->m_id)
285 vec_nodes::const_iterator it = this->m_children.begin();
286 for( ; it != this->m_children.end() && !found; ++it)
287 if( (*it)->HasNode(node_searched) )
293 bool Node::HasNodeId(unsigned int id_node_searched) const
295 // If this is the node then return true
296 if(this->m_id == id_node_searched)
299 // Search in the children
301 vec_nodes::const_iterator it = this->m_children.begin();
302 for( ; it != this->m_children.end() && !found; ++it)
303 if( (*it)->HasNodeId(id_node_searched) )
309 bool Node::IsPointInfluencedByNode(float point_x, float point_y, float point_z) const
312 return m_edge->IsPointInfluencedByEdge(point_x, point_y, point_z);
317 void Node::GetBrancheNodesInfluencingPoint(float point_x, float point_y, float point_z, vec_nodes& vec_nodes_influence)
319 if(this->IsPointInfluencedByNode(point_x, point_y, point_z))
320 vec_nodes_influence.push_back(this);
322 vec_nodes::const_iterator it = this->m_children.begin();
323 for( ; it != this->m_children.end(); ++it)
324 (*it)->GetBrancheNodesInfluencingPoint(point_x, point_y, point_z, vec_nodes_influence);
327 void Node::GetChildrenUptoDepth(unsigned int Q, vec_nodes& fathers)
331 vec_nodes::const_iterator it = this->m_children.begin();
332 for( ; it != this->m_children.end(); ++it)
334 fathers.push_back((*it));
335 (*it)->GetChildrenUptoDepth(Q-1, fathers);
338 fathers.push_back(this);
340 // If the depth is greater that 1 then add the children of this node
343 vec_nodes::const_iterator it = this->m_children.begin();
344 for( ; it != this->m_children.end(); ++it)
345 (*it)->GetChildrenUptoDepth(Q-1, fathers);
350 void Node::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)
352 //std::cout << "---------------------------------------------------------" << std::endl;
353 //std::cout << "Comparing [A,B]: " << this->m_id << "," << nodeB->m_id << std::endl;
356 double distanceAtoB = 0;
357 double distanceBtoA = 0;
358 Node* node_bestA = NULL;
359 Node* node_bestB = NULL;
362 // The algorithm is recursive it is implemented the node class. The idea is to overlap the initial nodes of the subtrees
363 // and find the best branch correspondence for the first level of the trees.
364 // Hypothesis: It is supposed that the roots of the trees are common, so the algorithm does not run in the root nodes
365 // 1. Translate one of the subtree so that the initial nodes overlap.
366 // 2. While one of the trees has non-marked child
367 // 2.1 Compare each child to all the branches is the other tree.
368 // 2.2 Select the pair, child and branch in the other tree, that has the lowest distance function.
369 // 2.3 Add the pair and the distance to the final result.
370 // 2.4 Mark the nodes
371 // 2.5 Find and mark the omitted nodes in the similar branch. If the selected branch has more that 2 nodes it means that intermediary nodes do not have correspondence.
372 // 2.6 Run the process (First step) using the found pair of nodes.
374 //1. Translate one of the subtree so that the initial nodes overlap.
375 // The translation must be applied later
377 Vec3 vector_trans_B_to_A = this->m_coords - nodeB->m_coords;
379 // ------------------------
380 // ------------------------
381 // Making the matching faster
382 std::multimap<double, pair_nodes> map_dist_pairNodes_A_to_B = this->CalculateDistanceToAllBranches_FatherAndFamily(nodeB, Q, F);
383 std::multimap<double, pair_nodes> map_dist_pairNodes_B_to_A = nodeB->CalculateDistanceToAllBranches_FatherAndFamily(this, Q, F);
385 // ------------------------
386 // ------------------------
388 while( this->GetNumberOfNonMarkedChildren( Q ) > 0 && nodeB->GetNumberOfNonMarkedChildren( Q ) > 0 )
390 // 2.1 Compare each child to all the branches is the other tree.
392 // 2.1.1 Get best translated branch from A to B
393 //std::pair<pair_nodes,double> pair_A_to_B = this->GetClosestBranch_FatherAndFamily(nodeB);
394 // 2.1.2 Get best translated branch from B to A
395 //std::pair<pair_nodes,double> pair_B_to_A = nodeB->GetClosestBranch_FatherAndFamily(this);
397 // ------------------------
398 // ------------------------
399 // Making the matching faster
400 // Get the next best pair
401 std::pair<double,pair_nodes> pair_A_to_B = GetPairWithClosestDistance_FirstNodeNonMarked(map_dist_pairNodes_A_to_B);
402 std::pair<double,pair_nodes> pair_B_to_A = GetPairWithClosestDistance_FirstNodeNonMarked(map_dist_pairNodes_B_to_A);
404 if( ! pair_A_to_B.second.first || ! pair_A_to_B.second.second )
405 std::cout << "There is no closest-non-marked branch!" << std::endl;
407 distanceAtoB = pair_A_to_B.first;
408 distanceBtoA = pair_B_to_A.first;
410 //std::map<double, pair_nodes> map_dist_pairNodes_A_to_B = this->CalculateDistanceToAllBranches_FatherAndFamily(nodeB);
411 //std::map<double, pair_nodes> map_dist_pairNodes_B_to_A = nodeB->CalculateDistanceToAllBranches_FatherAndFamily(this);
412 // ------------------------
413 // ------------------------
416 // Assign the distances
417 //distanceAtoB = pair_A_to_B.second;
418 //distanceBtoA = pair_B_to_A.second;
420 // 2.2 Select the pair, child and branch in the other tree, that has the lowest distance function.
421 if(distanceAtoB < distanceBtoA)
423 //node_bestA = pair_A_to_B.first.first;
424 //node_bestB = pair_A_to_B.first.second;
425 node_bestA = pair_A_to_B.second.first;
426 node_bestB = pair_A_to_B.second.second;
428 //std::cout << "Best Pair [A',B]: " << node_bestA->m_id << "," << node_bestB->m_id << std::endl;
430 // 2.2.1 Check that there are no topological problems before adding the pair
431 // Search all the nodes in the tree A linked to the found best node in B
432 vec_nodes nodesA_linkedToBestB = map_B_to_A[node_bestB->m_id];
434 // Look for topological problems
435 bool topo_problem = false;
436 for(vec_nodes::iterator it = nodesA_linkedToBestB.begin(); it != nodesA_linkedToBestB.end() && !topo_problem; ++it)
438 if( ! ( (*it)->HasNode( node_bestA ) || node_bestA->HasNode( (*it) ) ) )
441 //std::cout << "Topological problem adding node:" << node_bestA->m_id << std::endl;
447 // 2.3 Add the pair and the distance to the final result.
448 commonA.push_back(node_bestA);
449 commonB.push_back(node_bestB);
450 map_A_to_B[node_bestA->m_id].push_back(node_bestB);
451 map_B_to_A[node_bestB->m_id].push_back(node_bestA);
454 pair_nodes pair_edgeA(this, node_bestA);
455 pair_nodes pair_edgeB(nodeB, node_bestB);
456 std::pair< pair_nodes, pair_nodes > pair_edge(pair_edgeA, pair_edgeB);
457 vector_pair_edges.push_back(pair_edge);
460 // 2.4 Mark the nodes
464 // 2.5 Find and mark the omitted nodes in the similar branch. If the selected branch has more that 2 nodes it means that intermediary nodes do not have correspondence.
465 Node* node_nextA = this->GetNextNodeInPathToNode(node_bestA);
466 //bool markedA = node_nextA->MarkNodesUntilNode(node_bestA);
468 // std::cout << "NodeA not found for marking [A]:" << node_bestA->m_id << std::endl;
470 Node* node_nextB = nodeB->GetNextNodeInPathToNode(node_bestB);
471 //bool markedB = node_nextB->MarkNodesUntilNode(node_bestB);
473 // std::cout << "NodeB not found for marking [B]:" << node_bestB->m_id << std::endl;
475 // 2.6 Run the process (First step) using the found pair of nodes.
476 node_bestA->CompareSubTreesOrkiszMorales(node_bestB, Q, F, commonA, commonB, nonCommonA, nonCommonB, map_A_to_B, map_B_to_A, vector_pair_edges);
480 // 2.4 Mark the wrong node
482 nonCommonA.push_back(node_bestA);
487 //node_bestA = pair_B_to_A.first.second;
488 //node_bestB = pair_B_to_A.first.first;
489 node_bestA = pair_B_to_A.second.second;
490 node_bestB = pair_B_to_A.second.first;
492 //std::cout << "Best Pair [A,B']: " << node_bestA->m_id << "," << node_bestB->m_id << std::endl;
494 // 2.29 Check that there are no topological problems before adding the pair
495 // 2.291 Search all the nodes in the A tree linked to the found best node in B
496 vec_nodes nodesB_linkedToBestA = map_A_to_B[node_bestA->m_id];
498 // 2.292 Look for topological problems
499 bool topo_problem = false;
500 for(vec_nodes::iterator it = nodesB_linkedToBestA.begin(); it != nodesB_linkedToBestA.end() && !topo_problem; ++it)
502 if( ! ( (*it)->HasNode(node_bestB) || node_bestB->HasNode( (*it) ) ) )
505 //std::cout << "Topological problem adding node:" << node_bestB->m_id << std::endl;
511 // 2.3 Add the pair and the distance to the final result.
512 commonA.push_back(node_bestA);
513 commonB.push_back(node_bestB);
514 map_A_to_B[node_bestA->m_id].push_back(node_bestB);
515 map_B_to_A[node_bestB->m_id].push_back(node_bestA);
518 pair_nodes pair_edgeA(this, node_bestA);
519 pair_nodes pair_edgeB(nodeB, node_bestB);
520 std::pair< pair_nodes, pair_nodes > pair_edge(pair_edgeA, pair_edgeB);
521 vector_pair_edges.push_back(pair_edge);
523 // 2.4 Mark the nodes
527 // 2.5 Find and mark the omitted nodes in the similar branch. If the selected branch has more that 2 nodes it means that intermediary nodes do not have correspondence.
528 Node* node_nextA = this->GetNextNodeInPathToNode(node_bestA);
529 //bool markedA = node_nextA->MarkNodesUntilNode(node_bestA);
531 // std::cout << "NodeA not found for marking [A]:" << node_bestA->m_id << std::endl;
533 Node* node_nextB = nodeB->GetNextNodeInPathToNode(node_bestB);
534 //bool markedB = node_nextB->MarkNodesUntilNode(node_bestB);
536 // std::cout << "NodeB not found for marking [B]:" << node_bestB->m_id << std::endl;
538 // 2.6 Run the process (First step) using the found pair of nodes.
539 //node_bestB->CompareSubTreesOrkiszMorales(node_bestA, commonB, commonA, nonCommonB, nonCommonA, map_B_to_A, map_A_to_B, vector_pair_edges);
540 node_bestA->CompareSubTreesOrkiszMorales(node_bestB, Q, F, commonA, commonB, nonCommonA, nonCommonB, map_A_to_B, map_B_to_A, vector_pair_edges);
544 // 2.4 Mark the wrong node
546 nonCommonB.push_back(node_bestB);
551 //std::cout << "OUT Comparing [A,B]: " << this->m_id << "," << nodeB->m_id << std::endl;
552 //std::cout << "---------------------------------------------------------" << std::endl;
555 std::pair< std::pair<Node*, Node*>, double> Node::GetBestBranches_ActualTranslatedOneLevelBranches_To_AllPossibleBranches(Node* nodeB)
558 double distance = -1;
559 double distance_bestFinal = -1;
560 Node* node_A_bestFinal = NULL;
561 Node* node_B_bestFinal = NULL;
564 // Get the translation vector for root ovelapping
565 Vec3 vector_trans_A_to_B = nodeB->m_coords - this->m_coords;
567 // Iterate over my children
568 for(vec_nodes::iterator it_A = this->m_children.begin(); it_A != this->m_children.end(); ++it_A)
570 if( !(*it_A)->IsMarked() )
572 // Get the position of the actual child of this node
573 Vec3 position_actual = (*it_A)->m_coords;
575 // Translate the position
576 Vec3 position_translated = position_actual + vector_trans_A_to_B;
578 // Find the "closest" node in the subtree nodeB using a distance function
579 // a. Distance to ending point
580 //Node* bestNode_actual = nodeB->GetClosestRelativeToPoint(position_translated, distance);
581 // b. Distance point to point
582 Node* bestNode_actual = nodeB->GetClosestRelativeToBranch( (*it_A)->m_edge, vector_trans_A_to_B, distance);
587 node_A_bestFinal = (*it_A);
588 node_B_bestFinal = bestNode_actual;
589 distance_bestFinal = distance;
591 else if(distance < distance_bestFinal)
593 node_A_bestFinal = (*it_A);
594 node_B_bestFinal = bestNode_actual;
595 distance_bestFinal = distance;
601 std::cout << "GetBestTranslatedBranchFromOtherTree NOT FOUND!" << std::endl;
603 pair_nodes pair_best(node_A_bestFinal, node_B_bestFinal);
604 std::pair<pair_nodes,double> best_pair_score(pair_best, distance_bestFinal);
605 return best_pair_score;
608 std::multimap< double, std::pair<Node*, Node*> > Node::CalculateDistanceToAllBranches_FatherAndFamily(Node* node_gradfather, unsigned int Q, unsigned int F)
610 // "this" is a grandfather node
612 std::multimap< double, pair_nodes > map_dist_pairNodeNode;
613 double distance_actual = -1;
615 // Get the translation vector for root overlapping
616 Vec3 vector_trans_A_to_B_grandfathers = node_gradfather->m_coords - this->m_coords;
618 // Get all the possible "fathers" based on Q
620 this->GetChildrenUptoDepth(Q, fathers);
621 //fathers = this->m_children;
623 // Iterate over my children which actually are fathers
625 //vec_nodes::iterator it_father = this->m_children.begin();
626 vec_nodes::iterator it_father = fathers.begin();
627 //for( ; it_father != this->m_children.end(); ++it_father)
628 for( ; it_father != fathers.end(); ++it_father)
630 if( ! (*it_father)->IsMarked() )
633 Node* node_actualBest = node_gradfather->GetClosestRelativeFatherAndFamily( this, (*it_father), F, vector_trans_A_to_B_grandfathers, distance_actual);
635 pair_nodes pair_actual((*it_father), node_actualBest);
637 std::pair<double,pair_nodes> actual_dist_pair(distance_actual,pair_actual);
638 map_dist_pairNodeNode.insert(actual_dist_pair);
642 return map_dist_pairNodeNode;
646 /*std::pair< std::pair<Node*, Node*>, double> Node::GetClosestBranch_FatherAndFamily(Node* node_gradfather)
648 // "this" is a grandfather node
650 double distance_actual = -1;
651 double distance_bestFinal = -1;
652 Node* node_A_bestFinal = NULL;
653 Node* node_B_bestFinal = NULL;
656 // Get the translation vector for root overlapping
657 Vec3 vector_trans_A_to_B_grandfathers = node_gradfather->m_coords - this->m_coords;
659 // Iterate over my children which actually are fathers
660 vec_nodes::iterator it_father = this->m_children.begin();
661 for( ; it_father != this->m_children.end(); ++it_father)
663 if( !(*it_father)->IsMarked() )
665 // Get the position of the actual child of this node
666 //Vec3 position_actualFather = (*it_father)->m_coords;
668 // Find the "closest" node in the subtree nodeB using a distance function
669 // a. Distance to ending point
670 // Translate the position
671 //Vec3 position_translated = position_actualFather + vector_trans_A_to_B_grandfathers;
672 //Node* bestNode_actual = nodeB->GetClosestRelativeToPoint(position_translated, distance);
673 // b. Distance point to point
674 Node* node_actualBest = node_gradfather->GetClosestRelativeFatherAndFamily( (*it_father), vector_trans_A_to_B_grandfathers, distance_actual);
679 node_A_bestFinal = (*it_father);
680 node_B_bestFinal = node_actualBest;
681 distance_bestFinal = distance_actual;
683 else if(distance_actual < distance_bestFinal)
685 node_A_bestFinal = (*it_father);
686 node_B_bestFinal = node_actualBest;
687 distance_bestFinal = distance_actual;
693 std::cout << "GetBestTranslatedBranchFromOtherTree NOT FOUND!" << std::endl;
695 pair_nodes pair_best(node_A_bestFinal, node_B_bestFinal);
696 std::pair<pair_nodes,double> best_pair_score(pair_best, distance_bestFinal);
697 return best_pair_score;
701 Node* Node::GetClosestRelativeToPoint(Vec3 position, double& distance)
711 double actualDistance = -1;
712 Node* node_Best = NULL;
713 Node* node_Actual = NULL;
715 for(vec_nodes::const_iterator it = this->m_children.begin(); it != this->m_children.end(); ++it)
717 node_Actual = (*it)->GetClosestNodeToPoint(position, actualDistance);
722 node_Best = node_Actual;
723 distance = actualDistance;
725 else if(actualDistance < distance)
727 node_Best = node_Actual;
728 distance = actualDistance;
733 std::cout << "GetClosestRelativeToPoint NOT FOUND!" << std::endl;
736 std::cout << "GetClosestRelativeToPoint NULL!" << std::endl;
741 Node* Node::GetClosestRelativeToBranch(Edge* branch, Vec3 vector_translation, double& distance)
746 //std::cout << "GetClosestRelativeToBranch -- This node is a leaf" << std::endl;
752 double actualDistance = -1;
753 Node* node_Best = NULL;
754 Node* node_Actual = NULL;
756 for(vec_nodes::const_iterator it = this->m_children.begin(); it != this->m_children.end(); ++it)
758 node_Actual = (*it)->GetClosestBranchToTranslatedBranch(branch,vector_translation, actualDistance, NULL);
763 node_Best = node_Actual;
764 distance = actualDistance;
766 else if(actualDistance < distance)
768 node_Best = node_Actual;
769 distance = actualDistance;
774 std::cout << "GetClosestRelativeToPoint NOT FOUND!" << std::endl;
777 std::cout << "GetClosestRelativeToPoint NULL!" << std::endl;
782 Node* Node::GetClosestRelativeFatherAndFamily(Node* node_grandfather, Node* node_father, unsigned int F, Vec3 vector_translation, double& distance)
784 // "this" is a grandfather node
791 double actualDistance = -1;
792 Node* node_Best = NULL;
793 Node* node_Actual = NULL;
795 // Iterate over the children of this granfather which means
796 // iterate over the fathers
797 vec_nodes::const_iterator it_father = this->m_children.begin();
799 for( ; it_father != this->m_children.end(); ++it_father)
801 node_Actual = (*it_father)->GetClosestFatherAndFamilyToTranslatedFatherAndFamily(node_grandfather, node_father, F, vector_translation, actualDistance, NULL);
806 node_Best = node_Actual;
807 distance = actualDistance;
809 else if(actualDistance < distance)
811 node_Best = node_Actual;
812 distance = actualDistance;
817 std::cout << "GetClosestRelativeToPoint NOT FOUND!" << std::endl;
820 std::cout << "GetClosestRelativeToPoint NULL!" << std::endl;
825 Node* Node::GetClosestBranchToTranslatedBranch(Edge* branch, Vec3 vector_translation, double& distance, Edge* edgeSuperior)
827 Node* node_best = this;
828 Node* node_Actual = NULL;
829 Edge* edge_composed = NULL;
831 // Joint the superior edge with this edge
832 edge_composed = this->ConcatenateEdgeToSuperiorEdge(edgeSuperior);
834 distance = edge_composed->GetDistanceToTranslatedEdge(branch, vector_translation);
835 distance += branch->GetDistanceToTranslatedEdge(edge_composed, -vector_translation);
836 //distance = edge_composed->GetDistanceWeigthedToTranslatedEdge(branch, vector_translation);
837 //distance += branch->GetDistanceWeigthedToTranslatedEdge(edge_composed, -vector_translation);
838 //std::cout << "DW[thisId,toBranchTargetId,Dist]:[" << this->m_id << "," << branch->GetTarget()->GetId() << "," << distance << "]";
840 // Lance the recursion and the the minumum distance and node
841 double distance_actual = -1;
843 // Check the children and get the best
844 for(vec_nodes::iterator it = this->m_children.begin(); it != this->m_children.end(); ++it)
846 Edge* edge_forChild = new Edge(edge_composed);
847 node_Actual = (*it)->GetClosestBranchToTranslatedBranch(branch, vector_translation, distance_actual, edge_forChild);
849 if(distance_actual < distance)
851 node_best = node_Actual;
852 distance = distance_actual;
854 delete(edge_forChild);
860 Node* Node::GetClosestFatherAndFamilyToTranslatedFatherAndFamily(Node* node_grandfather, Node* node_father, unsigned int F, Vec3 vector_translation, double& distance, Edge* edgeSuperior)
862 // "this" is a father node_father
863 Node* node_best = this; // Best matching node is "this" in the beginnig.
864 Node* node_Actual = NULL;
865 Edge* edge_composed = NULL;
867 // Joint the superior edge with this edge
868 edge_composed = this->ConcatenateEdgeToSuperiorEdge(edgeSuperior);
870 //distance = edge_composed->GetDistanceToTranslatedEdge(branch, vector_translation);
871 //distance += branch->GetDistanceToTranslatedEdge(edge_composed, -vector_translation);
873 //Edge* branch_father = node_father->m_edge;
874 Edge* branch_father = node_father->GetEdgeToAncestor(node_grandfather, NULL);
875 if( branch_father == NULL )
876 std::cout << "No branch father" << std::endl;
879 distance = edge_composed->GetDistanceWeigthedToTranslatedEdge(branch_father, vector_translation);
880 distance += branch_father->GetDistanceWeigthedToTranslatedEdge(edge_composed, -vector_translation);
882 // Find the family distance from the node_father family to this family
883 double distance_family_A_to_B = 0;
884 // Add the distances to the family, up to one generation by the moment
885 Vec3 vector_translation_child_A_to_B = this->m_coords - node_father->m_coords; // Vector that align the fathers
887 // Get the family up to depth F
889 node_father->GetChildrenUptoDepth(F, family);
890 //vec_nodes family = node_father->m_children;
892 vec_nodes::iterator it_child_other = family.begin();
893 for(; it_child_other != family.end(); ++it_child_other)
895 // Create the "child" edge
896 Edge* childEdge = (*it_child_other)->GetEdgeToAncestor(node_father, NULL);
897 //Edge* childEdge = (*it_child_other)->m_edge;
899 double distance_child = 0;
902 // The distance of the each point edge to the root point because the fathers are aligned
903 distance_child = childEdge->GetDistanceToPoint(this->m_coords);
907 this->GetClosestRelativeToBranch(childEdge,vector_translation_child_A_to_B, distance_child);
909 distance_family_A_to_B += distance_child;
912 distance += distance_family_A_to_B;
914 // Find the family distance from this family to node_father family
915 double distance_family_B_to_A = 0;
917 // Add the distances to the family, up to one generation by the moment
918 Vec3 vector_translation_child_B_to_A = node_father->m_coords - this->m_coords; // Vector that align the fathers
920 // Get the family up to depth F
922 this->GetChildrenUptoDepth(F, my_family);
923 //vec_nodes my_family = this->m_children;
925 vec_nodes::iterator it_child_my = my_family.begin();
926 for(; it_child_my != my_family.end(); ++it_child_my)
928 // Create the "child" edge
929 Edge* my_childEdge = (*it_child_my)->GetEdgeToAncestor(this, NULL);
930 //Edge* my_childEdge = (*it_child_my)->m_edge;
932 double distance_child = 0;
933 if(node_father->IsLeaf())
935 // The distance of the each point edge to the root point because the fathers are aligned
936 distance_child = my_childEdge->GetDistanceToPoint(node_father->m_coords);
940 node_father->GetClosestRelativeToBranch(my_childEdge, vector_translation_child_B_to_A, distance_child);
942 distance_family_B_to_A += distance_child;
945 distance += distance_family_B_to_A;
947 //std::cout << "DW[thisId,toBranchTargetId,Dist]:[" << this->m_id << "," << branch->GetTarget()->GetId() << "," << distance << "]";
949 // Lance the recursion and the minimum distance and node_father
950 double distance_actual = -1;
952 // Check the children and get the best
953 vec_nodes::iterator it = this->m_children.begin();
954 for( ; it != this->m_children.end(); ++it)
956 Edge* edge_forChild = new Edge(edge_composed);
957 node_Actual = (*it)->GetClosestFatherAndFamilyToTranslatedFatherAndFamily(node_grandfather, node_father, F, vector_translation, distance_actual, edge_forChild);
959 if(distance_actual < distance)
961 node_best = node_Actual;
962 distance = distance_actual;
964 delete(edge_forChild);
970 const Node* Node::GetClosestCommonAscendingNode() const
972 Node* node_closestCommonAscendingNode = NULL;
976 if(this->m_edge->GetSource()->IsMarked() || this->m_edge->GetSource()->HasMarkedChildren())
977 node_closestCommonAscendingNode = this->m_edge->GetSource();
979 return this->m_edge->GetSource()->GetClosestCommonAscendingNode();
982 return node_closestCommonAscendingNode;
985 bool Node::MarkNodesUntilNode(Node* nodeB)
989 if(this->m_id == nodeB->m_id)
993 bool actualFound = false;
994 for(vec_nodes::const_iterator it = this->m_children.begin(); it != this->m_children.end(); ++it)
996 actualFound = (*it)->MarkNodesUntilNode(nodeB);
1005 Node* Node::GetNextNodeInPathToNode(Node* node_searched)
1007 Node* nextNode = NULL;
1008 for(vec_nodes::const_iterator it = this->m_children.begin(); it != this->m_children.end() && !nextNode; ++it)
1010 if( (*it)->HasNode(node_searched) )
1017 void Node::GetPathToNode(Node* node_end, vec_nodes& vector_pathNodes)
1019 if(!this->HasNode(node_end))
1022 vector_pathNodes.push_back(this);
1023 for(vec_nodes::const_iterator it = this->m_children.begin(); it != this->m_children.end(); ++it)
1024 (*it)->GetPathToNode(node_end, vector_pathNodes);
1027 void Node::MarkPathFromNodeToNode(Node* node_begin, Node* node_end)
1029 if(this->m_id == node_begin->m_id)
1031 if(this->HasNode(node_end))
1032 this->MarkPathNodesToNode(node_end);
1035 for(vec_nodes::const_iterator it = this->m_children.begin(); it != this->m_children.end(); ++it)
1036 (*it)->MarkPathFromNodeToNode(node_begin, node_end);
1039 void Node::MarkPathNodesToNode(Node* node_end)
1041 if(this->HasNode(node_end))
1044 for(vec_nodes::const_iterator it = this->m_children.begin(); it != this->m_children.end(); ++it)
1045 (*it)->MarkPathNodesToNode(node_end);
1048 Node* Node::GetDetachedRootCopy()
1050 Node* node_copy = new Node(this);
1052 // Change properties for root node
1053 Node* root_detached = new Node();
1054 root_detached->m_coords = node_copy->m_edge->GetSource()->GetCoords();
1055 root_detached->m_edge = NULL;
1056 vec_nodes vector_new;
1057 vector_new.push_back(node_copy);
1058 root_detached->m_children = vector_new;
1060 // Change properties for the copy node
1061 node_copy->m_edge->SetSource(root_detached);
1063 return root_detached;
1066 bool Node::CompareNodes(Node* nodeTreeB)
1068 if (this == NULL && nodeTreeB == NULL)
1070 else if (this == NULL || nodeTreeB == NULL)
1072 vec_nodes::iterator it = this->m_children.begin();
1073 for (; it != this->m_children.end(); ++it)
1078 vec_nodes::iterator it2 = nodeTreeB->m_children.begin();
1079 for (; it2 != nodeTreeB->m_children.end(); ++it2)
1080 suc = (*it)->CompareNodes(*it2);
1084 if (*this != *nodeTreeB)
1086 this->m_mark = true;
1087 nodeTreeB->m_mark = true;
1091 Edge* Node::GetComposedEdge(unsigned int idNode)
1093 // If this is the node, then a copy edge (to the parent) is returned
1094 if(this->m_id == idNode)
1096 //std::cout << "This is the searched idNode: " << this->m_id << std::endl;
1097 Edge* nEdge = new Edge(this->m_edge);
1102 Edge* composedEdge = NULL;
1104 for(std::vector<Node*>::iterator it = this->m_children.begin(); it != this->m_children.end(); ++it)
1106 // If one of my children has the composed node, then my edge must be added
1107 // and the composed edge is returned
1108 Edge* childEdge = (*it)->GetComposedEdge(idNode);
1111 //std::cout << "My id: " << this->m_id << ", Looking for: " << idNode << std::endl;
1112 return AddChildEdgeInformation(childEdge);
1116 return composedEdge;
1119 Edge* Node::AddChildEdgeInformation(Edge* nEdge)
1121 // If this is the root then the edge to be compose is null, so the same edge must be returned
1122 if(this->m_edge == NULL)
1124 //std::cout << "This is the root node" << std::endl;
1128 // New information vector
1129 vec_pair_posVox_rad vector_newInformation;
1130 vec_pair_posVox_rad actualEdgeInformation = this->m_edge->GetEdgeInfo();
1131 vec_pair_posVox_rad composedInformation = nEdge->GetEdgeInfo();
1133 // Check that last and initial information, from this and the other edge respectively, are equal.
1134 if(actualEdgeInformation[actualEdgeInformation.size()-1].first != composedInformation[0].first)
1137 std::cout << "actualEdgeInformation[0;end]: [" << actualEdgeInformation[0].first << ";" << actualEdgeInformation[actualEdgeInformation.size()-1].first << "], Points: " << actualEdgeInformation.size() << std::endl;
1138 std::cout << "ActualEdge[source;target]: [" << this->m_edge->GetSource()->GetCoords() << "];[" << this->m_edge->GetTarget()->GetCoords() << "]" << std::endl;
1139 std::cout << "-- -- -- " << std::endl;
1140 std::cout << "composedInformation[0;end]: [" << composedInformation[0].first << ";" << composedInformation[composedInformation.size()-1].first << "], Points: " << composedInformation.size() << std::endl;
1141 std::cout << "AddChildEdge[source;target]: [" << nEdge->GetSource()->GetCoords() << "];[" << nEdge->GetTarget()->GetCoords() << "]" << std::endl;
1142 std::cout << "End and initial information are not equal! : " << actualEdgeInformation[actualEdgeInformation.size()-1].first << " , " << composedInformation[0].first << std::endl;
1145 std::cout << "Print composed edge information" << std::endl;
1146 std::cout << "Composed [source, target] " << nEdge->GetSource()->GetCoords() << "];[" << nEdge->GetTarget()->GetCoords() << "]" << std::endl;
1147 std::cout << "Composed information using iterator:" << std::endl;
1149 for(vec_pair_posVox_rad::const_iterator it_composed = nEdge->GetEdgeInfo().begin(); it_composed != nEdge->GetEdgeInfo().end(); ++it_composed)
1150 std::cout << "[" << (*it_composed).first << "], ";
1153 // Change the source
1154 nEdge->SetSource(this->m_edge->GetSource());
1156 // Change properties
1157 nEdge->SetLength(nEdge->GetLength()+this->m_edge->GetLength());
1158 nEdge->SetEDistance(nEdge->GetEDistance()+this->m_edge->GetEDistance());
1160 // Create the new information vector and calculate the new radii attributes
1161 for(vec_pair_posVox_rad::iterator it_actual = actualEdgeInformation.begin(); it_actual != actualEdgeInformation.end(); ++it_actual)
1162 vector_newInformation.push_back((*it_actual));
1164 bool connectionVoxel = true;
1165 for(vec_pair_posVox_rad::iterator it_composed = composedInformation.begin(); it_composed != composedInformation.end(); ++it_composed)
1168 connectionVoxel = false;
1170 vector_newInformation.push_back((*it_composed));
1173 // Set the new information
1174 nEdge->SetSkeletonPairVector(vector_newInformation);
1179 Edge* Node::GetEdgeToAncestor(Node* node_ancestor, Edge* edge)
1181 Edge* edge_composed = NULL;
1185 edge_composed = new Edge(this->m_edge);
1187 edge_composed = edge->ConcatenateToSuperior(new Edge(this->m_edge));
1189 // Check if the father is the ancestor
1190 if(this->m_edge->GetSource()->GetId() == node_ancestor->GetId())
1191 return edge_composed;
1193 return this->m_edge->GetSource()->GetEdgeToAncestor(node_ancestor, edge_composed);
1196 Edge* Node::ConcatenateEdgeToSuperiorEdge(Edge* superiorEdge)
1198 if(superiorEdge == NULL)
1199 return new Edge(this->m_edge);
1201 // Check concatenation condition in the nodes
1202 if(superiorEdge->GetTarget()->GetCoords() != this->m_edge->GetSource()->GetCoords())
1204 std::cout << "Node::ConcatenateEdgeToSuperiorEdge - superiorEdge.target != actualEdge.source. Actual idNode:" << this->m_id << std::endl;
1205 std::cout << "[superiorEdge.target;actualEdge.source]: [" << superiorEdge->GetTarget()->GetCoords() << ";" << this->m_edge->GetSource()->GetCoords() << "]" << std::endl;
1209 // Check concatenation condition in the edge information
1210 vec_pair_posVox_rad vectorInfo_thisEdge = this->m_edge->GetEdgeInfo(); // Actual edge information
1211 vec_pair_posVox_rad vectorInfo_superiorEdge = superiorEdge->GetEdgeInfo(); // Superior edge information
1213 // Check that last superior edge position is equal to first initial actual edge position
1214 if(vectorInfo_superiorEdge[vectorInfo_superiorEdge.size()-1].first != vectorInfo_thisEdge[0].first)
1216 std::cout << "Node::ConcatenateEdgeToSuperiorEdge - superiorEdge.info[end] != actualEdge.info[begin]. Actual idNode:" << this->m_id << std::endl;
1220 // Change the superior edge target, the superior length, and the euclidian distance
1221 superiorEdge->SetTarget(this->m_edge->GetTarget());
1222 superiorEdge->SetLength(superiorEdge->GetLength()+this->m_edge->GetLength()-1);
1223 superiorEdge->SetEDistance(superiorEdge->GetEDistance()+this->m_edge->GetEDistance());
1225 // Add the position information
1226 vec_pair_posVox_rad::iterator it_actualInfo = vectorInfo_thisEdge.begin();
1227 ++it_actualInfo; // Skip the first position because is it shared between both edges
1228 for(; it_actualInfo != vectorInfo_thisEdge.end(); ++it_actualInfo)
1229 vectorInfo_superiorEdge.push_back((*it_actualInfo));
1231 // Set the new information
1232 superiorEdge->SetSkeletonPairVector(vectorInfo_superiorEdge);
1234 return superiorEdge;
1237 bool Node::FindSimilarEdgeByAccumulation(Node* nodeB, Node* nodeBAcc)
1239 bool firstTime = false;
1240 if (nodeBAcc == NULL)
1242 nodeBAcc = new Node();
1243 nodeBAcc->m_edge = new Edge();
1246 nodeBAcc->m_coords = nodeB->m_coords;
1247 nodeBAcc->m_level = this->m_level;
1248 Edge* edgeBAcc = nodeBAcc->m_edge;
1249 Edge* edgeB = nodeB->m_edge;
1250 edgeBAcc->m_angle = edgeB->m_angle;
1251 edgeBAcc->m_eDistance = edgeB->m_eDistance;
1254 edgeBAcc->m_length += edgeB->m_length;
1255 //edgeBAcc->m_aRadius = (edgeB->m_aRadius + edgeBAcc->m_aRadius) / 2.0;
1256 edgeBAcc->m_maxRadius = edgeB->m_maxRadius > edgeBAcc->m_maxRadius ? edgeB->m_maxRadius : edgeBAcc->m_maxRadius;
1257 edgeBAcc->m_minRadius = edgeB->m_minRadius < edgeBAcc->m_minRadius ? edgeB->m_minRadius : edgeBAcc->m_minRadius;
1261 edgeBAcc->m_length = edgeB->m_length;
1262 edgeBAcc->m_aRadius = edgeB->m_aRadius;
1263 edgeBAcc->m_maxRadius = edgeB->m_maxRadius;
1264 edgeBAcc->m_minRadius = edgeB->m_minRadius;
1267 if (*this == *nodeBAcc)
1271 vec_nodes::iterator it = nodeB->m_children.begin();
1272 for (; it != nodeB->m_children.end(); ++it)
1275 if (this->FindSimilarEdgeByAccumulation(aux, nodeBAcc))
1289 bool Node::FindMarked(Node* result)
1291 vec_nodes::iterator it = this->m_children.begin();
1292 for (; it != this->m_children.end(); ++it)
1298 else if ((*it)->FindMarked(result))
1304 bool Node::MarkPath(Node* nodeB)
1306 if (this == NULL || nodeB == NULL)
1308 //comparing addresses
1311 nodeB->m_mark = true;
1314 vec_nodes::iterator it = this->m_children.begin();
1315 for (; it != this->m_children.end(); ++it)
1316 if ((*it)->MarkPath(nodeB))
1318 (*it)->m_mark = true;
1325 unsigned int Node::GetCost(Node* nodeB)
1327 if (this == NULL || nodeB == NULL)
1329 unsigned int maxCost = 0;
1330 if (*this == *nodeB)
1332 vec_nodes::iterator it = this->m_children.begin();
1333 for (; it != this->m_children.end(); ++it)
1335 vec_nodes::iterator it2 = nodeB->m_children.begin();
1336 for (; it2 != nodeB->m_children.end(); ++it2)
1338 unsigned int currentCost = (*it)->GetCost(*it2);
1339 if (currentCost > maxCost)
1340 maxCost = currentCost;
1349 //Setters and Modifiers
1351 void Node::SetId(unsigned int nM_id)
1357 void Node::AddChild(Node* node)
1359 this->m_children.push_back(node);
1362 void Node::SetChildren(std::vector<Node*>& children)
1364 this->m_children = children;
1367 void Node::SetFather(Node* nFather)
1372 void Node::SetEdge(Edge* edge)
1374 this->m_edge = edge;
1377 void Node::SetCoords(const Vec3& coords)
1379 this->m_coords = coords;
1382 void Node::SetLevel(const int& level)
1384 this->m_level = level;
1387 bool Node::DeleteNodeById(unsigned int nId)
1392 bool deleted = false;
1394 vec_nodes::iterator it = this->m_children.begin();
1395 while(it != this->m_children.end() && !deleted)
1397 if((*it)->m_id == nId)
1399 it = m_children.erase(it);
1408 for(vec_nodes::const_iterator it = this->m_children.begin(); it != this->m_children.end() && !deleted; ++it)
1410 deleted = (*it)->DeleteNodeById(nId);
1417 void Node::MergeNodes(Node* nodeB)
1421 this->m_coords = nodeB->m_coords;
1422 Edge* edgeA = this->m_edge;
1423 Edge* edgeB = nodeB->m_edge;
1424 edgeA->m_angle = edgeB->m_angle;
1425 edgeA->m_eDistance = edgeB->m_eDistance;
1426 edgeA->m_length += edgeB->m_length;
1427 edgeA->m_aRadius = (edgeB->m_aRadius + edgeA->m_aRadius) / 2.0;
1428 edgeA->m_maxRadius = edgeB->m_maxRadius > edgeA->m_maxRadius ? edgeB->m_maxRadius : edgeA->m_maxRadius;
1429 edgeA->m_minRadius = edgeB->m_minRadius < edgeA->m_minRadius ? edgeB->m_minRadius : edgeA->m_minRadius;
1430 edgeA->m_vec_pair_posVox_rad.insert(edgeA->m_vec_pair_posVox_rad.end(), edgeB->m_vec_pair_posVox_rad.begin(), edgeB->m_vec_pair_posVox_rad.end());
1435 this->m_mark = true;
1440 this->m_mark = false;
1443 void Node::UpdateLevels(unsigned int level)
1445 this->m_level = level;
1447 vec_nodes::iterator it = this->m_children.begin();
1448 for (; it != this->m_children.end(); ++it)
1449 (*it)->UpdateLevels(level);
1452 void Node::printUpToLevel(int level)
1455 cout << "level" << level << " " << m_coords << " || " << endl;
1459 // Print my children
1460 for (vec_nodes::iterator it = this->m_children.begin(); it != this->m_children.end(); ++it)
1462 (*it)->printUpToLevel(level-1);
1466 void Node::printNodeAndChildrenIds( )
1468 std::cout << "------------------------------------------" << std::endl;
1469 std::cout << "Id: " << this->m_id << std::endl;
1472 for(vec_nodes::const_iterator it = this->m_children.begin(); it != this->m_children.end(); ++it)
1473 std::cout << (*it)->m_id << ";";
1476 for(vec_nodes::const_iterator it = this->m_children.begin(); it != this->m_children.end(); ++it)
1477 (*it)->printNodeAndChildrenIds( );
1480 void Node::printChildrenIds( )
1482 std::cout << "------------------------------------------" << std::endl;
1483 std::cout << "Id: " << this->m_id << std::endl;
1486 for(vec_nodes::const_iterator it = this->m_children.begin(); it != this->m_children.end(); ++it)
1487 std::cout << (*it)->m_id << ";";
1490 void Node::createQuaternionsUpToLevel(int level, int requiredLevel)
1492 //cout << "Level:" << requiredLevel-level <<endl;
1494 if(level >= 2 && this->HasMinimumLevels(2))
1496 // 1. Take the vector to each son (SP - The vector that points from the son to the parent [P-S]).
1497 // 2. For each son take each vector from son to grandson (SG - the vector that points from the son to the grandson [G-S])
1498 // 3. For each combination SP-SG calculate the quaternion
1499 for(vec_nodes::iterator it = this->m_children.begin(); it != this->m_children.end(); ++it)
1501 // Create vector from son to parent (SP = [P - S])
1502 Vec3 sp(this->m_coords - (*it)->m_coords);
1504 // Get the mean radius for the parent-son branch
1505 double radMeanSP=(*it)->m_edge->GetARadius();
1507 // Get distance son to parent
1508 double distSonParent = (*it)->m_edge->GetEDistance();
1510 // Get the vectors from son to each grandson (SG = [G - S] )
1511 for(vec_nodes::iterator itps = (*it)->m_children.begin(); itps != (*it)->m_children.end(); ++itps)
1513 // Build the sg vector and get the quaternion
1514 Vec3 sg((*itps)->m_coords - (*it)->m_coords);
1515 Quaternion q(sp, sg);
1517 // Get distance son to grandson
1518 double distSonGrandson = (*itps)->m_edge->GetEDistance();
1520 // Get the mean radius for the son-grandson branch
1521 double radMeanSG=(*itps)->m_edge->GetARadius();
1523 //cout << "Vectors:" << ps << sg <<endl;
1524 //cout << "Q:" << q << ", Distance=" << (*itps)->m_edge->GetEDistance() << endl << endl;
1526 // Level | PositionSon | SPvector | SGvector | Quaternion | distanceSonParent | distanceSonGrandSon | meanRadiusSP | meanRadiusSG
1527 cout << requiredLevel-level << " " << (*it)->m_coords << " " << sp << " " << sg << " " << q << " " << distSonParent << " " << distSonGrandson << " " << radMeanSP << " " << radMeanSG << endl;
1531 for(vec_nodes::iterator it = this->m_children.begin(); it != this->m_children.end(); ++it)
1533 (*it)->createQuaternionsUpToLevel(level-1, requiredLevel);
1538 std::pair<double, std::pair<Node*, Node*> > Node::GetPairWithClosestDistance_FirstNodeNonMarked(std::multimap<double, pair_nodes> map_dist_pairNodes)
1541 bool pairFound = false;
1542 std::pair<Node*, Node*> pairNodes_null (NULL, NULL);
1543 std::pair<double, std::pair<Node*, Node*> > pair_closest_dist_pairNodes (-1, pairNodes_null);
1545 std::multimap<double, pair_nodes>::iterator it = map_dist_pairNodes.begin();
1547 for( ; it != map_dist_pairNodes.end() && !pairFound; ++it)
1549 if( ! (*it).second.first->IsMarked() )
1551 pair_closest_dist_pairNodes.first=(*it).first;
1552 pair_closest_dist_pairNodes.second=(*it).second;
1557 return pair_closest_dist_pairNodes;
1560 void Node::getStasticsBifurcations(int* p)
1562 int numBif = this->m_children.size();
1563 if(numBif>0 && numBif<=6)
1564 p[numBif-1]=p[numBif-1]+1;
1566 for(vec_nodes::iterator it = this->m_children.begin(); it != this->m_children.end(); ++it)
1568 (*it)->getStasticsBifurcations(p);
1572 //Operator Overloads
1574 Node &Node::operator=(Node & node)
1576 this->m_children = node.m_children;
1577 this->m_edge = node.m_edge;
1578 this->m_coords = node.m_coords;
1579 this->m_level = node.m_level;
1580 this->m_mark = node.m_mark;
1584 const Node&Node::operator=(const Node& node)
1586 this->m_children = node.m_children;
1587 this->m_edge = node.m_edge;
1588 this->m_coords = node.m_coords;
1589 this->m_level = node.m_level;
1590 this->m_mark = node.m_mark;
1594 bool Node::operator ==(const Node& node)
1597 if (this->m_edge == NULL && this->m_edge != NULL)
1599 else if (this->m_edge != NULL && this->m_edge == NULL)
1601 else if (this->m_edge == NULL && this->m_edge == NULL)
1604 comp = ((*this->m_edge) == (*node.m_edge));
1605 bool ret = (/*(this->m_coords == node.m_coords)
1606 && (this->m_children.size() == node.m_children.size())
1607 && */(this->m_level == node.m_level) && comp);
1611 bool Node::operator !=(const Node& node)
1614 if (this->m_edge == NULL && this->m_edge != NULL)
1616 else if (this->m_edge != NULL && this->m_edge == NULL)
1618 else if (this->m_edge == NULL && this->m_edge == NULL)
1621 comp = ((*this->m_edge) == (*node.m_edge));
1622 return (/*(this->m_coords != node.m_coords)
1623 && (this->m_children.size() != node.m_children.size())
1624 && */(this->m_level != node.m_level) && !comp);
1627 bool Node::operator <(const Node& node)
1630 if (this->m_edge == NULL && this->m_edge != NULL)
1632 else if (this->m_edge != NULL && this->m_edge == NULL)
1634 else if (this->m_edge == NULL && this->m_edge == NULL)
1637 comp = ((*this->m_edge) < (*node.m_edge));
1641 bool Node::operator >(const Node& node)
1644 if (this->m_edge == NULL && this->m_edge != NULL)
1646 else if (this->m_edge != NULL && this->m_edge == NULL)
1648 else if (this->m_edge == NULL && this->m_edge == NULL)
1651 comp = ((*this->m_edge) > (*node.m_edge));
1655 } /* namespace airways */