Boost库功能介绍GeometryR树空间索引

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include namespace bg &＃61; boost::geometry;
namespace bgi &＃61; boost::geometry::index;
typedef bg::model::d2::point_xy<double, boost::geometry::cs::cartesian> DPoint; //双精度的点
typedef bg::model::box<DPoint> DBox; //矩形
typedef std::pair<DBox, unsigned> Value;int main()
{//创建R树 linear quadratic rstar三种算法bgi::rtree<Value, bgi::quadratic<16>> rtree;//采用quadratic algorithm&＃xff0c;节点中元素个数最多16个//填充元素for (unsigned i &＃61; 0; i < 10; &＃43;&＃43;i){DBox b(DPoint(i &＃43; 0.0f, i &＃43; 0.0f), DPoint(i &＃43; 0.5f, i &＃43; 0.5f));rtree.insert(std::make_pair(b, i));//r树插入外包围矩形 i为索引}//查询与矩形相交的矩形索引DBox query_box(DPoint(0, 0), DPoint(5, 5));std::vector<Value> result_s;rtree.query(bgi::intersects(query_box), std::back_inserter(result_s));//查找5个离点最近的索引std::vector<Value> result_n;rtree.query(bgi::nearest(DPoint(0, 0), 5), std::back_inserter(result_n));//显示值std::cout << "spatial query box:" << std::endl;std::cout << bg::wkt<DBox>(query_box) << std::endl;std::cout << "spatial query result:" << std::endl;BOOST_FOREACH(Value const& v, result_s)std::cout << bg::wkt<DBox>(v.first) << " - " << v.second << std::endl;std::cout << "knn query point:" << std::endl;std::cout << bg::wkt<DPoint>(DPoint(0, 0)) << std::endl;std::cout << "knn query result:" << std::endl;BOOST_FOREACH(Value const& v, result_n)std::cout << bg::wkt<DBox>(v.first) << " - " << v.second << std::endl;return 0;
}


  在源代码中&＃xff0c;有详细的注释&＃xff0c;请读者先阅读&＃xff0c;从中可以看出能够非常的简单的构建一颗R树&＃xff0c;然后非常方便的往R树里添加矩形索引。另外一方面Geometry中提供的R树功能非常多&＃xff0c;主要包括3类方式找到目标对象。

1.空间几何关系

  上图是官方提供的一张图&＃xff0c;表示查询的几何关系。查询样式如下&＃xff1a;

rt.query(index::contains(box), std::back_inserter(result));
rt.query(index::covered_by(box), std::back_inserter(result));
rt.query(index::covers(box), std::back_inserter(result));
rt.query(index::disjont(box), std::back_inserter(result));
rt.query(index::intersects(box), std::back_inserter(result));
rt.query(index::overlaps(box), std::back_inserter(result));
rt.query(index::within(box), std::back_inserter(result));


2.最近邻查询

std::vector<Value> returned_values;
Point pt(/*...*/);
rt.query(bgi::nearest(pt, k), std::back_inserter(returned_values));//返回最近的k个空间索引Segment seg(/*...*/);
rt.query(bgi::nearest(seg, k), std::back_inserter(returned_values));


3.函数查询

bool is_red(Value const& v) //函数
{return v.is_red();
}struct is_red_o //函数对象
{template <typename Value>bool operator()(Value const& v){return v.is_red();}
}
rt.query(index::intersects(box) && index::satisfies(is_red),std::back_inserter(result));
rt.query(index::intersects(box) && index::satisfies(is_red_o()),std::back_inserter(result));
//lambda表达式
#ifndef BOOST_NO_CXX11_LAMBDAS
rt.query(index::intersects(box) && index::satisfies([](Value const& v) { return v.is_red(); }),std::back_inserter(result));
#endif


  R树在几何计算中&＃xff0c;最常用的还是空间几何关系查询&＃xff0c;同时查询的第一个条件参数还可以采用&&运算符来组合条件&＃xff0c;单个可采用非(!)来表示相反的条件&＃xff0c;形式如下所示&＃xff1a;

//Pred1 && Pred2 && Pred3 && ....
rt.query(index::intersects(box1) && !index::within(box2),std::back_inserter(result));
rt.query(index::intersects(box1) && !index::within(box2) && index::overlaps(box3),std::back_inserter(result));index::query(rt, index::nearest(pt, k) && index::within(b), std::back_inserter(returned_values));
BOOST_FOREACH(Value & v, rt | index::adaptors::queried(index::nearest(pt, k) && index::covered_by(b))); // do something with v


  最后简单介绍下一个多边形构建R树的例子&＃xff0c;源代码如下所示&＃xff1a;

#include
#include
#include
#include
#include
#include
#include
#include
#include namespace bg &＃61; boost::geometry;
namespace bgi &＃61; boost::geometry::index;
typedef bg::model::point<double, 2, bg::cs::cartesian> DPoint;
typedef bg::model::box<DPoint> DBox;
typedef bg::model::polygon<DPoint, false, false> DPolygon; // ccw, open polygon
typedef std::pair<DBox, unsigned> DValue;int main()
{std::vector<DPolygon> polygons;//构建多边形for (unsigned i &＃61; 0; i < 10; &＃43;&＃43;i){//创建多边形DPolygon p;for (float a &＃61; 0; a < 6.28316f; a &＃43;&＃61; 1.04720f){float x &＃61; i &＃43; int(10 * ::cos(a))*0.1f;float y &＃61; i &＃43; int(10 * ::sin(a))*0.1f;p.outer().push_back(DPoint(x, y));}//插入polygons.push_back(p);}//打印多边形值std::cout << "generated polygons:" << std::endl;BOOST_FOREACH(DPolygon const& p, polygons)std::cout << bg::wkt<DPolygon>(p) << std::endl;//创建R树bgi::rtree< DValue, bgi::rstar<16, 4> > rtree; //最大最小//计算多边形包围矩形并插入R树for (unsigned i &＃61; 0; i < polygons.size(); &＃43;&＃43;i){//计算多边形包围矩形DBox b &＃61; bg::return_envelope<DBox>(polygons[i]);//插入R树rtree.insert(std::make_pair(b, i));}//按矩形范围查找DBox query_box(DPoint(0, 0), DPoint(5, 5));std::vector<DValue> result_s;rtree.query(bgi::intersects(query_box), std::back_inserter(result_s));//5个最近点std::vector<DValue> result_n;rtree.query(bgi::nearest(DPoint(0, 0), 5), std::back_inserter(result_n));// note: in Boost.Geometry the WKT representation of a box is polygon// note: the values store the bounding boxes of polygons// the polygons aren&＃39;t used for querying but are printed// display resultsstd::cout << "spatial query box:" << std::endl;std::cout << bg::wkt<DBox>(query_box) << std::endl;std::cout << "spatial query result:" << std::endl;BOOST_FOREACH(DValue const& v, result_s)std::cout << bg::wkt<DPolygon>(polygons[v.second]) << std::endl;std::cout << "knn query point:" << std::endl;std::cout << bg::wkt<DPoint>(DPoint(0, 0)) << std::endl;std::cout << "knn query result:" << std::endl;BOOST_FOREACH(DValue const& v, result_n)std::cout << bg::wkt<DPolygon>(polygons[v.second]) << std::endl;return 0;
}


4.作者寄语

  合理的脚本代码可以有效的提高工作效率&＃xff0c;减少重复劳动。