Boost库-功能介绍-Geometry-R树-空间索引

  R树是一种多级平衡树,它是B树在多维空间上的扩展。在R树中存放的数据并不是原始数据，而是这些数据的最小边界矩形（MBR），空间对象的MBR被包含于R树的叶结点中。在R树空间索引中，设计一些虚拟的矩形目标，将一些空间位置相近的目标，包含在这个矩形内，这些虚拟的矩形作为空间索引，它含有所包含的空间对象的指针。虚拟矩形还可以进一步细分，即可以再套虚拟矩形形成多级空间索引。   R+树，在R树的构造中，要求虚拟矩形一般尽可能少地重叠，并且一个空间对通常仅被一个虚拟矩形所包含。但空间对象千姿百态，它们的最小矩形范围经常重叠。 R+ 改进R树的空间索引，为了平衡，它允许虚拟矩形相互重叠，并允许一个空间目标被多个虚拟矩形所包含。   在Boost.Geometry中有R树的实现，它依赖Boost.Container, Boost.Core, Boost.Move, Boost.MPL, Boost.Range, Boost.Tuple.这些库。R树的元素都是box（矩形）和整数索引值。R树的实现在Geometry中被很好封装，如果使用它，最主要的需要掌握它的查询技巧。先介绍个简单的例子，希望读者能有个大概 的映像，源码如下：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

namespace bg = boost::geometry;
namespace bgi = boost::geometry::index;
typedef bg::model::d2::point_xy DPoint; //双精度的点
typedef bg::model::box DBox; //矩形
typedef std::pair Value;

int main()
{
	//创建R树 linear quadratic rstar三种算法
	bgi::rtree rtree;//采用quadratic algorithm，节点中元素个数最多16个

	//填充元素
	for (unsigned i = 0; i