Computer >> Hướng Dẫn Máy Tính >  >> Lập Trình >> C++

Chuyển đổi đối ngẫu (Duality) giữa Điểm và Đường thẳng trong C++

Trong hình học tính toán, Duality Transform (chuyển đổi đối ngẫu) ánh xạ giữa điểm và đường thẳng trong mặt phẳng, bảo toàn quan hệ xảy ra (incidence) và thứ tự (above/below).

Biến đổi chuẩn (Standard Duality)

  • Điểm → Đường thẳng: Điểm p = (a, b) ánh xạ thành đường thẳng p*: y = a*x - b.
  • Đường thẳng → Điểm: Đường thẳng L: y = c*x + d ánh xạ thành điểm L* = (c, -d).

Tính chất

  • Đối ngẫu của đối ngẫu là chính nó: (p*)* = p, (L*)* = L.
  • Điểm p nằm trên đường thẳng L ⇔ Điểm L* nằm trên đường thẳng p*.
  • Điểm p nằm trên đường thẳng L ⇔ b ≤ c*a + d ⇔ -d ≤ a*c - b ⇔ L* trên p*.

Chương trình C++ minh họa

#include <iostream>
#include <iomanip>

using namespace std;

// Điểm (a,b) -> Duong thang y = a*x - b
void pointToLine(double a, double b) {
    cout << "Diem (" << a << ", " << b << ") -> Duong thang: y = " 
         << a << "x " << (b >= 0 ? "-" : "+") << " " << abs(b) << '\n';
}

// Duong thang y = c*x + d -> Diem (c, -d)
void lineToPoint(double c, double d) {
    cout << "Duong thang y = " << c << "x " << (d >= 0 ? "+" : "") << d 
         << " -> Diem: (" << c << ", " << -d << ")\n";
}

int main() {
    cout << "=== CHUYEN DOI DOI NGUAU DIEM <-> DUONG THANG ===\n\n";
    
    // Test 1: Điểm -> Đường thẳng
    cout << "1. DIEM -> DUONG THANG\n";
    pointToLine(2, 3);   // y = 2x - 3
    pointToLine(-1, 4);  // y = -1x - 4
    pointToLine(0, -5);  // y = 0x + 5 (duong ngang)
    
    cout << "\n2. DUONG THANG -> DIEM\n";
    lineToPoint(2, -3);   // (2, 3)
    lineToPoint(0.5, 2);  // (0.5, -2)
    lineToPoint(-2, 0);   // (-2, 0)
    
    cout << "\n3. KIEM TRA TINH CHAT (p nam tren L <=> L* nam tren p*)\n";
    double a = 2, b = 1;      // Diem p(2,1)
    double c = 1, d = -2;     // Duong L: y = x - 2
    // p nam tren L? 1 <= 1*2 - 2 = 0 -> FALSE (p nam DUOI L)
    // L* = (1, 2), p*: y = 2x - 1. L* nam tren p*? 2 <= 2*1 - 1 = 1 -> FALSE (L* nam DUOI p*)
    // Cung vi tri tuong doi -> DUNG
    
    bool p_on_L = (b <= c*a + d);
    bool Lstar_on_pstar = (-d <= a*c - b);
    
    cout << "Diem p(" << a << "," << b << ") nam tren L: y=" << c << "x" << (d>=0?"+":"") << d << " ? " 
         << (p_on_L ? "CO" : "KHONG") << '\n';
    cout << "Diem L*(" << c << "," << -d << ") nam tren p*: y=" << a << "x" << (b>=0?"-":"+") << abs(b) << " ? " 
         << (Lstar_on_pstar ? "CO" : "KHONG") << '\n';
    cout << "=> Tinh chat giu nguyen: " << (p_on_L == Lstar_on_pstar ? "DUNG" : "SAI") << '\n';
    
    return 0;
}

Kết quả

=== CHUYEN DOI DOI NGUAU DIEM <-> DUONG THANG ===

1. DIEM -> DUONG THANG
Diem (2, 3) -> Duong thang: y = 2x - 3
Diem (-1, 4) -> Duong thang: y = -1x - 4
Diem (0, -5) -> Duong thang: y = 0x + 5

2. DUONG THANG -> DIEM
Duong thang y = 2x - 3 -> Diem: (2, 3)
Duong thang y = 0.5x + 2 -> Diem: (0.5, -2)
Duong thang y = -2x + 0 -> Diem: (-2, 0)

3. KIEM TRA TINH CHAT (p nam tren L <=> L* nam tren p*)
Diem p(2,1) nam tren L: y=1x-2 ? KHONG
Diem L*(1,2) nam tren p*: y=2x-1 ? KHONG
=> Tinh chat giu nguyen: DUNG

Ứng dụng trong Computational Geometry

  • Half-plane intersection: Chuyển đổi bài toán giao nửa mặt phẳng thành Convex Hull đối ngẫu.
  • Arrangements of lines: Phân tích cấu trúc đường thẳng qua đối ngẫu điểm.
  • Point location: Tìm điểm nằm trong face nào của arrangement.
  • Optimization: Linear programming dual (primal-dual).
  • Kinetic data structures: Theo dõi sự thay đổi topology.

Mở rộng: Parabola Duality (cho Voronoi/Delaunay)

Ánh xạ điểm (a,b) → parabol y = (x-a)² + b (hoặc y = x² - 2ax + (a²+b)). Đây là cơ sở của thuật toán Fortune cho Voronoi Diagram và Delaunay Triangulation.

Duality là khái niệm cốt lõi, biến đổi bài toán khó trên điểm thành bài toán dễ trên đường thẳng (và ngược lại).