Cấu trúc dữ liệu không gian

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

Cấu trúc dữ liệu không gian

K-D Tree (K-Dimensional Tree)

Thời gian (Time) O(log N) tìm kiếm
Không gian (Space) O(N)

Mô tả nguyên lý

Cây phân cấp không gian đa chiều dùng để tìm kiếm điểm gần nhất (Nearest Neighbor Search).

Cài đặt mẫu (Implementation)

// Phân chia không gian luân phiên theo các trục tọa độ X, Y, Z ở mỗi tầng của cây.
Cấu trúc dữ liệu không gian

Octree 3D Spatial Indexing

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

Mô tả nguyên lý

Cây phân rã không gian 3 chiều thành 8 khối lập phương nhỏ hơn cho đồ họa và mô phỏng vật lý.

Cài đặt mẫu (Implementation)

// Phân chia không gian 3D thành 8 octants để quản lý va chạm và điểm ảnh 3D.
Cấu trúc dữ liệu không gian

Quadtree Spatial Indexing

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

Mô tả nguyên lý

Cây phân rã không gian 2D thành 4 ô vuông con, dùng trong game physics và GIS.

Cài đặt mẫu (Implementation)

// Đệ quy chia không gian thành 4 góc phần tư khi số lượng đối tượng trong ô vượt ngưỡng.