12 #ifndef KD_TREE_SEARCH_H_
13 #define KD_TREE_SEARCH_H_
15 #include <CGAL/Orthogonal_k_neighbor_search.h>
16 #include <CGAL/Orthogonal_incremental_neighbor_search.h>
17 #include <CGAL/Search_traits.h>
18 #include <CGAL/Search_traits_adapter.h>
19 #include <CGAL/Fuzzy_sphere.h>
20 #include <CGAL/property_map.h>
21 #include <CGAL/version.h>
23 #include <Eigen/src/Core/util/Macros.h>
25 #include <boost/property_map/property_map.hpp>
26 #include <boost/iterator/counting_iterator.hpp>
32 #if CGAL_VERSION_NR < 1041101000
33 # error Alpha_complex_3d is only available for CGAL >= 4.11
36 #if !EIGEN_VERSION_AT_LEAST(3,1,0)
37 # error Alpha_complex_3d is only available for Eigen3 >= 3.1.0 installed with CGAL
41 namespace spatial_searching {
69 template <
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> Traits_base;
88 typedef CGAL::Search_traits_adapter<
92 typedef CGAL::Distance_adapter<
95 CGAL::Euclidean_distance<Traits_base> > Orthogonal_distance;
97 typedef CGAL::Orthogonal_k_neighbor_search<STraits> K_neighbor_search;
98 typedef typename K_neighbor_search::Tree Tree;
99 typedef typename K_neighbor_search::Distance Distance;
105 typedef CGAL::Orthogonal_incremental_neighbor_search<
106 STraits, Distance, CGAL::Sliding_midpoint<STraits>, Tree>
107 Incremental_neighbor_search;
113 typedef CGAL::Fuzzy_sphere<STraits> Fuzzy_sphere;
119 m_tree(boost::counting_iterator<std::ptrdiff_t>(0),
120 boost::counting_iterator<std::ptrdiff_t>(points.size()),
121 typename Tree::Splitter(),
122 STraits(std::begin(points))) {
132 template <
typename Po
int_indices_range>
134 Point_range
const& points,
135 Point_indices_range
const& only_these_points)
138 only_these_points.begin(), only_these_points.end(),
139 typename Tree::Splitter(),
140 STraits(std::begin(points))) {
151 Point_range
const& points,
152 std::size_t begin_idx, std::size_t past_the_end_idx)
155 boost::counting_iterator<std::ptrdiff_t>(begin_idx),
156 boost::counting_iterator<std::ptrdiff_t>(past_the_end_idx),
157 typename Tree::Splitter(),
158 STraits(std::begin(points))) {
165 void insert(std::ptrdiff_t point_idx) {
166 m_tree.insert(point_idx);
179 FT eps =
FT(0))
const {
183 K_neighbor_search search(
189 Orthogonal_distance(std::begin(m_points)), sorted);
205 Incremental_neighbor_search search(
210 Orthogonal_distance(std::begin(m_points)) );
225 FT eps =
FT(0))
const {
229 K_neighbor_search search(
235 Orthogonal_distance(std::begin(m_points)), sorted);
251 Incremental_neighbor_search search(
256 Orthogonal_distance(std::begin(m_points)) );
267 template <
typename OutputIterator>
271 FT eps =
FT(0))
const {
272 m_tree.search(it, Fuzzy_sphere(p, radius, eps, m_tree.traits()));
275 int tree_depth()
const {
276 return m_tree.root()->depth();
280 Point_range
const& m_points;
287 #endif // KD_TREE_SEARCH_H_