k-d tree search with projection traits

[ipadjen]

Hello,

I was wondering if it was possible to conduct a 2D spatial search using projected 3D points? Tried to work my way around with k-d tree using Search_traits_2 and Projection_traits_xy_3 but I couldn't do it.

[sloriot]

Some types are missing in Projection_traits_xy_3 so it's not a model of SearchGeomTraits_2. I think an easy option is to use the Search_traits_adaptor with a property map doing the projection on the fly.

Something like the following for the map:

template<class K>
struct Projection_xy_property_map
{
  typedef typename K::Point_3 key_type;
  typedef typename K::Point_2 value_type;
  typedef value_type reference;
  typedef boost::readable_property_map_tag category;


  friend value_type get(Projection_xy_property_map<K>, const key_type& k)
  {
    return value_type(k.x(), k.y());
  }
};

and the following typedefs:

typedef CGAL::Search_traits_2<Kernel>Traits_base;
typedef CGAL::Search_traits_adapter<Kernel::Point_3,Projection_xy_property_map<Kernel>,Traits_base> Traits;

Then you can adapt this example with the aforementioned types.

[ipadjen]

Great, thank you for the quick reply!

[sloriot]

If you feel like writing a small example, we can include it in the release :)

[ipadjen]

Sounds good! Will make one soon

[afabri]

@sloriot shall we nevertheless make it a feature request issue to enrich the projection traits class, or is there a fundamental problem?

[sloriot]

we sure can but I'm not sure how time consuming it is

[ipadjen]

If it's not trivial, maybe the work with projections/search trees can be expanded a bit and formed into a GSOC project?

[sloriot]

You'd be interested as a GSoC contributor ?

[ipadjen]

In principle, yes. It's something I would have to discuss about with my supervisors.