碰撞检测 | 图解凸多边形分离轴定理(附ROS C++可视化)
目录
- 0 专栏介绍
- 1 凸多边形碰撞检测
- 2 多边形判凸算法
- 3 分离轴定理(SAT)
- 4 算法仿真与可视化
- 4.1 核心算法
- 4.2 仿真实验
0 专栏介绍
🔥课设、毕设、创新竞赛必备!🔥本专栏涉及更高阶的运动规划算法轨迹优化实战,包括:曲线生成、碰撞检测、安全走廊、优化建模(QP、SQP、NMPC、iLQR等)、轨迹优化(梯度法、曲线法等),每个算法都包含代码实现加深理解
🚀详情:运动规划实战进阶:轨迹优化篇
本期实现如下的碰撞检测效果

1 凸多边形碰撞检测
在计算机图形学、游戏开发和机器人运动规划中,碰撞检测是保证物体交互真实性的核心技术。凸多边形因其独特的几何特性(任意两点连线均位于图形内部),成为碰撞检测的高效研究对象。与凹多边形相比,凸多边形的碰撞判定可通过分离轴定理(Separating Axis Theorem, SAT)在多项式时间内完成,且无需复杂的三角剖分。本节将通过几何投影原理,揭示如何通过极值投影快速判断两个凸多边形是否相交
2 多边形判凸算法
并非所有多边形都天生为“凸”。判凸算法是碰撞检测的前置关卡,其任务是判断给定多边形的顶点序列是否满足凸性条件,只有凸多边形才能应用分离轴定理进行碰撞检测。
通过向量积可以判断向量的旋转方向。如图所示,由于
P 1 P 2 → × P 2 P 3 → > 0 \overrightarrow{P_1P_2}\times \overrightarrow{P_2P_3}>0 P1P2×P2P3>0
说明从 P 1 P 2 → \overrightarrow{P_1P_2} P1P2到 P 2 P 3 → \overrightarrow{P_2P_3} P2P3是向左转;由于
P 2 P 3 → × P 3 P 4 → > 0 \overrightarrow{P_2P_3}\times \overrightarrow{P_3P_4}>0 P2P3×P3P4>0
说明从 P 2 P 3 → \overrightarrow{P_2P_3} P2P3到 P 3 P 4 → \overrightarrow{P_3P_4} P3P4是向右转。若多边形是凸多边形,则向量的选择方向始终同向——逆时针遍历则总是向左转、顺时针遍历则总是向右转。所以在逆时针遍历多边形顶点的过程中,若存在
P i − 1 P i → × P i P i + 1 → < 0 \overrightarrow{P_{i-1}P_i}\times \overrightarrow{P_iP_{i+1}}<0 Pi−1Pi×PiPi+1<0
则表明多边形非凸,否则为凸多边形。

3 分离轴定理(SAT)
分离轴定理的核心思想直击几何本质:若存在一条直线能将两图形投影分隔,则二者不相交;反之则碰撞。直观地,如下图所示,若两个凸多边形没有发生碰撞,则必存在某角度的光源使两物体的投影存在间隙;也即必存在一条直线使得两个多边形在这条直线上的投影不重叠,这条直线被称为分离轴

如下图所示,称凸多边形的某条边为边缘向量,平行于边缘向量法向的直线称为投影轴。所有投影轴组成投影轴集合 P P P, ∣ P ∣ |P| ∣P∣等于两个凸多边形的边数之和。遍历 P P P中的每条投影轴 p i \boldsymbol{p}_i pi,将两个多边形分别投影到 p i \boldsymbol{p}_i pi上得到两个投影线段,其重叠区域的长度称为重叠深度 d i o v e r l a p d_{i}^{\mathrm{overlap}} dioverlap。定义穿透深度
d p = min i { d i o v e r l a p } d^p=\min _i\left\{ d_{i}^{\mathrm{overlap}} \right\} dp=imin{dioverlap}
若 d p = 0 d^p=0 dp=0则两个凸多边形没有发生碰撞;若 d p > 0 d^p>0 dp>0则两凸多边形存在碰撞,其中 d p d^p dp所在的投影轴称为穿透向量或分离向量,将其中一个多边形沿分离向量运动 d p d^p dp个单位可以最快消除碰撞。

