
Boost : 
Subject: Re: [boost] new library (space partitioning)
From: Adam Wulkiewicz (adam.wulkiewicz_at_[hidden])
Date: 20100807 09:03:55
Hi,
I couldn't decide what point concept is the best so I've implemented
kdtree building for 3 kind of points to perform some tests and to work
out the basic structure of the library, data types adaptors etc.
These are 'internal' point concepts:
1. compiletime point
point_category = compiletime_point_tag
coordinate_type
coordinate_count
coordinate_type const & get<K>()
void set<K>(v)
2. runtimetime point
point_category = runtime_point_tag
coordinate_type
coordinate_count
coordinate_type const & get(k)
void set(k, v)
3. dynamic point
point_category = dynamic_point_tag
coordinate_type
coordinate_type const & get(k)
void set(k, v)
coordinate_count()
I don't know which one is the best for space partitioning (ct or rt).
There are some 'runtime' data structures (different BSPtree, including
kdtree) and there are 'compiletime' data structures
(quadtree/octree/..., regular grid, hierarchical grid, BVH tree).
'Runtime' and 'compiletime' means specific access to the coordinates.
Building of all data structures is performed in runtime because
coordinates values are set in runtime.
Kdtree (kdtree.hpp) has 2 template parameters Point and PointAdaptor.
The default PointAdaptor is point_traits<Point>::point_adaptor.
One may write adaptor modeling any of concepts above. There are some
adaptors written allready (types.hpp). And if he doesn't want to pass
PointAdaptor each time he creates kdtree, he may specialize point_traits.
So, kdtree should work for:
userdefined types
boost::geometry  concept 1
boost::array  concept 2
std::vector, std::deque, uBlas vectors  concept 3
Example:
Lets assume that point is defined as follows:
template <typename V, size_t D>
class runtime_point
{
public:
typedef V coordinate_type;
static const size_t coordinate_count = D;
inline coordinate_type const& operator[](size_t i);
inline coordinate_type & operator[](size_t i);
private:
coordinate_type c[coordinate_count];
};
The adaptor looks like this:
template <typename Point>
struct runtime_point_indexop : private Point
{
typedef runtime_point_tag point_category;
typedef typename Point::coordinate_type coordinate_type;
static const size_t coordinate_count = Point::coordinate_count;
inline runtime_point_indexop() {}
inline runtime_point_indexop(Point const& pt) : Point(pt) {}
inline coordinate_type const& get(size_t i) const {
return Point::operator[](i); }
inline void set(size_t i, coordinate_type const& v) {
Point::operator[](i) = v; }
};
Btw, it's the default adaptor. One might write:
typedef runtime_point<float, 2> rtp;
std::vector<rtp> rtv;
// ... //
space::kdtree<rtp> rtkdt(rtv.begin(), rtv.end());
Or explicitly:
typedef space::runtime_point_indexop<rtp> rtpadapt;
space::kdtree<rtp, rtpadapt> rtkdt(rtv.begin(), rtv.end());
Or specialize point_traits in the first place:
namespace space {
template <typename T>
struct point_traits<rtp>
{
typedef runtime_point_indexop<rtp> point_adaptor;
};
}
And then:
space::kdtree<rtp> rtkdt(rtv.begin(), rtv.end());
In main.cpp there are:
 2 userdefined point types defined:
* compiletime_point (boost::geometry::point interface)
* runtime_point (point with operator[] instead of get/set)
 point_traits specializations for:
* boost::array
* std::vector
 kdtree build time tests
On my computer building takes (Core 2 Duo 2GHz, Release build, 50000
points, 2 coordinates per point, floats, full optimization):
MSVC10 GCC3.4.5
runtime_point 0.018s 0.023s
compiletime_point 0.017s 0.017s
boost::array 0.019s 0.022s
std::vector 9.5s 0.278s
runtime_point
adapted from 0.022s 0.023s
compiletime_point
compiletime_point
adapted from 0.017s 0.017s
runtime_point
Btw, the results for std::vector are wierd.
I think that it is nice to have space partitioning working for many
point types (even for std::vectors, uBlas etc). But there must be 3
different kind of algorithms for some cases.
It's not bad to convert from one representation to another. It's obvious
that it's the best to have algorithms working on compiletime points and
convert runtime points when necessary.
What do you think about it?
And what do you think about my data types, adaptors etc?
Regards,
Adam
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk