CGAL K-D trees - How do I associate information to a point when range searching?

Question

I am using CGAL to randomly generate points on a square and I want to assign each point an arbitrary int value. The goal is to do a range search using Fuzzy_sphere. My code runs without the added int values however, I can't seem to add a int value and make it run.

I've looked at the examples provided in the manual for doing this with neighbour searching but I can't get it to work with a range searching query.

My working code so far:

#include <CGAL/Simple_cartesian.h>
#include <CGAL/Kd_tree.h>
#include <CGAL/Search_traits_2.h>
#include <CGAL/point_generators_2.h>
#include <CGAL/algorithm.h>
#include <CGAL/Fuzzy_sphere.h>
#include <CGAL/Random.h>

typedef CGAL::Simple_cartesian<double> K;
typedef K::Point_2 Point;
typedef CGAL::Random_points_in_square_2<Point> Random_points_iterator;
typedef CGAL::Counting_iterator<Random_points_iterator> N_Random_points_iterator;
typedef CGAL::Search_traits_2<K> Traits;
typedef CGAL::Fuzzy_sphere<Traits> Fuzzy_circle;
typedef CGAL::Kd_tree<Traits> Tree;
typedef CGAL::Random Random;

int main() {

    const int no_points = 2000; // arbitrary 
    const int size = 1000;
    Random rand;
    // Vector to store Points
    std::vector<Point> point_vec;

    for (int i = 0; i < no_points; ++i)
        point_vec.push_back(Point(rand.get_double(0, size), rand.get_double(0, size))); 

        // Add this to a K-D tree 
        Tree tree(point_vec.begin(), point_vec.end());

    // Find a random point to search
    Point search_point = Point(rand.get_double(0, 12), rand.get_double(0, 12));

    // Creating a fuzzy circle 
    Fuzzy_circle search_circle(search_point, 20, 0.1); // Center, sqrd radius, fuzziness 

    // Searching an the area that is specified in "search_area"
    boost::optional<Point> search_area = tree.search_any_point(search_circle);

    // declare list to store points found in search query
    std::list<Point> search_result;

    // Doing a range search on the tree KD tree space 
    tree.search(std::back_inserter(search_result), search_circle);

    std::cout << "\n Points in search area: " << search_point << ":\n";

    // initiate iterator that will be used to iterate over the elements of the result list.
    std::list<Point>::iterator iter;

    for (iter = search_result.begin(); (iter != search_result.end()); ++iter)
        std::cout << *iter << "\n";

    search_result.clear();
    return 0;
}

The goal is to access which points are within the range query and their associated values. Any ideas?

I'm pretty new to CGAL and C++ in general, so I'm sorry if this is an easy one.

Answer 1

Found what is probably a very inefficient way of doing this and I'll see how the performance goes later in the program. It works but at what cost

#include <CGAL/Simple_cartesian.h>
#include <CGAL/Kd_tree.h>
#include <CGAL/Search_traits_2.h>
#include <CGAL/point_generators_2.h>
#include <CGAL/algorithm.h>
#include <CGAL/Fuzzy_sphere.h>
#include <CGAL/Random.h>

#include <iostream>
#include <map>
#include <string>
#include <boost/property_map/property_map.hpp>

// Vector to store Points
//std::vector<Point> point_vec;
//point_vec.push_back(Point(rand.get_double(0, size), rand.get_double(0, size)));

typedef CGAL::Simple_cartesian<double> K;
typedef K::Point_2 Point;
typedef CGAL::Random_points_in_square_2<Point> Random_points_iterator;
typedef CGAL::Counting_iterator<Random_points_iterator> N_Random_points_iterator;
typedef CGAL::Search_traits_2<K> Traits;
typedef CGAL::Fuzzy_sphere<Traits> Fuzzy_circle;
typedef CGAL::Kd_tree<Traits> Tree;
typedef CGAL::Random Random;

