当前位置: 首页 > 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…...

基于算法竞赛的c++编程(28)结构体的进阶应用

结构体的嵌套与复杂数据组织 在C中&#xff0c;结构体可以嵌套使用&#xff0c;形成更复杂的数据结构。例如&#xff0c;可以通过嵌套结构体描述多层级数据关系&#xff1a; struct Address {string city;string street;int zipCode; };struct Employee {string name;int id;…...

铭豹扩展坞 USB转网口 突然无法识别解决方法

当 USB 转网口扩展坞在一台笔记本上无法识别,但在其他电脑上正常工作时,问题通常出在笔记本自身或其与扩展坞的兼容性上。以下是系统化的定位思路和排查步骤,帮助你快速找到故障原因: 背景: 一个M-pard(铭豹)扩展坞的网卡突然无法识别了,扩展出来的三个USB接口正常。…...

云计算——弹性云计算器(ECS)

弹性云服务器&#xff1a;ECS 概述 云计算重构了ICT系统&#xff0c;云计算平台厂商推出使得厂家能够主要关注应用管理而非平台管理的云平台&#xff0c;包含如下主要概念。 ECS&#xff08;Elastic Cloud Server&#xff09;&#xff1a;即弹性云服务器&#xff0c;是云计算…...

.Net框架,除了EF还有很多很多......

文章目录 1. 引言2. Dapper2.1 概述与设计原理2.2 核心功能与代码示例基本查询多映射查询存储过程调用 2.3 性能优化原理2.4 适用场景 3. NHibernate3.1 概述与架构设计3.2 映射配置示例Fluent映射XML映射 3.3 查询示例HQL查询Criteria APILINQ提供程序 3.4 高级特性3.5 适用场…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院查看报告小程序

一、开发环境准备 ​​工具安装​​&#xff1a; 下载安装DevEco Studio 4.0&#xff08;支持HarmonyOS 5&#xff09;配置HarmonyOS SDK 5.0确保Node.js版本≥14 ​​项目初始化​​&#xff1a; ohpm init harmony/hospital-report-app 二、核心功能模块实现 1. 报告列表…...

(转)什么是DockerCompose?它有什么作用?

一、什么是DockerCompose? DockerCompose可以基于Compose文件帮我们快速的部署分布式应用&#xff0c;而无需手动一个个创建和运行容器。 Compose文件是一个文本文件&#xff0c;通过指令定义集群中的每个容器如何运行。 DockerCompose就是把DockerFile转换成指令去运行。 …...

PostgreSQL——环境搭建

一、Linux # 安装 PostgreSQL 15 仓库 sudo dnf install -y https://download.postgresql.org/pub/repos/yum/reporpms/EL-$(rpm -E %{rhel})-x86_64/pgdg-redhat-repo-latest.noarch.rpm# 安装之前先确认是否已经存在PostgreSQL rpm -qa | grep postgres# 如果存在&#xff0…...

实战三:开发网页端界面完成黑白视频转为彩色视频

​一、需求描述 设计一个简单的视频上色应用&#xff0c;用户可以通过网页界面上传黑白视频&#xff0c;系统会自动将其转换为彩色视频。整个过程对用户来说非常简单直观&#xff0c;不需要了解技术细节。 效果图 ​二、实现思路 总体思路&#xff1a; 用户通过Gradio界面上…...

c# 局部函数 定义、功能与示例

C# 局部函数&#xff1a;定义、功能与示例 1. 定义与功能 局部函数&#xff08;Local Function&#xff09;是嵌套在另一个方法内部的私有方法&#xff0c;仅在包含它的方法内可见。 • 作用&#xff1a;封装仅用于当前方法的逻辑&#xff0c;避免污染类作用域&#xff0c;提升…...

6️⃣Go 语言中的哈希、加密与序列化:通往区块链世界的钥匙

Go 语言中的哈希、加密与序列化:通往区块链世界的钥匙 一、前言:离区块链还有多远? 区块链听起来可能遥不可及,似乎是只有密码学专家和资深工程师才能涉足的领域。但事实上,构建一个区块链的核心并不复杂,尤其当你已经掌握了一门系统编程语言,比如 Go。 要真正理解区…...