Boost Geometry/Spatial Query Shapes

Question

I am currently using the boost geometry/spatial index library, in order to perform range queries on 3d bounding boxes. For example I am able to get a list of all bounding boxes, that overlap a query bounding box.

The documentation (http://www.boost.org/doc/libs/1_54_0_beta1/libs/geometry/doc/html/geometry/spatial_indexes/queries.html) shows, that -- at least in 2d -- polygons can be used instead of the bounding box as a query object. Is it possible to use more advanced query shapes in 3d as well? I am thinking of objects like oriented bounding boxes, pyramids, or camera frustums. If so: how can I do that/where can I find an example for that?

Thanks

Answer 1

In short: it's not supported because for now in Boost.Geometry OOB, Pyramid and Frustum concepts are not available/supported.

But, theoretically it should be possible to perform such a query. During the query, the bgi::rtree calls adequate boolean algorithm defined in the boost::geometry namespace, e.g. if you call

rtree.query(bgi::intersects(my_geometry), out_it);

internally

bg::intersects(xxx, my_geometry);

is called, where xxx is node's bounding box or value's indexable (geometry extracted from ValueType passed by the user into the bgi::rtree, e.g. also a box or a point). So if you implemented e.g.

namespace boost { namespace geometry {

template <typename Box> inline
bool intersects(Box const& b, MyFrustum const& f)
{
    // your implementation
}

}}

theoretically it should work. Didn't tested it though.

Above:

namespace bg = boost::geometry;
namespace bgi = boost::geometry::index;

Also if you'd like to contact the developers directly you might consider subscribing to the Boost.Geometry mailing list: http://lists.boost.org/mailman/listinfo.cgi/geometry

Answer 2

I had the same problems and after chatting with @Adam he proposed the following solution which fixed the issue for me (I'm building my code on GCC and the solution above seems to compile only on Visual Studio).

#include <boost/geometry.hpp>

struct MyFrustum
{
    MyFrustum(int d) : dummy(d) {}
    int dummy;
};

namespace boost { namespace geometry {

// This will be called for Nodes and Values!

template <typename Box> inline
bool intersects(Box const& b, MyFrustum const& f)
{
    std::cout << "checking the intersection with " << f.dummy << std::endl;
    return true;
}

}}

#include <boost/geometry/index/rtree.hpp>

Apparently the order in which things are defined is important so that the compiler does not fallback to its default implementation (which produces not-yet-implemented errors).

Hope that helps, and again, thanks to Adam!

Answer 3

The other answers here are great, but I still encountered trouble in Xcode, no matter what order I included/declared things. I am posting this answer for others who can't get this to work in their environment. The other solution(s) here worked fine for me in Visual Studio 2013, but not in Xcode 5.1.1. There appears to be an overload resolution issue in that compiler. The solution is to avoid using a template type for "Box" and use all the concrete types directly, like this:

#include <boost/geometry.hpp>

namespace bg = boost::geometry;
using point3d = bg::model::point<float, 3, bg::cs::cartesian>;
using box3d = bg::model::box<point3d>;

namespace boost { namespace geometry {

    template <> inline
    bool intersects(box3d const& b, MyFrustum const& p) {
        // your implementation
        return true;
    }
}