校园地图
发布时间
阅读量：
阅读量
1.项目描述
利用课余时间创建了一个小型作品, 该项目聚焦于校园地图系统, 其主要目标在于练习Qt编程语言以及掌握一些基础的数据结构与算法. 该系统的首要功能即是从下拉菜单中选择起始地点与目的地, 随后在地图界面中即可直观地展示出路径规划结果. 主要的技术实现手段包括: 通过图像贴图技术实现路径展示, 并基于动态规划算法计算最优路线
2.基本思路
构建路网是首要任务（不可或缺）。随后编写了一个新版本程序，并将所有路网节点进行标记并保存起来。用于存储数据的结构体包含详细的节点信息，并通过C++中的vector库来存储所有路网节点的信息。（vector库确实非常强大！）
struct road_dot{
int// 该节点的idint//该节点是否可访问//该节点在地图上的位置// 保存与该节点相连的节点的id下面是我用来标记路网并自动储存的模块：
/************************************************************************************************ *
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * These under codes construct a tool to get the road nodes infomation * * <2016-10-29><wuhui> * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */voidevent)
{
if014800800// if on the pic {
Road_node new_node;
new_node.self Point(x,y);
new_node.i 200// not a pos
cv::circle(img,Point(x,y),625502551);
qimg Mat2QImage(img);
uisetPixmap(QPixmap::fromImage(qimg));
iffirst_node)
{start_node 120;}
forint0)
{
if1010// if at pos {
new_node.i i;
qDebug()"this is pos "i;
break;
}
}
road.push_back(new_node);// record this new node ;forint01)
{
if1010// if at node// yes
road.pop_back(); // drop this nodeifevent// if leftButton {
start_node // set start node1;
pre_nodes_id i;
}
elseifevent Qt::RightButton)
{
start_node // this is start1;
end_node road[i];
end_set_flag 1;
road[i].others_id.push_back(pre_nodes_id);
road[pre_nodes_id].others_id.push_back(i);
pre_nodes_id i;
}
qDebug()"this node's others.size = "road[i].others_id.size();
break;
}
elseif2)
{ // noif// if have no start_node {
start_node road[pre_nodes_id];
start_set_flag 1;
}
ifend_set_flag)
{
end_node 1];
end_set_flag 1;
}
road[pre_nodes_id].others_id.push_back(road.size()1// push now node1].others_id.push_back(pre_nodes_id);
qDebug()"this node's others.size = "1].others_id.size();
pre_nodes_id 1;
break;
}
}
if start_set_flag)
{
end_set_flag 0;
start_set_flag 0;
cv::line(img,start_node.self,end_node.self,cv::Scalar(0003);
qimg Mat2QImage(img);
ui// flush the pic
}
qDebug()"road.size"road.size();
}
} // :)查看代码
该代码主要通过地图上的点击动作进行标记操作，在右键位置完成一个连续段落的操作标识过程；每个节点会自动记录与其相关联的所有其他节点的信息编号；结果展示图如下所示：（此外，请注意这些地图截取自谷歌软件，并经过精细调整以提高视觉效果）
在完成道路网络的标注之后就需要为这个项目设计一个路径finding算法了，在初步考虑时曾打算采用深度优先搜索或广度优先搜索这两种常见的探索型算法但在实际操作中发现这些方法虽然思路清晰但效率较低于是转而基于道路网络的几何特征开发了一种看似简单却效果显著的新方法：
首先布置两个哨兵，在当前出站口布置第一个哨兵（记为哨兵A），并在下一目的出站口布置第二个哨兵（记为哨兵B）。其中第二个哨兵的位置由其所有子节点中与最终出站口最近的那个子节点来决定。
当B位于一个存在可探索子节点且未到达目标的位置时，在确认该位置并非死胡同之后,A移动至该点,并将其所有行经的道路记录下来以便后续回溯,B随后开始进一步探索路径.在探索过程中,如果遇到死胡同则需返回上一步,并转向最近未被访问过的分支继续搜索潜在路径
该寻路算法如下：
int// get start and end node's id /intcurrentIndex();
forint0)
{
road[i].vistable 0// set all nodes are visitable; }
// Road_node start_node_temp,end_node_temp; // temp nodeint road_start_i,road_end_i;
int road_start_i_temp,road_end_i_temp;
forint0// search which node is on the start/end point; {
if start_id)
{
qDebug()"start"i;
start_node road[i];
road_start_i // get the id of start roadnode;"i = "start_node.i;
}
elseif end_id)
{
qDebug()"end"i;
end_node road[i];
road_end_i // get the id of end roadnode;"i = "end_node.i;
}
}
/***********/
road_start_i_temp road_start_i;
road_end_i_temp road_start_i;
// start_node_temp = start_node;
//end_node_temp = start_node_temp;
std::vectorint road_temp;
int9000000;
while end_id)
//for(int xx = 0;xx<10;xx++) {
int0;
forint0// if the current endpoint to have next point {
if0)
useable_flag 1// have useable point
}
if// have useable next node {
// start_node_temp = end_node_temp; road_end_i_temp;
road[road_start_i_temp].vistable 1// have visited it;
//start_node_temp.vistable = 1; // have visited it;
road_temp.push_back(road_start_i_temp); // record the walked nodeint temp_min_id;
forint0// find the min dis node // int these next points {
if0// if this node have not visited; {
int tempx,tempy;
tempx end_node.self.x);
tempy end_node.self.y);
iftempy))
{
qDebug()"pre_distance = "pre_distance;
qDebug()"now distance = "tempy;
// end_node_temp = road[road[road_start_i_temp].others_id[i-1]]; road[road_start_i_temp].others_id[temp_min_id];
}
else {
//end_node_temp = road[start_node_temp.others_id[i]]; road[road_start_i_temp].others_id[i];
temp_min_id i;
pre_distance tempy;
}
}
}
pre_distance 9000000;
}
else// have no useable next node {
road[road_end_i_temp].vistable 1;
loop: forint0// if have other useable nodes {
if0)
useable_flag 1// have useable point
}
if(useable_flag)
{
int temp_min_id;
forint0// fine the min dis node {
if0// if this node have not visited; {
int tempx,tempy;
tempx end_node.self.x);
tempy end_node.self.y);
iftempy))
{
//end_node_temp = road[road[road_start_i_temp].others_id[i-1]]; road[road_start_i_temp].others_id[temp_min_id];
}
else {
//end_node_temp = road[start_node_temp.others_id[i]]; road[road_start_i_temp].others_id[i];
temp_min_id i;
pre_distance tempy;
}
}
}
pre_distance 9000000;
}
else
{
road_temp.pop_back(); // drop this start_temp node1];
goto loop;
}
}
/*
int pre_distance = 90000000;
for(int i = 0;i<start_node_temp.others_id.size();i++) //
{
int tempx,tempy;
tempx = (road[start_node_temp.others_id[i]].self.x- end_node.self.x)*(road[start_node_temp.others_id[i]].self.x - end_node.self.x);
tempy = (road[start_node_temp.others_id[i]].self.y- end_node.self.y)*(road[start_node_temp.others_id[i]].self.y - end_node.self.y);
if(pre_distance<(tempx+tempy))
{
end_node_temp = road[start_node_temp.others_id[i-1]];
}
else {
end_node_temp = road[start_node_temp.others_id[i]];
pre_distance = tempx+tempy;
}
}
cv::line(img,start_node_temp.self,end_node_temp.self,cv::Scalar(0,0,0),3);
qimg = Mat2QImage(img);
ui->pic->setPixmap(QPixmap::fromImage(qimg)); // flush the pic
start_node_temp = end_node_temp;
xx++;*/
}
road_temp.push_back(road_end_i_temp);
forint01)
{
cv::line(img,road[road_temp[i]].self,road[road_temp[i10003);
qimg Mat2QImage(img);
ui// flush the pic }
qDebug()road_temp.size();
}查看代码
经过实验该算法还是很可靠的 ;)
效果图：
另外当鼠标悬停于某一特定位置时会呈现该位置对应的图片资料（经过仔细核对和拍照确认后确认无误）
-----------------------------------------------------------------------------------------------
全部评论 (0)
还没有任何评论哟~