当前位置: 首页 > news >正文

碰撞检测 | 图解凸多边形分离轴定理(附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 Pi1Pi ×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插件

s

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

  • 未相交情形

在这里插入图片描述

  • 相交情形

在这里插入图片描述

完整工程代码请联系下方博主名片获取


🔥 更多精彩专栏

  • 《ROS从入门到精通》
  • 《Pytorch深度学习实战》
  • 《机器学习强基计划》
  • 《运动规划实战精讲》

👇源码获取 · 技术交流 · 抱团学习 · 咨询分享 请联系👇

相关文章:

碰撞检测 | 图解凸多边形分离轴定理(附ROS C++可视化)

目录 0 专栏介绍1 凸多边形碰撞检测2 多边形判凸算法3 分离轴定理(SAT)4 算法仿真与可视化4.1 核心算法4.2 仿真实验 0 专栏介绍 &#x1f525;课设、毕设、创新竞赛必备&#xff01;&#x1f525;本专栏涉及更高阶的运动规划算法轨迹优化实战&#xff0c;包括&#xff1a;曲线…...

Python 基本数据类型

目录 1. 字符串&#xff08;String&#xff09; 2. 列表&#xff08;List&#xff09; 3. 字典&#xff08;Dictionary&#xff09; 4. 集合&#xff08;Set&#xff09; 5. 数字&#xff08;Number&#xff09; 6. 布尔值&#xff08;Boolean&#xff09; 1. 字符串&…...

突破“第一崇拜“:五维心理重构之路

一、视频介绍 在这个崇尚"第一"的时代&#xff0c;我们如何找到自己的独特价值&#xff1f;本视频将带您踏上五维心理重构之旅&#xff0c;从诗意人生的角度探讨如何突破"圣人之下皆蝼蚁"的局限。我们将穿越人生的不同阶段&#xff0c;从青春的意气风发到…...

KubeKey一键安装部署k8s集群和KubeSphere详细教程

目录 一、KubeKey简介 二、k8s集群KubeSphere安装 集群规划 硬件要求 Kubernetes支持版本 操作系统要求 SSH免密登录 配置集群时钟 所有节点安装依赖 安装docker DNS要求 存储要求 下载 KubeKey 验证KubeKey 配置集群文件 安装集群 验证命令 登录页面 一、Ku…...

UE5网络通信架构解析

文章目录 前言一、客户端-服务器架构&#xff08;C/S Model&#xff09;二、对等网络架构&#xff08;P2P&#xff0c;非原生支持&#xff09;三、混合架构&#xff08;自定义扩展&#xff09;四、UE5网络核心机制 前言 UE5的网络通信主要基于客户端-服务器&#xff08;C/S&am…...

实验3 知识表示与推理

实验3 知识表示与推理 一、实验目的 &#xff08;1&#xff09;掌握知识和知识表示的基本概念&#xff0c;理解其在AI中的深刻含义与意义&#xff1b; &#xff08;2&#xff09;熟悉AI中常用的知识表示方法的优缺点及其应用场景&#xff1b; &#xff08;3&#xff09;掌握产…...

基于Springboot银行信用卡额度管理系统【附源码】

基于Springboot银行信用卡额度管理系统 效果如下&#xff1a; 系统登陆页面 用户个人中心页面 新增信用卡申请页面 评估审核页面 管理员主页面 评估审核页面 操作日志管理页面 消费页面 研究背景 随着金融行业的快速发展和信息技术的不断进步&#xff0c;信用卡作为一种便捷…...

达梦数据库学习笔记@1

目录 达梦数据库学习笔记一、表空间管理&#xff08;一&#xff09;默认表空间&#xff08;二&#xff09;相关数据字典&#xff08;三&#xff09;表空间操作&#xff08;四&#xff09;临时表空间管理 二、重做日志管理&#xff08;一&#xff09;系统视图&#xff08;二&…...

图像处理篇---图像处理中常见参数

文章目录 前言一、分贝&#xff08;dB&#xff09;的原理1.公式 二、峰值信噪比&#xff08;PSNR, Peak Signal-to-Noise Ratio&#xff09;1.用途2.公式3.示例 三、信噪比&#xff08;SNR, Signal-to-Noise Ratio&#xff09;1.用途2.公式3.示例 四、动态范围&#xff08;Dyna…...

AI Agent实战:打造京东广告主的超级助手 | 京东零售技术实践

前言 自2022年末ChatGPT的问世&#xff0c;大语言模型&#xff08;LLM&#xff09;技术引发全球关注。在大模型技术落地的最佳实践中&#xff0c;智能体&#xff08;Agent&#xff09;架构显现出巨大潜力&#xff0c;成为业界的普遍共识&#xff0c;各大公司也纷纷启动Agent技…...

50周学习go语言:第1周 环境搭建

以下是为零基础学习者准备的详细第1周教程&#xff0c;包含环境搭建、工具配置和首个Go程序的完整操作指南&#xff1a; 一、Go语言环境安装&#xff08;Windows/macOS/Linux通用&#xff09; 1. 下载安装包 官网地址&#xff1a;https://go.dev/dl//根据系统选择对应版本&am…...

4. MySQL 逻辑架构说明

4. MySQL 逻辑架构说明 文章目录 4. MySQL 逻辑架构说明1. 逻辑架构剖析1.1 服务器处理客户端请求1.2 Connectors(连接器)1.3 第1层&#xff1a;连接层1.4 第2层&#xff1a;服务层1.5 第3层&#xff1a;引擎层1.6 存储层 2. SQL执行流程2.1 MySQL 中的 SQL 执行流程 2.2 MySQL…...

《AI与NLP:开启元宇宙社交互动新纪元》

在科技飞速发展的当下&#xff0c;元宇宙正从概念逐步走向现实&#xff0c;成为人们关注的焦点。而在元宇宙诸多令人瞩目的特性中&#xff0c;社交互动体验是其核心魅力之一。人工智能&#xff08;AI&#xff09;与自然语言处理&#xff08;NLP&#xff09;技术的迅猛发展&…...

面对STM32的庞大体系,如何避免迷失在细节中?

我第一次接触STM32时&#xff0c;我以为抱着开发板就是拥抱未来&#xff0c;实际上一开机就喜提四大耳光&#xff0c;看到卖家演示的MP3播放、TFT彩屏、网口通信好炫酷&#xff0c;忍不住买回来掌握这些神技&#xff0c;到最后发现最实用的还是开发板的关机键和复位键。 看视频…...

ragflow-RAPTOR到底是什么?请通俗的解释!

RAPTOR有两种不同的含义&#xff0c;具体取决于上下文&#xff1a; RAPTOR作为一种信息检索技术 RAPTOR是一种基于树状结构的信息检索系统&#xff0c;全称为“Recursive Abstractive Processing for Tree-Organized Retrieval”&#xff08;递归抽象处理树组织检索&#xff09…...

Linux系统移植之Uboot启动流程

Linux系统移植之Uboot启动流程 一&#xff0c;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. 等待用户输入&#xf…...

【Open X-Embodiment】简单数据下载与预处理

文章目录 1. RLDS Dataset2. 处理成numpy格式3. 存储桶 1. RLDS Dataset 从 Octo 里面找到数据下载的代码 rlds_dataset_mod github 按照官网代码配置环境后&#xff0c;修改 prepare_open_x.sh&#xff0c;相当于只用 gsutil 下载数据&#xff1a; DOWNLOAD_DIR/mnt/data…...

【第四节】C++设计模式(创建型模式)-Builder(建造者)模式

目录 引言 一、Builder 模式概述 二、Builder 模式举例 三、Builder 模式的结构 四、Builder 模式的实现 五、Builder 模式的优缺点 六、总结 引言 Builder 模式是一种创建型设计模式&#xff0c;旨在将复杂对象的构建过程与其表示分离。通过一步步构建对象&#xff0c;…...

排查JVM的一些命令

查看JVM相关信息的方法 环境&#xff1a; Win10, jdk17 查看端口的Pid netstat -ano | findstr <端口号>列出当前运行的JVM进程 ## 用于输出JVM中运行的进程状态信息。通过jps&#xff0c;可以快速获取Java进程的PID&#xff08;进程标识符&#xff09;&#xff0c; …...

uni-app(位置1)

文章目录 一、获取当前的地理位置、速度 uni.getLocation(OBJECT)二、打开地图选择位置 uni.chooseLocation(OBJECT)三、使用应用内置地图查看位置。uni.openLocation(OBJECT) 一、获取当前的地理位置、速度 uni.getLocation(OBJECT) App平台 manifest中配置好自己的地图厂商k…...

Python:操作 Excel 折叠

💖亲爱的技术爱好者们,热烈欢迎来到 Kant2048 的博客!我是 Thomas Kant,很开心能在CSDN上与你们相遇~💖 本博客的精华专栏: 【自动化测试】 【测试经验】 【人工智能】 【Python】 Python 操作 Excel 系列 读取单元格数据按行写入设置行高和列宽自动调整行高和列宽水平…...

成都鼎讯硬核科技!雷达目标与干扰模拟器,以卓越性能制胜电磁频谱战

在现代战争中&#xff0c;电磁频谱已成为继陆、海、空、天之后的 “第五维战场”&#xff0c;雷达作为电磁频谱领域的关键装备&#xff0c;其干扰与抗干扰能力的较量&#xff0c;直接影响着战争的胜负走向。由成都鼎讯科技匠心打造的雷达目标与干扰模拟器&#xff0c;凭借数字射…...

大学生职业发展与就业创业指导教学评价

这里是引用 作为软工2203/2204班的学生&#xff0c;我们非常感谢您在《大学生职业发展与就业创业指导》课程中的悉心教导。这门课程对我们即将面临实习和就业的工科学生来说至关重要&#xff0c;而您认真负责的教学态度&#xff0c;让课程的每一部分都充满了实用价值。 尤其让我…...

html-<abbr> 缩写或首字母缩略词

定义与作用 <abbr> 标签用于表示缩写或首字母缩略词&#xff0c;它可以帮助用户更好地理解缩写的含义&#xff0c;尤其是对于那些不熟悉该缩写的用户。 title 属性的内容提供了缩写的详细说明。当用户将鼠标悬停在缩写上时&#xff0c;会显示一个提示框。 示例&#x…...

C# 求圆面积的程序(Program to find area of a circle)

给定半径r&#xff0c;求圆的面积。圆的面积应精确到小数点后5位。 例子&#xff1a; 输入&#xff1a;r 5 输出&#xff1a;78.53982 解释&#xff1a;由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982&#xff0c;因为我们只保留小数点后 5 位数字。 输…...

网站指纹识别

网站指纹识别 网站的最基本组成&#xff1a;服务器&#xff08;操作系统&#xff09;、中间件&#xff08;web容器&#xff09;、脚本语言、数据厍 为什么要了解这些&#xff1f;举个例子&#xff1a;发现了一个文件读取漏洞&#xff0c;我们需要读/etc/passwd&#xff0c;如…...

MySQL:分区的基本使用

目录 一、什么是分区二、有什么作用三、分类四、创建分区五、删除分区 一、什么是分区 MySQL 分区&#xff08;Partitioning&#xff09;是一种将单张表的数据逻辑上拆分成多个物理部分的技术。这些物理部分&#xff08;分区&#xff09;可以独立存储、管理和优化&#xff0c;…...

VisualXML全新升级 | 新增数据库编辑功能

VisualXML是一个功能强大的网络总线设计工具&#xff0c;专注于简化汽车电子系统中复杂的网络数据设计操作。它支持多种主流总线网络格式的数据编辑&#xff08;如DBC、LDF、ARXML、HEX等&#xff09;&#xff0c;并能够基于Excel表格的方式生成和转换多种数据库文件。由此&…...

数据库——redis

一、Redis 介绍 1. 概述 Redis&#xff08;Remote Dictionary Server&#xff09;是一个开源的、高性能的内存键值数据库系统&#xff0c;具有以下核心特点&#xff1a; 内存存储架构&#xff1a;数据主要存储在内存中&#xff0c;提供微秒级的读写响应 多数据结构支持&…...

链式法则中 复合函数的推导路径 多变量“信息传递路径”

非常好&#xff0c;我们将之前关于偏导数链式法则中不能“约掉”偏导符号的问题&#xff0c;统一使用 二重复合函数&#xff1a; z f ( u ( x , y ) , v ( x , y ) ) \boxed{z f(u(x,y),\ v(x,y))} zf(u(x,y), v(x,y))​ 来全面说明。我们会展示其全微分形式&#xff08;偏导…...