Quadtree là cây dùng để lưu trữ hiệu quả dữ liệu điểm trên không gian hai chiều. Trong cây này, mỗi nút tối đa có bốn nút con.
Chúng ta có thể xây dựng quadtree từ vùng hai chiều bằng các bước sau:
- Chia không gian hai chiều hiện tại thành bốn ô (boxes).
- Nếu một ô chứa một hoặc nhiều điểm, tạo đối tượng con, lưu trữ không gian hai chiều của ô đó.
- Nếu ô không chứa điểm nào, không tạo con cho nó.
- Đệ quy cho từng con.
Quadtree được dùng trong nén hình ảnh, nơi mỗi nút chứa màu trung bình của các con của nó. Càng đi sâu vào cây, chi tiết hình ảnh càng nhiều.
Quadtree cũng dùng trong tìm kiếm nút trong vùng hai chiều. Ví dụ: muốn tìm điểm gần nhất với tọa độ cho trước, có thể dùng quadtree.
Hàm Insert (Chèn)
Hàm insert dùng để chèn nút vào Quad Tree hiện có. Hàm trước tiên kiểm tra nút cho trước có nằm trong biên của quad hiện tại không. Nếu không, hủy chèn ngay. Nếu có, chọn con phù hợp chứa nút này dựa trên vị trí. Hàm này O(log N) với N là kích thước khoảng cách.
Hàm Search (Tìm kiếm)
Hàm search dùng để định vị nút trong quad cho trước. Có thể chỉnh sửa để trả về nút gần nhất với điểm cho trước. Hàm áp dụng bằng cách lấy điểm cho trước, so sánh với biên các quad con và đệ quy. Hàm này O(log N) với N là kích thước khoảng cách.
Một số ứng dụng phổ biến của quadtree
- Biểu diễn hình ảnh (Image Representation).
- Xử lý hình ảnh (Image Processing).
- Tạo lưới (Mesh generation).
- Phát hiện va chạm hiệu quả hai chiều.
- Giải trường đa chiều (cơ học chất lỏng tính toán, điện từ).
- Ước lượng trạng thái (State estimation).
- Phân tích hình ảnh fractal (fractal image analysis).