知识卡片

普通读书笔记卡 · 8093.d · 生成模型:未记录

线段相交要双向跨越

理解等级:中级

先比较两段的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