int main() {

    const int no_points = 2000; // arbitrary 
    const int size = 10;
    Random rand;


    // New stuff
    std::map<int, Point> Point_map;
   
    boost::associative_property_map < std::map<int, Point> > address_map(Point_map);


    for (int i = 0; i < no_points; ++i){

        Point position_i = Point(rand.get_double(0, size), rand.get_double(0, size));
        int value_i = rand.get_int(0, 123);

        Point_map.insert(std::make_pair(value_i, position_i));

    }
    
        // Add this to a K-D tree 
    Tree tree; //(Point_map.begin(), Point_map.end());
    for (const auto& pair : Point_map) {
        tree.insert(pair.second);
    }



    // Find a random point to search
    Point search_point = Point(rand.get_double(0, 12), rand.get_double(0, 12));

    // Creating a fuzzy circle 
    Fuzzy_circle search_circle(search_point, 20, 0.1); // Center, sqrd radius, fuzziness 

    // Searching an the area that is specified in "search_area"
    boost::optional<Point> search_area = tree.search_any_point(search_circle);

    // declare list to store points found in search query
    std::list<Point> search_result;

    // Doing a range search on the tree KD tree space 
    tree.search(std::back_inserter(search_result), search_circle);

    std::cout << "\n Points in search area: " << search_point << ":\n";

    // Printing the points and their int value 
    std::cout << "\nPoints in search area: " << search_point << ":\n ";

    for (const auto& point : search_result) {

        // Find the int value associated with the current point
        int value = Point_map.begin()->first;

        for (const auto& pair : Point_map) {

            if (pair.second == point) {

                value = pair.first;
                break;

            }
        }

        std::cout << "Point: " << point << ", Value: " << value << "\n";
    }


    search_result.clear();
    return 0;
}

Answer 2

Have a look at the following section: https://doc.cgal.org/latest/Spatial_searching/index.html#title10

Pick the example that matches the best your setting.

Answer 3

Using @sloriots hint that there's a search traits adaptor that uses Property Maps to extract the geometric feature from an element, here's a modernized version of both the documentation example and the question code:

#include <boost/next_prior.hpp>

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Fuzzy_sphere.h>
#include <CGAL/Kd_tree.h>
#include <CGAL/Orthogonal_k_neighbor_search.h>
#include <CGAL/Random.h>
#include <CGAL/Search_traits_2.h>
#include <CGAL/Search_traits_adapter.h>
#include <CGAL/Simple_cartesian.h>
#include <CGAL/algorithm.h>
#include <CGAL/point_generators_2.h>
#include <deque>

using Kernel = CGAL::Exact_predicates_inexact_constructions_kernel;
using Point  = Kernel::Point_2;

struct Element {
    Point p;
    int   id;

    struct GetPoint { // property map to access the point
        using key_type   = Element;
        using value_type = Point;
        using reference  = value_type const&;
        using category   = boost::lvalue_property_map_tag;

        value_type const& operator[](Element const& p) const { return p.p; }

        friend reference get(GetPoint const&, Element const& p) { return p.p; }
        friend void put(GetPoint const&, Element& p, value_type v) { p.p = std::move(v); }
    };
};

using Random_points_iterator = CGAL::Random_points_in_square_2<Point>;
using Traits_base            = CGAL::Search_traits_2<Kernel>;
using Traits = CGAL::Search_traits_adapter<Element, Element::GetPoint, Traits_base>;
using K_neighbor_search = CGAL::Orthogonal_k_neighbor_search<Traits>;
using Fuzzy_circle      = CGAL::Fuzzy_sphere<Traits>;
using Tree              = K_neighbor_search::Tree;
using Distance          = K_neighbor_search::Distance;

void documentation_example_modernized_2d() {
    std::cout << std::setprecision(5) << std::fixed;

    std::vector<Element> points;
    generate_n(back_inserter(points), 7,
               [gen = Random_points_iterator(1.0), id = 0]() mutable {
                   return Element{*gen++, id++};
               });

    Tree tree(points.begin(), points.end());

    // search K nearest neighbors
    constexpr int K = 5;
    Point         p(0.0, 0.0);
    for (Distance tr_dist; auto&& [element, d] : K_neighbor_search(tree, p, K))
        std::cout << " d(q, nn) =  "                                                    //
                  << std::setw(10) << tr_dist.inverse_of_transformed_distance(d) << " " //
                  << std::showpos << element.p << " " << std::noshowpos                 //
                  << element.id                                                         //
                  << std::endl;
}

int main() {
    int const    no_points = 2000; // arbitrary
    int const    size      = 1000;

    std::vector<Element> elements;
    generate_n(back_inserter(elements), no_points,
               [gen = Random_points_iterator(size), id = 0]() mutable {
                   return Element{*gen++, id++};
               });

    // Add this to a K-D tree
    Tree tree(elements.begin(), elements.end());

    // Find a random point to search
    CGAL::Random rand;
    Point        search_point = Point(rand.get_double(0, size), rand.get_double(0, size));

    auto radius = 40;
    Fuzzy_circle search_circle(search_point, radius, 0.1);

    // boost::optional<Tree::Point_d> search_area = tree.search_any_point(search_circle);

    // Doing a range search on the tree KD tree space
    std::deque<Element> search_result;
    tree.search(back_inserter(search_result), search_circle);

    std::cout << "Points in within " << radius << " of " << search_point << ":\n";

    for (auto& [p, id] : search_result)
        std::cout << " - " << p << "(#" << id << ")\n";
}

With some live demo: