1、一個(gè)簡單的蜂窩小區(qū)最短路徑算法 #include "stdafx.h"#include <utility>#include <math.h>#define EQUAL_DOUBLE(x, y) (0.000001 < (x) - (y) && (x) - (y) < 0.000001)typedef unsigned int POS_NUM; / 點(diǎn)的編號(hào)typedef unsigned int RADIUS; / 半徑typedef unsigned int RANGE; / 距離struct XYPosdouble m

2、_x;double m_y;class Beehivepublic:XYPos GetMaxPos(RADIUS n);/ 第n圈最大編號(hào)的Pos；POS_NUM GetMaxPosNum(RADIUS n);/ 第n圈最大編號(hào)XYPos GetPosByPosNum(POS_NUM num); / 根據(jù)編號(hào)求點(diǎn)坐標(biāo)RADIUS GetRadiusByPosNum(POS_NUM num); / 根據(jù)編號(hào)求半徑RANGE GetMinRangeByTwoPos(POS_NUM num1, POS_NUM num2);/ 求亮點(diǎn)之間的距離;XYPos Beehive:GetMaxPos(RADI

3、US n)/ 第n圈最大編號(hào)的Pos；XYPos pos;pos.m_x = 0.866 * n;pos.m_y = -0.5 * n;return pos;POS_NUM Beehive:GetMaxPosNum(RADIUS n)/ 第n圈最大編號(hào)return 1 + 3*n*(n + 1);RADIUS Beehive:GetRadiusByPosNum(POS_NUM num) / 根據(jù)編號(hào)求半徑RADIUS radius = 0;while(num > GetMaxPosNum(radius)+radius;return radius;XYPos Beehive:GetPosB

4、yPosNum(POS_NUM num) / 根據(jù)編號(hào)求點(diǎn)坐標(biāo)RADIUS radius = GetRadiusByPosNum(num); / 根據(jù)編號(hào)求半徑POS_NUM MaxNum = GetMaxPosNum(radius); / 根據(jù)半徑求該圈最大編號(hào)，編號(hào)num必然在該圈上POS_NUM MaxMoveRange = MaxNum - num; / 編號(hào)與最大編號(hào)的差XYPos Pos = GetMaxPos(radius); / 半徑上的最大編號(hào)坐標(biāo)/ 按照指定方向移動(dòng)該坐標(biāo)到編號(hào)num, 需要移動(dòng)次數(shù)為 MaxNum - num/ 向上移動(dòng)for(int moveRange

5、= 1; moveRange <= radius && MaxMoveRange > 0; +moveRange)Pos.m_y += 1;- MaxMoveRange;/ 向左上移動(dòng)for(int moveRange = 1; moveRange <= radius && MaxMoveRange > 0; +moveRange)Pos.m_y += 0.5;Pos.m_x -= 0.866;- MaxMoveRange;/ 向左下移動(dòng)for(int moveRange = 1; moveRange <= radius &

6、& MaxMoveRange > 0; +moveRange)Pos.m_y -= 0.5;Pos.m_x -= 0.866;- MaxMoveRange;/ 向下移動(dòng)for(int moveRange = 1; moveRange <= radius && MaxMoveRange > 0; +moveRange)Pos.m_y -= 1;- MaxMoveRange;/ 向右下移動(dòng)for(int moveRange = 1; moveRange <= radius && MaxMoveRange > 0; +moveRa

7、nge)Pos.m_y -= 0.5;Pos.m_x += 0.866;- MaxMoveRange;/ 向右上移動(dòng)for(int moveRange = 1; moveRange <= radius && MaxMoveRange > 0; +moveRange)Pos.m_y += 0.5;Pos.m_x += 0.866;- MaxMoveRange;return Pos;RANGE Beehive:GetMinRangeByTwoPos(POS_NUM num1, POS_NUM num2)/ 求亮點(diǎn)之間的距離XYPos pos_1 = GetPosByPo

8、sNum(num1);XYPos pos_2 = GetPosByPosNum(num2);double range_x = abs(pos_1.m_x - pos_2.m_x);double range_y = abs(pos_1.m_y - pos_2.m_y);double dRange = sqrt(range_x* range_x + range_y * range_y);RANGE range = dRange;if (!EQUAL_DOUBLE(range, dRange)range+;return range;int _tmain(int argc, _TCHAR* argv)

9、Beehive beehive;XYPos pos_1 = beehive.GetPosByPosNum(1);XYPos pos_2 = beehive.GetPosByPosNum(2);XYPos pos_3 = beehive.GetPosByPosNum(3);XYPos pos_4 = beehive.GetPosByPosNum(4);XYPos pos_5 = beehive.GetPosByPosNum(5);XYPos pos_6 = beehive.GetPosByPosNum(6);XYPos pos_7 = beehive.GetPosByPosNum(7);XYPos pos_12 = beehive.GetPosByPosNum(12);XYPos pos_37 = beehive.GetPosByPosNum(37);XYPos pos_22 = beehive.GetPosByPosNum(22);int range_1_3 = beehive.GetMinRangeByTwoPos(1, 3);int range_1_10 = beehive.GetMinRangeByTwoPos(1, 10);int range_2_3 = beehive.GetMinRangeByTwoPos(2, 3);int range_2_