C++模板特化实战：在使用开源库boost::geometry::index::rtree时，用特化来让其支持自己的数据类型

 用自己定义的数据结构作为rtree的key。

// rTree的key
struct OverlapKey
{using BDPoint = boost::geometry::model::point<double, 3, boost::geometry::cs::cartesian>; //双精度的点using MyRTree = boost::geometry::index::rtree<OverlapKey, boost::geometry::index::linear<16> >;BDPoint GetKey() { return key; }std::wstring id;//keyBDPoint key;std::list<DgnHistory::FarElementID> mCurveLst;//         std::greater<double>>, std::less<int>> mData;/*--------------------------------------------------------------------------------------**//*** 将对方向相同的曲线（一般情况下是直线）进行分类，                                            *                                                            Created by Simon.Zou on 9/2021+---------------+---------------+---------------+---------------+---------------+-----------*///std::set<DataPtr, Data::DataSort> mData; void AddData(DgnHistory::FarElementID data){mCurveLst.push_back(data);}OverlapKey(){boost::uuids::uuid a_uuid = boost::uuids::random_generator()(); // 这里是两个() ，因为这里是调用的 () 的运算符重载id = boost::uuids::to_wstring(a_uuid);key.set<0>(0);key.set<1>(0);key.set<2>(0);//ICurvePrimitivePtr = NULL;}OverlapKey(const OverlapKey& r){*this = r;}OverlapKey(OverlapKey&& r){this->id = r.id;this->key = r.key;mCurveLst = r.mCurveLst;r.id = L"";r.key.set<0>(0);r.key.set<1>(0);r.key.set<2>(0);r.mCurveLst.clear();}OverlapKey& operator=(const OverlapKey& r){this->id = r.id;this->key = r.key;mCurveLst = r.mCurveLst;//this->ICurvePrimitivePtr = r.ICurvePrimitivePtr;return *this;}OverlapKey& operator=(OverlapKey&& r){this->id = r.id;this->key = r.key;mCurveLst = r.mCurveLst;//this->ICurvePrimitivePtr = r.ICurvePrimitivePtr;r.id = L"";r.key.set<0>(0);r.key.set<1>(0);r.key.set<2>(0);r.mCurveLst.clear();return *this;}//rTree.remove(...)函数会用到bool operator == (const OverlapKey& o) const{bool b1 = fabs(key.get<0>() - o.key.get<0>()) < 0.001;bool b2 = fabs(key.get<1>() - o.key.get<1>()) < 0.001;bool b3 = fabs(key.get<2>() - o.key.get<2>()) < 0.001;if (b1 && b2 && b3)return true;_SaveLog_Info_return_false("return false")}
};/*--------------------------------------------------------------------------------------**//**
*  为了能把自己的数据结构OverlapKey用到boost的rtree里，创建此特化                                           
*                                                            Created by Simon.Zou on 9/2021
+---------------+---------------+---------------+---------------+---------------+-----------*/
template <>
struct boost::geometry::index::indexable<OverlapKey>
{typedef OverlapKey::BDPoint result_type; //这个不能缺少const OverlapKey::BDPoint& operator()(const OverlapKey& c) const{return c.key;}
};

