判斷兩線是否相交
假設現有兩條直線(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));