diff options
author | vrouvrea <vrouvrea@636b058d-ea47-450e-bf9e-a15bfbe3eedb> | 2017-04-12 05:58:16 +0000 |
---|---|---|
committer | vrouvrea <vrouvrea@636b058d-ea47-450e-bf9e-a15bfbe3eedb> | 2017-04-12 05:58:16 +0000 |
commit | 387a5af3ee1b664346eb9686f00c986e9f7a1e3e (patch) | |
tree | 667bbb1e4c37fedbac5547296fca4007a9a825cf /src/Bottleneck_distance/include/gudhi/Neighbors_finder.h | |
parent | 46513e8ca08fe32074ddc12b8fbd48ef3de0eaec (diff) | |
parent | d3d1a314e6d32e54a2dfb2f919f0e1eb1f111c9b (diff) |
Merge of bottleneck-glisse branch to speed up bottleneck computation
git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/trunk@2335 636b058d-ea47-450e-bf9e-a15bfbe3eedb
Former-commit-id: 164b0e8de1d89e5b056dd01e63d5cb6dae6c67e1
Diffstat (limited to 'src/Bottleneck_distance/include/gudhi/Neighbors_finder.h')
-rw-r--r-- | src/Bottleneck_distance/include/gudhi/Neighbors_finder.h | 48 |
1 files changed, 34 insertions, 14 deletions
diff --git a/src/Bottleneck_distance/include/gudhi/Neighbors_finder.h b/src/Bottleneck_distance/include/gudhi/Neighbors_finder.h index cd5486f8..bdc47578 100644 --- a/src/Bottleneck_distance/include/gudhi/Neighbors_finder.h +++ b/src/Bottleneck_distance/include/gudhi/Neighbors_finder.h @@ -25,9 +25,6 @@ // Inclusion order is important for CGAL patch #include <CGAL/Kd_tree.h> -#include <CGAL/Kd_tree_node.h> -#include <CGAL/Orthogonal_k_neighbor_search.h> -#include <CGAL/Weighted_Minkowski_distance.h> #include <CGAL/Search_traits.h> #include <gudhi/Persistence_graph.h> @@ -40,6 +37,33 @@ namespace Gudhi { namespace persistence_diagram { +/** \internal \brief Variant of CGAL::Fuzzy_iso_box to ensure that the box ic closed. It isn't clear how necessary that is. + */ +struct Square_query { + typedef CGAL::Dimension_tag<2> D; + typedef Internal_point Point_d; + typedef double FT; + bool contains(Point_d p) const { + return std::abs(p.x()-c.x())<=size && std::abs(p.y()-c.y())<=size; + } + bool inner_range_intersects(CGAL::Kd_tree_rectangle<FT,D> const&r) const { + return + r.max_coord(0) >= c.x() - size && + r.min_coord(0) <= c.x() + size && + r.max_coord(1) >= c.y() - size && + r.min_coord(1) <= c.y() + size; + } + bool outer_range_contains(CGAL::Kd_tree_rectangle<FT,D> const&r) const { + return + r.min_coord(0) >= c.x() - size && + r.max_coord(0) <= c.x() + size && + r.min_coord(1) >= c.y() - size && + r.max_coord(1) <= c.y() + size; + } + Point_d c; + FT size; +}; + /** \internal \brief data structure used to find any point (including projections) in V near to a query point from U * (which can be a projection). * @@ -51,9 +75,7 @@ namespace persistence_diagram { class Neighbors_finder { typedef CGAL::Dimension_tag<2> D; typedef CGAL::Search_traits<double, Internal_point, const double*, Construct_coord_iterator, D> Traits; - typedef CGAL::Weighted_Minkowski_distance<Traits> Distance; - typedef CGAL::Orthogonal_k_neighbor_search<Traits, Distance> K_neighbor_search; - typedef K_neighbor_search::Tree Kd_tree; + typedef CGAL::Kd_tree<Traits> Kd_tree; public: /** \internal \brief Constructor taking the near distance definition as parameter. */ @@ -123,15 +145,13 @@ inline int Neighbors_finder::pull_near(int u_point_index) { } else { // Is the query point near to a V point in the plane ? Internal_point u_point = g.get_u_point(u_point_index); - std::array<double, 2> w = { - {1., 1.} - }; - K_neighbor_search search(kd_t, u_point, 1, 0., true, Distance(0, 2, w.begin(), w.end())); - auto it = search.begin(); - if (it == search.end() || g.distance(u_point_index, it->first.point_index) > r) + auto neighbor = kd_t.search_any_point(Square_query{u_point, r}); + if(!neighbor) return null_point_index(); - tmp = it->first.point_index; - kd_t.remove(g.get_v_point(tmp)); + tmp = neighbor->point_index; + auto point = g.get_v_point(tmp); + int idx = point.point_index; + kd_t.remove(point, [idx](Internal_point const&p){return p.point_index == idx;}); } return tmp; } |