剪切系数的选择与证明

扫描线从左往右处理线段端点和交点。遇到竖直线段时，我们可以把图形稍微“推斜”：点的高度不变，越高的点向右移动得越多。

这个变换叫作剪切：

$$x'=x+sy,\qquad y'=y.$$

这里的 $s$ 是剪切系数。本文解释为什么可以选

$$\boxed{s=\frac{1}{256(M+1)^5}}.$$

我们要分清两件事：有理数精确运算和可逆变换保证交集不会算错；系数足够小则保证事件原有的横向顺序不会颠倒。 后一件事才需要下面的大小估计。

先把有理坐标变成整数

输入端点的坐标都是有理数，即可以写成整数之比。选一个正整数公共分母 $D$，让所有端点坐标乘上 $D$ 后都是整数。公共分母不必最小；把各个正分母相乘也是合法选择。

用大写字母表示放大后的坐标：

$$X=Dx,\qquad Y=Dy.$$

例如，坐标中只有分母 $2$ 和 $3$ 时，可以取 $D=6$。这是对两个坐标方向做同倍数缩放。

定义 $M$ 为 $1$ 与所有放大后端点坐标绝对值的最大值。因此 $M$ 是整数，且

$$M\ge1,\qquad |X|\le M,\quad |Y|\le M.$$

以下先在放大后的整数坐标中证明，最后再回到原坐标。若原输入已经是整数，可以取 $D=1$。

交点分母为什么不超过 8M²

取两条非零线段。端点都在 $[-M,M]\times[-M,M]$ 里，因此每条线段的水平、竖直方向分量的绝对值都不超过 $2M$：从 $-M$ 到 $M$，最多相差 $2M$。

把一条线段延长成直线。它的两个整数端点为 $(X_1,Y_1)$、$(X_2,Y_2)$，直线方程可以写成

$$aX+bY=c,\qquad a=Y_2-Y_1,\quad b=X_1-X_2,\quad c=aX_1+bY_1.$$

$a,b,c$ 都是整数，并且 $|a|,|b|\le2M$。对两条不平行的直线，联立方程消元，得到

$$\Delta=a_1b_2-a_2b_1\ne0,$$ $$X=\frac{c_1b_2-c_2b_1}{\Delta},\qquad Y=\frac{a_1c_2-a_2c_1}{\Delta}.$$

$\Delta$ 称为行列式，在这里就是“两次乘法再相减”。每次乘法的绝对值最多为 $(2M)(2M)=4M^2$；两个数相减时，绝对值最多是它们绝对值的和。所以

$$1\le|\Delta| \le |a_1b_2|+|a_2b_1| \le4M^2+4M^2=8M^2.$$

交点坐标的分子也是整数。把分母改成正数并约分，只会让分母变小，不会变大。于是每个坐标约分后的正分母都不超过 $8M^2$。端点本来是整数，分母为 $1$，也满足这个界。

不同横坐标至少相差多少

这里考虑的事件位置包括所有输入端点，以及非平行线段之间落在两条线段上的实际交点。同一点可能对应多个输入对，也可能对应多个教学停步；本证明只讨论几何位置的先后，不把它们的身份合并。

两个事件的不同横坐标，约分后记为 $p/q$ 和 $r/t$，其中 $q,t$ 是正整数且不超过 $8M^2$。相减并通分：

$$\left|\frac pq-\frac rt\right|=\frac{|pt-rq|}{qt}.$$

因为横坐标不同，整数 $pt-rq$ 不为零，其绝对值至少为 $1$。因此

$$|X_P-X_Q|\ge\frac1{qt}\ge\frac1{(8M^2)^2} =\frac1{64M^4}.$$

这就像分数之间的“最小安全间隔”：只要分母有上界，不同分数就不能无限靠近。

另一方面，端点和实际线段交点都在线段包围盒内，故两个事件的高度差满足

$$|Y_P-Y_Q|\le2M.$$

注意：支撑直线的交点可能落在线段外很远的位置。上面的分母界对它仍成立，但这个高度差界只用于端点和实际线段交点，不能用于任意延长线交点。

五次方和系数 256 从哪里来

