From 61bc0a0443e610b851a8c1ee8bad8514ef0c894b Mon Sep 17 00:00:00 2001 From: cjamin Date: Wed, 11 May 2016 15:14:27 +0000 Subject: Add Spatial_tree_data_structure git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/subsampling_and_spatialsearching@1168 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: 8849698237c375d68d37dbe36f97b7b5252f5ff8 --- .../include/gudhi/Spatial_tree_data_structure.h | 169 +++++++++++++++++++++ 1 file changed, 169 insertions(+) create mode 100644 src/Spatial_searching/include/gudhi/Spatial_tree_data_structure.h (limited to 'src') diff --git a/src/Spatial_searching/include/gudhi/Spatial_tree_data_structure.h b/src/Spatial_searching/include/gudhi/Spatial_tree_data_structure.h new file mode 100644 index 00000000..48f9590b --- /dev/null +++ b/src/Spatial_searching/include/gudhi/Spatial_tree_data_structure.h @@ -0,0 +1,169 @@ +/* This file is part of the Gudhi Library. The Gudhi library + * (Geometric Understanding in Higher Dimensions) is a generic C++ + * library for computational topology. + * + * Author(s): Clement Jamin + * + * Copyright (C) 2016 INRIA Sophia-Antipolis (France) + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see . + */ + +#ifndef GUDHI_POINT_CLOUD_H +#define GUDHI_POINT_CLOUD_H + +#include +#include +#include +#include + +#include + +#include +#include + +namespace Gudhi { + +template +class Spatial_tree_data_structure +{ +public: + typedef typename Point_container_::value_type Point; + typedef K Kernel; + typedef typename Kernel::FT FT; + + typedef CGAL::Search_traits< + FT, Point, + typename Kernel::Cartesian_const_iterator_d, + typename Kernel::Construct_cartesian_const_iterator_d> Traits_base; + // using a pointer as a special property map type + typedef CGAL::Search_traits_adapter< + std::ptrdiff_t, Point*, Traits_base> STraits; + + typedef CGAL::Orthogonal_k_neighbor_search K_neighbor_search; + typedef typename K_neighbor_search::Tree Tree; + typedef typename K_neighbor_search::Distance Distance; + typedef typename K_neighbor_search::iterator KNS_iterator; + typedef K_neighbor_search KNS_range; + + typedef CGAL::Orthogonal_incremental_neighbor_search< + STraits, Distance, CGAL::Sliding_midpoint, Tree> + Incremental_neighbor_search; + typedef typename Incremental_neighbor_search::iterator INS_iterator; + typedef Incremental_neighbor_search INS_range; + + /// Constructor + Point_cloud_data_structure(Point_container_ const& points) + : m_points(points), + m_tree(boost::counting_iterator(0), + boost::counting_iterator(points.size()), + typename Tree::Splitter(), + STraits((Point*)&(points[0])) ) + { + // Build the tree now (we don't want to wait for the first query) + m_tree.build(); + } + + /// Constructor + template + Point_cloud_data_structure( + Point_container_ const& points, + Point_indices_range const& only_these_points) + : m_points(points), + m_tree( + only_these_points.begin(), only_these_points.end(), + typename Tree::Splitter(), + STraits((Point*)&(points[0]))) + { + // Build the tree now (we don't want to wait for the first query) + m_tree.build(); + } + + /// Constructor + Point_cloud_data_structure( + Point_container_ const& points, + std::size_t begin_idx, std::size_t past_the_end_idx) + : m_points(points), + m_tree( + boost::counting_iterator(begin_idx), + boost::counting_iterator(past_the_end_idx), + typename Tree::Splitter(), + STraits((Point*)&(points[0])) ) + { + // Build the tree now (we don't want to wait for the first query) + m_tree.build(); + } + + /*Point_container_ &points() + { + return m_points; + } + + const Point_container_ &points() const + { + return m_points; + }*/ + + // Be careful, this function invalidates the tree, + // which will be recomputed at the next query + void insert(std::ptrdiff_t point_idx) + { + m_tree.insert(point_idx); + } + + KNS_range query_ANN(const + Point &sp, + unsigned int k, + bool sorted = true) const + { + // Initialize the search structure, and search all N points + // Note that we need to pass the Distance explicitly since it needs to + // know the property map + K_neighbor_search search( + m_tree, + sp, + k, + FT(0), + true, + CGAL::Distance_adapter >( + (Point*)&(m_points[0])), + sorted); + + return search; + } + + INS_range query_incremental_ANN(const Point &sp) const + { + // Initialize the search structure, and search all N points + // Note that we need to pass the Distance explicitly since it needs to + // know the property map + Incremental_neighbor_search search( + m_tree, + sp, + FT(0), + true, + CGAL::Distance_adapter >( + (Point*)&(m_points[0])) ); + + return search; + } + +protected: + Point_container_ const& m_points; + Tree m_tree; +}; + +} //namespace Gudhi + +#endif // GUDHI_POINT_CLOUD_H -- cgit v1.2.3