用自己定义的数据结构作为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;
//key
BDPoint 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 polygon
typedef 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 results
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(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 polygon
typedef 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 polygon
typedef 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 constructor
rtree_t rtree;
// create some values
for ( 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 value
rtree.insert(data);
//rtree.insert({ static_cast<size_t>(f), f + 1,{ f, f } });
}
// query point
boostPoint2d pt(5.1, 5.1);
// iterate over nearest Values
//根据距离从近到远
/*
index=5, index2=6.000000, (5.000000, 5.000000), distance=0.141421
index=6, index2=7.000000, (6.000000, 6.000000), distance=1.272792
index=4, index2=5.000000, (4.000000, 4.000000), distance=1.555635
index=7, index2=8.000000, (7.000000, 7.000000), distance=2.687006break!
*/
/*
另外，这种写法的原因，是为了在满足数据条件后可以直接break。
https://www.py4u.net/discuss/75145
https://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_query
Breaking or pausing the query
The 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 value
if ( has_enough_nearest_values() )
break;
}
*/
for ( rtree_t::const_query_iterator
it = 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 big
if ( d > 2 )
{
std::cout << "break!" << std::endl;
break;
}
}
return 0;
}
};
void boostTest7()
{
BoostTest7 o;
o.DoTest();
}
