基于图的路径规划算法对比
基于图的路径规划算法对比
- 算法说明与实现效果
- 构造路网
- 1.打开Arcmap
- 2.新建Shapefile文件
- 3.编辑Shapefile属性
- 4.开始编辑
- 5.创建要素并绘制路网
- 6.打断相交线
- 7.保存编辑
- 8.打开图层属性表
- 9.添加字段
- 10.完成字段添加
- 11.计算字段id
- 12.计算点线字段
- 13.选中length字段
- 14.计算length字段
- 15.导出路网数据
- 16.查看最终的路网数据
- 路网数据转化为图
- matlab代码
算法说明与实现效果
通过构造邻接矩阵,在构造的路网中找到一个节点通向另一个节点的最短路径,包括DJ,Floyd,A*,ACO,GA算法。
路网与一般的无向图不同点是:在一般的无向图中,从起点开始,不论下一次选择哪个节点,最终都可以到达目标节点;而路网中存在死路,即算法需要回溯才能找到正确的通路
一般的无向图:

100个节点的路网中的路径规划:

1000个节点的路网中的路径规划:

根据路网生成的带权无向图:

构造路网
1.打开Arcmap
电脑上打开软件:ArcMap

2.新建Shapefile文件
右键ArcCatalog中文件夹链接下的目录,依次选择“新建”->“Shapefile”

3.编辑Shapefile属性
在弹出的创建新Shapefile对话框中,填写文件名称,选择要素类型为“折线”,点击“编辑”,弹出空间参考属性对话框,选择XY坐标系:地理坐标系->world->WGS 1984,最后点击“确定”,坐标将包含M值”和“坐标将包含Z值”千万不要勾选,否则后面路网数据处理过程中会报错,最后点击“确定”



4.开始编辑
左侧图层中出现了我们刚新增的Shapefile线类型图层,我们依次点击“编辑器”->“开始编辑”

5.创建要素并绘制路网
点击‘创建要素’,在右边侧栏中选中创建的文件,之后开始编辑

6.打断相交线
绘制编辑完道路数据后,依次点击工具栏中的“编辑器”->“更多编辑工具”->“高级编辑”,选中全部要素,然后点击高级编辑工具栏中的“打断相交线”


7.保存编辑
打断完成之后,依次点击“保存编辑内容”->“停止编辑”
注:若打断失败可以重启arcmap,重新新建文件,以上步骤重新来一次!!!

8.打开图层属性表
右击‘road’,打开属性表

9.添加字段
添加点与路径长度的字段
注:一定要保证‘停止编辑’了,才可以更改字段


10.完成字段添加
添加完成后的字段如下表所示

11.计算字段id
计算字段id的内容:右键Id字段,选择“字段计算器”,在字段计算器中,给Id进行重新计算赋值,双击FID字段,然后点击+,再输入数字1即可



12.计算点线字段
计算x1,y1,x2,y2字段:选中列x1并右击,选择‘计算几何’,选择‘线起点的x坐标’,点击确定,其余的y1,x2,y2同理





13.选中length字段
计算length字段,即计算路径长度:选中length列->选择字段计算器

14.计算length字段
在字段计算器中,选择解析程序为python,输入以下内容计算路径长度,点击确定
math.sqrt(( !x1! - !x2! )*( !x1! - !x2! )+( !y1! - !y2! )*( !y1! - !y2! ) )


15.导出路网数据
导出路网数据到表格


16.查看最终的路网数据
在表格中查看最终的路网数据

路网数据转化为图
将保存的excel数据加载到matlab中,编写并运行以下的matlab代码,得到路网与图
路网:

无向带权图:

