diff options
Diffstat (limited to 'src/Bottleneck_distance/include/gudhi/CGAL/Orthogonal_incremental_neighbor_search.h')
-rw-r--r-- | src/Bottleneck_distance/include/gudhi/CGAL/Orthogonal_incremental_neighbor_search.h | 497 |
1 files changed, 248 insertions, 249 deletions
diff --git a/src/Bottleneck_distance/include/gudhi/CGAL/Orthogonal_incremental_neighbor_search.h b/src/Bottleneck_distance/include/gudhi/CGAL/Orthogonal_incremental_neighbor_search.h index 0e911f41..dbe707ed 100644 --- a/src/Bottleneck_distance/include/gudhi/CGAL/Orthogonal_incremental_neighbor_search.h +++ b/src/Bottleneck_distance/include/gudhi/CGAL/Orthogonal_incremental_neighbor_search.h @@ -32,7 +32,7 @@ namespace CGAL { - template <class SearchTraits, + template <class SearchTraits, class Distance_= typename internal::Spatial_searching_default_distance<SearchTraits>::type, class Splitter_ = Sliding_midpoint<SearchTraits>, class Tree_= Kd_tree<SearchTraits, Splitter_, Tag_true> > @@ -55,7 +55,7 @@ namespace CGAL { template<class T> struct Object_wrapper - { + { T object; Object_wrapper(const T& t):object(t){} const T& operator* () const { return object; } @@ -74,11 +74,11 @@ namespace CGAL { private: typedef std::vector<FT> Distance_vector; - + Distance_vector dists; Distance Orthogonal_distance_instance; - + FT multiplication_factor; Query_item query_point; @@ -95,15 +95,15 @@ namespace CGAL { bool search_nearest; - Priority_higher(bool search_the_nearest_neighbour) - : search_nearest(search_the_nearest_neighbour) - {} + Priority_higher(bool search_the_nearest_neighbour) + : search_nearest(search_the_nearest_neighbour) + {} //highest priority is smallest distance - bool - operator() (Node_with_distance* n1, Node_with_distance* n2) const - { - return (search_nearest) ? (CGAL::cpp11::get<1>(*n1) > CGAL::cpp11::get<1>(*n2)) : (CGAL::cpp11::get<1>(*n2) > CGAL::cpp11::get<1>(*n1)); + bool + operator() (Node_with_distance* n1, Node_with_distance* n2) const + { + return (search_nearest) ? (CGAL::cpp11::get<1>(*n1) > CGAL::cpp11::get<1>(*n2)) : (CGAL::cpp11::get<1>(*n2) > CGAL::cpp11::get<1>(*n1)); } }; @@ -113,43 +113,43 @@ namespace CGAL { bool search_nearest; - Distance_smaller(bool search_the_nearest_neighbour) - : search_nearest(search_the_nearest_neighbour) - {} + Distance_smaller(bool search_the_nearest_neighbour) + : search_nearest(search_the_nearest_neighbour) + {} //highest priority is smallest distance bool operator() (Point_with_transformed_distance* p1, Point_with_transformed_distance* p2) const - { - return (search_nearest) ? (p1->second > p2->second) : (p2->second > p1->second); + { + return (search_nearest) ? (p1->second > p2->second) : (p2->second > p1->second); } }; std::priority_queue<Node_with_distance*, Node_with_distance_vector, - Priority_higher> PriorityQueue; + Priority_higher> PriorityQueue; public: std::priority_queue<Point_with_transformed_distance*, Point_with_transformed_distance_vector, - Distance_smaller> Item_PriorityQueue; + Distance_smaller> Item_PriorityQueue; public: int reference_count; - + // constructor Iterator_implementation(const Tree& tree,const Query_item& q, const Distance& tr, - FT Eps=FT(0.0), bool search_nearest=true) - : traits(tree.traits()),number_of_neighbours_computed(0), number_of_internal_nodes_visited(0), - number_of_leaf_nodes_visited(0), number_of_items_visited(0), - Orthogonal_distance_instance(tr), multiplication_factor(Orthogonal_distance_instance.transformed_distance(FT(1.0)+Eps)), - query_point(q), search_nearest_neighbour(search_nearest), - PriorityQueue(Priority_higher(search_nearest)), Item_PriorityQueue(Distance_smaller(search_nearest)), - reference_count(1) - - + FT Eps=FT(0.0), bool search_nearest=true) + : traits(tree.traits()),number_of_neighbours_computed(0), number_of_internal_nodes_visited(0), + number_of_leaf_nodes_visited(0), number_of_items_visited(0), + Orthogonal_distance_instance(tr), multiplication_factor(Orthogonal_distance_instance.transformed_distance(FT(1.0)+Eps)), + query_point(q), search_nearest_neighbour(search_nearest), + PriorityQueue(Priority_higher(search_nearest)), Item_PriorityQueue(Distance_smaller(search_nearest)), + reference_count(1) + + { if (tree.empty()) return; @@ -160,12 +160,12 @@ namespace CGAL { for(int i=0 ; i<dim ; ++i){ dists[i] = 0; } - - if (search_nearest){ - distance_to_root= - Orthogonal_distance_instance.min_distance_to_rectangle(q, tree.bounding_box(),dists); + + if (search_nearest){ + distance_to_root= + Orthogonal_distance_instance.min_distance_to_rectangle(q, tree.bounding_box(),dists); Node_with_distance *The_Root = new Node_with_distance(tree.root(), - distance_to_root, dists); + distance_to_root, dists); PriorityQueue.push(The_Root); // rd is the distance of the top of the priority queue to q @@ -174,8 +174,8 @@ namespace CGAL { } else{ distance_to_root= - Orthogonal_distance_instance.max_distance_to_rectangle(q, - tree.bounding_box()); + Orthogonal_distance_instance.max_distance_to_rectangle(q, + tree.bounding_box(), dists); Node_with_distance *The_Root = new Node_with_distance(tree.root(), distance_to_root, dists); PriorityQueue.push(The_Root); @@ -185,19 +185,19 @@ namespace CGAL { Compute_the_next_furthest_neighbour(); } - + } // * operator - const Point_with_transformed_distance& - operator* () const + const Point_with_transformed_distance& + operator* () const { - return *(Item_PriorityQueue.top()); + return *(Item_PriorityQueue.top()); } // prefix operator - Iterator_implementation& - operator++() + Iterator_implementation& + operator++() { Delete_the_current_item_top(); if(search_nearest_neighbour) @@ -209,7 +209,7 @@ namespace CGAL { // postfix operator Object_wrapper<Point_with_transformed_distance> - operator++(int) + operator++(int) { Object_wrapper<Point_with_transformed_distance> result( *(Item_PriorityQueue.top()) ); ++*this; @@ -217,252 +217,251 @@ namespace CGAL { } // Print statistics of the general priority search process. - std::ostream& + std::ostream& statistics (std::ostream& s) const { - s << "Orthogonal priority search statistics:" - << std::endl; - s << "Number of internal nodes visited:" - << number_of_internal_nodes_visited << std::endl; - s << "Number of leaf nodes visited:" - << number_of_leaf_nodes_visited << std::endl; - s << "Number of items visited:" - << number_of_items_visited << std::endl; - s << "Number of neighbours computed:" - << number_of_neighbours_computed << std::endl; + s << "Orthogonal priority search statistics:" + << std::endl; + s << "Number of internal nodes visited:" + << number_of_internal_nodes_visited << std::endl; + s << "Number of leaf nodes visited:" + << number_of_leaf_nodes_visited << std::endl; + s << "Number of items visited:" + << number_of_items_visited << std::endl; + s << "Number of neighbours computed:" + << number_of_neighbours_computed << std::endl; return s; } //destructor - ~Iterator_implementation() + ~Iterator_implementation() { - while (!PriorityQueue.empty()) { - Node_with_distance* The_top=PriorityQueue.top(); - PriorityQueue.pop(); - delete The_top; - } - while (!Item_PriorityQueue.empty()) { - Point_with_transformed_distance* The_top=Item_PriorityQueue.top(); - Item_PriorityQueue.pop(); - delete The_top; + while (!PriorityQueue.empty()) { + Node_with_distance* The_top=PriorityQueue.top(); + PriorityQueue.pop(); + delete The_top; + } + while (!Item_PriorityQueue.empty()) { + Point_with_transformed_distance* The_top=Item_PriorityQueue.top(); + Item_PriorityQueue.pop(); + delete The_top; } } private: - void - Delete_the_current_item_top() + void + Delete_the_current_item_top() { Point_with_transformed_distance* The_item_top=Item_PriorityQueue.top(); Item_PriorityQueue.pop(); delete The_item_top; } - void - Compute_the_next_nearest_neighbour() + void + Compute_the_next_nearest_neighbour() { // compute the next item bool next_neighbour_found=false; if (!(Item_PriorityQueue.empty())) { - next_neighbour_found= - (multiplication_factor*rd > Item_PriorityQueue.top()->second); + next_neighbour_found= + (multiplication_factor*rd > Item_PriorityQueue.top()->second); } - typename SearchTraits::Construct_cartesian_const_iterator_d construct_it=traits.construct_cartesian_const_iterator_d_object(); - typename SearchTraits::Cartesian_const_iterator_d query_point_it = construct_it(query_point); + typename SearchTraits::Construct_cartesian_const_iterator_d construct_it=traits.construct_cartesian_const_iterator_d_object(); + typename SearchTraits::Cartesian_const_iterator_d query_point_it = construct_it(query_point); // otherwise browse the tree further while ((!next_neighbour_found) && (!PriorityQueue.empty())) { - Node_with_distance* The_node_top=PriorityQueue.top(); - Node_const_handle N= CGAL::cpp11::get<0>(*The_node_top); + Node_with_distance* The_node_top=PriorityQueue.top(); + Node_const_handle N= CGAL::cpp11::get<0>(*The_node_top); dists = CGAL::cpp11::get<2>(*The_node_top); - PriorityQueue.pop(); - delete The_node_top; - FT copy_rd=rd; - while (!(N->is_leaf())) { // compute new distance + PriorityQueue.pop(); + delete The_node_top; + FT copy_rd=rd; + while (!(N->is_leaf())) { // compute new distance typename Tree::Internal_node_const_handle node = static_cast<typename Tree::Internal_node_const_handle>(N); - number_of_internal_nodes_visited++; - int new_cut_dim=node->cutting_dimension(); - FT new_rd,dst = dists[new_cut_dim]; - FT val = *(query_point_it + new_cut_dim); - FT diff1 = val - node->high_value(); - FT diff2 = val - node->low_value(); - if (diff1 + diff2 < FT(0.0)) { + number_of_internal_nodes_visited++; + int new_cut_dim=node->cutting_dimension(); + FT new_rd,dst = dists[new_cut_dim]; + FT val = *(query_point_it + new_cut_dim); + FT diff1 = val - node->upper_low_value(); + FT diff2 = val - node->lower_high_value(); + if (diff1 + diff2 < FT(0.0)) { new_rd= - Orthogonal_distance_instance.new_distance(copy_rd,dst,diff1,new_cut_dim); - - CGAL_assertion(new_rd >= copy_rd); + Orthogonal_distance_instance.new_distance(copy_rd,dst,diff1,new_cut_dim); + + CGAL_assertion(new_rd >= copy_rd); dists[new_cut_dim] = diff1; Node_with_distance *Upper_Child = - new Node_with_distance(node->upper(), new_rd, dists); - PriorityQueue.push(Upper_Child); + new Node_with_distance(node->upper(), new_rd, dists); + PriorityQueue.push(Upper_Child); dists[new_cut_dim] = dst; - N=node->lower(); + N=node->lower(); - } - else { // compute new distance - new_rd=Orthogonal_distance_instance.new_distance(copy_rd,dst,diff2,new_cut_dim); - CGAL_assertion(new_rd >= copy_rd); + } + else { // compute new distance + new_rd=Orthogonal_distance_instance.new_distance(copy_rd,dst,diff2,new_cut_dim); + CGAL_assertion(new_rd >= copy_rd); dists[new_cut_dim] = diff2; - Node_with_distance *Lower_Child = - new Node_with_distance(node->lower(), new_rd, dists); - PriorityQueue.push(Lower_Child); + Node_with_distance *Lower_Child = + new Node_with_distance(node->lower(), new_rd, dists); + PriorityQueue.push(Lower_Child); dists[new_cut_dim] = dst; - N=node->upper(); - } - } - // n is a leaf + N=node->upper(); + } + } + // n is a leaf typename Tree::Leaf_node_const_handle node = static_cast<typename Tree::Leaf_node_const_handle>(N); - number_of_leaf_nodes_visited++; - if (node->size() > 0) { - for (typename Tree::iterator it=node->begin(); it != node->end(); it++) { - number_of_items_visited++; - FT distance_to_query_point= - Orthogonal_distance_instance.transformed_distance(query_point,*it); - Point_with_transformed_distance *NN_Candidate= - new Point_with_transformed_distance(*it,distance_to_query_point); - Item_PriorityQueue.push(NN_Candidate); - } - // old top of PriorityQueue has been processed, - // hence update rd - - if (!(PriorityQueue.empty())) { - rd = CGAL::cpp11::get<1>(*PriorityQueue.top()); - next_neighbour_found = - (multiplication_factor*rd > - Item_PriorityQueue.top()->second); - } - else // priority queue empty => last neighbour found - { - next_neighbour_found=true; - } - - number_of_neighbours_computed++; - } + number_of_leaf_nodes_visited++; + if (node->size() > 0) { + for (typename Tree::iterator it=node->begin(); it != node->end(); it++) { + number_of_items_visited++; + FT distance_to_query_point= + Orthogonal_distance_instance.transformed_distance(query_point,*it); + Point_with_transformed_distance *NN_Candidate= + new Point_with_transformed_distance(*it,distance_to_query_point); + Item_PriorityQueue.push(NN_Candidate); + } + // old top of PriorityQueue has been processed, + // hence update rd + + if (!(PriorityQueue.empty())) { + rd = CGAL::cpp11::get<1>(*PriorityQueue.top()); + next_neighbour_found = + (multiplication_factor*rd > + Item_PriorityQueue.top()->second); + } + else // priority queue empty => last neighbour found + { + next_neighbour_found=true; + } + + number_of_neighbours_computed++; + } } // next_neighbour_found or priority queue is empty // in the latter case also the item priority quee is empty } - void - Compute_the_next_furthest_neighbour() + void + Compute_the_next_furthest_neighbour() { // compute the next item bool next_neighbour_found=false; if (!(Item_PriorityQueue.empty())) { - next_neighbour_found= - (rd < multiplication_factor*Item_PriorityQueue.top()->second); + next_neighbour_found= + (rd < multiplication_factor*Item_PriorityQueue.top()->second); } - typename SearchTraits::Construct_cartesian_const_iterator_d construct_it=traits.construct_cartesian_const_iterator_d_object(); - typename SearchTraits::Cartesian_const_iterator_d query_point_it = construct_it(query_point); + typename SearchTraits::Construct_cartesian_const_iterator_d construct_it=traits.construct_cartesian_const_iterator_d_object(); + typename SearchTraits::Cartesian_const_iterator_d query_point_it = construct_it(query_point); // otherwise browse the tree further while ((!next_neighbour_found) && (!PriorityQueue.empty())) { - Node_with_distance* The_node_top=PriorityQueue.top(); - Node_const_handle N= CGAL::cpp11::get<0>(*The_node_top); + Node_with_distance* The_node_top=PriorityQueue.top(); + Node_const_handle N= CGAL::cpp11::get<0>(*The_node_top); dists = CGAL::cpp11::get<2>(*The_node_top); - PriorityQueue.pop(); - delete The_node_top; - FT copy_rd=rd; - while (!(N->is_leaf())) { // compute new distance + PriorityQueue.pop(); + delete The_node_top; + FT copy_rd=rd; + while (!(N->is_leaf())) { // compute new distance typename Tree::Internal_node_const_handle node = static_cast<typename Tree::Internal_node_const_handle>(N); - number_of_internal_nodes_visited++; - int new_cut_dim=node->cutting_dimension(); - FT new_rd,dst = dists[new_cut_dim]; - FT val = *(query_point_it + new_cut_dim); - FT diff1 = val - node->high_value(); - FT diff2 = val - node->low_value(); - if (diff1 + diff2 < FT(0.0)) { + number_of_internal_nodes_visited++; + int new_cut_dim=node->cutting_dimension(); + FT new_rd,dst = dists[new_cut_dim]; + FT val = *(query_point_it + new_cut_dim); + FT diff1 = val - node->upper_low_value(); + FT diff2 = val - node->lower_high_value(); + if (diff1 + diff2 < FT(0.0)) { + diff1 = val - node->upper_high_value(); new_rd= - Orthogonal_distance_instance.new_distance(copy_rd,dst,diff1,new_cut_dim); - - CGAL_assertion(new_rd >= copy_rd); - Node_with_distance *Lower_Child = - new Node_with_distance(node->lower(), copy_rd, dists); - PriorityQueue.push(Lower_Child); - N=node->upper(); + Orthogonal_distance_instance.new_distance(copy_rd,dst,diff1,new_cut_dim); + Node_with_distance *Lower_Child = + new Node_with_distance(node->lower(), copy_rd, dists); + PriorityQueue.push(Lower_Child); + N=node->upper(); dists[new_cut_dim] = diff1; - copy_rd=new_rd; - - } - else { // compute new distance - new_rd=Orthogonal_distance_instance.new_distance(copy_rd,dst,diff2,new_cut_dim); - CGAL_assertion(new_rd >= copy_rd); - Node_with_distance *Upper_Child = - new Node_with_distance(node->upper(), copy_rd, dists); - PriorityQueue.push(Upper_Child); - N=node->lower(); + copy_rd=new_rd; + + } + else { // compute new distance + diff2 = val - node->lower_low_value(); + new_rd=Orthogonal_distance_instance.new_distance(copy_rd,dst,diff2,new_cut_dim); + Node_with_distance *Upper_Child = + new Node_with_distance(node->upper(), copy_rd, dists); + PriorityQueue.push(Upper_Child); + N=node->lower(); dists[new_cut_dim] = diff2; - copy_rd=new_rd; - } - } - // n is a leaf + copy_rd=new_rd; + } + } + // n is a leaf typename Tree::Leaf_node_const_handle node = static_cast<typename Tree::Leaf_node_const_handle>(N); - number_of_leaf_nodes_visited++; - if (node->size() > 0) { - for (typename Tree::iterator it=node->begin(); it != node->end(); it++) { - number_of_items_visited++; - FT distance_to_query_point= - Orthogonal_distance_instance.transformed_distance(query_point,*it); - Point_with_transformed_distance *NN_Candidate= - new Point_with_transformed_distance(*it,distance_to_query_point); - Item_PriorityQueue.push(NN_Candidate); - } - // old top of PriorityQueue has been processed, - // hence update rd - - if (!(PriorityQueue.empty())) { - rd = CGAL::cpp11::get<1>(*PriorityQueue.top()); - next_neighbour_found = - (multiplication_factor*rd < - Item_PriorityQueue.top()->second); - } - else // priority queue empty => last neighbour found - { - next_neighbour_found=true; - } - - number_of_neighbours_computed++; - } + number_of_leaf_nodes_visited++; + if (node->size() > 0) { + for (typename Tree::iterator it=node->begin(); it != node->end(); it++) { + number_of_items_visited++; + FT distance_to_query_point= + Orthogonal_distance_instance.transformed_distance(query_point,*it); + Point_with_transformed_distance *NN_Candidate= + new Point_with_transformed_distance(*it,distance_to_query_point); + Item_PriorityQueue.push(NN_Candidate); + } + // old top of PriorityQueue has been processed, + // hence update rd + + if (!(PriorityQueue.empty())) { + rd = CGAL::cpp11::get<1>(*PriorityQueue.top()); + next_neighbour_found = + (multiplication_factor*rd < + Item_PriorityQueue.top()->second); + } + else // priority queue empty => last neighbour found + { + next_neighbour_found=true; + } + + number_of_neighbours_computed++; + } } // next_neighbour_found or priority queue is empty // in the latter case also the item priority quee is empty } }; // class Iterator_implementaion - - + + public: class iterator; typedef iterator const_iterator; // constructor - Orthogonal_incremental_neighbor_search(const Tree& tree, - const Query_item& q, FT Eps = FT(0.0), - bool search_nearest=true, const Distance& tr=Distance()) + Orthogonal_incremental_neighbor_search(const Tree& tree, + const Query_item& q, FT Eps = FT(0.0), + bool search_nearest=true, const Distance& tr=Distance()) : m_tree(tree),m_query(q),m_dist(tr),m_Eps(Eps),m_search_nearest(search_nearest) {} - iterator + iterator begin() const { return iterator(m_tree,m_query,m_dist,m_Eps,m_search_nearest); } - iterator + iterator end() const { return iterator(); } - std::ostream& - statistics(std::ostream& s) + std::ostream& + statistics(std::ostream& s) { begin()->statistics(s); return s; @@ -490,24 +489,24 @@ namespace CGAL { public: // default constructor - iterator() + iterator() : Ptr_implementation(0) {} - int - the_number_of_items_visited() + int + the_number_of_items_visited() { return Ptr_implementation->number_of_items_visited; } // constructor - iterator(const Tree& tree,const Query_item& q, const Distance& tr=Distance(), FT eps=FT(0.0), - bool search_nearest=true) - : Ptr_implementation(new Iterator_implementation(tree, q, tr, eps, search_nearest)) - {} + iterator(const Tree& tree,const Query_item& q, const Distance& tr=Distance(), FT eps=FT(0.0), + bool search_nearest=true) + : Ptr_implementation(new Iterator_implementation(tree, q, tr, eps, search_nearest)) + {} // copy constructor - iterator(const iterator& Iter) + iterator(const iterator& Iter) { Ptr_implementation = Iter.Ptr_implementation; if (Ptr_implementation != 0) Ptr_implementation->reference_count++; @@ -523,25 +522,25 @@ namespace CGAL { if (Ptr_implementation != 0) Ptr_implementation->reference_count++; } return *this; - } - - - const Point_with_transformed_distance& - operator* () const + } + + + const Point_with_transformed_distance& + operator* () const { - return *(*Ptr_implementation); + return *(*Ptr_implementation); } - + // -> operator const Point_with_transformed_distance* - operator-> () const + operator-> () const { - return &*(*Ptr_implementation); + return &*(*Ptr_implementation); } // prefix operator - iterator& - operator++() + iterator& + operator++() { ++(*Ptr_implementation); return *this; @@ -549,47 +548,47 @@ namespace CGAL { // postfix operator Object_wrapper<Point_with_transformed_distance> - operator++(int) + operator++(int) { - return (*Ptr_implementation)++; + return (*Ptr_implementation)++; } - bool - operator==(const iterator& It) const + bool + operator==(const iterator& It) const { if ( - ((Ptr_implementation == 0) || - Ptr_implementation->Item_PriorityQueue.empty()) && - ((It.Ptr_implementation == 0) || - It.Ptr_implementation->Item_PriorityQueue.empty()) - ) - return true; + ((Ptr_implementation == 0) || + Ptr_implementation->Item_PriorityQueue.empty()) && + ((It.Ptr_implementation == 0) || + It.Ptr_implementation->Item_PriorityQueue.empty()) + ) + return true; // else return (Ptr_implementation == It.Ptr_implementation); } - bool - operator!=(const iterator& It) const + bool + operator!=(const iterator& It) const { return !(*this == It); } - std::ostream& - statistics (std::ostream& s) + std::ostream& + statistics (std::ostream& s) { - Ptr_implementation->statistics(s); + Ptr_implementation->statistics(s); return s; } - ~iterator() + ~iterator() { if (Ptr_implementation != 0) { - Ptr_implementation->reference_count--; - if (Ptr_implementation->reference_count==0) { - delete Ptr_implementation; - Ptr_implementation = 0; - } + Ptr_implementation->reference_count--; + if (Ptr_implementation->reference_count==0) { + delete Ptr_implementation; + Ptr_implementation = 0; + } } } @@ -600,17 +599,17 @@ namespace CGAL { const Tree& m_tree; Query_item m_query; Distance m_dist; - FT m_Eps; + FT m_Eps; bool m_search_nearest; - }; // class + }; // class template <class Traits, class Query_item, class Distance> - void swap (typename Orthogonal_incremental_neighbor_search<Traits, - Query_item, Distance>::iterator& x, - typename Orthogonal_incremental_neighbor_search<Traits, - Query_item, Distance>::iterator& y) + void swap (typename Orthogonal_incremental_neighbor_search<Traits, + Query_item, Distance>::iterator& x, + typename Orthogonal_incremental_neighbor_search<Traits, + Query_item, Distance>::iterator& y) { - typename Orthogonal_incremental_neighbor_search<Traits, + typename Orthogonal_incremental_neighbor_search<Traits, Query_item, Distance>::iterator::Iterator_implementation *tmp = x.Ptr_implementation; x.Ptr_implementation = y.Ptr_implementation; |