Simple Boost Geometry Spatial Index (R-Tree) Demo

I have been, in my free time, working on this diagram program. Kind of a hobby. I am using Qt for the diagram visualization part, which is fine (Qt is a wonderful framework with which to work). But, I decided I wanted to make the core of the program (the diagram model) independent of Qt, and use only C++ and [now] Boost. This would allow creation of the GUI portion in Qt (I currently use QGraphicsView), QML, wxWidgets, PyQt, OpenGL, and even C# (with some work to create bindings into the C++).

One thing that the graphics view framework in Qt does is manage lots of graphical items, and allow one to determine nearest item to the mouse; it uses Binary Space Partitioning to do this quickly. I decided that the diagram model could use its own partitioning such that any GUI platform could just query the model for items within an area, or nearest to the mouse. I wrote a simple linear search, which works fine for probably even a few hundred objects in the diagram model, but would not be scalable in the future (and maybe I shouldn’t care, but I do).

So I took a look at the Boost Geometry library; it is well suited for creating a diagram model, with rectangular nodes, multi-line connections, and connection points on nodes. The code here is my experiment with the R-Tree spatial index.

I’m not going to go through all the code, but I want to highlight how queries are done against the R-Tree. The query framework is flexible and powerful; one can use any number of predicates to help the algorithm select appropriate items in the index.

An R-Tree holds a value type, which can be just a “model” type from Geometry, such as Box (which is all I use for this demo). A value can also be a std::pair or a std::tuple. So when you store a value in the index, it takes with it any properties you find useful. Here is my value type (specifically BoxValue), and accompanying typedefs:

<code>
struct Info
{
    unsigned int id;
    unsigned char type;
};
typedef bg::model::point<unsigned int, 2, bg::cs::cartesian> Point;
typedef bg::model::box<Point> Box;
typedef std::pair<Box, Info> BoxValue;
typedef bgi::rtree<BoxValue, bgi::rstar<16,4>> RTree;
</code>

The RTree type holds BoxValue objects, each of which is paired with an Info struct that holds an identifier and type (0 for Box, 1 for Point). You can put anything you like in a value type. For instance, in a mapping application, you might put types such as “shopping mall” or “residence”, or whatever.

When you want to query the index to find certain types of items, you use predicates. Built in predicates include within and nearest. The demo also uses satisfies predicate for customizing searches.

Here is the within method in RTreeContainer:


std::vector&lt;unsigned int> RTreeContainer::within(double x, double y, double width, double height, unsigned int itemType)
{
    std::vector&lt;unsigned int> result;
    RTreeContainer::Point p1(x, y);
    RTreeContainer::Point p2(x+width, y+height);
    RTreeContainer::Box box_region(p1, p2);


    std::function&lt;bool(RTreeContainer::BoxValue const&amp;)> func;


    if ( itemType == 0 )
        func = std::bind(&amp;IsRect, _1);
    else
        func = std::bind(&amp;IsPoint, _1);


    for ( RTree::const_query_iterator it = mRTree.qbegin(bgi::within(box_region) &&
bgi::satisfies(func));
it != mRTree.qend(); ++it )
    {
        result.push_back(it->second.id);
    }
    return result;
}

Note the qbegin statement in the for loop. It takes a predicate, or this in this case two predicate strung together with &&. The within predicate accepts a region and finds everything inside that region. The satisfies predicate accepts a function object (you could use a lambda here, I used bind to create a function object).

I created three predicates:

bool IsPoint(RTreeContainer::BoxValue const& v)
{
    return v.second.type == 1;
}
bool IsRect(RTreeContainer::BoxValue const& v)
{
    return v.second.type == 0;
}
bool IsWithinRange(RTreeContainer::BoxValue const& v, double x, double y, double distance)
{
    return bg::distance(v.first, RTreeContainer::Point(x, y)) < distance;
}

IsPoint and IsRect check the type of a BoxValue object and return true if that object is a point or a rect type (both items are actually Geometry Box items, I am using the type to identify them as I see fit). IsWithinRange is used by the nearest method; as you move your mouse closer to an object on the QGraphicsScene, it will be highlighted. The query methods return a std::vector<unsigned int>, containing the unique id’s of found items. This information is used to highlight the items.

Please feel free to ask me any questions, and I welcome constructive criticism and comments. Maybe even hit like!

Advertisement