CGAL users discussion list

["Edson Tadeu" <>]

Bernd,

On Wed, Feb 20, 2008 at 10:08 AM, Bernd Gaertner <> wrote:

Edson Tadeu wrote:
> - Is this feature really missing, or is this possible to do in some
> other class, or using some Trait somewhere else?

The Kd-tree needs a search traits class as an argument, and that traits
class provides the point class. You could therefore in principle write
your own search traits class providing "light" points (pointers to
actual points, or indices w.r.t your container). But I guess this would
be pretty cumbersome in practice since the point class needs to satisfy
a lot of requirements (experts, please correct me if I'm wrong).

I thought about this too, but this solution would be a hack, and maybe it would need more work than to simply adapt the Kd_tree class :)
 

As far as memory is concerned, using CGAL's Point_d class is fine, since
it is reference-counted. This means that no actual copying of
coordinates takes place.

I'm actually using Simple_cartesian<double>, so, no referece-counting. I think it is fine to use ref-counting for Gmpz rational points, but I don't like to use ref-counting for simple points of double, because this means it will need to allocate each point (24-byte) on the heap, implying in heap memory and performance overhead for small objects, and also in cache performance penalization because the objects are not contiguous in memory.

I'm thinking about adding a generic Point_handle to the Search_traits, and a functor object that returns the Point_t given the Point_handle. In the actual case, the Point_handle would be Point_d*, and the functor object would only dereference this pointer. The only problem is in the initialization: the user should pass this functor, and a collection of point _handles_, not the points themselves. But this can be adapted so that the interface is not broken (i.e., copy the points in case the user pass the points themselves).

 Thanks,
Edson