最近在项目中遇到的一个问题，有些意思和启发，随手记下来。
问题简要描述为：在地图上的随便一个点，要搜索它周围n米范围内相邻的点，例如有一个的点A(555,369), 找出在它120米范围内所有的点。
容易想到的做法是用A与集合内所有的点进行距离运算，将距离小于120m的点记录下来即可。
但在测试中发现这样做存在以下问题：
（1）当点的集合特别大的时候，要进行很多运算与比较，效率相当低效。
（2）特别是当要经常求某些点一定范围内的相邻点时，这种低效更加明显，达到让人不能接受的地步。例如点的集合是100w, 而且要搜索所有点在120m范围内的相邻点，那就要 计算比较100w * 100w次，效率相当之低。
经过讨论与分析，最终确定一种简单且行之有效的方法：
主要思想是：
（1）将地图上所有的点所在的区域，划分为一个个格子，所有的点都会落到某个格子内。
例如：如以（0，0）为坐标原点，将所有点所在的区域划分为一个个100m * 100m的格子，点A(555,369)就落在坐标为[5,3]的格子。
（2）遍历每个点，确定每个点所在的格子坐标，遍历结束后生成一张
格子坐标 -> 在该格子内的所有点列表 的映射关系表。
如：[0,0]号格子共有两个点：(33,82),(60,72)
[2,0]号格子有两个点 ： [226,65],[229,43]
（3）根据上面的这张映射表，就很容易求得某个点方圆n米范围内所有的相邻点，并且效率相当的高，只需比较很少的点即可。
例如：要求点A(555,369) 90米内的所有相邻点 （假设整个区域有1000个点）
一般求法：遍历整个点区域内所有的点，与点A做距离运算，然后比较，得出结果。 --共需计算比较999次
运用上述映射关系表计算：
1）首先根据点A的原始坐标计算得到A点所在格子的坐标 为[5,3]
2) 因为max(1,90 / 100) = 1, 所以只需在格子[5,3]左右，上下、对角线方向共9各格子内搜索是否有距离小于90m的相邻点即可。
即在X坐标为： 5-1 -> 5+1, Y坐标：3-1 -> 3+1的范围内搜索即可 ，分别为[4,2],[4,3],[4,4] [5,2],[5,3],[5,4] [6,2],[6,3][6,4]九个格子。
只需比较10次即可得到结果，应为超出这9各格子的范围距离肯定大于90m。计算比较次数大大减少。
主要实现如下：
点结构：
struct Point
{
int posX;
int posY;
string pointName;
Point()
: posX(0)
, posY(0)
{
pointName = GetPointName(0,0);
}
Point(int pX, int pY)
: posX(pX)
, posY(pY)
{
pointName = GetPointName(pX,pY);
}
Point & operator=(const Point & p)
{
if (this == &p)
{
return *this;
}
posX = p.posX;
posY = p.posY;
pointName = p.pointName;
return *this;
}
friend bool operator<(const Point &p1, const Point & p2)
{
if (p1.posX == p2.posX)
{
return (p1.posY < p2.posY);
}
else
{
return p1.posX < p2.posX;
}
}
friend bool operator==(const Point & point, const Point & p2)
{
return (p2.posX == point.posX) && (p2.posY == point.posY);
}
string GetPointName(int pX, int pY) const
{
stringstream ss;
ss << pX << "-" << pY;
return ss.str();
}
string ToString() const
{
stringstream ss;
ss << "[" << posX << "," << posY << "]";
return ss.str();
}
//计算距离
double Distence(const Point & p) const
{
double d = sqrt((double)((p.posX-posX)*(p.posX-posX)+(p.posY-posY)*(p.posY-posY)));
return d;
}
};
格子坐标与点列表映射表定义：
typedef map<int,vector<const Point*> > PointBlock; typedef set<Point> PointSet; PointBlock _grids; //映射表 PointSet _points;//所有的点集合 int _blockUnit; //划分格子的大小 Point _firstPoint;//坐标原点
class Geo
{
public:
typedef map<int,vector<const Point*> > PointBlock;
typedef set<Point> PointSet;
Geo();
~Geo();
void GeneratePoints(int cnt);
string SavePoints();
int ReadPoints(const string & pointsFilePath);
bool GetNearByPoints(const Point & p, double threshold, set<Point> & nearByPoints);
//划分格子，生成映射表
bool InitBlock(int unit);
void OutPutBlocksMsg(const string & outputPath);
//根据点原始坐标，生成格子编号
int GetBlockIndex(const Point & p);
//根据格子的坐标，生成格子编号
int GetIdx(short dx, short dy);
//根据格子编号，得到格子的X坐标
short GetPosX(int Idx);
//根据格子编号，得到格子的Y坐标
short GetPosY(int Idx);
void GetNearByPointsByGrid(const Point & p, double threshold, set<Point> & nearByPoints);
void CountAllPointsNearByPoint(double threshold);
void CountAllPointsNearByPointG(double threshold);
private:
PointBlock _grids;
PointSet _points;
int _blockUnit; //划分格子的大小
Point _firstPoint;
};
主要实现如下：
bool Geo::InitBlock(int unit)
{
if (_points.empty())
{
return false;
}
_blockUnit = unit;
//m_FirstPoint = *(m_Points.begin());//以第一个点作为坐标原点
//std::cout << "FirstPoint X:" << m_FirstPoint.posX << "Y:" << m_FirstPoint.posY << std::endl;
//生成栅格
for (PointSet::iterator it = _points.begin(); it != _points.end(); ++it)
{
const Point & p = *it;
int gridIndex = GetBlockIndex(p);
vector<const Point *> & pList = _grids[gridIndex];
pList.push_back(&p);
}
return true;
}
int Geo::GetBlockIndex(const Point & p)
{
Point pDx(p.posX,_firstPoint.posY);
double xDis = _firstPoint.Distence(pDx);
short dX = (p.posX < _firstPoint.posX) ? -(short)(xDis / _blockUnit) : (short)(xDis / _blockUnit);
Point pDy(_firstPoint.posX,p.posY);
double yDis = _firstPoint.Distence(pDy);
short dY = (p.posY < _firstPoint.posY) ? -(short)(yDis / _blockUnit) : (short)(yDis / _blockUnit);
int gridIndex = GetIdx(dX,dY);
return gridIndex;
}
int Geo::GetIdx( short dx, short dy )
{
int Idx = ((int)dx << 16) | (dy & 0xFFFF);
return Idx;
}
short Geo::GetPosX( int Idx )
{
return (Idx >> 16 ) & 0xFFFF;
}
short Geo::GetPosY( int Idx )
{
return Idx & 0xFFFF;
}
//求相邻点
void Geo::GetNearByPointsByGrid(const Point & p, double threshold, set<Point> & nearByPoints )
{
int gridIndex = GetBlockIndex(p);
PointBlock::iterator it = _grids.find(gridIndex);
if (it == _grids.end())
{
return;
}
short dX = this->GetPosX(gridIndex);
short dY = this->GetPosY(gridIndex);
short num = (short)ceil((threshold / _blockUnit));
num = num < 1 ? 1 : num;
for (short i = dX - num; i <= dX + num; i++)
{
for (short j = dY - num; j <= dY + num; j++)
{
int tmpIndex = GetIdx(i,j);
PointBlock::iterator it = _grids.find(tmpIndex);
if (it == _grids.end())
{
continue;
}
vector<const Point *> & pList = it->second;
for (vector<const Point*>::iterator pIt = pList.begin(); pIt != pList.end(); ++pIt)
{
if (p == *(*pIt))
{
continue;
}
double dis = p.Distence(*(*pIt));
if (dis <= threshold)
{
nearByPoints.insert(*(*pIt));
}
}
}
}
}
//使用原始方法，即遍历所有点求相邻点
bool Geo::GetNearByPoints(const Point & p, double threshold, set<Point> & nearByPoints )
{
for (PointSet::iterator it = _points.begin(); it != _points.end(); ++it)
{
if (*it == p)
{
continue;
}
double dis = p.Distence(*it);
if (dis <= threshold)
{
nearByPoints.insert(*it);
}
}
return true;
}
测试结果：
10w数据，求所有点的在90m范围内的相邻点。
方法一： 遍历所有点计算距离 耗时864s
方法二：通过划分区域计算，耗时3.5s
差距巨大。
使用
原文：http://www.cnblogs.com/cmranger/p/4596721.html