Как проверить, находится ли какая-либо 2-мерная точка в ускоренном дереве в данном треугольнике?

Если я правильно понимаю, вы хотите иметь дерево, содержащее точки, и проверить, пересекает ли хотя бы один из них прямоугольник или треугольник. Код ниже показывает, как это можно сделать с помощью пространственных запросов (rtree::query()) и итераторы запросов (rtree::qbegin() а также rtree::qend()).

Смотрите также документацию (http://www.boost.org/libs/geometry), раздел пространственная Индексы.

Я не знал, какой компилятор вы используете, поэтому приведенный ниже код не использует никаких функций 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;
}
}