CODEWITHSUNDEEP
c++algorithmboostintervalsdiscretization
Michael Latz
Michael Latz

Reputation: 101

Interval Based Data Structure(similar to boost icl)

My goal is to represent a 3D space which is discretized inhomogeneous into bins.

A bin contains elements of an arbitrary type (the type is determined).
When adding a bin ( or the interval in which the bin lies ) and it intersects with a previous added bin both should be merged.

Right now I'm only adding bins(intervals) and afterwards I'm iterating to get the elements belonging to the right bin, but maybe in the future I might need to change elements/intervals and access elements at the same time.
The algorithm which uses this data structure should be time efficient.

Up to now i tend to use existing libraries and data structures whenever possible.
Boost::ICL seams convenient but the problem might be the merging.

Right now I'm doing this with a wrapper. F.e. with only two dimensions(Y,Z) and a set as bin:

class Set_wrapper : public boost::enable_shared_from_this<Set_wrapper>
{
public:
    Set_wrapper() :
        mValue(new boost::shared_ptr<std::set<int> >(new std::set<int>()))
    {
    }
    Set_wrapper(const std::set<int> & s)
    {
        mValue.reset(new boost::shared_ptr<std::set<int> >(new std::set<int>(s)));
    }
    void operator+=(const Set_wrapper &s)
    {
        Set_wrapper* sp = (Set_wrapper*) &s;
        (*sp->mValue)->insert((*mValue)->begin(), (*mValue)->end());
        *mValue = *(sp->mValue);
    }
    bool operator==(const Set_wrapper &s) const
    {
        return *s.mValue == *mValue;
    }

    boost::shared_ptr<boost::shared_ptr<std::set<int>>> mValue;

};

typedef interval_map<double, Set_wrapper> ZMap;

class Z_map_wrapper : public boost::enable_shared_from_this<Z_map_wrapper>
{
public:
    Z_map_wrapper() :
        mValue(new boost::shared_ptr<ZMap>(new ZMap()))
    {
    }
    Z_map_wrapper(const ZMap & s)
    {
        mValue.reset(new boost::shared_ptr<ZMap>(new ZMap(s)));
    }

    void operator+=(const Z_map_wrapper &s)
    {
        Z_map_wrapper* sp = (Z_map_wrapper*) &s;
        for(auto it = (*mValue)->begin(); it != (*mValue)->end(); ++it)
        {
          *(*sp->mValue) += std::make_pair(it->first, it->second);
        }
        *mValue = *(sp->mValue);
    }
    bool operator==(const Z_map_wrapper &s) const
    {
        return *s.mValue == *mValue;
    }

    boost::shared_ptr<boost::shared_ptr<ZMap>> mValue;

};

typedef interval_map<double, Z_map_wrapper> YMap;

This seams a little bit hacky to me :-)

The other option would be to write my own data structure using b-trees or interval trees(fe from cgal). Or adapting or extending boost::icl. But I'm not the most advanced programmer.

So my questions are:

Despite the ugliness of my approach ... is this going to work or are there certain problems that may occur?

Are there any data structures that might be more suitable?

What do i have to consider when implementing my own data structure?

Thanks very much for your help

Upvotes: 2

Views: 309

Answers (1)

sehe
sehe

Reputation: 392911

Are there any data structures that might be more suitable?

Perhaps you're looking Boost geometry Spatial Index containers (e.g. rtree)

It might be this means you have to do the merging, but at least you get the scalability requirements for free: lookups are fast, spatial queries are available and iteration is a feature.

Upvotes: 1

Related Questions