C++ Program: Duality Transformation of Line and Point (Point-Line Duality)

Point-Line Duality เป็นการแปลงระหว่าง Point และ Line ใน Computational Geometry มีหลายรูปแบบ แบบมาตรฐานคือ:

Standard Duality Transform

• Point → Line: Point p = (a, b) → Line y = ax - b
• Line → Point: Line y = cx + d → Point (c, -d)

Properties

1. Involution: Dual(Dual(p)) = p
2. Incidence Preserving: Point อยู่บน Line ⟺ Dual Line ผ่าน Dual Point
3. Above/Below: Point อยู่เหนือ Line ⟺ Dual Line อยู่เหนือ Dual Point
4. Vertical Lines: ไม่มี Dual Point (Slope = ∞) → ใช้ Projective Duality แทน

Projective Duality (Homogeneous Coordinates)

Line: ax + by + c = 0 ↔ Point: (a, b, c) ใน Projective Plane

• Point (x, y) → Line x·X + y·Y + 1 = 0 (หรือ y = x·X - Y)
• Line y = mx + c → Point (m, -c)

โค้ด C++ (Interactive Demo)

#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;

struct Point { double x, y; };
struct Line { double m, c; }; // y = mx + c

// Standard Duality
Line pointToLine(const Point& p) {
    return {p.x, -p.y}; // y = px - py
}

Point lineToPoint(const Line& l) {
    return {l.m, -l.c}; // (m, -c)
}

// Check if point lies on line
bool pointOnLine(const Point& p, const Line& l, double eps = 1e-9) {
    return abs(p.y - (l.m * p.x + l.c)) < eps;
}

// Check if line passes through point (dual of above)
bool lineThroughPoint(const Line& l, const Point& p, double eps = 1e-9) {
    return abs(l.c - (p.x * l.m - p.y)) < eps; // Dual condition
}

void printPoint(const Point& p) { cout << "(" << p.x << ", " << p.y << ")"; }
void printLine(const Line& l) { cout << "y = " << l.m << "x " << (l.c >= 0 ? "+" : "") << l.c; }

int main() {
    cout << "=== Point-Line Duality Demo ===\n\n";
    
    // Demo 1: Point → Line → Point
    Point p{2, 3};
    Line l = pointToLine(p);
    Point p2 = lineToPoint(l);
    
    cout << "Original Point: "; printPoint(p); cout << "\n";
    cout << "Dual Line:      "; printLine(l); cout << "\n";
    cout << "Dual of Line:   "; printPoint(p2); cout << "\n";
    cout << "Round-trip:     " << (abs(p.x - p2.x) < 1e-9 && abs(p.y - p2.y) < 1e-9 ? "EXACT" : "ERROR") << "\n\n";
    
    // Demo 2: Incidence Preservation
    Point q{1, 1};
    Line lq = pointToLine(q); // y = x - 1
    
    cout << "Point q: "; printPoint(q); cout << "\n";
    cout << "Line through q (dual): "; printLine(lq); cout << "\n";
    
    // Check if p lies on lq
    bool onLine = pointOnLine(p, lq);
    cout << "Does p lie on q's dual line? " << (onLine ? "YES" : "NO") << "\n";
    
    // Dual: Does lq's dual point lie on p's dual line?
    Point dual_q = lineToPoint(lq); // (1, 1)
    Line dual_p = pointToLine(p);   // y = 2x - 3
    bool dualOnDual = lineThroughPoint(dual_p, dual_q);
    cout << "Does dual(q) lie on dual(p)? " << (dualOnDual ? "YES" : "NO") << "\n";
    cout << "Incidence Preserved: " << (onLine == dualOnDual ? "YES" : "NO") << "\n\n";
    
    // Interactive
    cout << "=== Interactive ===\n";
    cout << "1. Point -> Line\n2. Line -> Point\nChoice: ";
    int choice; cin >> choice;
    
    if (choice == 1) {
        Point pt;
        cout << "Enter point (x y): "; cin >> pt.x >> pt.y;
        Line ln = pointToLine(pt);
        cout << "Dual Line: "; printLine(ln); cout << "\n";
    } else if (choice == 2) {
        Line ln;
        cout << "Enter line (m c) for y = mx + c: "; cin >> ln.m >> ln.c;
        Point pt = lineToPoint(ln);
        cout << "Dual Point: "; printPoint(pt); cout << "\n";
    }
    
    return 0;
}

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

=== Point-Line Duality Demo ===

Original Point: (2, 3)
Dual Line:      y = 2x -3
Dual of Line:   (2, 3)
Round-trip:     EXACT

Point q: (1, 1)
Line through q (dual): y = 1x -1
Does p lie on q's dual line? NO
Does dual(q) lie on dual(p)? NO
Incidence Preserved: YES

=== Interactive ===
1. Point -> Line
2. Line -> Point
Choice: 1
Enter point (x y): 1 2
Dual Line: y = 1x -2

Applications in Computational Geometry

• Arrangement of Lines: Dual → Points, หา Intersections = Convex Hull ใน Dual Space
• Half-plane Intersection: Dual → Point Set, Solve via Convex Hull
• Nearest Neighbor: Voronoi Diagram ↔ Delaunay Triangulation Duality
• Linear Programming: Primal-Dual Relationship
• Visibility Problems: Art Gallery, Line-of-sight

Limitations

• Vertical Lines (x = c) ไม่มี Dual ใน Standard Transform
• ใช้ Projective Duality หรือ Rotate Coordinates แทน
• Numerical Stability สำหรับ Large Coordinates