分离轴定理的算法流程如下所示

4 算法仿真与可视化
4.1 核心算法
首先,找到两个待检测多边形的分离轴。分离轴平行于边缘法向量,其位置不限,因为其长度是无限的,该轴的方向才是关键
std::vector<Ogre::Vector3> axes;
for (int i = 0; i < size(); ++i)
{const auto& pt1 = points_[i];const auto& pt2 = points_[next(i)];const auto& edge = pt2 - pt1;Ogre::Vector3 nor(edge.y, -edge.x, 0.0);nor.normalise();axes.emplace_back(std::move(nor));
}for (int i = 0; i < other->size(); ++i)
{const auto& pt1 = other->points()[i];const auto& pt2 = other->points()[other->next(i)];const auto& edge = pt2 - pt1;Ogre::Vector3 nor(edge.y, -edge.x, 0.0);nor.normalise();axes.emplace_back(std::move(nor));
}
接着,对每一条分离轴计算两个多边形在该轴的投影。通过将一个多边形上的每个顶点向量,与选定的投影轴进行点积,然后保留该多边形在该投影轴上所有投影中的最大值和最小值,即可表示一个多边形在某投影轴上的投影
double proj_1_min, proj_1_max;
double proj_2_min, proj_2_max;
project(points_, axis, proj_1_min, proj_1_max);
project(other->points(), axis, proj_2_min, proj_2_max);
只要存在一条分离轴使两个多边形的投影不重合,即表明不发生碰撞
if (!(proj_1_min <= proj_2_max && proj_2_min <= proj_1_max))
{return false;
}
4.2 仿真实验
通过Rviz->Add New Tool添加Polygon Simulation插件

开启碰撞检测功能后验证凸多边形的相交检测功能
- 未相交情形

- 相交情形

