线段相交（跨立试验）
计算几何 · 叉积判定 · O(1) / 对
两条线段交不交？
判断两条线段是否相交，是几何里最基本的判定——扫描线求交、多边形裁剪、碰撞检测都由它一块块搭起来。直觉做法是解直线方程求交点再验范围，但除法带来精度陷阱。计算几何的答案还是那把刀：叉积——只用乘法和符号比较。
互相跨立
线段 AB 与 CD 相交，等价于互相跨立：A、B 分居直线 CD 两侧，同时 C、D 分居直线 AB 两侧。「在哪一侧」正是叉积的符号：算四个数 D1=cross(C,D,A)、D2=cross(C,D,B)、D3=cross(A,B,C)、D4=cross(A,B,D)。若 D1·D2<0 且 D3·D4<0（两两异号）→ 规范相交；若某个 D 为 0，说明有端点落在对方所在直线上——再查它是否落在对方线段的包围框内，是则端点相触（也算相交）。任何一组同号即可提前判否。
下面固定三对线段，正好覆盖三种结局。点「下一步」逐步看：当前对琥珀高亮并给出四个叉积；判定后绿色=相交、灰色虚线=不相交。第 1 对两两异号规范相交；第 2 对 D1、D2 同号一步判否；第 3 对 D3=0、端点 (7,1) 恰落在对方线段上——相触。右侧代码随每一步同步高亮。
三对线段，逐对判断是否相交。工具还是叉积：看两端点分别落在对方直线的哪一侧（跨立试验），全程只用乘法和比较
1function segIntersect(a: Pt, b: Pt, c: Pt, d: Pt): boolean {
2 const d1 = cross(c, d, a); // A 在直线 CD 的哪一侧
3 const d2 = cross(c, d, b); // B 在直线 CD 的哪一侧
4 const d3 = cross(a, b, c); // C 在直线 AB 的哪一侧
5 const d4 = cross(a, b, d); // D 在直线 AB 的哪一侧
6 if (d1 * d2 < 0 && d3 * d4 < 0) // 两两异号：互相跨立
7 return true; // 规范相交
8 if (d1 === 0 && onSeg(c, d, a)) return true; // 共线端点相触
9 if (d2 === 0 && onSeg(c, d, b)) return true;
10 if (d3 === 0 && onSeg(a, b, c)) return true;
11 if (d4 === 0 && onSeg(a, b, d)) return true;
12 return false; // 同侧/共线不搭 → 不相交
13}
线段对3
1 / 8
四个叉积，零除法
跨立：AB、CD 相交 ⟺ 两端点互相分居对方直线两侧。
判定：D1·D2 < 0 且 D3·D4 < 0 → 规范相交；同号 → 不相交。
边界：D = 0（共线）时补包围框检查 → 端点相触。
鲁棒：全程乘法 + 比较，整数坐标下零精度误差。
判定：D1·D2 < 0 且 D3·D4 < 0 → 规范相交；同号 → 不相交。
边界：D = 0（共线）时补包围框检查 → 端点相触。
鲁棒：全程乘法 + 比较，整数坐标下零精度误差。
有了 O(1) 的相交判定，把 n 条线段的端点按 x 排序、用一条竖直扫描线从左扫到右、动态维护「当前与扫描线相交的线段」的上下邻居关系，就得到求全部交点的 Bentley-Ottmann 扫描线算法（O((n+k) log n)）。至此，叉积在本大类里判过转向（凸包）、量过远近（卡壳）、断过相交——一把刀，整个计算几何。