ตรวจสอบว่าส่วนเส้นสองเส้น تتัดกันหรือไม่

บทนำ

กำหนดส่วนเส้นสองเส้น จุด p1, p2 จากส่วนเส้นแรก และ q1, q2 จากส่วนเส้นที่สอง ต้องการตรวจสอบว่าส่วนเส้นทั้งสองตัดกันหรือไม่

เราสามารถบอกได้ว่าส่วนเส้นทั้งสองตัดกันเมื่อเงื่อนไขเหล่านี้เป็นจริง:

• เมื่อ (p1, p2, q1) และ (p1, p2, q2) มีทิศทางต่างกัน และ
• (q1, q2, p1) และ (q1, q2, p2) มีทิศทางต่างกัน

เงื่อนไขอีกอย่างคือเมื่อ (p1, p2, q1), (p1, p2, q2), (q1, q2, p1), (q1, q2, p2) อยู่บนเส้นตรงเดียวกัน (Collinear)

อินพุตและเอาต์พุต

Input: จุดของส่วนเส้นสองเส้น
ส่วนเส้น 1: (0, 0) ถึง (5, 5)
ส่วนเส้น 2: (2, -10) ถึง (3, 10)
Output: เส้นตัดกัน

อัลกอริทึม

direction(a, b, c)

Input: สามจุด

Output: ตรวจสอบว่าจุดอยู่บนเส้นตรงเดียวกัน (collinear) หรือทิศทางตรงข้ามเข็มนาฬิกา (anti-clockwise) หรือตามเข็มนาฬิกา (clockwise)

Begin
    val := (b.y-a.y)*(c.x-b.x) - (b.x-a.x)*(c.y-b.y)
    if val = 0, then
        return collinear
    else if val < 0, then
        return anti-clockwise
    return clockwise
End

isIntersect(l1, l2)

Input: สองส่วนเส้น แต่ละเส้นมีสองจุด p1 และ p2

Output: True เมื่อตัดกัน

Begin
    dir1 = direction(l1.p1, l1.p2, l2.p1);
    dir2 = direction(l1.p1, l1.p2, l2.p2);
    dir3 = direction(l2.p1, l2.p2, l1.p1);
    dir4 = direction(l2.p1, l2.p2, l1.p2);
    if dir1 ≠ dir2 and dir3 ≠ dir4, then
        return true
    if dir1 = 0 and l2.p1 on the line l1, then
        return true
    if dir2 = 0 and l2.p2 on the line l1, then
        return true
    if dir3 = 0 and l1.p1 on the line l2, then
        return true
    if dir4 = 0 and l1.p2 on the line l2, then
        return true
    return false
End

ตัวอย่างโค้ด (C++)

#include <iostream>
using namespace std;

struct Point {
    int x, y;
};

struct line {
    Point p1, p2;
};

bool onLine(line l1, Point p) {
    // ตรวจสอบว่า p อยู่บนเส้นหรือไม่
    if (p.x <= max(l1.p1.x, l1.p2.x) && p.x >= min(l1.p1.x, l1.p2.x) &&
        (p.y <= max(l1.p1.y, l1.p2.y) && p.y >= min(l1.p1.y, l1.p2.y)))
        return true;
    return false;
}

int direction(Point a, Point b, Point c) {
    int val = (b.y-a.y)*(c.x-b.x) - (b.x-a.x)*(c.y-b.y);
    if (val == 0)
        return 0;  // collinear
    else if (val < 0)
        return 2;  // anti-clockwise direction
    return 1;  // clockwise direction
}

bool isIntersect(line l1, line l2) {
    // ทิศทางสี่ทิศทางสำหรับสองเส้นและจุดของอีกเส้น
    int dir1 = direction(l1.p1, l1.p2, l2.p1);
    int dir2 = direction(l1.p1, l1.p2, l2.p2);
    int dir3 = direction(l2.p1, l2.p2, l1.p1);
    int dir4 = direction(l2.p1, l2.p2, l1.p2);
    
    if (dir1 != dir2 && dir3 != dir4)
        return true;  // พวกมันตัดกัน
    if (dir1==0 && onLine(l1, l2.p1))  // เมื่อ p2 ของ line2 อยู่บน line1
        return true;
    if (dir2==0 && onLine(l1, l2.p2))  // เมื่อ p1 ของ line2 อยู่บน line1
        return true;
    if (dir3==0 && onLine(l2, l1.p1))  // เมื่อ p2 ของ line1 อยู่บน line2
        return true;
    if (dir4==0 && onLine(l2, l1.p2))  // เมื่อ p1 ของ line1 อยู่บน line2
        return true;
    return false;
}

int main() {
    line l1 = {{0,0}, {5, 5}};
    line l2 = {{2,-10}, {3, 10}};
    if (isIntersect(l1, l2))
        cout << "Lines are intersecting";
    else
        cout << "Lines are not intersecting";
}

ผลลัพธ์

Lines are intersecting