Giao diện
Hình Học Tính Toán (Computational Geometry) 📐
Hình học tính toán không chỉ là bài toán trên giấy — nó là nền tảng của collision detection trong game engines, motion planning trong robotics, geofencing trong hệ thống bản đồ, và object detection trong computer vision. Bất kỳ hệ thống nào xử lý dữ liệu không gian đều cần các thuật toán hình học hiệu quả.
Module này xây dựng từ công cụ nền tảng (Cross Product) đến thuật toán cốt lõi (Convex Hull), sau đó mở rộng ra các bài toán nâng cao hơn. Mỗi thuật toán đều được trình bày với trực giác hình học, triển khai polyglot, và phân tích production trade-offs.
Lộ trình học
Cross Product là công cụ cốt lõi xuyên suốt module — nắm vững nó trước khi bước vào Convex Hull. Từ Convex Hull, các bài toán nâng cao sẽ tự nhiên mở ra.
Cross Product (công cụ nền tảng) ↓ Convex Hull ↓ ┌─────┴─────┐ ↓ ↓ Line Intersection Point in Polygon ↓ Rotating Calipers
Nội dung
Nền tảng (Foundation)
| Bài học | Mô tả | Độ khó |
|---|---|---|
| Convex Hull (Bao Lồi) | Graham Scan, Andrew's Monotone Chain, Jarvis March — collision detection, image processing | Intermediate |
Sắp ra mắt
| Chủ đề | Mô tả |
|---|---|
| Line Intersection | Giao điểm đoạn thẳng — Bentley-Ottmann sweep line |
| Point in Polygon | Kiểm tra điểm trong đa giác — ray casting, winding number |
| Closest Pair | Cặp điểm gần nhất — divide and conquer O(n log n) |
| Rotating Calipers | Đường kính Convex Hull, cặp điểm xa nhất |
| Voronoi Diagram | Phân vùng không gian Thiessen |
Tại sao hình học quan trọng trong production?
| Lĩnh vực | Ứng dụng cụ thể |
|---|---|
| Game Development | Collision detection, frustum culling, physics simulation |
| Robotics | Motion planning, obstacle avoidance, SLAM |
| Computer Vision | Object detection, image segmentation, feature matching |
| GIS / Bản đồ | Geofencing, route optimization, spatial queries |
| CAD / Sản xuất | CNC toolpath, 3D printing slicing, mesh processing |
🧠 Quiz
Câu 1: Thuật toán Convex Hull nào có độ phức tạp O(n log n)?
- [ ] A) Brute Force — thử mọi tam giác
- [x] B) Graham Scan hoặc Andrew's Monotone Chain
- [ ] C) Jarvis March (Gift Wrapping)
- [ ] D) Tất cả thuật toán Convex Hull đều O(n²)
💡 Giải thích: Graham Scan: sort theo góc O(n log n) + scan O(n) = O(n log n). Andrew's Monotone Chain: sort theo x O(n log n) + upper/lower hull O(n) = O(n log n). Jarvis March: O(nh) với h = số điểm trên hull — worst case O(n²) khi tất cả điểm nằm trên hull.
Câu 2: Cross product của vector (a,b) và (c,d) bằng bao nhiêu?
- [ ] A) a×c + b×d
- [x] B) a×d - b×c
- [ ] C) a×c - b×d
- [ ] D) (a+c) × (b+d)
💡 Giải thích: Cross product 2D: (a,b) × (c,d) = ad - bc. Kết quả dương → counterclockwise, âm → clockwise, bằng 0 → collinear. Đây là phép toán quan trọng nhất trong computational geometry.