Geometry & Spatial

Module 5 — Geometry & Spatial: tổng quan

Thuật toán hình học & không gian: sweep line, convex hull, quadtree, R-tree, geohash, H3/S2. Nền của PostGIS, Uber, bản đồ.

Sweep line — quét đường tìm giao điểm

Quét một đường tưởng tượng qua mặt phẳng, duy trì trạng thái active để tìm giao điểm đoạn thẳng O((n+k)log n). Bentley-Ottmann.

Convex hull — bao lồi (Graham / Andrew)

Tìm đa giác lồi nhỏ nhất bao mọi điểm: Graham scan và Andrew monotone chain O(n log n). Ứng dụng collision, clustering.

Quadtree — chia không gian 2D đệ quy

Chia mặt phẳng thành 4 phần đệ quy để index điểm/vùng, truy vấn lân cận và range nhanh. Nền của game, GIS, image.

R-tree — index hình chữ nhật bao (MBR)

Cây cân bằng index MBR cho đối tượng không gian; truy vấn range/nearest hiệu quả. Nền của Postgres GiST, không gian địa lý.

Geohash — mã hoá toạ độ thành chuỗi

Đan xen bit kinh/vĩ độ thành chuỗi base32; prefix chung nghĩa là gần nhau. Cho phép range query không gian bằng index chuỗi thường.

H3 & S2 — lưới phân cấp toàn cầu

H3 (lục giác, Uber) và S2 (Google) chia bề mặt Trái Đất thành ô phân cấp, ổn định hơn geohash ở ranh giới. Index và truy vấn lân cận.

Mini-challenge — tìm điểm lân cận (geohash)

Lab: index điểm bằng geohash và tìm tất cả điểm trong bán kính cho trước, xử lý edge case ranh giới ô.

Case study — PostGIS GiST & Uber H3

PostGIS dùng GiST/R-tree cho truy vấn không gian thế nào, và Uber dùng H3 để matching tài xế-khách ra sao.

Module 5 — Tổng kết & cheat sheet

Recap spatial: bảng chọn cấu trúc theo bài toán (point/range/nearest, 2D/cầu), glossary, self-assessment.