画在纸上的两条线段可能交叉、共用端点、沿一条直线重叠,也可能互不相交。程序必须根据坐标区分这些情况,包括竖直线段和两端点重合的线段。先计算斜率会引入本可避免的除法,还要特别处理竖直直线。方向行列式则能直接给出所需的侧向信息。
我们使用整数坐标和精确运算。主要任务是一个判定问题:对交集分类,而不一定要构造交点坐标。把这两件事分开,即使实际交点的坐标不是整数,也能保持分类精确。
从两个位移向量推导方向测试
定义 8.2.1
(普通笛卡尔(Descartes)坐标系中的方向)
对点 、 和 ,定义
当 时,结果为正表示 在有向直线 的左侧,为负表示在右侧,为零表示在直线上。这个约定使用通常的坐标轴方向:x 向右增大,y 向上增大。
若 ,则对每个 ,表达式都为零,但此时并不存在唯一的有向支撑直线。因此,对零长度线段应使用下文的归属条件,而不能把这个退化表达式解释为侧向测试。
这个公式是向量 和 构成的行列式。它的绝对值等于两向量张成的平行四边形面积,也等于相应三角形面积的两倍。反转第一个方向会使它变号。将所有点平移同一向量不会改变任何位移,因此结果也不变。
方向值本身不是有符号距离。当 时,将它除以 ,才得到点到有向直线的有符号垂直距离。例如,、、 的方向值是 10,有符号距离却是 。判断点位于哪一侧只需要行列式;线段相交分类无需计算这个距离。
共线只是点在线段上的条件之一
定义 8.2.2
(闭线段)
闭线段 包含两个端点,由形如 、满足 的点组成。特别地,若 ,它只包含这一个点。
命题 8.2.3
(闭线段的归属判定)
点 属于闭线段 ,当且仅当其方向值为零,且两个坐标都满足边界条件:
证明
(方向值为零确定直线,边界确定参数)
若点属于线段,显然满足这些条件。反过来,若 ,方向值为零说明 在支撑直线上,因此对某个实数 有 。至少一个位移坐标非零;相应的坐标边界迫使 。若 ,两个边界条件则迫使 。因此,同一判断也能正确处理点线段。
证明透视
为什么一个非零坐标已经足够
每项假设各只用一次。方向值为零表示 与 平行;因为 ,这就给出实数 使 。然后只对 非零的某个坐标 使用坐标边界:,所以 ,而“ 在 与 之间”恰好就是 。另一个坐标的边界随之自动成立,并非独立的检查。非常规的一步,是选一个线段并非常数的坐标,这样就避开斜率与竖直线的特例。论证在 处分开:那时不存在参数,边界直接把 钉在 。没有这些边界,论证就只停在“ 在直线上”。
所以只看方向值,永远不足以判断归属;下一个具体例子说明这一点。
反例模式
方向值为零不代表点在线段端点之间
点 、 和 共线,故第三个点相对于前两个点的方向值为零。然而它的 x 坐标大于 2,所以在前两点确定的闭线段之外。只检查方向值为零,会把无限延伸的支撑直线误认为有限线段。
用两组侧向测试判断严格交叉
对于线段 和 ,定义
严格交叉指两条不共线线段只有一个交点,且该点严格位于两条线段的内部。当且仅当 严格异号,并且 也严格异号时,发生严格交叉。这里零不与任何数构成严格异号;含零的情况属于边界情况。
定理 8.2.4
(严格交叉的判定准则)
设 与 是长度为正、且不在同一直线上的线段。它们有一个对双方都是内部点的公共点,当且仅当 严格异号,并且 严格异号。
证明
(方向值沿线段是仿射函数)
沿着 ,相对于 的方向值等于 。
设 严格异号。这个式子便有唯一零点,出现在 。两条直线不平行,因为若方向平行,两个方向值就会相等。所以两条支撑直线的唯一交点严格位于线段 内部。 异号对同一个唯一直线交点给出同样结论,即它在 内部,所以该点是两条线段的内部点。
反过来,设 ()是公共点,同时是 的内部点。这时 在直线 上,所以 。因此 要么全为零,要么严格异号。若全为零,、 都在直线 上,与两条线段不在同一直线矛盾。所以 严格异号;把两条线段的角色对调,同一论证给出 严格异号。
证明透视
每组符号只证明一条线段
证明的引擎是:方向值沿线段是仿射函数,所以两个端点的值决定它在哪里为零。严格性使零点落在开区间内:若有端点的值为零,交点就在端点,属于边界情况。两个同号的严格值,则使零点落在线段之外,或使两条直线平行。不共线只用于必要性,用来排除 。第一组符号说明直线 穿过线段 ;第二组说明直线 穿过线段 。证明能够收尾,是因为两个陈述指向同一个点,即两条直线的唯一交点。只留一组符号,就只得到一半结论。
每组符号只证明其中一条线段,下面的例子把这个缺口具体化。
反例模式
只分居其中一条支撑直线的两侧并不充分
设 、、、。、 表明 穿过经过 的直线。
但 和 同号。直线交点是 ,它越过了端点 ,因此两条线段不相交。第二组符号正是用来排除这种情况的。
例题 8.2.5
(无需计算斜率的精确交叉判断)
取 、、、。四个方向值为
两组符号都严格相反。两条线段的参数方程分别在参数为 时相遇,交点为 。判定函数本身只需要符号,不需要构造该点时所用的除法。
整数输入并不意味着交点也是整数:从 到 的线段与从 到 的线段严格交叉于 。把这个点四舍五入到整数坐标不属于精确判定的步骤。
有意识地处理共线和退化情况
若四个方向值均为零,且至少一条线段长度非零,则所有端点都在该线段的支撑直线上。按字典序排列点:先比较 x 坐标,再比较 y 坐标。在非竖直直线上,此顺序沿着 x 坐标变化;在竖直直线上,它沿着 y 坐标变化。因此可以用这个顺序中的区间来判断重叠。
设候选重叠部分的端点为
其中最小值和最大值均按字典序取。若 ,两线段不相交;若 ,它们只有一个公共点;若 ,它们重叠成一条长度为正的线段。
两条点线段的四个方向值也全为零,即使它们所代表的点不同、因而没有指定唯一的共同支撑直线,也依然如此。它们的字典序区间各只含一个点,因此同一重叠规则仍能正确判断两点是否重合。
如果四个方向值不全为零,某个零值仍可能表示共用端点,或表示一条点线段位于另一条线段上。对相应端点应用完整的 on_segment 判断。方向值为零而不检查坐标边界是不够的。
例题 8.2.6
(边界情况属于闭线段的定义范围)
除特别说明外,下列例子都在 x 轴上。
| 第一条线段 | 第二条线段 | 分类 |
|---|---|---|
| 到 | 到 | 单点接触 |
| 到 | 到 | 正长度重叠 |
| 到 | 到 | 不相交 |
| 点 | 到 | 单点接触 |
| 点 | 到 | 不相交 |
| 点 | 点 | 单点接触 |
| 点 | 点 | 不相交 |
这里的“点”指两个端点重合的线段。单点接触可以发生在另一条线段的内部;该点不一定是两条线段共同的端点。
例题 8.2.7
(T 形接触需要零方向值加归属判断)
取 、、、。则 ,,第一组不是严格异号,所以不是严格交叉。又 ,,严格异号。由于 ,把 对 做归属判断:方向值为零,且 、,所以 在线段 上。分类为 touch:竖直线段终止于水平线段的内部。单靠零方向值不能下此结论;若 改为 ,方向值仍是零,边界条件却不成立。
命题 8.2.8
(两条闭线段的精确分类)
设 与 是闭线段,长度可以为零,方向值 如上。
- 若 ,交集是字典序中由 到 的区间: 时为空, 时为一点, 时为正长度线段。
- 否则交集至多一个点。它非空,当且仅当两条线段严格交叉,或某个方向值为零的端点对另一条线段通过闭线段归属判断。
证明
(按支撑直线的配置分情况)
设四个方向值全为零。若 长度为正,则 把 、 放在直线 上;若 长度为正,则 把 、 放在直线 上;若两者都是点,就只有两个点。每种情况下,所有端点都在同一直线上,字典序与沿直线的位置一致,所以每条线段就是其端点在此顺序下之间的区间;两个这样区间的交集是 , 时为空。
现设四个方向值并非全为零, 是公共点。若其中一条线段是点,例如 ,则 在 上,由归属命题,即 且 通过边界测试; 的情况对称。若两者长度都为正而两条直线平行,则两直线不同时没有公共点,重合时四个方向值全为零。否则两条直线恰交于一点, 就是该点,交集至多一点。若 在两条线段内部,由上面的准则,两条线段严格交叉;否则 是某条线段的端点,并在另一条线段上,所以该端点方向值为零,并通过归属判断。反过来,每个所列条件都由交叉准则或归属判定给出一个公共点。
常见错误
(用非严格不等式测试乘积)
一个诱人的捷径,在 且 时报告相交。对 、、、,四个方向值全为零,两个乘积都是零,捷径便报告接触。但这两条闭线段不相交:,,所以 。必须先把共线情况分出,再用区间测试决定。
常见错误
(在竖直线上只比较 x 坐标)
从 到 与从 到 的线段, 值都只有 ,所以只比较 的重叠测试看到相同的区间,报告接触。这两条线段其实不相交。字典序在 相同时比较 ,得 、,所以 。
精确整数分类函数
函数以前提条件规定输入点是含两个整数的元组,不检查坐标类型或元组形状。它用 cross 表示严格交叉,用 touch 表示边界或退化情况中的单点接触,用 overlap 表示共线且交集长度为正,其余情况返回 disjoint。这些字符串只分类交集,不返回交点坐标。
def orient(a, b, p):
return ((b[0] - a[0]) * (p[1] - a[1])
- (b[1] - a[1]) * (p[0] - a[0]))
def on_segment(a, b, p):
return (orient(a, b, p) == 0
and min(a[0], b[0]) <= p[0] <= max(a[0], b[0])
and min(a[1], b[1]) <= p[1] <= max(a[1], b[1]))
def opposite(x, y):
return (x < 0 < y) or (y < 0 < x)
def segment_relation(a, b, c, d):
o1, o2 = orient(a, b, c), orient(a, b, d)
o3, o4 = orient(c, d, a), orient(c, d, b)
if o1 == o2 == o3 == o4 == 0:
lower = max(min(a, b), min(c, d))
upper = min(max(a, b), max(c, d))
if lower > upper:
return "disjoint"
return "touch" if lower == upper else "overlap"
if opposite(o1, o2) and opposite(o3, o4):
return "cross"
if ((o1 == 0 and on_segment(a, b, c))
or (o2 == 0 and on_segment(a, b, d))
or (o3 == 0 and on_segment(c, d, a))
or (o4 == 0 and on_segment(c, d, b))):
return "touch"
return "disjoint"
例如,segment_relation((0,0),(4,2),(1,3),(3,-1)) 返回 cross;只有一组端点分居直线两侧的反例则返回 disjoint。反转任一线段的端点,或交换两条线段,都会保持分类不变,虽然某些方向值的符号会改变。
这个函数也直接处理竖直线段、重复端点和相同的点线段。它不使用除法、斜率比较或人为选定的容差。这个精确整数约定并不能作为把所有零值判断替换为任意浮点 的理由:近似坐标需要单独建立数值模型并进行分析。
选择定宽整数类型前先估算运算范围
代码使用常数次算术运算和比较。对于无界整数坐标,这只是运算次数,并不意味着按位计算的运行时间为常数。若坐标的绝对值至多为 ,则每个差的绝对值至多为 ,每个乘积的绝对值至多为 ,而方向行列式满足保守估计
这个界足以帮助推算所需数值范围;我们并不声称它是最紧的界。若坐标有 位,则差和行列式有 位,必须将乘法开销计入。Python 整数保持运算精确。移植到定宽整数类型时,必须保证差和乘积本身都使用足够宽的表示,而不能等溢出后才扩大结果类型。
如上所示,通过比较来判断异号,可以避免仅为了检查乘积是否为负而计算 。两个行列式相乘需要的中间结果范围可能大于任一行列式本身,而几何判断只需要它们的符号。
练习与解答
快速检查
(对 、、,计算方向值以及点到有向直线的有符号距离。为什么判断 位于哪一侧时无需归一化?)
只有需要距离时,才除以 的长度。
解答 · 答案
方向值为 。由于 ,除以 得到有符号距离 。正的归一化因子不会改变符号,所以只用方向值就能正确判断点在左侧。
快速检查
(对 、、、,写出四个方向值。为什么第一组异号不足以证明线段相交?)
除了 、,也要算 、。
解答 · 答案
四个值为 。线段 穿过经过 的无限直线,但交点 在线段 之外。另一组符号同号,因此完整的严格交叉测试排除了这一情况。
快速检查
(在 轴上,先比较从 到 与从 到 的线段,再比较从 到 与从 到 的线段。两次的 和 各是多少?分类有何不同?)
把 、 当作字典序的最大与最小来计算。
解答 · 答案
第一组的候选重叠部分从 到 ,长度为正,返回 overlap。第二组有 ,因而是单点接触 touch。区间端点是严格有序还是相等,决定了两者的区别。
快速检查
(当 ,另一条线段从 到 时,为什么仅有方向值为零还不够?如果该点换成 ,或者两条线段都是这个点,结果又如何?)
比较两个单点区间。
解答 · 答案
所有方向值均为零,但只含 的区间与另一条线段的端点区间不重叠,因此答案是 disjoint。换成点 则得到 touch。两条线段都由同一个点组成时也得到 touch;边界条件或有序区间条件处理了这些情况,无须为一个点人为构造有向直线。
快速检查
(如果将所有点平移同一个固定向量,四个方向值会如何变化?如果交换 与 ,第一组符号及最终相交分类又会如何变化?)
方向值是两个位移向量的行列式。
解答 · 答案
平移不改变任何位移向量,因此每个方向值都不变。交换 会使 变号,并交换 。异号、零值和线段归属条件仍描述相同的几何线段,所以分类不变。
快速检查
(如果每个坐标的绝对值至多为 ,推导上面的保守行列式界。定宽整数实现中,为什么直接判断异号可能优于计算两个方向值的乘积?)
先界定每个差,再界定每个乘积。
解答 · 答案
每个坐标差的绝对值至多为 ,两个乘积各自的绝对值至多为 ,所以它们的差的绝对值至多为 。两个这样的行列式相乘可能需要大得多的数值范围;直接比较正负可以避免额外乘积,同时恰好完成判定所需的符号判断。