点到线段的最短距离——矢量法

zz/2024/7/24 1:17:53

最近在看recast&detour源码的时候有遇到许多数学上的算法问题,特此记录,以便以后查看。

矢量法推导: 

求点P到线段AB的最短距离。分成以下三种情况(a),(b),(c)。

(勘误:d=PC 应该是在 ∠PAB和∠PBA都小于90°的情况下,而不是▲ABP为锐角▲)

所以可以先根据计算出r的值,进而对应计算A点 B点  C点 和 P点之间的距离即可。

特殊情况:

1.当P在线段AB上:计算出来r仍然是 1>r>0, P点即C点,PC的距离d = 0; 

2.当P在线段AB端点或其延长线上:r仍然有是 r<=0 或者是 r >= 1,仍然是计算 PA 或 PB 的距离;

3.当AB是同一点:无法计算r,所以需要对AB的长度进行一个判断,如果是AB为零,直接令r = 0,直接计算AP或BP的距离都一样。

库中代码:

点pt 到线段pq的最短距离。

static float distancePtSeg(const float* pt, const float* p, const float* q)
{// 先计算r的值 看r的范围 (p相当于A点,q相当于B点,pt相当于P点)// AB 向量float pqx = q[0] - p[0];float pqy = q[1] - p[1];float pqz = q[2] - p[2];// AP 向量float dx = pt[0] - p[0];float dy = pt[1] - p[1];float dz = pt[2] - p[2];// qp线段长度的平方=上面公式中的分母:AB向量的平方。float d = pqx*pqx + pqy*pqy + pqz*pqz;   // (p pt向量)点积 (pq 向量)= 公式中的分子:AP点积ABfloat t = pqx*dx + pqy*dy + pqz*dz;         // t 就是 公式中的r了 if (d > 0)         // 除数不能为0; 如果为零 t应该也为零。下面计算结果仍然成立。                   t /= d;    // 此时t 相当于 上述推导中的 r。// 分类讨论 if (t < 0)t = 0;     // 当t(r)< 0时,最短距离即为 pt点 和 p点(A点和P点)之间的距离。else if (t > 1)t = 1;     // 当t(r)> 1时,最短距离即为 pt点 和 q点(B点和P点)之间的距离。// t = 0,计算 pt点 和 p点的距离; (A点和P点)// t = 1, 计算 pt点 和 q点 的距离; (B点和P点)// 否则计算 pt点 和 投影点 的距离。(C点和P点 ,t*(pqx,pqy,pqz)就是向量AC)dx = p[0] + t*pqx - pt[0];dy = p[1] + t*pqy - pt[1];dz = p[2] + t*pqz - pt[2];// 算出来是距离的平方,后续自行计算距离return dx*dx + dy*dy + dz*dz;
}

算法优点:

矢量法代码简单,计算量少。无需进行复杂的分类讨论,无需进行角度计算,无需进行面积计算等。

参考:

新浪博客

GitHub - recastnavigation/recastnavigation: Navigation-mesh Toolset for Games


http://www.ngui.cc/zz/2769448.html

相关文章

Restore IP Addresses---LeetCode

题目要求&#xff1a;输入一串字符串&#xff0c;输出可能组成的ip地址。 先申请题意&#xff0c;弄清需求&#xff1a; 会存在不是数字的字符串吗&#xff1f;都是数字 10.10.10.01 最后一个01&#xff0c;符合要求吗&#xff1f;不符合要求。 leetcode上的示例答案&#x…

Recast Detour 寻路引擎学习建议

1.初步了解Recast&Detour,完成工程的下载和生成运行 http://www.stevefsp.org/projects/rcndoc/prod/index.html 2.了解Recast-导航数据的创建 看源代码中的Sample_SoloMesh.handleBuild 函数 http://www.critterai.org/projects/nmgen_study/overview.html 此英文文档…

Failed to load Assets/Plugins/xxx.dll with error

遇到这个错误&#xff0c;首先检查看提示的路径下面是否真的有 xxx.dll 如果有&#xff0c;那就是这个dll所引用的其他的库你电脑上没有&#xff0c;本地电脑的环境问题&#xff0c;把相关的dll拷贝到系统目录或者特定的目录下就可。 如何查看你缺少什么库&#xff1a; 下载一…

std::lambda小记

目录 不同形式的语法说明 [ capture ] 例子 lambda是C11中才引入的新特性&#xff0c;能定义匿名对象&#xff0c;而不必定义独立的函数和函数对象。 在介绍函数对象的for_each例子中&#xff0c;如果不用创建函数对象&#xff0c;可以使用下面 std::for_each(dest.begin()…

std::bind小记

当std::bind函数&#xff08;是一个函数模版&#xff09;&#xff0c;用来绑定函数的某些参数并生成一个新的std::function对象。 如何来确定绑定的是函数的第几个参数&#xff0c;引入std::placeholders命名空间&#xff1a; _1,函数调用的第一个参数&#xff0c; _2第2个参…

win10 ‘XXX’不是内部或者外部命令,也不是可执行的程序

比如说 ‘Python’不是内部或者外部命令&#xff0c;也不是可执行的程序 比如说 ‘svn ’不是内部或者外部命令&#xff0c;也不是可执行的程序 没有给可执行程序设置Path环境变量 如下图进行 我的电脑右键选择属性&#xff0c;然后依此选择。把需要执行的exe&#xff0c;比如…

汇编指令和寄存器

《汇编语言》比较旧的书了&#xff0c;讲的都是实模式下的 8086 cpu 《软件调试》比较新的书 以及分析dump文件的时候的例子。 目的是看懂代码的反汇编&#xff0c;设计到汇编指令&#xff0c;相关的硬件如寄存器存储器等。 有一些寄存器的常用名字还是记住的好&#xff0c;…

MyEclipse8.5快捷键总结(持续更新)

快速查找文件&#xff1a;shift ctrl R 快速定位到行&#xff1a;ctrl L java类中快速匹配方法&#xff1a;ctrl O 不显示已关闭的项目&#xff1a;如图中所示&#xff0c; 点击反向箭头旁边的向下的箭头&#xff0c;出现下拉框&#xff0c;点击Filters&#xff0c;在C…

静态方法中为什么不能使用super和this

1.this和super的用法 this是对本身对象的引用&#xff0c;指向本身已经创建的对象。super是对父类对象的引用&#xff0c;指向父类对象。、 但是通过上一篇文章&#xff0c;我们可以知道&#xff0c;静态比对象出现的更早&#xff0c;所以this和super的指向就失去了意义。

中国天气网城市代码 Map形式和mysql数据库脚本

Map<String,String> map new HashMap<String, String>();map.put("北京","101010100");map.put("海淀","101010200");map.put("朝阳","101010300");map.put("顺义","101010400"…