12#ifndef KD_TREE_SEARCH_H_
13#define KD_TREE_SEARCH_H_
15#include <gudhi/Debug_utils.h>
17#include <CGAL/Orthogonal_k_neighbor_search.h>
18#include <CGAL/Orthogonal_incremental_neighbor_search.h>
19#include <CGAL/Search_traits.h>
20#include <CGAL/Search_traits_adapter.h>
21#include <CGAL/property_map.h>
22#include <CGAL/version.h>
24#include <Eigen/src/Core/util/Macros.h>
26#include <boost/property_map/property_map.hpp>
27#include <boost/iterator/counting_iterator.hpp>
33#if CGAL_VERSION_NR < 1041101000
34# error Kd_tree_search is only available for CGAL >= 4.11
37#if !EIGEN_VERSION_AT_LEAST(3,1,0)
38# error Kd_tree_search is only available for Eigen3 >= 3.1.0 installed with CGAL
42namespace spatial_searching {
69template <
typename Search_traits,
typename Po
int_range>
71 typedef boost::iterator_property_map<
72 typename Point_range::const_iterator,
73 CGAL::Identity_property_map<std::ptrdiff_t> > Point_property_map;
79 typedef typename Traits::FT
FT;
81 typedef typename Point_range::value_type
Point;
83 typedef CGAL::Search_traits<
85 typename Traits::Cartesian_const_iterator_d,
86 typename Traits::Construct_cartesian_const_iterator_d,
87 typename Traits::Dimension> Traits_base;
89 typedef CGAL::Search_traits_adapter<
93 typedef CGAL::Distance_adapter<
96 CGAL::Euclidean_distance<Traits_base> > Orthogonal_distance;
98 typedef CGAL::Orthogonal_k_neighbor_search<STraits> K_neighbor_search;
99 typedef typename K_neighbor_search::Tree Tree;
100 typedef typename K_neighbor_search::Distance Distance;
106 typedef CGAL::Orthogonal_incremental_neighbor_search<
107 STraits, Distance, CGAL::Sliding_midpoint<STraits>, Tree>
108 Incremental_neighbor_search;
115 struct Sphere_for_kdtree_search
117 typedef typename Traits::Point_d Point_d;
118 typedef typename Traits::FT
FT;
119 typedef typename Traits::Dimension D;
125 FT sqradmin, sqradmax;
131 Sphere_for_kdtree_search(Point_d
const& c_,
FT const& r2min,
FT const& r2max,
bool prefer_max=
true, STraits
const& traits_ = {})
132 : traits(traits_), c(c_), sqradmin(r2min), sqradmax(r2max), use_max(prefer_max)
133 { GUDHI_CHECK(r2min >= 0 && r2max >= r2min,
"0 <= r2min <= r2max"); }
135 bool contains(std::ptrdiff_t i)
const {
136 const Point_d& p =
get(traits.point_property_map(), i);
137 auto ccci = traits.construct_cartesian_const_iterator_d_object();
138 return contains_point_given_as_coordinates(ccci(p), ccci(p, 0));
141 template <
typename Coord_iterator>
142 bool contains_point_given_as_coordinates(Coord_iterator pi, Coord_iterator)
const {
144 auto ccci = traits.construct_cartesian_const_iterator_d_object();
146 auto ce = ccci(c, 0);
147 FT const& limit = use_max ? sqradmax : sqradmin;
149 distance += CGAL::square(*pi++ - *ci++);
153 if (distance > limit)
return false;
158 bool inner_range_intersects(CGAL::Kd_tree_rectangle<FT, D>
const& rect)
const {
159 auto ccci = traits.construct_cartesian_const_iterator_d_object();
162 auto ce = ccci(c, 0);
163 for (
int i = 0; ci != ce; ++i, ++ci) {
164 distance += CGAL::square(CGAL::max<FT>(CGAL::max<FT>(*ci - rect.max_coord(i), rect.min_coord(i) - *ci), 0 ));
165 if (distance > sqradmin)
return false;
171 bool outer_range_contains(CGAL::Kd_tree_rectangle<FT, D>
const& rect)
const {
172 auto ccci = traits.construct_cartesian_const_iterator_d_object();
175 auto ce = ccci(c, 0);
176 for (
int i = 0; ci != ce; ++i, ++ci) {
177 distance += CGAL::square(CGAL::max<FT>(*ci - rect.min_coord(i), rect.max_coord(i) - *ci));
178 if (distance > sqradmax)
return false;
189 m_tree(boost::counting_iterator<
std::ptrdiff_t>(0),
190 boost::counting_iterator<
std::ptrdiff_t>(points.size()),
191 typename Tree::Splitter(),
192 STraits(
std::begin(points))) {
202 template <
typename Po
int_indices_range>
204 Point_range
const& points,
205 Point_indices_range
const& only_these_points)
208 only_these_points.begin(), only_these_points.end(),
209 typename Tree::Splitter(),
210 STraits(
std::begin(points))) {
221 Point_range
const& points,
222 std::size_t begin_idx, std::size_t past_the_end_idx)
225 boost::counting_iterator<
std::ptrdiff_t>(begin_idx),
226 boost::counting_iterator<
std::ptrdiff_t>(past_the_end_idx),
227 typename Tree::Splitter(),
228 STraits(
std::begin(points))) {
235 void insert(std::ptrdiff_t point_idx) {
236 m_tree.insert(point_idx);
249 FT eps =
FT(0))
const {
253 K_neighbor_search search(
259 Orthogonal_distance(std::begin(m_points)), sorted);
275 Incremental_neighbor_search search(
280 Orthogonal_distance(std::begin(m_points)) );
295 FT eps =
FT(0))
const {
299 K_neighbor_search search(
305 Orthogonal_distance(std::begin(m_points)), sorted);
321 Incremental_neighbor_search search(
326 Orthogonal_distance(std::begin(m_points)) );
337 template <
typename OutputIterator>
341 FT eps =
FT(0))
const {
353 template <
typename OutputIterator>
355 FT const& sq_radius_min,
356 FT const& sq_radius_max,
357 OutputIterator it)
const {
358 m_tree.search(it, Sphere_for_kdtree_search(p, sq_radius_min, sq_radius_max,
true, m_tree.traits()));
361 int tree_depth()
const {
362 return m_tree.root()->depth();
366 Point_range
const& m_points;
Spatial tree data structure to perform (approximate) nearest and furthest neighbor search.
Definition: Kd_tree_search.h:70
Point_range::value_type Point
The point type.
Definition: Kd_tree_search.h:81
KNS_range k_furthest_neighbors(Point const &p, unsigned int k, bool sorted=true, FT eps=FT(0)) const
Search for the k-furthest points from a query point.
Definition: Kd_tree_search.h:291
K_neighbor_search KNS_range
The range returned by a k-nearest or k-furthest neighbor search. Its value type is std::pair<std::siz...
Definition: Kd_tree_search.h:104
void all_near_neighbors(Point const &p, FT const &radius, OutputIterator it, FT eps=FT(0)) const
Search for all the neighbors in a ball.
Definition: Kd_tree_search.h:338
Traits::FT FT
Number type used for distances.
Definition: Kd_tree_search.h:79
INS_range incremental_nearest_neighbors(Point const &p, FT eps=FT(0)) const
Search incrementally for the nearest neighbors from a query point.
Definition: Kd_tree_search.h:271
Kd_tree_search(Point_range const &points)
Constructor.
Definition: Kd_tree_search.h:187
Search_traits Traits
The Traits.
Definition: Kd_tree_search.h:77
Kd_tree_search(Point_range const &points, Point_indices_range const &only_these_points)
Constructor.
Definition: Kd_tree_search.h:203
KNS_range k_nearest_neighbors(Point const &p, unsigned int k, bool sorted=true, FT eps=FT(0)) const
Search for the k-nearest neighbors from a query point.
Definition: Kd_tree_search.h:245
Kd_tree_search(Point_range const &points, std::size_t begin_idx, std::size_t past_the_end_idx)
Constructor.
Definition: Kd_tree_search.h:220
void all_near_neighbors2(Point const &p, FT const &sq_radius_min, FT const &sq_radius_max, OutputIterator it) const
Search for all the neighbors in a ball. This is similar to all_near_neighbors but takes directly the ...
Definition: Kd_tree_search.h:354
Incremental_neighbor_search INS_range
The range returned by an incremental nearest or furthest neighbor search. Its value type is std::pair...
Definition: Kd_tree_search.h:112
INS_range incremental_furthest_neighbors(Point const &p, FT eps=FT(0)) const
Search incrementally for the furthest neighbors from a query point.
Definition: Kd_tree_search.h:317
constexpr auto & get(Gudhi::persistence_matrix::Persistence_interval< Dimension, Event_value > &i) noexcept
Partial specialization of get for Gudhi::persistence_matrix::Persistence_interval.
Definition: persistence_interval.h:199
Gudhi namespace.
Definition: SimplicialComplexForAlpha.h:14