Kiểm tra hai đoạn thẳng có cắt nhau không

Giới thiệu

Cho hai đoạn thẳng. Các điểm p1, p2 từ đoạn thẳng thứ nhất và q1, q2 từ đoạn thẳng thứ hai. Ta phải kiểm tra xem cả hai đoạn thẳng có cắt nhau hay không.

Ta có thể nói rằng cả hai đoạn thẳng cắt nhau khi các trường hợp sau được thỏa mãn:

• Khi (p1, p2, q1) và (p1, p2, q2) có hướng khác nhau và
• (q1, q2, p1) và (q1, q2, p2) có hướng khác nhau.

Có một điều kiện khác là khi (p1, p2, q1), (p1, p2, q2), (q1, q2, p1), (q1, q2, p2) thẳng hàng (collinear).

Đầu vào và Đầu ra

Đầu vào: Các điểm của hai đoạn thẳng
Đoạn 1: (0, 0) đến (5, 5)
Đoạn 2: (2, -10) đến (3, 10)
Đầu ra: Hai đoạn thẳng cắt nhau

Thuật toán

direction(a, b, c)

Đầu vào: Ba điểm.

Đầu ra: Kiểm tra chúng có thẳng hàng hay ngược chiều kim đồng hồ hay cùng chiều kim đồng hồ.

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)

Đầu vào: Hai đoạn thẳng, mỗi đoạn có hai điểm p1 và p2.

Đầu ra: True, khi chúng cắt nhau.

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

Ví dụ (C++)

#include <iostream>
using namespace std;

struct Point {
    int x, y;
};

struct line {
    Point p1, p2;
};

bool onLine(line l1, Point p) {
    // kiểm tra p có trên đoạn thẳng hay không
    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;  // thẳng hàng
    else if(val < 0)
        return 2;  // ngược chiều kim đồng hồ
    return 1;  // cùng chiều kim đồng hồ
}

bool isIntersect(line l1, line l2) {
    // bốn hướng cho hai đường và điểm của đường kia
    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; // chúng cắt nhau
    if(dir1==0 && onLine(l1, l2.p1)) // khi p2 của line2 nằm trên line1
        return true;
    if(dir2==0 && onLine(l1, l2.p2)) // khi p1 của line2 nằm trên line1
        return true;
    if(dir3==0 && onLine(l2, l1.p1)) // khi p2 của line1 nằm trên line2
        return true;
    if(dir4==0 && onLine(l2, l1.p2)) // khi p1 của line1 nằm trên 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";
}

Kết quả

Lines are intersecting