Above-Below-On Test: ตรวจสอบตำแหน่งจุดเทียบเส้นใน C++

Above-Below-On Test ใช้กำหนดตำแหน่งของจุดเทียบกับเส้นตรง โดยใช้ค่า sign ของฟังก์ชันเส้น

ทฤษฎี

เส้นตรงผ่านจุด m(x₁,y₁) และ n(x₂,y₂) มีสมการ:

F(x, y) = (y₂ - y₁)x + (x₁ - x₂)y + (x₂y₁ - x₁y₂) = 0

สำหรับจุดทดสอบ t(xₜ, yₜ) คำนวณ s = F(xₜ, yₜ):

• s < 0 → จุดอยู่ด้าน **clockwise** (below/left) ของเส้น
• s > 0 → จุดอยู่ด้าน **counter-clockwise** (above/right) ของเส้น
• s = 0 → จุดอยู่ **บนเส้น**

ตัวอย่างโค้ด

#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;

struct Point {
    int x, y;
};

// คำนวณค่า sign สำหรับจุด p เทียบกับเส้น p1-p2
long long positionTest(const Point& p1, const Point& p2, const Point& p) {
    return 1LL * (p2.y - p1.y) * p.x + 
           1LL * (p1.x - p2.x) * p.y + 
           1LL * (p2.x * p1.y - p1.x * p2.y);
}

string positionToString(long long s) {
    if (s < 0) return "ด้านล่าง/ซ้าย (Clockwise side)";
    if (s > 0) return "ด้านบน/ขวา (Counter-clockwise side)";
    return "อยู่บนเส้น";
}

void printLineEquation(const Point& p1, const Point& p2) {
    long long A = p2.y - p1.y;
    long long B = p1.x - p2.x;
    long long C = p2.x * p1.y - p1.x * p2.y;
    cout << "สมการเส้น: (" << A << ")x + (" << B << ")y + (" << C << ") = 0" << endl;
}

int main() {
    srand(time(0));
    
    // เส้นสุ่ม
    Point p1 = {rand() % 21, rand() % 21};
    Point p2 = {rand() % 21, rand() % 21};
    
    // รับจุดจากผู้ใช้
    Point testPt;
    cout << "ป้อนจุดทดสอบ (x y): ";
    cin >> testPt.x >> testPt.y;
    
    printLineEquation(p1, p2);
    cout << "จุดทดสอบ: (" << testPt.x << ", " << testPt.y << ")" << endl;
    
    long long s = positionTest(p1, p2, testPt);
    cout << "ค่า s = " << s << endl;
    cout << "ตำแหน่ง: " << positionToString(s) << endl;
    
    // ทดสอบกรณีต่างๆ
    cout << "\n--- ทดสอบกรณีมาตรฐาน ---" << endl;
    
    // เส้นแนวนอน y = 2
    Point h1 = {0, 2}, h2 = {10, 2};
    Point above = {5, 5}, below = {5, -1}, on = {3, 2};
    
    printLineEquation(h1, h2);
    cout << "จุด (5,5): " << positionToString(positionTest(h1, h2, above)) << endl;
    cout << "จุด (5,-1): " << positionToString(positionTest(h1, h2, below)) << endl;
    cout << "จุด (3,2): " << positionToString(positionTest(h1, h2, on)) << endl;
    
    // เส้นแนวตั้ง x = 3
    Point v1 = {3, 0}, v2 = {3, 10};
    Point left = {0, 5}, right = {6, 5};
    
    printLineEquation(v1, v2);
    cout << "จุด (0,5): " << positionToString(positionTest(v1, v2, left)) << endl;
    cout << "จุด (6,5): " << positionToString(positionTest(v1, v2, right)) << endl;
    
    return 0;
}

ผลลัพธ์ตัวอย่าง

สมการเส้น: (7)x + (0)y + (-105) = 0
จุดทดสอบ: (7, 6)
ค่า s = -105
ตำแหน่ง: ด้านล่าง/ซ้าย (Clockwise side)

--- ทดสอบกรณีมาตรฐาน ---
สมการเส้น: (0)x + (10)y + (-20) = 0
จุด (5,5): ด้านบน/ขวา (Counter-clockwise side)
จุด (5,-1): ด้านล่าง/ซ้าย (Clockwise side)
จุด (3,2): อยู่บนเส้น
สมการเส้น: (10)x + (0)y + (-30) = 0
จุด (0,5): ด้านล่าง/ซ้าย (Clockwise side)
จุด (6,5): ด้านบน/ขวา (Counter-clockwise side)

การประยุกต์ใช้

• Point in Polygon: Ray casting algorithm ใช้ above-below test
• Convex Hull: Gift wrapping ใช้ orientation test
• Line Clipping: Cohen-Sutherland ใช้ region codes จาก above-below
• Collision Detection: Separating axis theorem

ข้อควรระวัง

• Integer overflow: ใช้ long long หรือ __int128 สำหรับพิกัดใหญ่
• Floating point precision: ใช้ epsilon เมื่อทำงานกับ double
• ทิศทางเส้น (p1→p2 vs p2→p1) จะกลับเครื่องหมาย s