c++ - 如何检查boost r-tree中的任何2d点是否在给定的三角形中？

Question

如何检查boost r-tree中的任何二维点是否在给定的矩形中？这是我在 boost中了解 r-tree 的网站。

但是我很困惑如何检查 r-tree 中的任何点是否位于给定的矩形内。C ++代码将是可观的。

Answer 1

R-trees 仅适用于矩形。

如果您将非矩形数据存储在 r-tree 中，它只会为您提供您需要更详细检查（“验证”、“验证”、“优化”）的候选对象。

毕竟，整个 R-tree 的想法是用更简单（有效存储和管理）边界框的几何形状来逼近对象。

也许 boost 库为此提供了一些帮助功能，但可能在 rtree 包之外，在几何包本身中。

Answer 2

如果我理解正确，您希望拥有一个包含点的 rtree，并检查其中至少一个是否与矩形或三角形相交。下面的代码展示了如何使用空间查询 ( rtree::query()) 和查询迭代器 (rtree::qbegin()和rtree::qend()) 来完成此操作。

另请参阅文档 ( http://www.boost.org/libs/geometry )，空间 索引部分。

我不知道您使用的是哪个编译器，所以下面的代码不使用任何 C++11 功能。例如，在 C++11 中，您可以使用诸如std::find_if()lambda 表达式之类的算法来代替原始循环。

#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;
    }
}