线段交叉判断方法
线性函数
初等数学方法以多项式函数的方式找出交叉点,换句话说,如果找得出交叉点即两线段交叉。
算法
当p、q皆存在时应符合 与
如果p存在但q不存在,有可能会发生以下情形
结论
虽然线性函数的方法可以非常容易的以程式码呈现,但是线性函数使用除法,在程式运行时,可能需要消耗较多时间且浮点数可能使结果不準确。因此,判断两线段是否相交,需要进一步分析。
对立与定界框测试 On Opposite Side and Bounding Box Test
导入 与
的概念,将其细分为两个测试,对立测试与定界框匡测试。
满足这两个测试的两直线则可能相交。
对立测试
在对立测试中,检查 与
互相在L1的另外一边。
利用线性函数所推导出的直线方程式
L1 =
将 与
放入左式后,得到g与h值。
如果 成立则
与
互相在L的另外一边。
虽然对立测试确定了 与
互相在L的另外一边,但是无法完全说明两线相交,如下图:
虽然L1与L2相交,却无法保证两线相交。
测试二:定界框测试
定界框是以线段两端为矩形斜对角所画出的矩形框(红框及蓝框)。
而定界框测试为确认两直线的定界框有重叠部分。
基本上,这个测试会出现三种不同情况。
情况一:定界框重叠且两线相交
情况二:定界框重叠但两线不相交
这种情况主要由其中一条直线的两端点不在另一条直线的两侧,即未通过对立测试。
情况三:定界框不重叠且两线不相交
这种情况即为未通过定界框测试,且很明显两线不可能相交。
缺点
若同时符合两个情况:
L1两点在L2的两边L2两点在L1的两边这样已经可以判定大部分情况两线确实相交,但仍然有漏洞。
如果两条线平行,则有可能以上情况仍然成立,如图:
因此,要确定两线段确实相交,需要以上两个情况及L1定界框与L2定界框有重叠的情况都成立。