Hình học tính toán

Danh sách đầy đủ các thuật toán trong nhóm (Tổng: 16)

Hình học tính toán

Circle-Circle Intersection

Thời gian (Time) O(1)
Không gian (Space) O(1)

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.
Hình học tính toán

Closest Pair of Points (2D)

Thời gian (Time) O(N log N)
Không gian (Space) O(N)

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.
Hình học tính toán

Convex Hull - Graham Scan

Thời gian (Time) O(n log n)
Không gian (Space) O(n)

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.
Hình học tính toán

Convex Hull - Jarvis March

Thời gian (Time) O(n * h)
Không gian (Space) O(n)

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.
Hình học tính toán

Delaunay Triangulation

Thời gian (Time) O(N log N)
Không gian (Space) O(N)

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ù.
Hình học tính toán

Half-Plane Intersection

Thời gian (Time) O(N log N)
Không gian (Space) O(N)

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.
Hình học tính toán

Line Intersection Test

Thời gian (Time) O(1)
Không gian (Space) O(1)

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']);
}
Hình học tính toán

Minkowski Sum of Polygons

Thời gian (Time) O(N + M)
Không gian (Space) O(N + M)

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.
Hình học tính toán

Pick Theorem Implementation

Thời gian (Time) O(1)
Không gian (Space) O(1)

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).
Hình học tính toán

Point in Convex Polygon Query

Thời gian (Time) O(log N)
Không gian (Space) O(N)

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.
Hình học tính toán

Point in Polygon (Ray Casting)

Thời gian (Time) O(n)
Không gian (Space) O(1)

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.
Hình học tính toán

Polygon Triangulation (Ear Clipping)

Thời gian (Time) O(N^2)
Không gian (Space) O(N)

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ệ.
Hình học tính toán

Rotating Calipers Algorithm

Thời gian (Time) O(N log N)
Không gian (Space) O(N)

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.
Hình học tính toán

Shoelace Formula

Thời gian (Time) O(n)
Không gian (Space) O(1)

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;
}
Hình học tính toán

Sweepline Segment Intersection

Thời gian (Time) O((N + K) log N)
Không gian (Space) O(N)

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.
Hình học tính toán

Voronoi Diagram Construction

Thời gian (Time) O(N log N)
Không gian (Space) O(N)

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.