使用 rtree(或任何其他算法)计算向量中组的频率
count the frequency of groups in vector using rtree ( or any other algorithm )
给定向量中的以下一组点
{( 100, 150 ), ( 101, 152 ), ( 102, 151 ), ( 105, 155 ), ( 50, 50 ), ( 51, 55 ), ( 55, 55 ), ( 150, 250 ), ( 190, 260)}
我需要确定相邻点及其数量。假设可接受的距离已设置为 5。现在我需要以下输出:
5 个单位中点 ( 100, 150 ) 的频率为 4。
5 个单位中点 ( 50, 50 ) 的频率为 3
5 个单位内的点 ( 150, 250 ) 的频率为 1
5个单位内的点(190, 260)出现频率为1
我已尝试使用 RTree 解决此问题,但无法确定将所有相邻点排除为候选点的逻辑。意味着一旦我确定了 ( 100, 150 ) 有四个邻居,我不想确定这些邻居的邻居。我想转到下一个值。以下是假设:
1.效率是最关心的问题
2.向量未排序
3. 向量可能包含数千个点。
我正在使用 C++ 并提升 RTree 的实现。请指导我如何实现解决方案
下面是计算向量中唯一点的邻居数量的代码。一旦确定了一个点的邻居,我需要指导将其排除在外。
include set, iostream, boost/geometry.hpp, boost/geometry/geometries/point.hpp, boost/geometry/index/rtree.hpp
using namespace std;
namespace bg = boost::geometry;
namespace bgi = boost::geometry::index;
typedef bg::model::point<int, 2, bg::cs::cartesian> point;
typedef std::pair<point, unsigned> value;
struct ltstr
{
bool operator()(const point &p1, const point &p2) const
{
return (p1.get < 0 >() < p2.get < 0 >() || p1.get < 1 >() < p2.get < 1 >());
}
};
void main()
{
vector<point> candidatePoints{ point(457, 184), point(457, 184), point(457, 184), point(457, 184), point(457, 184),
point(456, 184), point(456, 184), point(456, 184), point(456, 184), point(456, 184),
point(456, 184), point(457, 184), point(457, 184), point(457, 184), point(458, 184), point(459, 185) };
bgi::rtree< value, bgi::quadratic<16> > rtree;
set<point, ltstr> uniqueCandidatePoints;
for (int i = 0; i < candidatePoints.size(); ++i)
{
int x = candidatePoints[i].get < 0 >();
int y = candidatePoints[i].get < 1 >();
uniqueCandidatePoints.insert(point(x, y));
rtree.insert(make_pair(candidatePoints[i], i));
}
for (auto it = uniqueCandidatePoints.begin(); it != uniqueCandidatePoints.end(); ++it)
{
std::vector<value> returnedValues;
point currentItem = *it;
rtree.query(bgi::satisfies([&](value const& v) {return bg::distance(v.first, currentItem) < 5; }),
std::back_inserter(returnedValues));
cout << "Current Item: " << currentItem.get < 0 >() << "," << currentItem.get < 1 >() << "Count: " << returnedValues.size() << endl;
}
getchar();
}
R-tree is just a data structure but not an algorithm and to me it looks quite complicated. Unless you really need to deal with mirco efficiency I would use plain standard algorithms and a vector of points. std::count_if
是我的第一个猜测。
R 树是最有用的 空间索引 数据结构之一,但已被证明对特定领域和问题很有用。话虽这么说,但这并不是避免说教的理由(毕竟所问的可能是对实际问题的简化)。
如果您选择使用 R 树,您将执行域分解。就像 space 填充曲线一样,您可以手头对 space 进行排序,但节点元素保持空间邻近(离根越远)。
理想的解决方案是以 radius=5
区域形成的方式构建 R 树,但这需要自定义数据结构和 STR 或批量加载算法的自定义,并且类似于聚类算法。
有了 boost::index
,您可以 identify all neiborhoods,我将尝试详细说明代码:
强制包括
#include <vector>
#include <iostream>
#include <boost/geometry.hpp>
#include <boost/geometry/geometries/point.hpp>
#include <boost/geometry/geometries/box.hpp>
#include <boost/geometry/index/rtree.hpp>
定义
namespace bg = boost::geometry;
namespace bgi = boost::geometry::index;
using point = bg::model::point < float, 2, bg::cs::cartesian > ;
助剂
Boost R 树有一个 query
方法。尽管它设计用于执行 kNN 或重叠等典型查询,但您可以为其提供 自定义谓词 。这里我们设计一个 returns true
如果我们查询的点最多 max_dist
远离 base
点(两个变量在构造时指定)
struct distance_pred
{
point const& _base;
double _threshold;
distance_pred(point const& base, double max_dist)
: _base(base)
, _threshold(max_dist)
{
}
bool operator()(point const& p) const
{
auto d = boost::geometry::distance(_base, p);
return d && d < _threshold;
}
};
// just for output
std::ostream& operator<<(std::ostream &os, point const& p)
{
os << "{ " << p.get<0>() << ", " << p.get<1>() << " }";
return os;
}
执行
对于每个点,我们查询最多相距 distance=5
的点
int main()
{
std::vector<point> cloud {
point(100, 150), point(101, 152), point(102, 151),
point(105, 155), point( 50, 50), point( 51, 55),
point( 55, 55), point(150, 250), point(190, 260)
};
bgi::rtree<point, bgi::quadratic<16>> rtree(cloud.begin(), cloud.end());
std::vector<point> hood;
for (auto &&p : cloud)
{
hood.clear();
std::cout << "neighborhood of point " << p << "\n-----------------\n\n";
rtree.query(bgi::satisfies(distance_pred(p, 5)), std::back_inserter(hood));
// Output the results -----------------------------------------
if (!hood.empty())
{
for (auto &&pt : hood) std::cout << '\t' << pt << std::endl;
}
else
{
std::cout << "\t... is empty\n";
}
std::cout << std::endl;
}
}
扩展程序
如果你想排除某些东西,我相信 聚类 算法会更合适,这超出了 RTrees 的范围。例如,如果由于靠近 point1 而排除的点恰好靠近 point2 怎么办?
然而,如果你真的想做,这只是一个记账的问题。像这样定义一个点
using pointI = std::pair<point, std::size_t>; // remember : geometric info first
并将 for 循环转换为
for (std::size_t i(0), i < cloud.size(); ++i)
{
if (cloud.end() != std::find(rec.begin(), rec.end(), i))
{ // you'll only be building neighorhoods for points that are not touched
// queries and recording performed on point2 types
}
}
Full code 证明了这个逻辑中的问题:许多街区仍然空无一人。
可以用更少的代码实现与上面相同的代码,但稍微复杂一些(基本上我们将查询放入 lambda 函数并使用查询迭代器循环遍历结果)Demo
给定向量中的以下一组点 {( 100, 150 ), ( 101, 152 ), ( 102, 151 ), ( 105, 155 ), ( 50, 50 ), ( 51, 55 ), ( 55, 55 ), ( 150, 250 ), ( 190, 260)}
我需要确定相邻点及其数量。假设可接受的距离已设置为 5。现在我需要以下输出: 5 个单位中点 ( 100, 150 ) 的频率为 4。 5 个单位中点 ( 50, 50 ) 的频率为 3 5 个单位内的点 ( 150, 250 ) 的频率为 1 5个单位内的点(190, 260)出现频率为1
我已尝试使用 RTree 解决此问题,但无法确定将所有相邻点排除为候选点的逻辑。意味着一旦我确定了 ( 100, 150 ) 有四个邻居,我不想确定这些邻居的邻居。我想转到下一个值。以下是假设: 1.效率是最关心的问题 2.向量未排序 3. 向量可能包含数千个点。 我正在使用 C++ 并提升 RTree 的实现。请指导我如何实现解决方案
下面是计算向量中唯一点的邻居数量的代码。一旦确定了一个点的邻居,我需要指导将其排除在外。
include set, iostream, boost/geometry.hpp, boost/geometry/geometries/point.hpp, boost/geometry/index/rtree.hpp
using namespace std;
namespace bg = boost::geometry;
namespace bgi = boost::geometry::index;
typedef bg::model::point<int, 2, bg::cs::cartesian> point;
typedef std::pair<point, unsigned> value;
struct ltstr
{
bool operator()(const point &p1, const point &p2) const
{
return (p1.get < 0 >() < p2.get < 0 >() || p1.get < 1 >() < p2.get < 1 >());
}
};
void main()
{
vector<point> candidatePoints{ point(457, 184), point(457, 184), point(457, 184), point(457, 184), point(457, 184),
point(456, 184), point(456, 184), point(456, 184), point(456, 184), point(456, 184),
point(456, 184), point(457, 184), point(457, 184), point(457, 184), point(458, 184), point(459, 185) };
bgi::rtree< value, bgi::quadratic<16> > rtree;
set<point, ltstr> uniqueCandidatePoints;
for (int i = 0; i < candidatePoints.size(); ++i)
{
int x = candidatePoints[i].get < 0 >();
int y = candidatePoints[i].get < 1 >();
uniqueCandidatePoints.insert(point(x, y));
rtree.insert(make_pair(candidatePoints[i], i));
}
for (auto it = uniqueCandidatePoints.begin(); it != uniqueCandidatePoints.end(); ++it)
{
std::vector<value> returnedValues;
point currentItem = *it;
rtree.query(bgi::satisfies([&](value const& v) {return bg::distance(v.first, currentItem) < 5; }),
std::back_inserter(returnedValues));
cout << "Current Item: " << currentItem.get < 0 >() << "," << currentItem.get < 1 >() << "Count: " << returnedValues.size() << endl;
}
getchar();
}
R-tree is just a data structure but not an algorithm and to me it looks quite complicated. Unless you really need to deal with mirco efficiency I would use plain standard algorithms and a vector of points. std::count_if
是我的第一个猜测。
R 树是最有用的 空间索引 数据结构之一,但已被证明对特定领域和问题很有用。话虽这么说,但这并不是避免说教的理由(毕竟所问的可能是对实际问题的简化)。
如果您选择使用 R 树,您将执行域分解。就像 space 填充曲线一样,您可以手头对 space 进行排序,但节点元素保持空间邻近(离根越远)。
理想的解决方案是以 radius=5
区域形成的方式构建 R 树,但这需要自定义数据结构和 STR 或批量加载算法的自定义,并且类似于聚类算法。
有了 boost::index
,您可以 identify all neiborhoods,我将尝试详细说明代码:
强制包括
#include <vector>
#include <iostream>
#include <boost/geometry.hpp>
#include <boost/geometry/geometries/point.hpp>
#include <boost/geometry/geometries/box.hpp>
#include <boost/geometry/index/rtree.hpp>
定义
namespace bg = boost::geometry;
namespace bgi = boost::geometry::index;
using point = bg::model::point < float, 2, bg::cs::cartesian > ;
助剂
Boost R 树有一个 query
方法。尽管它设计用于执行 kNN 或重叠等典型查询,但您可以为其提供 自定义谓词 。这里我们设计一个 returns true
如果我们查询的点最多 max_dist
远离 base
点(两个变量在构造时指定)
struct distance_pred
{
point const& _base;
double _threshold;
distance_pred(point const& base, double max_dist)
: _base(base)
, _threshold(max_dist)
{
}
bool operator()(point const& p) const
{
auto d = boost::geometry::distance(_base, p);
return d && d < _threshold;
}
};
// just for output
std::ostream& operator<<(std::ostream &os, point const& p)
{
os << "{ " << p.get<0>() << ", " << p.get<1>() << " }";
return os;
}
执行
对于每个点,我们查询最多相距 distance=5
的点
int main()
{
std::vector<point> cloud {
point(100, 150), point(101, 152), point(102, 151),
point(105, 155), point( 50, 50), point( 51, 55),
point( 55, 55), point(150, 250), point(190, 260)
};
bgi::rtree<point, bgi::quadratic<16>> rtree(cloud.begin(), cloud.end());
std::vector<point> hood;
for (auto &&p : cloud)
{
hood.clear();
std::cout << "neighborhood of point " << p << "\n-----------------\n\n";
rtree.query(bgi::satisfies(distance_pred(p, 5)), std::back_inserter(hood));
// Output the results -----------------------------------------
if (!hood.empty())
{
for (auto &&pt : hood) std::cout << '\t' << pt << std::endl;
}
else
{
std::cout << "\t... is empty\n";
}
std::cout << std::endl;
}
}
扩展程序
如果你想排除某些东西,我相信 聚类 算法会更合适,这超出了 RTrees 的范围。例如,如果由于靠近 point1 而排除的点恰好靠近 point2 怎么办?
然而,如果你真的想做,这只是一个记账的问题。像这样定义一个点
using pointI = std::pair<point, std::size_t>; // remember : geometric info first
并将 for 循环转换为
for (std::size_t i(0), i < cloud.size(); ++i)
{
if (cloud.end() != std::find(rec.begin(), rec.end(), i))
{ // you'll only be building neighorhoods for points that are not touched
// queries and recording performed on point2 types
}
}
Full code 证明了这个逻辑中的问题:许多街区仍然空无一人。
可以用更少的代码实现与上面相同的代码,但稍微复杂一些(基本上我们将查询放入 lambda 函数并使用查询迭代器循环遍历结果)Demo