示意图能提示一个点位于边的哪一侧,但程序需要的是精确的判定。叉积提供了这种判定;把同一个行列式沿多边形求和,便得到它的有向面积。本章把三个问题分开处理:顶点顺序是否为顺时针、某点是否位于边界上,以及所用的算术能否表示答案。
1. 不用斜率判断方向
定义 8.1.1
(点相对于有向直线的叉积测试)
对于点 、 和 ,定义
当 位于有向直线 的左侧时它为正,位于右侧时为负,位于直线上时为零。
这对竖直边同样适用,而斜率公式在这种情况下会出现除以零。仅凭结果为零,只能说明 与该边共线,并不能说明它位于有限线段上。若要判断是否在线段上,还须检查两个坐标是否都落在端点所确定的区间之内。
例题 8.1.2
(共线但在线段之外的点)
取 和 ,则 。点 、 和 的叉积为
第一个点在左侧,第二个点在右侧。最后的叉积为零,所以 与该直线共线;但它的 坐标 在区间 之外,因此不在线段上。
快速检查
(对 、、,计算 。 是否在线段 上?)
代入 和 。
解答 · 答案
,所以 在直线 上。但 不在 之内,所以 不在线段上。
2. 有向面积的两倍
定义 8.1.3
(有向面积的两倍(鞋带和))
设 是按边界顺序排列的简单多边形顶点,令 ,,定义
面积为 。在通常的笛卡尔(Descartes)坐标定向下,逆时针边界给出 ,顺时针边界给出 。将顶点列表反转会使每条有向边反向,从而改变 的符号,但不改变其绝对值。该公式是相对于原点的有向三角形贡献之和:把区域分解为三角形时,内部的有向边会以相反方向各出现一次,因而相互抵消。当原点在多边形之外时,有向贡献是不可缺少的。输入必须是简单多边形;若对任意自相交的路径套用 ,得到的是代数意义上的有向面积,未必等于其填充区域的面积。
例题 8.1.4
(五边形的鞋带和)
取逆时针顶点 ,并以 封闭。正向乘积 为 ,和为 ;反向乘积 为 ,和为 。于是 ,面积为 。
将 保持为整数可以精确保留半整数面积:计算 |S| / 2,并且恰在 |S| % 2 == 1 时附加 .5。要确保所选类型既能表示 ,也能表示 ;对最小的有符号负值取绝对值可能会溢出。
例题 8.1.5
(半整数面积与顺时针列表)
对三角形 ,各求和项为 、 和 ,所以 。因为 为奇数,面积为 ,输出为 1.5。若把同一个三角形按顺时针列为 ,求和项为 ,故 :面积相同,符号相反。
快速检查
(计算顺时针正方形 的 及面积。)
用 封闭列表,计算四个求和项。
解答 · 答案
四个求和项为 、、 和 。所以 :因为列表是顺时针的,所以为负。面积为 ,与边长为 的正方形相符。
快速检查
(若把上面五边形的顶点列表反转, 与面积各是多少?)
反转列表会使每条有向边反向,每个求和项配对都变号。
解答 · 答案
,因为反转列表会使总和变号。面积 不变。
3. 凸性把每条边变成一个约束条件
假设已知输入是一个按逆时针排列的非退化、简单、凸多边形。它的闭区域(包括边界)是其各条有向边的闭左半平面的交集;它的内部则是相应开半平面的交集。因此,对每条边计算与 的叉积。
定理 8.1.6
(点的边测试分类)
设 是非退化的简单凸多边形,顶点 按逆时针排列,。对点 ,记 。则:
- 若有某个 ,则 在 的外部;
- 若没有 为负,且至少有一个为零,则 在 的边界上;
- 若所有 ,则 严格位于 的内部。
证明
(半平面给出三种情形)
令 为第 条边的闭左半平面。我们引用凸多边形的标准半平面描述:各边按逆时针排列时,。(其中一个方向是容易的:每条边都支撑 ,所以 的每个点都在每个 内;反方向的包含才需要凸性。)
因此 恰当所有 。取逆否命题即得第一种情形:只要有某个 为负, 就在 之外。
有限个集合的交集的内部等于各集合内部的交集,而 的内部是开半平面 。所以 在 的内部恰当所有 ,这就是第三种情形。
闭集 的边界是 去掉它的内部。所以 在边界上恰当所有 而并非所有 ,也就是没有负值且至少有一个零。这就是第二种情形。
证明透视
凸性与零叉积在哪里起作用
证明中只有一步用到凸性:等式 。对凸多边形,每条边都支撑 ,这给出包含关系 ;反向的包含则是半平面定理。对凹多边形,该等式不成立,下面的反例就给出一个属于 却不在某个 内的点。有了这个等式之后,论证只涉及半平面:有限交集的内部等于各内部之交(有限性是必要的),而闭集的边界是该集去掉其内部。因此,单独一个零叉积并不是边界的凭证;它之所以有效,是因为其余叉积全部非负,已先把 放进 之内。
凸性并不只是形式上的条件,一个具体的凹多边形就能说明。
反例模式
单侧测试需要凸性
人们很容易把同一个“所有叉积”测试用到任何按逆时针排列的简单多边形上。取凹多边形 。它的鞋带和为 ,所以是逆时针排列,面积为 (正方形 去掉面积为 的凹口三角形 )。点 在多边形内部:它在正方形内,而凹口只在 处与直线 相交。对边 ,,,叉积为 。这个测试会把内部的点判为外部。修正的办法是加上凸性的假设:对凹多边形,各左半平面的交集小于多边形本身。
例题 8.1.7
(用五边形分类三个点)
沿用五顶点的例子。对 ,五个叉积为 ,全部为正,所以 严格位于内部。对 ,前两个叉积为 和 ,第三个为 ,所以 在外部。对 ,叉积为 :没有负值,而第一个为零,所以 在边界上(它位于 到 的边上)。
例题 8.1.8
(顶点属于边界点)
取同一五边形的顶点 ,它位于在该处相交的两条边上。边 给出 ,边 给出 。其余三个叉积同样计算:边 ,,得 ;边 ,,得 ;边 ,,得 。两个零和三个正值:没有负叉积且有零,所以 在边界上,与预期相符。
常见错误
(把零叉积当作在边界上)
取 和五边形的第一条边 :叉积为 ,但 并不在多边形上。第二条边 给出 ,所以 在外部。只有在没有其他叉积为负时,零才是边界的凭证。
常见错误
(把顺时针列表交给逆时针规则)
把五边形反向列出:。每条反向的边会使叉积变号,所以 的五个叉积为 ,按原规则会把严格位于内部的点判为外部。应先计算 ,在 时反转列表。
输入的约定十分重要:对顺时针多边形,各符号会反转。使用此规则前,应先计算有向面积,并把顺时针的顶点列表反转。在非退化多边形的前提条件下,有向面积为零的输入应予拒绝;仅凭符号并不能证明任意输入是简单或凸的。
快速检查
(对上面的五边形,利用边叉积把 分类。)
对五条有向边逐一计算叉积;遇到第一个负值即可停止。
解答 · 答案
边 :。边 :,故 。边 :,故 。边 :,故 。边 :,故 。五个叉积全部为正,所以 严格位于内部。
4. 成本与精确算术
命题 8.1.9
(单次扫描的线性成本)
对有 个顶点的多边形,一次有向面积计算或一次点查询恰好计算 个求和项或叉积,因此需要 次算术运算及 个额外标量。
证明
(对各边的单一循环)
条边 ()各被访问一次,每次访问只做常数次减法、乘法,以及一次比较或把值加进累加值。除输入外,只需保存循环计数器、累加和及当前的叉积。
单次有向面积计算或单次点查询会访问 条边,需要 次算术运算。对 个点重复查询需要 ;此分析并不声称有更快的预处理方法。若要保留多边形以供多次查询,需要 的存储空间;一次扫描只需 个额外标量。
命题 8.1.10
(整数范围上界)
若每个整数坐标的绝对值至多为 ,则每个坐标差的绝对值至多为 ,每个叉积值 的绝对值至多为 ,鞋带公式中每个求和项的绝对值至多为 ,而任意 个求和项的累加和的绝对值至多为 。
证明
(逐项使用三角不等式)
两个属于 的数之差属于 。叉积中的两个乘积各自是两个这样的差相乘,绝对值至多为 ,二者之差的绝对值至多为 。在鞋带求和项 中,每个乘积的绝对值至多为 ,所以求和项至多为 ,而 个求和项之和至多为 。
这些是安全的上界,并不意味着每个输入都会同时达到它们。应选择一种能表示所需中间值的有符号类型,并在相减或相乘之前提升坐标的类型。在溢出发生之后再取余数或扩展类型,无法恢复已丢失的值。简单的累加和上界 可能超出足以完成单次方向测试的类型的范围。要么使用更宽的累加器,要么为每个部分和证明更紧的上界。虽然对于位于该方框内的简单多边形,最终的 至多为 ,但这一关于最终值的上界本身并不能约束部分和。
概念视角几何
同一个和,看成三角形扇
固定顶点 ,把多边形切成三角形 。则 ;五边形的各项为 ,同样得 。对逆时针的凸多边形,每一项都是正数,所以部分和递增至 ,累加器不会超出最终的界。
例题 8.1.11
(十亿量级的坐标下 64 位算术够用吗?)
设 。坐标差至多为 ,一个乘积至多为 ,一个叉积至多为 。由于 ,只要在相减之前先把坐标提升到 64 位,单个叉积就能放进有符号 64 位整数。对 的鞋带和,上界 超过 ,所以这个简单上界不能证明 64 位累加器够用;需要更宽的累加器或更紧的论证。
常见错误
(用最终值的上界代替部分和的上界)
对简单多边形,最终的 至多为 ,但 是逐个求和项累加而得,而部分和有凭证的上界只是 个求和项之后的 。声称只要某个类型能容纳 就足以作累加器,就忽略了这个差距。
快速检查
(当 ,且坐标先提升为有符号 64 位整数再运算时,单个叉积会溢出吗?)
比较上界 与 。
解答 · 答案
不会。叉积的绝对值至多为 ,小于 。若坐标在提升之前就以 32 位相乘,乘积可能已经溢出,所以必须先提升再运算。
检查清单。 在应用边测试之前,确认输入是简单、凸且非退化的。确定边界方向,在方向确定之前保留有向面积,区分直线与线段,并针对实际的输入范围推导溢出上界。