C++ Program: Check Collinearity of Three Points (3 จุดอยู่เส้นตรงเดียวกันหรือไม่)

จุด 3 จุด P1(x1,y1), P2(x2,y2), P3(x3,y3) อยู่บนเส้นตรงเดียวกัน (Collinear) ก็ต่อเมื่อ พื้นที่สามเหลี่ยมที่เกิดขึ้น = 0

Mathematical Formula

พื้นที่สามเหลี่ยม (Shoelace Formula):

Area = ½ | x1(y2 - y3) + x2(y3 - y1) + x3(y1 - y2) |

Collinear ⟺ Area = 0 ⟺ x1(y2 - y3) + x2(y3 - y1) + x3(y1 - y2) = 0

Alternative Methods

1. Slope Comparison (ระวัง Division by Zero)

(y2 - y1) / (x2 - x1) == (y3 - y1) / (x3 - x1)
// Cross-multiply to avoid division:
(y2 - y1) * (x3 - x1) == (y3 - y1) * (x2 - x1)

2. Cross Product (Vector Approach)

Vector v1 = P2 - P1 = (x2-x1, y2-y1)
Vector v2 = P3 - P1 = (x3-x1, y3-y1)
Cross Product = v1.x * v2.y - v1.y * v2.x = 0 → Collinear

โค้ด C++ (Complete with Random Test)

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <cmath>
using namespace std;

struct Point {
    int x, y;
    Point(int x_=0, int y_=0) : x(x_), y(y_) {}
};

// Method 1: Area Formula (Integer, Exact)
bool collinearArea(const Point& p1, const Point& p2, const Point& p3) {
    long long area2 = 1LL * p1.x * (p2.y - p3.y)
                    + 1LL * p2.x * (p3.y - p1.y)
                    + 1LL * p3.x * (p1.y - p2.y);
    return area2 == 0;
}

// Method 2: Cross Product (Integer, Exact)
bool collinearCross(const Point& p1, const Point& p2, const Point& p3) {
    long long cross = 1LL * (p2.x - p1.x) * (p3.y - p1.y)
                    - 1LL * (p2.y - p1.y) * (p3.x - p1.x);
    return cross == 0;
}

// Method 3: Slope (Double, Approximate - Avoid for Exact)
bool collinearSlope(const Point& p1, const Point& p2, const Point& p3) {
    if (p2.x == p1.x && p3.x == p1.x) return true; // Vertical line
    if (p2.x == p1.x || p3.x == p1.x) return false;
    
    double slope1 = double(p2.y - p1.y) / (p2.x - p1.x);
    double slope2 = double(p3.y - p1.y) / (p3.x - p1.x);
    return abs(slope1 - slope2) < 1e-9;
}

void printPoint(const Point& p) {
    cout << "(" << p.x << ", " << p.y << ")";
}

int main() {
    srand(time(0));
    const int L = 1, U = 20;
    
    cout << "=== Random Collinearity Tests ===\n\n";
    
    for (int test = 0; test < 10; test++) {
        Point p1(rand() % (U-L+1) + L, rand() % (U-L+1) + L);
        Point p2(rand() % (U-L+1) + L, rand() % (U-L+1) + L);
        Point p3(rand() % (U-L+1) + L, rand() % (U-L+1) + L);
        
        cout << "Points: ";
        printPoint(p1); cout << ", ";
        printPoint(p2); cout << ", ";
        printPoint(p3); cout << "\n";
        
        bool col = collinearArea(p1, p2, p3);
        cout << "Area Method:    " << (col ? "COLLINEAR" : "NOT COLLINEAR") << "\n";
        
        col = collinearCross(p1, p2, p3);
        cout << "Cross Product:  " << (col ? "COLLINEAR" : "NOT COLLINEAR") << "\n";
        
        // Force collinear case for demo
        if (test == 0) {
            p1 = {1, 1}; p2 = {2, 2}; p3 = {3, 3};
            cout << "\nForced Collinear: ";
            printPoint(p1); cout << ", ";
            printPoint(p2); cout << ", ";
            printPoint(p3); cout << "\n";
            cout << "Area Method:    " << (collinearArea(p1,p2,p3) ? "COLLINEAR" : "NOT") << "\n";
        }
        cout << "---\n";
    }
    
    // Interactive
    cout << "\n=== Manual Input ===\n";
    Point a, b, c;
    cout << "Enter x1 y1: "; cin >> a.x >> a.y;
    cout << "Enter x2 y2: "; cin >> b.x >> b.y;
    cout << "Enter x3 y3: "; cin >> c.x >> c.y;
    
    if (collinearArea(a, b, c)) {
        cout << "The points ARE collinear (lie on a straight line)\n";
    } else {
        cout << "The points are NOT collinear\n";
    }
    
    return 0;
}

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

Points: (20, 9), (6, 13), (13, 11)
Area Method:    COLLINEAR
Cross Product:  COLLINEAR
---
Points: (9, 15), (4, 15), (11, 16)
Area Method:    NOT COLLINEAR
Cross Product:  NOT COLLINEAR
---

Integer Overflow Protection

ใช้ long long (64-bit) สำหรับการคำนวณ พิกัดสูงสุด ~10⁹ ก่อน Overflow

Floating Point Precision

สำหรับ Double Coordinates ใช้ Epsilon Comparison:

bool collinearDouble(const Point& p1, const Point& p2, const Point& p3, double eps = 1e-9) {
    double area = 0.5 * abs(
        p1.x*(p2.y-p3.y) + p2.x*(p3.y-p1.y) + p3.x*(p1.y-p2.y)
    );
    return area < eps;
}

Applications

• Computational Geometry: Convex Hull, Line Sweep
• Computer Graphics: Degenerate Triangle Detection
• GIS: Road Network Simplification
• Computer Vision: Line Detection (Hough Transform)
• Robotics: Path Planning Collision Check