Searching...
No Matches
Spatial_searching

Classes

class  Gudhi::spatial_searching::Kd_tree_search< Search_traits, Point_range >
Spatial tree data structure to perform (approximate) nearest and furthest neighbor search. More...

Introduction

This Gudhi component is a wrapper around CGAL dD spatial searching algorithms. It provides a simplified API to perform (approximate) neighbor searches. Contrary to CGAL default behavior, the tree does not store the points themselves, but stores indices.

For more details about the data structure or the algorithms, or for more advanced usages, reading CGAL documentation is highly recommended.

Example

This example generates 500 random points, then performs all-near-neighbors searches, and queries for nearest and furthest neighbors using different methods.

#include <gudhi/Kd_tree_search.h>
#include <CGAL/Epick_d.h>
#include <CGAL/Random.h>
#include <vector>
namespace gss = Gudhi::spatial_searching;
int main(void) {
typedef CGAL::Epick_d<CGAL::Dimension_tag<4> > K;
typedef typename K::Point_d Point;
typedef std::vector<Point> Points;
typedef gss::Kd_tree_search<K, Points> Points_ds;
CGAL::Random rd;
Points points;
for (int i = 0; i < 500; ++i)
points.push_back(Point(rd.get_double(-1., 1), rd.get_double(-1., 1), rd.get_double(-1., 1), rd.get_double(-1., 1)));
Points_ds points_ds(points);
// 10-nearest neighbor query
std::clog << "10 nearest neighbors from points[20]:\n";
auto knn_range = points_ds.k_nearest_neighbors(points[20], 10, true);
for (auto const nghb : knn_range)
std::clog << nghb.first << " (sq. dist. = " << nghb.second << ")\n";
// Incremental nearest neighbor query
std::clog << "Incremental nearest neighbors:\n";
auto inn_range = points_ds.incremental_nearest_neighbors(points[45]);
// Get the neighbors in distance order until we hit the first point
for (auto ins_iterator = inn_range.begin(); ins_iterator->first != 0; ++ins_iterator)
std::clog << ins_iterator->first << " (sq. dist. = " << ins_iterator->second << ")\n";
// 10-furthest neighbor query
std::clog << "10 furthest neighbors from points[20]:\n";
auto kfn_range = points_ds.k_furthest_neighbors(points[20], 10, true);
for (auto const nghb : kfn_range)
std::clog << nghb.first << " (sq. dist. = " << nghb.second << ")\n";
// Incremental furthest neighbor query
std::clog << "Incremental furthest neighbors:\n";
auto ifn_range = points_ds.incremental_furthest_neighbors(points[45]);
// Get the neighbors in distance reverse order until we hit the first point
for (auto ifs_iterator = ifn_range.begin(); ifs_iterator->first != 0; ++ifs_iterator)
std::clog << ifs_iterator->first << " (sq. dist. = " << ifs_iterator->second << ")\n";
// All-near-neighbors search
std::clog << "All-near-neighbors search:\n";
std::vector<std::size_t> rs_result;
points_ds.all_near_neighbors(points[45], 0.5, std::back_inserter(rs_result));
K k;
for (auto const& p_idx : rs_result)
std::clog << p_idx << " (sq. dist. = " << k.squared_distance_d_object()(points[p_idx], points[45]) << ")\n";
return 0;
}
Spatial tree data structure to perform (approximate) nearest and furthest neighbor search.
Definition: Kd_tree_search.h:70