知识卡片
线段相交要双向跨越
先比较两段的x区间和y区间是否相交;任一区间分离则线段不相交。包围盒重叠只是必要条件。之后分别计算P3、P4相对P1→P2所在直线的方向,以及P1、P2相对P3→P4所在直线的方向,两组符号都须相反或含零,才能结合包围盒判相交。
书正文只列第一组z1、z2就称相交,少了另一方向的跨越条件;03105–03106源码实际计算四个符号并同时要求两组乘积≤0。共线、端点相触在闭线段定义下通过含零符号与包围盒处理。
方向表达式的正负含义依向量顺序决定;本书z=(P−P1)×(P2−P1),与常见(P2−P1)×(P−P1)符号相反,不能脱离约定直接套左右标签。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- · 查看原书依据
跨越检测(straddle test)。只有当快速剔除检测和跨越检测都成功时,这两条线段才会相交。 首先,针对每条线段建立一个边框(bounding box),以此来执行快速剔除检测。线段的边界框是一个包围该线段的最小矩形,其边分别平行于x轴和y轴。对于由端点P1=(x1,y1)和P2=(x2,y2
参考来源
- 位置:《算法精解:C语言描述》第17章《用计算机来检测线段是否相交》(spine1422;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1388.html;u310-ch17-005)。
- 结论依据:310全文、03103四种图和03105–03106双向测试实际源码已实读。
- 原始内容:跨越检测(straddle test)。只有当快速剔除检测和跨越检测都成功时,这两条线段才会相交。 首先,针对每条线段建立一个边框(bounding box),以此来执行快速剔除检测。线段的边界框是一个包围该线段的最小矩形,其边分别平行于x轴和y轴。对于由端点P1=(x1,y1)和P2=(x2,y2