几何向量 / 叉积与方向

几何、扫描线、模拟与解析 · HTML

数学 / 逻辑形态

cross(OA,OB)=ax*by-ay*bx；符号给左转/右转/共线，点积给夹角与投影方向。

识别信号

• 判断三点方向或共线
• 线段是否相交
• 多边形有向面积
• 凸包或边界顺序
• 斜率可能出现竖线与精度问题

容易误判的相似信号

核心不变量

叉积符号在同一坐标方向与点序约定下稳定表示有向转角；共线特例再用坐标范围判断在线段上。

状态、转移与处理顺序

Python 骨架

def cross(a, b, c):
    return (b[0]-a[0])*(c[1]-a[1]) - (b[1]-a[1])*(c[0]-a[0])

def on_segment(a, b, p):
    return (cross(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 segments_intersect(a, b, c, d):
    x1, x2, x3, x4 = cross(a,b,c), cross(a,b,d), cross(c,d,a), cross(c,d,b)
    if ((x1 > 0 > x2 or x2 > 0 > x1) and
        (x3 > 0 > x4 or x4 > 0 > x3)):
        return True
    return (x1 == 0 and on_segment(a,b,c) or
            x2 == 0 and on_segment(a,b,d) or
            x3 == 0 and on_segment(c,d,a) or
            x4 == 0 and on_segment(c,d,b))

正确性思路

1. 叉积是两个向量张成平行四边形的有向面积，符号对应转向。
2. 非共线相交时每条线段的端点位于另一支撑线两侧。
3. 该两侧条件对两条线段同时成立时交点落在二者内部。
4. 叉积为零时，on_segment 的包围范围恰处理端点与重叠特例。

复杂度

边界条件

• 零长度线段
• 端点接触是否算相交
• 共线重叠
• 大整数乘法溢出
• 浮点近共线需 epsilon

错误模式

选择与排除规则

• 方向、共线、相交：先写 cross。
• 输入整数且乘积安全：保持整数精确计算。
• 浮点数据：集中定义 epsilon。
• 凸性与有向面积先固定顺/逆时针约定。

相关模板

原创微型例子

Recall prompts

• 叉积符号如何对应左右转？
• 为何包围盒重叠不够？
• 共线线段相交需再检查什么？

我的补充