完整工程代码请联系下方博主名片获取
🔥 更多精彩专栏:
- 《ROS从入门到精通》
- 《Pytorch深度学习实战》
- 《机器学习强基计划》
- 《运动规划实战精讲》
- …
相关文章:
碰撞检测 | 图解凸多边形分离轴定理(附ROS C++可视化)
目录 0 专栏介绍1 凸多边形碰撞检测2 多边形判凸算法3 分离轴定理(SAT)4 算法仿真与可视化4.1 核心算法4.2 仿真实验 0 专栏介绍 🔥课设、毕设、创新竞赛必备!🔥本专栏涉及更高阶的运动规划算法轨迹优化实战,包括:曲线…...
Python 基本数据类型
目录 1. 字符串(String) 2. 列表(List) 3. 字典(Dictionary) 4. 集合(Set) 5. 数字(Number) 6. 布尔值(Boolean) 1. 字符串&…...
突破“第一崇拜“:五维心理重构之路
一、视频介绍 在这个崇尚"第一"的时代,我们如何找到自己的独特价值?本视频将带您踏上五维心理重构之旅,从诗意人生的角度探讨如何突破"圣人之下皆蝼蚁"的局限。我们将穿越人生的不同阶段,从青春的意气风发到…...
KubeKey一键安装部署k8s集群和KubeSphere详细教程
目录 一、KubeKey简介 二、k8s集群KubeSphere安装 集群规划 硬件要求 Kubernetes支持版本 操作系统要求 SSH免密登录 配置集群时钟 所有节点安装依赖 安装docker DNS要求 存储要求 下载 KubeKey 验证KubeKey 配置集群文件 安装集群 验证命令 登录页面 一、Ku…...
UE5网络通信架构解析
文章目录 前言一、客户端-服务器架构(C/S Model)二、对等网络架构(P2P,非原生支持)三、混合架构(自定义扩展)四、UE5网络核心机制 前言 UE5的网络通信主要基于客户端-服务器(C/S&am…...
实验3 知识表示与推理
实验3 知识表示与推理 一、实验目的 (1)掌握知识和知识表示的基本概念,理解其在AI中的深刻含义与意义; (2)熟悉AI中常用的知识表示方法的优缺点及其应用场景; (3)掌握产…...
基于Springboot银行信用卡额度管理系统【附源码】
基于Springboot银行信用卡额度管理系统 效果如下: 系统登陆页面 用户个人中心页面 新增信用卡申请页面 评估审核页面 管理员主页面 评估审核页面 操作日志管理页面 消费页面 研究背景 随着金融行业的快速发展和信息技术的不断进步,信用卡作为一种便捷…...
达梦数据库学习笔记@1
目录 达梦数据库学习笔记一、表空间管理(一)默认表空间(二)相关数据字典(三)表空间操作(四)临时表空间管理 二、重做日志管理(一)系统视图(二&…...
图像处理篇---图像处理中常见参数
文章目录 前言一、分贝(dB)的原理1.公式 二、峰值信噪比(PSNR, Peak Signal-to-Noise Ratio)1.用途2.公式3.示例 三、信噪比(SNR, Signal-to-Noise Ratio)1.用途2.公式3.示例 四、动态范围(Dyna…...
AI Agent实战:打造京东广告主的超级助手 | 京东零售技术实践
前言 自2022年末ChatGPT的问世,大语言模型(LLM)技术引发全球关注。在大模型技术落地的最佳实践中,智能体(Agent)架构显现出巨大潜力,成为业界的普遍共识,各大公司也纷纷启动Agent技…...
50周学习go语言:第1周 环境搭建
以下是为零基础学习者准备的详细第1周教程,包含环境搭建、工具配置和首个Go程序的完整操作指南: 一、Go语言环境安装(Windows/macOS/Linux通用) 1. 下载安装包 官网地址:https://go.dev/dl//根据系统选择对应版本&am…...
4. MySQL 逻辑架构说明
4. MySQL 逻辑架构说明 文章目录 4. MySQL 逻辑架构说明1. 逻辑架构剖析1.1 服务器处理客户端请求1.2 Connectors(连接器)1.3 第1层:连接层1.4 第2层:服务层1.5 第3层:引擎层1.6 存储层 2. SQL执行流程2.1 MySQL 中的 SQL 执行流程 2.2 MySQL…...
《AI与NLP:开启元宇宙社交互动新纪元》
在科技飞速发展的当下,元宇宙正从概念逐步走向现实,成为人们关注的焦点。而在元宇宙诸多令人瞩目的特性中,社交互动体验是其核心魅力之一。人工智能(AI)与自然语言处理(NLP)技术的迅猛发展&…...
面对STM32的庞大体系,如何避免迷失在细节中?
我第一次接触STM32时,我以为抱着开发板就是拥抱未来,实际上一开机就喜提四大耳光,看到卖家演示的MP3播放、TFT彩屏、网口通信好炫酷,忍不住买回来掌握这些神技,到最后发现最实用的还是开发板的关机键和复位键。 看视频…...
ragflow-RAPTOR到底是什么?请通俗的解释!
RAPTOR有两种不同的含义,具体取决于上下文: RAPTOR作为一种信息检索技术 RAPTOR是一种基于树状结构的信息检索系统,全称为“Recursive Abstractive Processing for Tree-Organized Retrieval”(递归抽象处理树组织检索)…...
Linux系统移植之Uboot启动流程
Linux系统移植之Uboot启动流程 一,Uboot启动流程1.Uboot的两阶段1.1.第一阶段1.11.硬件初始化1.12.复制 U-Boot 到 RAM1.13.跳转到第二阶段 1.2.第二阶段1.21.C 语言环境初始化1.22. 硬件设备初始化1.23. 加载环境变量1.24. 显示启动信息1.25. 等待用户输入…...
【Open X-Embodiment】简单数据下载与预处理
文章目录 1. RLDS Dataset2. 处理成numpy格式3. 存储桶 1. RLDS Dataset 从 Octo 里面找到数据下载的代码 rlds_dataset_mod github 按照官网代码配置环境后,修改 prepare_open_x.sh,相当于只用 gsutil 下载数据: DOWNLOAD_DIR/mnt/data…...
【第四节】C++设计模式(创建型模式)-Builder(建造者)模式
目录 引言 一、Builder 模式概述 二、Builder 模式举例 三、Builder 模式的结构 四、Builder 模式的实现 五、Builder 模式的优缺点 六、总结 引言 Builder 模式是一种创建型设计模式,旨在将复杂对象的构建过程与其表示分离。通过一步步构建对象,…...
排查JVM的一些命令
查看JVM相关信息的方法 环境: Win10, jdk17 查看端口的Pid netstat -ano | findstr <端口号>列出当前运行的JVM进程 ## 用于输出JVM中运行的进程状态信息。通过jps,可以快速获取Java进程的PID(进程标识符), …...
uni-app(位置1)
文章目录 一、获取当前的地理位置、速度 uni.getLocation(OBJECT)二、打开地图选择位置 uni.chooseLocation(OBJECT)三、使用应用内置地图查看位置。uni.openLocation(OBJECT) 一、获取当前的地理位置、速度 uni.getLocation(OBJECT) App平台 manifest中配置好自己的地图厂商k…...
前端导出带有合并单元格的列表
// 导出async function exportExcel(fileName "共识调整.xlsx") {// 所有数据const exportData await getAllMainData();// 表头内容let fitstTitleList [];const secondTitleList [];allColumns.value.forEach(column > {if (!column.children) {fitstTitleL…...
深入解析C++中的extern关键字:跨文件共享变量与函数的终极指南
🚀 C extern 关键字深度解析:跨文件编程的终极指南 📅 更新时间:2025年6月5日 🏷️ 标签:C | extern关键字 | 多文件编程 | 链接与声明 | 现代C 文章目录 前言🔥一、extern 是什么?&…...
分布式增量爬虫实现方案
之前我们在讨论的是分布式爬虫如何实现增量爬取。增量爬虫的目标是只爬取新产生或发生变化的页面,避免重复抓取,以节省资源和时间。 在分布式环境下,增量爬虫的实现需要考虑多个爬虫节点之间的协调和去重。 另一种思路:将增量判…...
docker 部署发现spring.profiles.active 问题
报错: org.springframework.boot.context.config.InvalidConfigDataPropertyException: Property spring.profiles.active imported from location class path resource [application-test.yml] is invalid in a profile specific resource [origin: class path re…...
使用Spring AI和MCP协议构建图片搜索服务
目录 使用Spring AI和MCP协议构建图片搜索服务 引言 技术栈概览 项目架构设计 架构图 服务端开发 1. 创建Spring Boot项目 2. 实现图片搜索工具 3. 配置传输模式 Stdio模式(本地调用) SSE模式(远程调用) 4. 注册工具提…...
NPOI Excel用OLE对象的形式插入文件附件以及插入图片
static void Main(string[] args) {XlsWithObjData();Console.WriteLine("输出完成"); }static void XlsWithObjData() {// 创建工作簿和单元格,只有HSSFWorkbook,XSSFWorkbook不可以HSSFWorkbook workbook new HSSFWorkbook();HSSFSheet sheet (HSSFSheet)workboo…...
计算机基础知识解析:从应用到架构的全面拆解
目录 前言 1、 计算机的应用领域:无处不在的数字助手 2、 计算机的进化史:从算盘到量子计算 3、计算机的分类:不止 “台式机和笔记本” 4、计算机的组件:硬件与软件的协同 4.1 硬件:五大核心部件 4.2 软件&#…...
上位机开发过程中的设计模式体会(1):工厂方法模式、单例模式和生成器模式
简介 在我的 QT/C 开发工作中,合理运用设计模式极大地提高了代码的可维护性和可扩展性。本文将分享我在实际项目中应用的三种创造型模式:工厂方法模式、单例模式和生成器模式。 1. 工厂模式 (Factory Pattern) 应用场景 在我的 QT 项目中曾经有一个需…...
VisualXML全新升级 | 新增数据库编辑功能
VisualXML是一个功能强大的网络总线设计工具,专注于简化汽车电子系统中复杂的网络数据设计操作。它支持多种主流总线网络格式的数据编辑(如DBC、LDF、ARXML、HEX等),并能够基于Excel表格的方式生成和转换多种数据库文件。由此&…...
FFmpeg avformat_open_input函数分析
函数内部的总体流程如下: avformat_open_input 精简后的代码如下: int avformat_open_input(AVFormatContext **ps, const char *filename,ff_const59 AVInputFormat *fmt, AVDictionary **options) {AVFormatContext *s *ps;int i, ret 0;AVDictio…...
