判斷兩線是否相交

假設現有兩條直線（L1, L2）

L1由A,B兩點所構成

L2由C,D兩點所構成

判斷L1,L2是否相交

步驟一：過濾絕無相交可能

若A,B的最大值小於C,D的最小值

表示兩線必無相交

反之亦然

所以可以得到

// 絕無相交情況
// 彼此的最大小於對方的最小
if (
    max($A->x, $B->x) < min($C->x, $D->x) ||
    max($A->y, $B->y) < min($C->y, $D->y) ||
    max($C->x, $D->x) < min($A->x, $B->x) ||
    max($C->y, $D->y) < min($A->y, $B->y)
) {
	return false;
}

步驟二：利用向量積計算C,D兩點是否在L1兩側

計算L2兩端點C,D是否在L1的兩側

利用向量積取得

A-B向量與A-C向量的角度

A-B向量與A-D向量的角度

角度相乘後若為負數，代表C,D在A,B直線的兩側（一個順時針一個逆時針角度）

則絕對相交

向量積的公式為

X1 * Y2 - X2 * Y1

A-B向量則為(B.X - A.X, B.Y-A.Y)

A-C向量則為(C.X-A.X, C.Y-A.Y)

A-B直線與另一點的向量積函數則是

function crossProduct(Point $a, Point $b, Point $other) {
    return ($b->x - $a->x) * ($other->y - $a->y) - ($other->x - $a->x) * ($b->y - $a->y);
}

$c1 = crossProduct($A, $B, $C);
$c2 = crossProduct($A, $B, $D);

再計算A,B是否在L2兩側

$c3 = crossProduct($C, $D, $A);
$c4 = crossProduct($C, $D, $B);

// 向量積相乘 < 0
// 代表線的端點在另一條線的兩端
if ($c1 * $c2 < 0 || $c3 * $c4 < 0) {
    return true;
}

步驟三：若在同一條線，則判斷點是否在線上

若向量積為0

代表點與線在同一條直線上

則判斷點是否在線上

// 點與線段已確定共線，判斷相交。
function pointIntersect(Point $p, Point $p1, Point $p2)
{
    return $p->x >= min($p1->x, $p2->x)
        && $p->x <= max($p1->x, $p2->x)
        && $p->y >= min($p1->y, $p2->y)
        && $p->y <= max($p1->y, $p2->y);
}

// 點 共線
// 判斷 點 是否在線上
if ($c1 === 0) {
	return pointIntersect($C, $A, $B);
}

if ($c2 === 0) {
	return pointIntersect($D, $A, $B);
}

if ($c3 === 0) {
	return pointIntersect($A, $C, $D);
}

if ($c4 === 0) {
	return pointIntersect($B, $C, $D);
}

步驟四：其餘狀況皆為不相交

其餘情況皆為不相交

return false;

完整程式碼

class Point
{
    public $x;
    public $y;

    public function __construct($x, $y)
    {
        $this->x = $x;
        $this->y = $y;
    }
}

function crossProduct(Point $a, Point $b, Point $other) {
    return ($b->x - $a->x) * ($other->y - $a->y) - ($other->x - $a->x) * ($b->y - $a->y);
}

// 點與線段已確定共線，判斷相交。
function pointIntersect(Point $p, Point $p1, Point $p2)
{
    return $p->x >= min($p1->x, $p2->x)
        && $p->x <= max($p1->x, $p2->x)
        && $p->y >= min($p1->y, $p2->y)
        && $p->y <= max($p1->y, $p2->y);
}

function intersect(Point $A, Point $B, Point $C, Point $D) {
    // 絕無相交情況
    // 彼此的最大小於對方的最小
    if (
        max($A->x, $B->x) < min($C->x, $D->x) ||
        max($A->y, $B->y) < min($C->y, $D->y) ||
        max($C->x, $D->x) < min($A->x, $B->x) ||
        max($C->y, $D->y) < min($A->y, $B->y)
    ) {
        return false;
    }

    $c1 = crossProduct($A, $B, $C);
    $c2 = crossProduct($A, $B, $D);

    $c3 = crossProduct($C, $D, $A);
    $c4 = crossProduct($C, $D, $B);

    // 向量積相乘 < 0
    // 代表線的端點在另一條線的兩端
    if ($c1 * $c2 < 0 || $c3 * $c4 < 0) {
        return true;
    }

    // 點 共線
    // 判斷 點 是否在線上
    if ($c1 === 0) {
        return pointIntersect($C, $A, $B);
    }

    if ($c2 === 0) {
        return pointIntersect($D, $A, $B);
    }

    if ($c3 === 0) {
        return pointIntersect($A, $C, $D);
    }

    if ($c4 === 0) {
        return pointIntersect($B, $C, $D);
    }

    // 其餘不相交
    return false;
}

測試

$a1 = new Point(0, 0);
$a2 = new Point(3, 3);
$b1 = new Point(2, 3);
$b2 = new Point(5, 3);

var_dump(intersect($a1, $a2, $b1, $b2));

窮得只剩技術