Circle-Circle Intersection
Mô tả nguyên lý
Tính toán các điểm giao nhau giữa hai hình tròn trên mặt phẳng.
Cài đặt mẫu (Implementation)
// Giải hệ phương trình đường tròn và tính toán khoảng cách vector tâm.
Closest Pair of Points (2D)
Mô tả nguyên lý
Tìm khoảng cách nhỏ nhất giữa hai điểm bất kỳ trong tập hợp điểm trên mặt phẳng.
Cài đặt mẫu (Implementation)
// Chia để trị theo tọa độ X và lọc dải băng trung tâm theo tọa độ Y.
Convex Hull - Graham Scan
Mô tả nguyên lý
Tìm bao lồi nhỏ nhất chứa toàn bộ tập hợp các điểm trên mặt phẳng 2D.
Cài đặt mẫu (Implementation)
// Sắp xếp các điểm theo góc cực và dùng stack để lọc bao lồi.
Convex Hull - Jarvis March
Mô tả nguyên lý
Thuật toán gói quà tìm bao lồi bằng cách liên tục xoay tìm điểm góc lệch lớn nhất.
Cài đặt mẫu (Implementation)
// Chọn điểm xuất phát ngoài cùng và tìm điểm tiếp theo tạo góc xoay trái xa nhất.
Delaunay Triangulation
Mô tả nguyên lý
Chia mặt phẳng chứa các điểm thành các tam giác sao cho không có điểm nào nằm trong đường tròn ngoại tiếp.
Cài đặt mẫu (Implementation)
// Xây dựng mạng lưới tam giác tối ưu không có góc quá nhọn hoặc quá tù.
Half-Plane Intersection
Mô tả nguyên lý
Tìm miền giao nhau của một tập hợp các nửa mặt phẳng trên mặt phẳng 2D.
Cài đặt mẫu (Implementation)
// Sắp xếp các đường thẳng theo góc hướng và sử dụng hàng đợi hai đầu để cắt gọt miền giao.
Line Intersection Test
Mô tả nguyên lý
Kiểm tra xem hai đoạn thẳng trên mặt phẳng có cắt nhau hay không.
Cài đặt mẫu (Implementation)
function ccw($p1, $p2, $p3) {
return ($p3['y'] - $p1['y']) * ($p2['x'] - $p1['x']) > ($p2['y'] - $p1['y']) * ($p3['x'] - $p1['x']);
}
Minkowski Sum of Polygons
Mô tả nguyên lý
Tính tổng Minkowski của hai đa giác lồi (dùng trong lập kế hoạch đường đi robot).
Cài đặt mẫu (Implementation)
// Sắp xếp các cạnh của hai đa giác theo góc cực và hợp nhất các vector hướng.
Pick Theorem Implementation
Mô tả nguyên lý
Tính diện tích đa giác có các đỉnh nằm trên hệ tọa độ nguyên (lattice polygon).
Cài đặt mẫu (Implementation)
// Công thức $Area = I + B/2 - 1$ liên kết diện tích với số điểm trong (I) và điểm biên (B).
Point in Convex Polygon Query
Mô tả nguyên lý
Xác định điểm có nằm trong đa giác lồi hay không bằng tìm kiếm nhị phân góc.
Cài đặt mẫu (Implementation)
// Phân chia đa giác thành các tam giác từ đỉnh gốc và dùng tích có hướng để kiểm tra.
Point in Polygon (Ray Casting)
Mô tả nguyên lý
Xác định một điểm có nằm bên trong đa giác 2D hay không bằng tia ray.
Cài đặt mẫu (Implementation)
// Đếm số lần tia đi ngang qua các cạnh của đa giác.
Polygon Triangulation (Ear Clipping)
Mô tả nguyên lý
Chia một đa giác đơn bất kỳ thành các tam giác bằng cách cắt bỏ các "tai" đa giác.
Cài đặt mẫu (Implementation)
// Xác định các đỉnh lồi lõm và cắt bỏ liên tục các tam giác hợp lệ.
Rotating Calipers Algorithm
Mô tả nguyên lý
Thuật toán thước xoay tìm đường kính hình học hoặc cặp điểm xa nhất trên bao lồi 2D.
Cài đặt mẫu (Implementation)
// Xoay đồng thời các tiếp tuyến vuông góc quanh bao lồi để quét các cặp điểm đối ứng.
Shoelace Formula
Mô tả nguyên lý
Tính diện tích của một đa giác đơn giản dựa vào tọa độ các đỉnh.
Cài đặt mẫu (Implementation)
function polygonArea($points) {
$n = count($points); $area = 0.0;
for ($i = 0; $i < $n; $i++) {
$j = ($i + 1) % $n;
$area += $points[$i]['x'] * $points[$j]['y'];
$area -= $points[$j]['x'] * $points[$i]['y'];
}
return abs($area) / 2.0;
}
Sweepline Segment Intersection
Mô tả nguyên lý
Tìm tất cả các giao điểm giữa N đoạn thẳng trên mặt phẳng bằng kỹ thuật đường quét.
Cài đặt mẫu (Implementation)
// Duy chuyển đường thẳng quét qua các sự kiện đầu/cuối đoạn thẳng kết hợp cấu trúc cây cân bằng.
Voronoi Diagram Construction
Mô tả nguyên lý
Phân rã mặt phẳng thành các vùng ảnh hưởng gần nhất xung quanh tập hợp các điểm mốc.
Cài đặt mẫu (Implementation)
// Xây dựng sơ đồ Voronoi đối ngẫu trực tiếp từ lưới tam giác Delaunay.