这是个很实用的问题——尤其是处理曲线/路径数据的时候，自相交检测是很多几何应用（比如CAD、机器人路径规划）里的基础需求。下面我分情况给你拆解解法，从2D到多维，再讲优化思路：

首先明确：你的路径是由连续线段组成的（点p[i]到p[i+1]是一段线段），自相交的本质就是任意两条非相邻的线段发生了相交（相邻线段共享端点，不算自相交；如果是闭环路径，最后一段和第一段算相邻，除非端点重合）。

基础线段相交检测 #

要判断两条线段是否相交，常用的是跨立实验（结合端点检查），原理是看每条线段是否跨立另一条线段所在的直线，再加上端点落在对方线段上的情况。

我给你写个Python风格的实现（带浮点误差处理）：

def segments_intersect(a1, a2, b1, b2, eps=1e-9):
    # 计算向量
    v_a = (a2[0]-a1[0], a2[1]-a1[1])
    v_b = (b2[0]-b1[0], b2[1]-b1[1])
    v_a1_to_b1 = (b1[0]-a1[0], b1[1]-a1[1])
    v_a1_to_b2 = (b2[0]-a1[0], b2[1]-a1[1])
    v_b1_to_a1 = (a1[0]-b1[0], a1[1]-b1[1])
    v_b1_to_a2 = (a2[0]-b1[0], a2[1]-b1[1])

    # 计算叉积，判断跨立
    cross1 = v_a[0] * v_a1_to_b1[1] - v_a[1] * v_a1_to_b1[0]
    cross2 = v_a[0] * v_a1_to_b2[1] - v_a[1] * v_a1_to_b2[0]
    cross3 = v_b[0] * v_b1_to_a1[1] - v_b[1] * v_b1_to_a1[0]
    cross4 = v_b[0] * v_b1_to_a2[1] - v_b[1] * v_b1_to_a2[0]

    # 互相跨立，说明线段内部相交
    if (cross1 * cross2 < -eps) and (cross3 * cross4 < -eps):
        return True

    # 检查端点是否落在对方线段上的情况
    def point_on_segment(p, seg_start, seg_end):
        # 先判断共线
        cross = (seg_end[0]-seg_start[0])*(p[1]-seg_start[1]) - (seg_end[1]-seg_start[1])*(p[0]-seg_start[0])
        if abs(cross) > eps:
            return False
        # 再判断坐标在区间内
        return (min(seg_start[0], seg_end[0]) - eps <= p[0] <= max(seg_start[0], seg_end[0]) + eps and
                min(seg_start[1], seg_end[1]) - eps <= p[1] <= max(seg_start[1], seg_end[1]) + eps)

    return (point_on_segment(a1, b1, b2) or point_on_segment(a2, b1, b2) or
            point_on_segment(b1, a1, a2) or point_on_segment(b2, a1, a2))

路径自相交检测主逻辑 #

遍历所有非相邻线段对，只要有一对相交，就返回True：

def path_self_intersects_2d(points, eps=1e-9):
    n = len(points)
    if n < 4:
        return False  # 少于4个点，最多3条线段，不可能有非相邻线段相交
    # 遍历每一段线段
    for i in range(n-1):
        # 只和后面间隔至少一段的线段比较（避免相邻线段）
        for j in range(i+2, n-1):
            if segments_intersect(points[i], points[i+1], points[j], points[j+1], eps):
                return True
        # 如果是闭环路径，需要额外检查当前线段和最后一段（如果不相邻）
        # if i != n-2 and segments_intersect(points[i], points[i+1], points[-1], points[0], eps):
        #     return True
    return False

用你给的例子测试：points = [[0,0], [1,0], [1,1], [0.5,-0.5]]，调用这个函数会返回True，完全符合预期。

多维空间里，两条线段相交的条件更苛刻：它们必须共面（共超平面），且在该平面内相交。

3D场景的实现思路 #

1. 判断共面：计算三个向量的混合积（标量三重积）是否为0。向量分别是p1-p0、q1-q0、q0-p0，混合积为(p1-p0) · [(q1-q0) × (q0-p0)]，如果绝对值小于epsilon，说明共面。
2. 共面后转2D检测：把两条线段投影到一个合适的2D平面（比如去掉坐标中变化最小的那个轴），然后用2D的线段相交算法判断。
3. 或者直接解参数方程：设线段1的参数方程是P(t) = p0 + t*(p1-p0)，t∈[0,1]；线段2是Q(s) = q0 + s*(q1-q0)，s∈[0,1]。解线性方程组P(t) = Q(s)，看是否存在t和s都在[0,1]范围内的解。

更高维空间 #

思路类似：先判断四个点是否在同一超平面内（可以通过线性代数的秩来判断），如果是，就投影到该超平面的一个2D子空间，再用2D算法检测。

如果你的路径点非常多（比如n>1000），O(n²)的基础算法会很慢，这时候可以用这些优化手段：

• Bounding Box 预检查：先计算每条线段的包围盒，如果两个线段的包围盒不相交，直接跳过，不用做后续的相交检测。
• 空间划分：比如把空间分成网格，每个线段只和同一网格或相邻网格的线段比较，减少不必要的检查。
• 扫描线算法：适合2D场景，时间复杂度降到O(n log n)。原理是用一条扫描线从左到右移动，维护当前“活跃”的线段，每次加入新线段时，只和活跃线段中可能相交的部分比较。

• 浮点精度：一定要引入epsilon（比如1e-9）来处理浮点计算的误差，避免因为微小的数值偏差导致误判。
• 闭环路径：如果你的路径是闭环的（最后一个点和第一个点相连），记得额外检查最后一段和前面非相邻的线段是否相交。

内容的提问来源于stack exchange，提问作者Robbie Rosati