matlab代码
(1)将原始的road数据(即保存的excel数据)转化为图和邻接矩阵的matlab代码
%% 函数功能:
%(1)读取arcmap数据,进行点合并,绘制路网图,保存处理后的数据
%(2)坐标编号,坐标关系转化为点关系,根据点关系得到邻接矩阵
%(3)根据邻接矩阵构造图
%data属性:fid id x1 y1 x2 y2 length%% 返回值:
%A:邻接矩阵
%G:无向图
%data:原始数据的所有坐标
%uniqueValues:不重复的节点坐标及其对应的唯一id
%% 读取数据
%文件名
filename = 'road.xls';
% 指定要读取的文件名和工作表名
sheet = 1; % 第一个工作表
% 使用xlsread函数读取数据 header为列名称
[data, header] = xlsread(filename, sheet);
data=data(:,2:7);%读取列
%data属性:id x1 y1 x2 y2 length
name_id = data(:,1);%记录id
start_point=data(:,2:3);%记录起点坐标x1 y1
end_point=data(:,4:5);%记录终点坐标x2 y2
length_list=data(:,6);%记录路径长度length%% 处理数据:合并距离很近的点
distanceThreshold=3;%距离阈值,两点距离小于此阈值则合并两个点
numNodes = size(start_point, 1);
for kk = 1:5%通过迭代,不断减少距离阈值distanceThreshold=distanceThreshold/2;Preprocessed_data=[];%记录要替换的数据for i = 1:numNodesfor j = 1:numNodesif i ~= jdistance1 = norm(start_point(i, :) - start_point(j, :));if distance1 <= distanceThreshold%两点距离过近Preprocessed_data=[Preprocessed_data;start_point(i, :),start_point(j, :)];enddistance2 = norm(end_point(i, :) - end_point(j, :));if distance2 <= distanceThreshold%两点距离过近Preprocessed_data=[Preprocessed_data;end_point(i, :),end_point(j, :)];enddistance3 = norm(start_point(i, :) - end_point(j, :));if distance3 <= distanceThreshold%两点距离过近Preprocessed_data=[Preprocessed_data;start_point(i, :),end_point(j, :)];endendendend%for%根据记录处理原始数据for i = 1:size(data,1)for j = 1:size(Preprocessed_data,1)if data(i,2)==Preprocessed_data(j,1) && data(i,3)==Preprocessed_data(j,2)data(i,2)=Preprocessed_data(j,3);data(i,3)=Preprocessed_data(j,4);end if data(i,4)==Preprocessed_data(j,1) && data(i,5)==Preprocessed_data(j,2)data(i,4)=Preprocessed_data(j,3);data(i,5)=Preprocessed_data(j,4);end end end%for %重新读取数据name_id = data(:,1);%记录idstart_point=data(:,2:3);%记录起点坐标end_point=data(:,4:5);%记录终点坐标length_list=data(:,6);%记录路径长度
end
% %重新计算路径长度
% data(:,6) = norm(data(:,2:3) - data(:, 4:5));
%% 绘制路网
figure(1);
hold on;
% 逐个连接起点和终点
for i = 1:size(start_point, 1)x = [start_point(i, 1), end_point(i, 1)];y = [start_point(i, 2), end_point(i, 2)];distance=sqrt((start_point(i, 1)-start_point(i, 2))^2+(end_point(i, 1)-end_point(i, 2))^2);if distance>0.1%两点距离过近则删除% text(start_point(i, 1),start_point(i, 2),num2str(i),'color','r','FontSize', 12);%图上打上名称plot(x, y, 'b-o'); % 使用蓝色圆形标记连线end
end
% 设置坐标轴范围和标签
xlabel('X轴');
ylabel('Y轴');
% 添加标题和图例
title('路网');
legend('节点');
hold off;%% 保存数据到表格
% 创建表格
T = array2table(data, 'VariableNames', {'Id', 'x1', 'y1','x2','y2','length'});
% 保存表格数据到 CSV 文件
filename = 'data.csv';
writetable(T, filename);%% 二维数组去重值,计算剩余的节点数
uniqueValues = unique(data(:,2:3), 'rows');
node_length = size(uniqueValues,1);
fprintf('路网中包含节点的数目为:%d \n\n',node_length)%% 给数据的坐标编号,使每个坐标具有唯一id
for i = 1:node_lengthuniqueValues(i,3)=i;
end %% 将data数据中的点的关系转化为id的关系
new_data = zeros(size(data,1),3);
for i = 1:size(data,1)for j = 1:size(uniqueValues,1)if data(i,2)==uniqueValues(j,1) && data(i,3)==uniqueValues(j,2)new_data(i,1)=uniqueValues(j,3);endif data(i,4)==uniqueValues(j,1) && data(i,5)==uniqueValues(j,2)new_data(i,2)=uniqueValues(j,3);endend
end
new_data(:,3)=data(:,6);%载入路径权值,即路径长度
save('data.mat', 'new_data');%% 根据id的关系绘制邻接矩阵
edges=new_data(:,1:2);%载入边的关系
% 提取节点数量
numNodes = max(edges(:));
% 创建空的邻接矩阵
adjMatrix = zeros(numNodes);
% 根据边关系设置邻接矩阵
numEdges = size(edges, 1);
for i = 1:numEdgesstartNode = edges(i, 1);endNode = edges(i, 2);if startNode==0 ||endNode==0continue end adjMatrix(startNode, endNode) = new_data(i, 3);%记录权值
end
A = adjMatrix+adjMatrix';%转置得到对称阵
G = graph(A, 'upper', 'omitselfloops');%创建无向图
figure(2);%开启画图
h = plot(G, 'EdgeLabel', G.Edges.Weight,'EdgeLabelColor','r');
layout(h, 'force'); % 使用强制布局算法进行节点布局
(2)根据邻接矩阵进行二维路径规划的完整matlab代码
完整代码过一段时间在github上开源。
实现效果:







