c++ - ブーストrツリーの2次元点が特定の三角形にあるかどうかを確認する方法は?

Question

ブーストrツリーの2次元点が特定の長方形にあるかどうかを確認するにはどうすればよいですか? これは、 boost の r-treeを知るためにフォローしていた Web サイトです。

しかし、r ツリーの任意の点が特定の長方形内にあるかどうかを確認する方法がわかりません。C++ コードはかなりの価値があります。

Answer 1

私の理解が正しければ、ポイントを含む rtree を作成し、それらの少なくとも 1 つが長方形または三角形と交差するかどうかを確認したいと考えています。以下のコードは、空間クエリ ( rtree::query()) とクエリ イテレータ (rtree::qbegin()およびrtree::qend()) を使用してこれを行う方法を示しています。

ドキュメント ( http://www.boost.org/libs/geometry ) のセクションSpatial Indexesも参照してください。

どのコンパイラを使用しているかわからなかったので、以下のコードでは C++11 の機能を使用していません。たとえば C++11 では、生のループの代わりにstd::find_if()、ラムダ式のようなアルゴリズムを使用できます。

#include <iostream> // to print the results
#include <vector>   // to store the points and results

// only for convenience
#include <boost/foreach.hpp>

// Boost.Geometry headers
#include <boost/geometry.hpp>
#include <boost/geometry/geometries/geometries.hpp>
#include <boost/geometry/index/rtree.hpp>

// convenient namespaces
namespace bg = boost::geometry;
namespace bgi = boost::geometry::index;
// convenient typedefs
typedef bg::model::point<double, 2, bg::cs::cartesian> point_t;
typedef bg::model::box<point_t> box_t;
typedef bg::model::ring<point_t, true, false> ring_t; // clockwise, open
typedef bgi::rtree<point_t, bgi::linear<16> > rtree_t;

int main()
{
    // prepare a container of points
    std::vector<point_t> points;
    points.push_back(point_t(0, 0));
    points.push_back(point_t(1, 1));
    points.push_back(point_t(2, 2));
    points.push_back(point_t(3, 3));

    // build a rtree
    rtree_t rtree(points.begin(), points.end());

    // prepare a triangle (not intersecting any point)
    ring_t triangle;
    bg::append(triangle, point_t(0.5, 0.6));
    bg::append(triangle, point_t(0.5, 1.5));
    bg::append(triangle, point_t(1.4, 1.5));

    // create axis-aligned bounding box of a triangle
    box_t box = bg::return_envelope<box_t>(triangle);

    // using rtree::query()
    // rather naiive approach since all points intersecting a geometry are returned
    {
        // check if at least 1 point intersecting a box was found
        std::vector<point_t> result;
        rtree.query(bgi::intersects(box), std::back_inserter(result));
        bool test = !result.empty();
        std::cout << test << std::endl;
    }
    {
        // check if at least 1 point intersecting a triangle was found
        std::vector<point_t> result;
        rtree.query(bgi::intersects(triangle), std::back_inserter(result));
        bool test = !result.empty();
        std::cout << test << std::endl;
    }
    {
        // check if at least 1 point intersecting a triangle was found
        // similar to the above but should be faster since during a spatial query
        // a box is checked and triangle only if needed
        std::vector<point_t> result;
        rtree.query(bgi::intersects(box), std::back_inserter(result));
        bool test = false;
        BOOST_FOREACH(point_t const& pt, result)
        {
            if ( bg::intersects(pt, triangle) )
            {
                test = true;
                break;
            }
        }
        std::cout << test << std::endl;
    }

    // using iterative queries - rtree::qbegin() and rtree::qend()
    // the query is stopped when the first point is found
    {
        // check if at least 1 point intersecting a box was found
        bool test = rtree.qbegin(bgi::intersects(box)) != rtree.qend();
        std::cout << test << std::endl;
    }
    {
        // check if at least 1 point intersecting a triangle was found
        bool test = rtree.qbegin(bgi::intersects(triangle)) != rtree.qend();
        std::cout << test << std::endl;
    }
    {
        // check if at least 1 point intersecting a triangle was found
        // this version should be faster than the above because a box is checked
        // during the spatial query and triangle only if needed
        bool test = false;
        // for each Point intersecting a box
        for ( rtree_t::const_query_iterator it = rtree.qbegin(bgi::intersects(box)) ;
              it != rtree.qend() ;
              ++it )
        {
            // check if this Point also intersects a triangle
            if ( bg::intersects(triangle, *it) )
            {
                test = true;
                break;
            }
        }
        std::cout << test << std::endl;
    }
}