1. 算法思路：

略
时间复杂度： $O(1)$

2. 实例代码：

2.1 import

1 2	import primitives.Point; import primitives.Segment;

2.2 SegmentsIntersect.class

2.2.1 方法

2.2.1.1 叉乘确定两线段的相对位置

private static double direction(Point p0, Point p1, Point p2) {
    return ((p2.getX() - p0.getX()) * (p1.getY() - p0.getY()) -
            (p2.getY() - p0.getY()) * (p1.getX() - p0.getX()));
}

定义：

\begin{cases} \vec{v_1} = (P_0,&P_1) \\ \vec{v_2} = (P_0,&P_2) \end{cases}

\vec{v_2} \times \vec{v_1} = \begin{vmatrix} \vec{v_{2x}} & \vec{v_{1x}} \\ \vec{v_{2y}} & \vec{v_{1y}} \end{vmatrix} = \begin{vmatrix} (p_{2x} - p_{0x}) & (p_{1x} - p_{0x}) \\ (p_{2y} - p_{0y}) & (p_{1y} - p_{0y}) \end{vmatrix}

2.2.1.2 确定三点的相对位置

private static boolean onSegment(Point pi, Point pj, Point pk) {
    return (Math.min(pi.getX(), pj.getX()) <= pk.getX() &&
            pk.getX() <= Math.max(pi.getX(), pj.getX()) &&
            Math.min(pi.getY(), pj.getY()) <= pk.getY() &&
            pk.getY() <= Math.max(pi.getY(), pj.getY()));
}

2.2.1.3 检测两线段是否相交

public static boolean two(Segment s1, Segment s2) {
    
    Point p1 = s1.getLeft();
    Point p2 = s1.getRight();
    Point p3 = s2.getLeft();
    Point p4 = s2.getRight();
    
    double d1 = direction(p3, p4, p1);
    double d2 = direction(p3, p4, p2);
    double d3 = direction(p1, p2, p3);
    double d4 = direction(p1, p2, p4);
    
    if (((d1 > 0 && d2 < 0) || (d1 < 0 && d2 > 0)) &&
        ((d3 > 0 && d4 < 0) || (d3 < 0 && d4 > 0))) {
        return true;
    } else if (d1 == 0 && onSegment(p3, p4, p1)) {
        return true;
    } else if (d2 == 0 && onSegment(p3, p4, p2)) {
        return true;
    } else if (d3 == 0 && onSegment(p1, p2, p3)) {
        return true;
    } else if (d4 == 0 && onSegment(p1, p2, p4)) {
        return true;
    } else {
        return false;
    }
}

(d1 > 0 && d2 < 0) || (d1 < 0 && d2 > 0) : $P_3P_4$ 在 $P_3P_1$ 和 $P_3P_2$ 之间
- (d1 > 0 && d2 < 0)：
$\begin{cases} P_3P_1 \times P_3P_4 > 0 \\ P_3P_2 \times P_3P_4 < 0 \end{cases}$
- (d1 < 0 && d2 > 0)：
$\begin{cases} P_3P_1 \times P_3P_4 < 0 \\ P_3P_2 \times P_3P_4 > 0 \end{cases}$
(d3 > 0 && d4 < 0) || (d3 < 0 && d4 > 0) : $P_1P_2$ 在 $P_1P_3$ 和 $P_1P_4$ 之间
- (d3 > 0 && d4 < 0)
$\begin{cases} P_1P_3 \times P_1P_2 > 0 \\ P_1P_4 \times P_1P_2 < 0 \end{cases}$
- (d3 < 0 && d4 > 0)
$\begin{cases} P_1P_3 \times P_1P_2 < 0 \\ P_1P_4 \times P_1P_2 > 0 \end{cases}$