相关文章:
基于图的路径规划算法对比
基于图的路径规划算法对比 算法说明与实现效果构造路网1.打开Arcmap2.新建Shapefile文件3.编辑Shapefile属性4.开始编辑5.创建要素并绘制路网6.打断相交线7.保存编辑8.打开图层属性表9.添加字段10.完成字段添加11.计算字段id12.计算点线字段13.选中length字段14.计算length字段…...
SQL Server 索引
1、索引的概念 假设数据库中现在有2万条记录,现在要执行这样一个查询:SELECT * FROM table where num10000。如果没有索引,必须遍历整个表,直到num等于10000的这一行被找到为止;如果在num列上创建索引,SQL …...
java抽奖
目录 一、简要描述 二、代码 一、简要描述 此抽奖方式为:在1~30个数字之间 挑选7个不重复的数字输入,系统会根据中奖的号码与用户输入的号码进行比较,系统会输出是否中奖的提示! 二、代码 import java.util.Scanner; import ja…...
【springboot+云计算】B/S医院信息管理系统源码(云HIS)
一、基于云计算技术的B/S架构的医院管理系统(简称云HIS) 采用前后端分离架构,前端由Angular框架、JavaScript语言开发;后端使用Java语言开发。系统遵循服务化、模块化原则开发,具有强大的可扩展性,二次开发方便快捷。为医疗机构提…...
go 读写 excel 读取 txt 繁体中文转码
读取txt,繁体中文转码 package mainimport ("bufio""fmt""golang.org/x/text/encoding/traditionalchinese""os" )func readTxtTest() {txtPath : C:\Users\admin\Desktop\contact.txtfile, err : os.Open(txtPath)if err…...
docker网卡的IP地址修改
1. 安装docker 请参考 Linux系统在线安装docker任意版本完整教程 2. dockers启动一个容器查看容器ip docker run -d --name nginx -p 80:80 nginx #启动一个容器 docker ps -a #查看容器正常运行 docker inspect --format {{ .NetworkSettings.IPAddress }} nginx ##查看…...
python与深度学习——基础环境搭建
一、安装jupyter notebook Jupyter Notebook是一个开源的交互式笔记本环境,可以用于编写和执行代码、创建可视化效果、展示数据分析结果等。我们在这里用它实现代码运行和观察运行结果。安装jupyter notebook实质上是安装Anaconda,后续还要在Anaconda Prompt中使用c…...
Django实现简单的音乐播放器 2
在《Django实现简单的音乐播放器 1》前期准备的基础上开始开发。 效果: 目录 项目视图 创建视图方法 路由加载视图 加载模板 创建首页html文件 加载静态资源文件 加载静态文件 使用方法 启动服务器 加载数据表 创建表模型 生成表迁移 执行创建表 插入…...
OpenCV 入门教程:图像读取和显示
OpenCV 入门教程:图像读取和显示 导语一、图像读取1.1、导入 OpenCV 库1.2、读取图像文件1.3、图像读取的返回值 二、图像显示2.1、创建窗口2.2、图像显示2.3、等待按键2.4、关闭窗口 三、示例应用总结 导语 在计算机视觉和图像处理领域,读取和显示图像…...
什么是GPT?
文章目录 1、什么是GPT?2、gpt版本时间线3、我们能用GPT做什么?4、如何快速体验GPT?5、作为一名开发者,如何在代码中使用GPT?6、如何在现有项目中使用和部署GPT?7、GPT的优缺点?8、对于人工智能…...
如何通过浏览器配置哪些网页不走代理服务器,Lantern开启后部分网页打不开了
浏览器点设置 > 搜索“代理” > “打开计算机的代理设置” > 编辑“使用代理服务器” 搜索“代理” > “打开计算机的代理设置” > 编辑“使用代理服务器”,将不用代理的url链接域名写进来,点击保存。然后刷新打不开的网页,…...
Redis常见面试题
什么是Redis持久化?Redis有哪几种持久化方式?优缺点是什么 把redis内存中的数据持久化到磁盘的过程就是redis持久化。RDB:快照存储,每隔一段时间对redis内存中的数据进程快照存储。优点:恢复数据快 缺点:数据完整性差 AOF:日志追加 把每个写…...
应用零信任原则:案例研究和现场经验教训
随着云架构、软件即服务和分布式劳动力日益成为当今现代组织的主导现实,零信任安全模型已成为首选安全范例。 因此,描述零信任安全原则以及构成零信任架构 (ZTA) 的组件的出版物和资源数量几乎令人瘫痪。该行业缺乏的是一个多样化的示例库,可…...
RabbitMQ系列(14)--Topics交换机的简介与实现
1、Topics交换机的介绍 Topics交换机能让消息只发送往绑定了指定routingkey的队列中去,不同于Direct交换机的是,Topics能把一个消息往多个不同的队列发送;Topics交换机的routingkey不能随意写,必须是一个单词列表,并以…...
解决PyInstaller打包selenium脚本时弹出driver终端窗口
解决PyInstaller打包selenium脚本时弹出driver终端窗口 找到service.py C:\Users\XXX\AppData\Roaming\Python\Python39\site-packages\selenium\webdriver\common\service.py添加creationflags 在第77行添加: creationflags134217728使用PyInstaller打包 pyinstaller -F -w -…...
基于卷积神经网络VGG的猫狗识别
!有需要本项目的实验源码的可以私信博主! 摘要:随着大数据时代的到来,深度学习、数据挖掘、图像处理等已经成为了一个热门研究方向。深度学习是一个复杂的机器学习算法,在语音和图像识别方面取得的效果,远远…...
mysql查询语句练习总结(涵盖所有sql语法)
最近在学习SQL嘛,所以各个地方找题目来练手,毕竟现在能离得开数据库么? Student(S#,Sname,Sage,Ssex) 学生表 Course(C#,Cname,T#) 课程表 SC(S#,C#,score) 成绩表 Teacher(T#,Tname) 教师表 问题: 1、查询“001”课程比“002”课程成绩高的所有学生的学号&#x…...
TypeScript 中 any、unknown、never 和 void 有什么区别?
一 unknown: 未知类型 unknown: 未知类型是typescript 3.0 中引入的新类型。 1.1 所有类型的字面量都可以分配给unknown类型 unknown未知类型,代表变量类型未知,也就是可能为任意类型,所以, 所有类型的字面量都可以分配给unkno…...
算法Day60 | 84.柱状图中最大的矩形,刷题总结
Day60 84.柱状图中最大的矩形刷题总结 84.柱状图中最大的矩形 题目链接:84.柱状图中最大的矩形 遍历每个元素,找到左右元素小于当前元素的,以左右元素间的区间(左开右开区间)所围成的面积中的最大值。 数组尾部加一个…...
python实现pdf转换为word文档,尽量保持格式不变
from pdf2docx import Converterdef convert_pdf_to_word(pdf_path, docx_path, font_path):# 创建 pdf2docx.Converter 对象,用于进行 PDF 到 Word 文档的转换操作。cv Converter(pdf_path)# 设置系统默认字体文件的路径cv.font_path font_path# docx_path 转换…...
[特殊字符] 智能合约中的数据是如何在区块链中保持一致的?
🧠 智能合约中的数据是如何在区块链中保持一致的? 为什么所有区块链节点都能得出相同结果?合约调用这么复杂,状态真能保持一致吗?本篇带你从底层视角理解“状态一致性”的真相。 一、智能合约的数据存储在哪里…...
进程地址空间(比特课总结)
一、进程地址空间 1. 环境变量 1 )⽤户级环境变量与系统级环境变量 全局属性:环境变量具有全局属性,会被⼦进程继承。例如当bash启动⼦进程时,环 境变量会⾃动传递给⼦进程。 本地变量限制:本地变量只在当前进程(ba…...
通过Wrangler CLI在worker中创建数据库和表
官方使用文档:Getting started Cloudflare D1 docs 创建数据库 在命令行中执行完成之后,会在本地和远程创建数据库: npx wranglerlatest d1 create prod-d1-tutorial 在cf中就可以看到数据库: 现在,您的Cloudfla…...
可靠性+灵活性:电力载波技术在楼宇自控中的核心价值
可靠性灵活性:电力载波技术在楼宇自控中的核心价值 在智能楼宇的自动化控制中,电力载波技术(PLC)凭借其独特的优势,正成为构建高效、稳定、灵活系统的核心解决方案。它利用现有电力线路传输数据,无需额外布…...
376. Wiggle Subsequence
376. Wiggle Subsequence 代码 class Solution { public:int wiggleMaxLength(vector<int>& nums) {int n nums.size();int res 1;int prediff 0;int curdiff 0;for(int i 0;i < n-1;i){curdiff nums[i1] - nums[i];if( (prediff > 0 && curdif…...
【SQL学习笔记1】增删改查+多表连接全解析(内附SQL免费在线练习工具)
可以使用Sqliteviz这个网站免费编写sql语句,它能够让用户直接在浏览器内练习SQL的语法,不需要安装任何软件。 链接如下: sqliteviz 注意: 在转写SQL语法时,关键字之间有一个特定的顺序,这个顺序会影响到…...
Spring AI 入门:Java 开发者的生成式 AI 实践之路
一、Spring AI 简介 在人工智能技术快速迭代的今天,Spring AI 作为 Spring 生态系统的新生力量,正在成为 Java 开发者拥抱生成式 AI 的最佳选择。该框架通过模块化设计实现了与主流 AI 服务(如 OpenAI、Anthropic)的无缝对接&…...
自然语言处理——Transformer
自然语言处理——Transformer 自注意力机制多头注意力机制Transformer 虽然循环神经网络可以对具有序列特性的数据非常有效,它能挖掘数据中的时序信息以及语义信息,但是它有一个很大的缺陷——很难并行化。 我们可以考虑用CNN来替代RNN,但是…...
UR 协作机器人「三剑客」:精密轻量担当(UR7e)、全能协作主力(UR12e)、重型任务专家(UR15)
UR协作机器人正以其卓越性能在现代制造业自动化中扮演重要角色。UR7e、UR12e和UR15通过创新技术和精准设计满足了不同行业的多样化需求。其中,UR15以其速度、精度及人工智能准备能力成为自动化领域的重要突破。UR7e和UR12e则在负载规格和市场定位上不断优化…...
如何在最短时间内提升打ctf(web)的水平?
刚刚刷完2遍 bugku 的 web 题,前来答题。 每个人对刷题理解是不同,有的人是看了writeup就等于刷了,有的人是收藏了writeup就等于刷了,有的人是跟着writeup做了一遍就等于刷了,还有的人是独立思考做了一遍就等于刷了。…...
