CGAL users discussion list

["Edson Tadeu" <>]

Hi,

On Wed, Feb 20, 2008 at 11:23 AM, Bernd Gaertner <> wrote:

I think it's the other way around: the former is well in line with the
generic programming paradigm, while the latter is a hack :-) In reality,
both are hacks, since the issue is not specific to Kd-tress. As soon as
some algo/data structure is parameterized in some way with points,
somebody might want to pass handles/pointers instead. The cleaner
solution would then be to use the adaptable kernel mechanism and build a
kernel whose point class is just a handle or pointer class. The
applicability of this is not restricted to Kd-trees, then. I encourage
you to contribute such a kernel.

Bernd.

But to correctly extend a class in the G.P. paradigm, you must have the right extension point. In this case, the right extension point would be a template parameter (or a trait type) over a Point Collection Concept (or Point Map, or Point Function), but this is not available.
I think that the Point Concept ("Point_d") is for points only... to simulate a Point using a handle plus a container pointer plus adaptor methods is to abuse this concept.

Let's suppose I create a (very simplified) point structure like this:

struct PointHandle {
  size_t point_index;
  std::vector<Point_3>* point_container;
};
// + zillions of methods to adapt this structure to work like a point (difference, distance, etc, etc)

Then, if I have an array with 1000000 points, I would be repeating the *point_container pointer 1000000 times in memory unnecessarily. Ok, I could do a hack for this, but it would be a hack over a hack... and later it would need a hack over a hack over hack... etc...

The problem is that the algorithm is restricting the points container to a fixed type (std::vector), and is restricting the point handle to a fixed type (Point_d*). Suppose, for example, that my points are not even in memory... I have a functor that creates them on the fly, given a n integer handle:

struct My_spring_points {
  inline Point_d operator()(int handle) const {
    return Point_d( cos(handle / 30.0 * PI), sin(handle / 30.0 * PI), handle / 100.0);
  }
};

If the Points Collection were parametrized, I could pass an object with this type, and it would work accordingly, using 0 extra bytes.
So, the be well in line with the generic programming paradigm, shouldn't we make this algorithm more generic, putting these other types in the Search_traits?

Cheers,
 Edson