剪切会给两个事件的横坐标差增加 $s(Y_Q-Y_P)$。为了不颠倒原来的左右顺序，只要这一扰动的绝对值小于最小安全间隔即可：

$$2Ms<\frac1{64M^4}.$$

也就是说，$s<1/(128M^5)$ 就足够。五次方来自横向间距中的四次方，再乘上高度差中的一次方。

我们不追求最大的可用系数，而取更保守、统一的

$$s=\frac1{256(M+1)^5}.$$

因为 $M\ge1$，有 $M^5<2(M+1)^5$，从而

$$|s(Y_Q-Y_P)|\le\frac{2M}{256(M+1)^5} <\frac1{64M^4}.$$

$256=2\times128$，再把 $M$ 换成 $M+1$，留下了额外余量。这个数是一个充分的保守选择，并不是唯一正确或最优的常数。

若原先 $X_P<X_Q$，那么

$$X'_Q-X'_P =(X_Q-X_P)+s(Y_Q-Y_P) \ge(X_Q-X_P)-s|Y_Q-Y_P|>0.$$

所以原先靠左的事件仍然靠左。

同横坐标、竖直线段和退化输入

若两个事件原先 $X_P=X_Q$，剪切后

$$X'_Q-X'_P=s(Y_Q-Y_P).$$

因为 $s>0$，较低的事件在左、较高的事件在右。这保持了“先比较横坐标，再比较纵坐标”的事件顺序。完全重合的位置仍然重合，不能把同一点上参与的线段拆成不同事件位置。

非零线段的两个端点不同：若横坐标不同，上面的保序证明保证剪切后仍不同；若横坐标相同，纵坐标必不同，正系数剪切也会使横坐标不同。因此非零竖直线段被消除，其他非零线段不会变成竖直线段。

上述唯一交点公式不能直接套用到所有输入：

• 平行但不共线：没有交点，不使用除以非零行列式的公式。
• 共线：可能相离、仅接触一点，或重叠成完整区间。重叠区间的两个边界来自输入端点，已经包含在事件位置中；不必把区间内无限多个点都当成事件。第三条非平行线段穿过重叠区间时，穿越位置仍由实际交点的估计覆盖。
• 零长度的点输入：没有唯一支撑直线，其位置作为端点被包含。剪切后它仍是点，不能把它当作具有斜率的非零线段。

当前计算实现只有在存在非零竖直线段时才选择这里证明的正系数；否则使用 $s=0$，不做剪切。因此“同横坐标的不同位置被分开”描述的是正系数分支，并不是每次计算都会发生的变化。

回到原坐标，为什么不用再调整系数

缩放和剪切可以交换顺序：

$$D(x+sy)=Dx+sDy=X+sY.$$

因此原坐标与放大坐标使用同一个 $s$，不用再乘或除一次 $D$。等价地，在原坐标中横向间距下界变成 $1/(64DM^4)$，高度差上界变成 $2M/D$；两边共有的 $1/D$ 正好抵消。

剪切也能精确撤销：

$$x=x'-sy',\qquad y=y'.$$

它是可逆线性变换，保持相交、平行、共线以及完整的重叠区间。使用精确有理数运算时，这些加法和乘法没有浮点舍入误差；结果经过逆剪切可恢复到原坐标。几何上重合的输入仍然保留各自的原始输入身份。

可逆性对任意有理系数都成立；本文的小系数额外保证了事件顺序。不能把“足够小”误当成精确性的来源。

示例：最大绝对坐标为 3

假设输入端点坐标都是整数，最大绝对值为 $3$。取 $D=1$，于是 $M=3$：

$$s=\frac1{256(3+1)^5} =\frac1{256\cdot4^5} =\frac1{256\cdot1024} =\boxed{\frac1{262144}}.$$

例如，竖直线段的端点 $(0,-3)$ 和 $(0,3)$ 变为

$$\left(-\frac3{262144},-3\right),\qquad \left(\frac3{262144},3\right).$$

横坐标不同了，线段不再竖直，但变换没有丢失信息。对这个例子，最大横向差扰动为 $6/262144$，小于安全间距下界 $1/(64\cdot3^4)=1/5184$；可以用整数比较 $6\cdot5184=31104<262144$ 核实，而无需依赖小数近似。