项目随笔1

最近在项目中遇到的一个问题，有些意思和启发，随手记下来。

问题简要描述为：在地图上的随便一个点，要搜索它周围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

差距巨大。

使用