Re: [boost] new library (space partitioning)

Subject: Re: [boost] new library (space partitioning)
From: Adam Wulkiewicz (adam.wulkiewicz_at_[hidden])
Date: 2010-07-29 21:15:47

Simonson, Lucanus J wrote:
> This is more of an intention to write a library than a library.

Yes, you're right. Maby I was too hasty.

> Since Boost.Geometry already provides an nD point type and point concept and planned to eventually provide nD kd-trees you might want to reconsider working with them and adopting their interface design

I wanted to show you what I've got at this stage.

You're right I should adopt their nD point interface and box probably.

But, if boost::geometry::point you have in mind, coordinates are chosen 
in compile-time only(or maby I'm wrong?) and this can't be used by space 
partitioning data structures.

> By the way, the iterators over nD data structures problem is an age old debate in C++ and there are people on this list who can provide you with valuable insight on what to do and what not to do based on fifteen years of experience with trying and sometimes failing to define a good iterator based interface for nD containers.
[...]

I will appreciate any help.

> Your interface seems a little off to me, not what I was expecting.

Yes, it's not fully designed and rather low-level. It is the implmented 
interface, not the target.

> If you don't find a point within 100.0f does it return a null pointer?

Yes. Btw, 100.0f is a square distance (it should be a distance).

> Why not use a boost::optional or pass point_object by reference as first argument and return bool?  Either is better by a long shot.

The thing is, there aren't copies of point_objects in kd-tree. There are 
pointers. If there were copies, the 2nd option will be the best.

Btw, it's another issue I'm not sure about. Should copies or 
references/pointers be kept in kd-tree?

> Are you dynamically allocating the point_object you return?

No, this is a pointer to one of the point_object passed in the constructor.

> Why does point_object exist, why not just use point_type directly?

Because there may be some complex point object which shouldn't been 
point's interface implementation because it isn't a point. Fe. in Photon 
Mapping algorithm photons are used. They are point objects but aren't 
points, they have some position but may have some other nD attributes 
direction, color, etc.

But, I'm open to suggestion.

> Why does found_points exist, why not pass by reference a back inserter that accepts point_type as the first argument of find and return the number of points found?

Yes, this should be corrected. found_points should be encapsulated in 
the kd-tree. It is a container designed to take part in search of N 
point_objects in some max distance. If more than N objects are found the 
distance may be closer than max distance. This class contains 
information about the search. Without it in the interface, the number of 
points found and the max distance should be returned with the point objects.

> Don't take this feedback as criticism, I'm still excited that you plan to contribute this library and supportive of your efforts.

I expect and appreciate criticism. I'm still learning.

So, I think the searching interface might look more or less like this:
(I assume that copies are used)

[code]

// find one closest point, max distance = 10
point_object p;
bool found = kdt.find(p, point_type(...), 10);

// find max 5 closest points, initial max distance = 10
// output: number of pointsfound and distance to the furthest point
std::vector<point_object> fv;
fv.reserve(5);
std::pair<size_t, value_type> found_data = 
kdt.find(std::back_inserter(fv), point_type(...), 10, 5);
// or
value_type max_distance;
size_t found_points = kdt.find(std::back_inserter(fv), max_distance, 
point_type(...), 10, 5);

// find all points in area, initial max distance = 10
std::vector<point_object> fv2;
fv2.reserve(10);
size_t found_num = kdt.find(std::back_inserter(fv2), point_type(...), 10);

[code]

And building interface like this:

[code]

std::vector<point_object> v(100);
std::vector<point_object> v2(10);

// build kd-tree here
space::spar::kd_tree<point_object> kdt(v.begin(), v.end());

kdt.add(v2.begin(), v2.end());
kdt.add(point_object(...));
kdt.rebuild();

kdt.clear();
kdt.build(v.begin(), v.end());

[code]

Eventually:

[code]

std::vector<point_object> v(100);
std::vector<point_object> v2(10);
std::vector<point_object> v3(20);

// just add points, tree not built
space::spar::kd_tree<point_object> kdt(v.begin(), v.end());
kdt.add(v2.begin(), v2.end());
kdt.add(point_object(...));

// build kd-tree here
kdt.rebuild();

kdt.add(v3.begin(), v3.end());
kdt.add(point_object(...));
kdt.rebuild();

[code]

Eventually, rebuilding might be 'inside' add method.
Rebuild might be implemented in build.
There might be methods for removing points from given area of kd-tree.

I used rebuild(), not (rebalance()) because there are some splitting 
rules producing nice, not balanced kd-trees (see: 
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.39.8380).

Regards,
Adam