/*--------------------------------------------------------------------------------------+
|   HchxAlgorithm.cpp
|
+--------------------------------------------------------------------------------------*/
#include "HchxUnitTestPch.h"#include "gtest\gtest.h"using namespace std;
using namespace boost;USING_NAMESPACE_BENTLEY_ECOBJECT;#include <cmath>
#include <vector>
#include <iostream>
#include <boost/geometry.hpp>
#include <boost/geometry/geometries/point.hpp>
#include <boost/geometry/geometries/box.hpp>
#include <boost/geometry/geometries/point_xy.hpp>
#include <boost/geometry/geometries/polygon.hpp>
#include <boost/geometry/index/rtree.hpp>
#include <boost/assign/std/vector.hpp>
#include <boost/geometry/algorithms/area.hpp>
#include <boost/geometry/algorithms/assign.hpp>
#include <boost/geometry/io/dsv/write.hpp>
#include <boost/foreach.hpp>bool boost_test1()
{namespace bg = boost::geometry;namespace bgi = 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 polygontypedef std::pair<DBox, unsigned> DValue;std::vector<DPolygon> polygons;//构建多边形for (unsigned i = 0; i < 10; ++i){//创建多边形DPolygon p;for (float a = 0; a < 6.28316f; a += 1.04720f){float x = i + int(10 * ::cos(a))*0.1f;float y = i + 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 = 0; i < polygons.size(); ++i){//计算多边形包围矩形DBox b = 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'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 true;
}void boost_test2()
{namespace bg = boost::geometry;namespace bgi = boost::geometry::index;typedef bg::model::d2::point_xy<double, boost::geometry::cs::cartesian> DPoint; //双精度的点typedef bg::model::polygon<DPoint, false, false> DPolygon; // ccw, open polygontypedef bg::model::box<DPoint> DBox; //矩形typedef std::pair<DBox, unsigned> Value;//创建R树 linear quadratic rstar三种算法bgi::rtree<Value, bgi::quadratic<16>> rtree;//采用quadratic algorithm，节点中元素个数最多16个//bgi::rtree<Value, bgi::rstar<32>> rtree;//采用quadratic algorithm，节点中元素个数最多16个//bgi::rtree<Value, bgi::linear<32>> rtree;//采用quadratic algorithm，节点中元素个数最多16个//bgi::rtree<std::pair<DBox, std::string>, bgi::rstar<16> > rtree;//填充元素
// 	for (unsigned i = 0; i < 10; ++i)
// 	{
// 		DBox b(DPoint(i + 0.0f, i + 0.0f), DPoint(i + 0.5f, i + 0.5f));
// 		rtree.insert(std::make_pair(b, i));//r树插入外包围矩形 i为索引
// 	}DBox b1(DPoint(0.0f, 0.0f), DPoint(1.0f, 1.0f));rtree.insert(std::make_pair(b1, 0));//r树插入外包围矩形 i为索引DBox b2(DPoint(-1.0f, -1.0f), DPoint(0.0f, 0.0f));rtree.insert(std::make_pair(b2, 1));//r树插入外包围矩形 i为索引DBox b3(DPoint(0.0f, 0.0f), DPoint(1.5f, 1.5f));rtree.insert(std::make_pair(b3, 2));//r树插入外包围矩形 i为索引//查询与矩形相交的矩形索引DBox query_box(DPoint(-0.1f, -0.1f), DPoint(1.2f, 1.2f));std::vector<Value> result_s;//https://www.boost.org/doc/libs/1_54_0/libs/geometry/doc/html/geometry/spatial_indexes/queries.html//查出与query_box相交的所有box。可以overlaps，也可以是包含关系。//rtree.query(bgi::intersects(query_box), std::back_inserter(result_s));//被query_box完全覆盖的所有box//rtree.query(bgi::covered_by(query_box), std::back_inserter(result_s));//查出所有包含query_box的box。注意是“包含”。如果仅仅是相交，是不会放到结果集中的。rtree.query(bgi::covers(query_box), std::back_inserter(result_s)); //查出与query_box不相交的集合。这些集合和query_box没有任何重叠。//rtree.query(bgi::disjoint(query_box), std::back_inserter(result_s));//查出与query_box相交的集合。与intersects不同的是：如果query_box在box内部，那么这个box不会被记录到结果集。//rtree.query(bgi::overlaps(query_box), std::back_inserter(result_s));//查到被query_box完全包含的box。不包含那种相交的//rtree.query(bgi::within(query_box), std::back_inserter(result_s));//rtree.bgi::query(bgi::intersects(box), std::back_inserter(result));/*--------------------------------------------------------------------------------------**//***  支持ring和polygon                                       Commented by Simon.Zou on 5/2021+---------------+---------------+---------------+---------------+---------------+-----------*///查找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;
}void boost_test3()
{using namespace boost::assign;typedef boost::geometry::model::d2::point_xy<double> point_xy;// Create points to represent a 5x5 closed polygon.std::vector<point_xy> points;points +=point_xy(0, 0),point_xy(0, 5),point_xy(5, 5),point_xy(5, 0),point_xy(0, 0);// Create a polygon object and assign the points to it.boost::geometry::model::polygon<point_xy> polygon;boost::geometry::assign_points(polygon, points);std::cout << "Polygon " << boost::geometry::dsv(polygon) <<" has an area of " << boost::geometry::area(polygon) << std::endl;
}/*--------------------------------------------------------------------------------------**//**
*  用polygon来查询                                       Commented by Simon.Zou on 5/2021
+---------------+---------------+---------------+---------------+---------------+-----------*/
void boost_test4()
{namespace bg = boost::geometry;namespace bgi = boost::geometry::index;typedef bg::model::d2::point_xy<double, boost::geometry::cs::cartesian> DPoint; //双精度的点typedef bg::model::polygon<DPoint, false, false> DPolygon; // ccw, open polygontypedef bg::model::box<DPoint> DBox; //矩形typedef std::pair<DBox, unsigned> Value;//创建R树 linear quadratic rstar三种算法bgi::rtree<Value, bgi::quadratic<16>> rtree;//采用quadratic algorithm，节点中元素个数最多16个//bgi::rtree<Value, bgi::rstar<32>> rtree;//采用quadratic algorithm，节点中元素个数最多16个//bgi::rtree<Value, bgi::linear<32>> rtree;//采用quadratic algorithm，节点中元素个数最多16个//bgi::rtree<Value, bgi::rstar<16>> rtree;//采用quadratic algorithm，节点中元素个数最多16个//bgi::rtree<std::pair<DBox, std::string>, bgi::rstar<16> > rtree;//填充元素
// 	for (unsigned i = 0; i < 10; ++i)
// 	{
// 		DBox b(DPoint(i + 0.0f, i + 0.0f), DPoint(i + 0.5f, i + 0.5f));
// 		rtree.insert(std::make_pair(b, i));//r树插入外包围矩形 i为索引
// 	}DBox b1(DPoint(0.0f, 0.0f), DPoint(1.0f, 1.0f));rtree.insert(std::make_pair(b1, 0));//r树插入外包围矩形 i为索引DBox b2(DPoint(-1.0f, -1.0f), DPoint(0.0f, 0.0f));rtree.insert(std::make_pair(b2, 1));//r树插入外包围矩形 i为索引DBox b3(DPoint(0.0f, 0.0f), DPoint(1.5f, 1.5f));rtree.insert(std::make_pair(b3, 2));//r树插入外包围矩形 i为索引//查询与矩形相交的矩形索引DBox query_box(DPoint(-0.1f, -0.1f), DPoint(1.2f, 1.2f));std::vector<Value> result_s;/*--------------------------------------------------------------------------------------**//***  支持ring和polygon                                       Commented by Simon.Zou on 5/2021+---------------+---------------+---------------+---------------+---------------+-----------*/using namespace boost::assign;typedef boost::geometry::model::d2::point_xy<double> point_xy;// Create points to represent a 5x5 closed polygon.std::vector<point_xy> points;points += point_xy(0.1, 0.1), point_xy(0.1, 5),point_xy(2.5, 5),point_xy(5, 2.5),point_xy(5, 0.1),point_xy(0.1, 0.1);// Create a polygon object and assign the points to it.boost::geometry::model::polygon<point_xy> polygon;DPolygon p;boost::geometry::assign_points(p, points);rtree.query(bgi::intersects(p), 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;
}//创建多边形
void boost_test5()
{typedef boost::geometry::model::point<float, 2, boost::geometry::cs::cartesian> Point;typedef boost::geometry::model::polygon<Point, false, false> Polygon; // ccw, open polygon//创建多边形Polygon p;for (float a = 0; a < 6.28316f; a += 1.04720f){float x = int(10 * ::cos(a))*0.1f;float y = int(10 * ::sin(a))*0.1f;p.outer().push_back(Point(x, y));}
}//创建多边形
void boost_test6()
{namespace bg = boost::geometry;typedef bg::model::d2::point_xy<double> DPoint; //双精度的点typedef bg::model::segment<DPoint> DSegment; //线段typedef bg::model::linestring<DPoint> DLineString; //多段线typedef bg::model::box<DPoint> DBox; //矩形//这里的ring就是我们通常说的多边形闭合区域(内部不存在缕空)，模板参数为true，表示顺时针存储点，为false，表示逆时针存储点,坐标系为正常向上向右为正的笛卡尔坐标系typedef bg::model::ring<DPoint, false> DRing; //环typedef bg::model::polygon<DPoint, false> DPolygon; //多边形#define A_PI 3.141592653589793238462643383279502884197//创建点DPoint pt1(0, 0), pt2(10, 10);//创建线段DSegment ds;ds.first = pt1;ds.second = pt2;//创建多段线DLineString dl;dl.push_back(DPoint(0, 0));dl.push_back(DPoint(15, 8));dl.push_back(DPoint(8, 13));dl.push_back(DPoint(13, 16));//创建矩形DBox db(pt1, pt2);//创建环DRing dr;dr.push_back(DPoint(0, 0));dr.push_back(DPoint(1, 2));dr.push_back(DPoint(3, 4));dr.push_back(DPoint(5, 6));//创建多边形DPolygon p;for (double a = 0; a < 2 * A_PI; a += 2 * A_PI / 18){double x = ::cos(a)*10.0f;double y = ::sin(a)*10.0f;p.outer().push_back(DPoint(x, y));}
}/*
如何让rtree用自己的数据。
看来最重要的操作是用indexable来让rtree知道，如何在你的结构体里得到point？
https://stackoverflow.com/questions/64179718/storing-or-accessing-objects-in-boost-r-tree
ou can store any type in a rtree, you just have to tell Boost how to get the coordinates out.So the first step is to make a type with both a index and point:struct CityRef {
size_t index;
point location;
};You can specialize boost::geometry::index::indexable to give Boost a way to find the point you've put in there:template <>
struct bgi::indexable<CityRef>
{
typedef point result_type;
point operator()(const CityRef& c) const { return c.location; }
};Then you can use your type in place of point when declaring your rtree:typedef bgi::rtree< CityRef, bgi::linear<16> > rtree_t;And when you iterate, the iterator will refer to your type instead of point:for ( rtree_t::const_query_iterator
it = rtree.qbegin(bgi::nearest(pt, 100)) ;
it != rtree.qend() ;
++it )
{
// *it is a CityRef, do whatever you want
}Here is a demo using that example with another type: https://godbolt.org/z/zT3xcf*/namespace bg = boost::geometry;
namespace bgi = boost::geometry::index;
typedef bg::model::point<double, 2, bg::cs::cartesian> boostPoint2d;
struct CityRef {size_t index;double index2;boostPoint2d location;//rtree在插入数据以及检索时，没走到这个函数，说明rtree内部是用指针的
//     CityRef& operator = (const CityRef& r)
//     {
//         index = r.index;
//         index2 = r.index2;
//         location = r.location;
//         return *this;
//     }//rtree在插入数据以及检索时，没走到这个函数
//     bool operator == (const CityRef& r) const
//     {
//         bool b1 = index == r.index;
//         bool b2 = index2 == r.index2;
//         bool b3 = (location.get<0>() == r.location.get<0>() && 
//             location.get<1>() == r.location.get<1>());
// 
//         if (b1&&b2&&b3)
//             return true;
// 
//         return false;
//     }
};template <>
struct bgi::indexable<CityRef>
{typedef boostPoint2d result_type; //这个不能缺少//boostPoint2d operator()(const CityRef& c) const { return c.location; }const boostPoint2d& operator()(const CityRef& c) const { return c.location; }
};struct BoostTest7
{int DoTest() {typedef CityRef value;typedef bgi::rtree< value, bgi::linear<16> > rtree_t;// create the rtree using default constructorrtree_t rtree;// create some valuesfor ( double f = 0 ; f < 10 ; f += 1 ){CityRef data;data.index = (static_cast<size_t>(f));data.index2 = f + 1;data.location.set<0>(f);data.location.set<1>(f);// insert new valuertree.insert(data);//rtree.insert({ static_cast<size_t>(f), f + 1,{ f, f } });}// query pointboostPoint2d pt(5.1, 5.1);// iterate over nearest Values//根据距离从近到远/*index=5, index2=6.000000, (5.000000, 5.000000), distance=0.141421index=6, index2=7.000000, (6.000000, 6.000000), distance=1.272792index=4, index2=5.000000, (4.000000, 4.000000), distance=1.555635index=7, index2=8.000000, (7.000000, 7.000000), distance=2.687006break!*//*另外，这种写法的原因，是为了在满足数据条件后可以直接break。https://www.py4u.net/discuss/75145https://www.boost.org/doc/libs/1_55_0/libs/geometry/doc/html/geometry/spatial_indexes/queries.html#geometry.spatial_indexes.queries.breaking_or_pausing_the_queryBreaking or pausing the queryThe query performed using query iterators may be paused and resumed if needed, e.g. when the query takes too long, or stopped at some point, e.g when all interesting values were gathered.for ( Rtree::const_query_iterator it = tree.qbegin(bgi::nearest(pt, 10000)) ;it != tree.qend() ; ++it ){// do something with valueif ( has_enough_nearest_values() )break;}*/for ( rtree_t::const_query_iteratorit = rtree.qbegin(bgi::nearest(pt, 100)) ;it != rtree.qend() ;++it ){double d = bg::distance(pt, it->location);///*可以修改除了point之外的数据*/CityRef& xx = const_cast<CityRef&>(*it);xx.index2 = 10;//std::cout << "index=" << it->index << ", " << bg::wkt(it->location) << ", distance= " << d << std::endl;wprintf(L"\n index=%d, index2=%f, (%f, %f), distance=%f", it->index , it->index2,it->location.get<0>() ,it->location.get<1>(), d );// break if the distance is too bigif ( d > 2 ){std::cout << "break!" << std::endl;break;}}return 0;
}};
void boostTest7()
{BoostTest7 o;o.DoTest();}