diff options
author | mcarrier <mcarrier@636b058d-ea47-450e-bf9e-a15bfbe3eedb> | 2017-04-12 07:50:07 +0000 |
---|---|---|
committer | mcarrier <mcarrier@636b058d-ea47-450e-bf9e-a15bfbe3eedb> | 2017-04-12 07:50:07 +0000 |
commit | 9a8649a45f61a9e152f26cb3fcbbdeabec5e0f37 (patch) | |
tree | 7a16c67262070914c5351f38bed9941824b1f053 /src/Bottleneck_distance/include/gudhi/Neighbors_finder.h | |
parent | 9a4ad421d6faf66c7fa3091340e07e8e61adaae8 (diff) | |
parent | 387a5af3ee1b664346eb9686f00c986e9f7a1e3e (diff) |
Merged latest trunk changes to Nerve_GIC
git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/Nerve_GIC@2336 636b058d-ea47-450e-bf9e-a15bfbe3eedb
Former-commit-id: 45e06633204b8da3a91751fd510f1639225beb2d
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; } |