Re: [boost] new library (space partitioning)

Subject: Re: [boost] new library (space partitioning)
From: Simonson, Lucanus J (lucanus.j.simonson_at_[hidden])
Date: 2010-07-29 15:07:13

Adam Wulkiewicz wrote:
> Sorry, I didn't write what is it called. It's space-0.1.zip.

I wish you had just posted the readme at the outset:

--------------------README.txt from space-0.1.zip--------------------------
It's a preliminary version of library I've called Space. As you can see it's _not_ fully operational.
The main reason is that I wanted to work out some basic concepts and interfaces before I'll go further.

Contents
1. Parts of the library
2. The interfaces and uses
3. Additional notes

1. Parts of the library:

space::ag - namespace containing compile-time linear algebra, it's not required by the other parts of the library but it's good supplement.
        - angle, vector, point, matrix, square_matrix - nD
        - orientation, rotation_matrix - 2/3D
        - rotation_quaternion - 3D

space::kd - nD containers, types and containers may be used in space::spar containers(in regular grid and regular tree)
        types.hpp contains nD versions of values
        deque, vector which are recursive_container(s) - nD containers which are internally fe. std::vector of std::vectors of std::vectors...
        dynamic_array - nD container which is internally a single std::vector
                * the name should be changed
        static_array - recursive const size container
                * it might be a derivation of recursive_container with boost::array as a basic type
                * it has additional operators to make possible dereferencing

        All containers has nD resize, insert, erase etc.
        The iterator is replaced by enumerator and it iterates in nD area of elements.
        There is a line_enumerator also which iterates by the elements on a nD line between two elements.

space::spar - nD space partitioning containers
        concepts
                point_type concept
                        defined type value_type
                        static member dimension
                        operator[]() returning nth coordinate
                point_object concept
                        defined point_type
                        position() method returning object of point_type
                volumetric_object concept
                        defined point_type
                        aabb() method returning object of space::spar::aabb<point_type>
                If there will be structures using on bounding spheres or other bounding objects there should be more volumetric objects concepts.
        aabb - nD AABB
                it may be tested for intersection with a ray (for now ray is defined by origin point and direction vector, both are an implementation of point_type concept (it should be fe. coordinates concept in this case))
        point_node_kd_tree - kd-tree for point objects
                internally has heap-like structure(all nodes in std::vector)
                points are the nodes, but only pointers are stored
                points passed by iterators in the constructor or build method
                splitting plane - position of the middle point - it is left balanced
                no addition of new points/rebalancing
                queries:
                        closest point
                        precise number of closest points
                        all points from a region (nD hypersphere)
        point_kd_tree - kd-tree for point objects
                internally has structure of a linked nodes binary tree
                points are stored in containers in nodes
                containers are in leaf nodes and in internal nodes (which is bad)
                points passed by iterators in the constructor or build method
                splitting plane - half of the longest edge of current node aabb - not balanced
                        this is just one of the algorithms because I want to implement different ones
                        fe. an algorithm of building a tree with clipping of empty space (some articles mentions that this gives good results)
                no addition of new points/rebalancing
                queries:
                        closest point
                        precise number of closest points
                        all points from a region (nD hypersphere)
        kd_tree - kd-tree for volumetric objects
                internally has structure of a linked nodes binary tree
                objects are stored in containers in nodes
                containers are in leaf nodes and in internal nodes (the same nodes are used in kd_tree and point_kd_tree)
                splitting plane - half of the longest edge of current node aabb - not balanced
                        this is just one of the algorithms because I want to implement different ones
                        fe. V. Havran proposed an algorithm of kd-tree building with cutting of empty space and automatical splitting stop detection which has O(NlogN) complexity,
                no addition of new points/rebalancing
                no queries
        regular_tree - nD generalization of 2Dquadtree/3Doctree
                internally has structure of a linked nodes, each node has 2^n children
                objects are stored in containers in nodes
                containers are in leaf nodes and in internal nodes (again)
                splitting plane - halves of the edges of current node aabb
                        this is just one of the algorithms
                no rebuilding/rebalancing
                no queries
        regular_grid - nD not fully functional regular grid which should be called regular_grid_base
                it is a container which has a dimension and i placed in space (has aabb) and contains not infinitesimal cells,
                it is able to do some operations on subspaces(ranges) of this grid

2. The interfaces and uses

It's an example where point_node_kd_tree is used but you may change it to space::spar::point_kd_tree as well.

#include <vector>
#include <boost/foreach.hpp>
#include <space/spar.hpp>

struct point
{
        typedef float value_type;
        static const size_t dimension = 3;

        point() {}
        point(float a, float b, float c) { arr[0] = a; arr[1] = b; arr[2] = c; }
        const float & operator[](size_t i) const { return arr[i]; }
        float & operator[](size_t i) { return arr[i]; }

        float arr[3];
};

struct point_object
{
        typedef point point_type;

        const point_type & position() const { return p; }

        point_type p;
};

int main()
{
        std::vector<point_object> points(100);
        BOOST_FOREACH(point_object &p, points)
        {
                p.p = point(rand() % 100, rand() % 100, rand() % 100);
        }

        space::spar::point_node_kd_tree<point_object> kdt(points.begin(), points.end());

        point_object *p = kdt.find(point(50.0f, 50.0f, 50.0f), 100.0f);

        found_points<point_object> fp(3);
        kdt.find(fp, point(50.0f, 50.0f, 50.0f), 400.0f);

        std::vector<point_object*> fpts;
        fpts.reserve(fp.size());
        fp.get(std::back_inserter(fpts));

        return 0;
}

3. Additional notes

There is a lot of additional things to do in this matter:
- different trees building algorithms,
- different trees structures,
- parallel building,
- parallel queries,
- incremental queries,
- ray queries,
- volume queries,
- use of pool allocators,
- etc.

But first, I need to know, what do you think about this?
Is it a good starting point?
If not, what are your suggestions?
--------------------------------------END of README.txt-------------------------------------

I'm a little dissapointed that there is no insertion or rebalancing on any of the trees.  This is more of an intention to write a library than a library.  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, which was arrived at after literally years of (sometimes heated) debate on this list about what the best design for the interfaces should be.  The argument that what you are doing is math and not geometry doesn't really hold water in my opinion.  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.

Your interface seems a little off to me, not what I was expecting.  Why does find return a pointer to point_object?  If you don't find a point within 100.0f does it return a null pointer?  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.  Are you dynamically allocating the point_object you return?  Why does point_object exist, why not just use point_type directly?  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?  There is some complexity to your interface design that needs to be justified with your rationale for making these design decisions.

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

Regards,
Luke