ตรวจสอบว่าจุดอยู่ภายในรูปหลายเหลี่ยม (Polygon) หรือไม่

บทนำ

ในปัญหานี้ กำหนดรูปหลายเหลี่ยม (Polygon) และจุด P ต้องการตรวจสอบว่าจุดอยู่ภายในรูปหลายเหลี่ยมหรือภายนอก

วิธีแก้: เราจะลากเส้นตรงจากจุด P ขยายไปจนถึงอนันต์ เส้นนี้เป็นแนวนอน หรือขนานกับแกน x

จากเส้นนั้น เราจะนับว่าเส้นตัดด้านของรูปหลายเหลี่ยมกี่ครั้ง เมื่อจุดอยู่ภายใน จะตัดด้านเป็นจำนวนคี่ ถ้า P อยู่บนด้านใดด้านหนึ่ง จะตัดเป็นจำนวนคู่ ถ้าไม่ใช่เงื่อนไขใดเลย คืออยู่นอกรูปหลายเหลี่ยม

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

Input: จุดของรูปหลายเหลี่ยม {(0, 0), (10, 0), (10, 10), (0, 10)} และจุด P (5, 3) ที่ต้องการตรวจสอบ
Output: จุดอยู่ภายใน

อัลกอริทึม

checkInside(Poly, n, p)
Input: จุดของรูปหลายเหลี่ยม, จำนวนจุดของรูปหลายเหลี่ยม, จุด p ที่ต้องการตรวจสอบ
Output: True เมื่อ p อยู่ภายในรูปหลายเหลี่ยม, มิฉะนั้น false

Begin
    if n < 3, then
        return false
    สร้างเส้นชื่อ exLine จากจุด p ไปจนถึงอนันต์ ความชันของเส้นคือ 0°
    count := 0 และ i := 0
    repeat
        สร้างเส้นชื่อ side จากจุด poly[i] ถึง poly[(i+1) mod n]
        if side และ exLine ตัดกัน, then
            if side และ exLine collinear, then
                if จุด p อยู่บน side, then
                    return true
                else return false
            count := count + 1
        i := (i + 1) mod n
    until i ≠ 0
    return true ถ้า count เป็นคี่
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;
}

bool checkInside(Point poly[], int n, Point p) {
    if (n < 3)
        return false;  // เมื่อรูปหลายเหลี่ยมมีขอบน้อยกว่า 3 ไม่ใช่ polygon
    line exline = {p, {9999, p.y}};  // สร้างจุดที่อนันต์ y เท่ากับจุด p
    int count = 0;
    int i = 0;
    do {
        line side = {poly[i], poly[(i+1)%n]};  // สร้างเส้นจากสองจุดติดกันของ poly
        if (isIntersect(side, exline)) {
            // ถ้า side ตัด exline
            if (direction(side.p1, p, side.p2) == 0)
                return onLine(side, p);
            count++;
        }
        i = (i+1)%n;
    } while (i != 0);
    return count & 1;  // เมื่อ count เป็นคี่
}

int main() {
    Point polygon[] = {{0, 0}, {10, 0}, {10, 10}, {0, 10}};
    Point p = {5, 3};
    int n = 4;
    if (checkInside(polygon, n, p))
        cout << "Point is inside.";
    else
        cout << "Point is outside.";
}

ผลลัพธ์

Point is inside.