mercredi 28 juin 2023

Use a Polygon in Boost RTree?

I'm using an RStar tree for a project and there is a need to move to a shape that is not axis aligned. The current implementation (and documentation example) uses box, which is defined by two points and so is always axis aligned. I still want boxes but they need to be able go diagonally through the space while being narrow. My first thought was to use polygon and specify the 8 vertices all manually. However, when I try and create a tree of this type it says Polygon is not indexable. I looked at the box documentation (and Point) and don't see the indexable property there so I'm not sure which objects have it or how to implement it myself. Has anyone else done this before?

RTree Example: https://www.boost.org/doc/libs/1_82_0/libs/geometry/doc/html/geometry/spatial_indexes/rtree_quickstart.html

Box Documentation (constructed via only two points): https://www.boost.org/doc/libs/1_82_0/libs/geometry/doc/html/geometry/reference/models/model_box.html

Polygon (that I want to use): https://www.boost.org/doc/libs/1_82_0/boost/geometry/geometries/polygon.hpp

Example code with parts that don't compile commented out (just to show the gist of what I want, the goal was to write code the performed exactly the same as the example but using a shape I had more control over):

#include <iostream>
#include <vector>
#include <boost/assign/std/vector.hpp>
#include <boost/geometry.hpp>
#include <boost/geometry/algorithms/area.hpp>
#include <boost/geometry/algorithms/assign.hpp>
#include <boost/geometry/geometries/point_xy.hpp>
#include <boost/geometry/geometries/polygon.hpp>
#include <boost/geometry/io/dsv/write.hpp>

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

int main()
{
    using namespace boost::assign;
    namespace bg = boost::geometry;
    namespace bgi = boost::geometry::index;

    typedef bg::model::d2::point_xy<float> point;
    typedef bg::model::polygon<point> polygon2d;
    typedef std::pair<polygon2d , unsigned> value;

    // create the rtree using default constructor
//    bgi::rtree< value, bgi::quadratic<16> > rtree;

    // create some values
    for ( unsigned i = 0 ; i < 10 ; ++i )
    {
        // create a polygon that's the same as the box in the online example
        // https://www.boost.org/doc/libs/1_72_0/libs/geometry/doc/html/geometry/spatial_indexes/rtree_quickstart.html
        std::vector<point> points;
        points +=
                point(i + 0.0f, i + 0.0f),
                point(i + 0.0f, i + 0.5f),
                point(i + 0.5f, i + 0.0f),
                point(i + 0.5f, i + 0.5f)
                ;

        polygon2d p;
        bg::assign_points(p, points);
//        // insert new value
//        rtree.insert(std::make_pair(p, i));
    }

    // find values intersecting some area defined by a box
    polygon2d query_box;
    std::vector<point> query_points;
    query_points +=
            point(0, 0),
            point(0, 5),
            point(5, 0),
            point(5, 5)
            ;
    bg::assign_points(query_box, query_points);
//    std::vector<value> result_s;
//    rtree.query(bgi::intersects(query_box), std::back_inserter(result_s));
//
//    // find 5 nearest values to a point
//    std::vector<value> result_n;
//    rtree.query(bgi::nearest(point(0, 0), 5), std::back_inserter(result_n));
//
//    // display results
//    std::cout << "spatial query box:" << std::endl;
//    std::cout << bg::wkt<box>(query_box) << std::endl;
//    std::cout << "spatial query result:" << std::endl;
//    BOOST_FOREACH(value const& v, result_s)
//    std::cout << bg::wkt<box>(v.first) << " - " << v.second << std::endl;
//
//    std::cout << "knn query point:" << std::endl;
//    std::cout << bg::wkt<point>(point(0, 0)) << std::endl;
//    std::cout << "knn query result:" << std::endl;
//    BOOST_FOREACH(value const& v, result_n)
//    std::cout << bg::wkt<box>(v.first) << " - " << v.second << std::endl;
}


Aucun commentaire:

Enregistrer un commentaire