[笔记本: 演算法] Line Segment Intersection 线段交叉判断

线段交叉判断方法

线性函数

http://img2.58codes.com/2024/201136227uvGSrjK8h.png

初等数学方法以多项式函数的方式找出交叉点,换句话说,如果找得出交叉点即两线段交叉。

算法

http://img2.58codes.com/2024/20113622ZKVAWYinM1.png

当p、q皆存在时应符合 http://img2.58codes.com/2024/20113622oOPBSmaGmP.pnghttp://img2.58codes.com/2024/20113622CtI29rDybS.png

如果p存在但q不存在,有可能会发生以下情形
http://img2.58codes.com/2024/20113622NFDwlGRQrX.png

结论

虽然线性函数的方法可以非常容易的以程式码呈现,但是线性函数使用除法,在程式运行时,可能需要消耗较多时间且浮点数可能使结果不準确。因此,判断两线段是否相交,需要进一步分析。

对立与定界框测试 On Opposite Side and Bounding Box Test

导入http://img2.58codes.com/2024/20113622oOPBSmaGmP.pnghttp://img2.58codes.com/2024/20113622CtI29rDybS.png 的概念,将其细分为两个测试,对立测试与定界框匡测试。
满足这两个测试的两直线则可能相交。

对立测试

http://img2.58codes.com/2024/20113622Tj6TbUbiag.png

在对立测试中,检查http://img2.58codes.com/2024/20113622RORTGYKAnV.pnghttp://img2.58codes.com/2024/20113622Gq1jaNf81k.png 互相在L1的另外一边。

利用线性函数所推导出的直线方程式http://img2.58codes.com/2024/20113622UVIPsOEfZb.png
L1 = http://img2.58codes.com/2024/20113622Buk9EUeBrA.png
http://img2.58codes.com/2024/20113622RORTGYKAnV.pnghttp://img2.58codes.com/2024/20113622Gq1jaNf81k.png 放入左式后,得到g与h值。
http://img2.58codes.com/2024/20113622fZ3ZgVVfnO.png
http://img2.58codes.com/2024/20113622iFnsqGHkdd.png
如果http://img2.58codes.com/2024/201136225nhFwcQn4A.png 成立则http://img2.58codes.com/2024/20113622RORTGYKAnV.pnghttp://img2.58codes.com/2024/20113622Gq1jaNf81k.png 互相在L的另外一边。

虽然对立测试确定了http://img2.58codes.com/2024/20113622RORTGYKAnV.pnghttp://img2.58codes.com/2024/20113622Gq1jaNf81k.png 互相在L的另外一边,但是无法完全说明两线相交,如下图:
http://img2.58codes.com/2024/201136221ytrMY0Yvi.png
虽然L1与L2相交,却无法保证两线相交。

测试二:定界框测试

定界框是以线段两端为矩形斜对角所画出的矩形框(红框及蓝框)。
而定界框测试为确认两直线的定界框有重叠部分。
基本上,这个测试会出现三种不同情况。

情况一:定界框重叠且两线相交

http://img2.58codes.com/2024/20113622Sb1G8NELmn.png

情况二:定界框重叠但两线不相交

http://img2.58codes.com/2024/20113622snL1ox51tg.png
这种情况主要由其中一条直线的两端点不在另一条直线的两侧,即未通过对立测试。

情况三:定界框不重叠且两线不相交

http://img2.58codes.com/2024/201136228vZeRCQomS.png
这种情况即为未通过定界框测试,且很明显两线不可能相交。

缺点

若同时符合两个情况:

L1两点在L2的两边L2两点在L1的两边

这样已经可以判定大部分情况两线确实相交,但仍然有漏洞。
如果两条线平行,则有可能以上情况仍然成立,如图:
http://img2.58codes.com/2024/201136224fb2EiGF4c.png

因此,要确定两线段确实相交,需要以上两个情况及L1定界框与L2定界框有重叠的情况都成立。
http://img2.58codes.com/2024/201136223LtUIpEUJk.png


关于作者: 网站小编

码农网专注IT技术教程资源分享平台,学习资源下载网站,58码农网包含计算机技术、网站程序源码下载、编程技术论坛、互联网资源下载等产品服务,提供原创、优质、完整内容的专业码农交流分享平台。

热门文章