Cây tứ phân là cây được thực hiện để lưu trữ hiệu quả dữ liệu của các điểm trên không gian hai chiều. Trong cây này, mỗi nút có tối đa bốn nút con.
Chúng ta có thể xây dựng một cây tứ phân từ một khu vực hai chiều bằng cách thực hiện các bước sau đây
- Không gian hai chiều hiện tại được chia thành bốn hộp.
- Nếu một hộp chứa một hoặc nhiều điểm trong đó, hãy tạo một đối tượng con, lưu trữ trong đó không gian hai chiều của hộp.
- Nếu một hộp không chứa bất kỳ điểm nào, đừng xây dựng một hộp con cho nó.
- Thực hiện đệ quy cho từng phần tử con.
Các nút tứ phân được thực hiện trong quá trình nén hình ảnh, trong đó mỗi nút bao gồm màu trung bình của mỗi nút con của nó.
Càng vào sâu trong cây, hình ảnh càng chi tiết hơn.
Các phần tư cũng được thực hiện trong việc tìm kiếm các nút trong một khu vực hai chiều. Ví dụ:nếu chúng tôi muốn tính toán điểm gần nhất với tọa độ đã cho, chúng tôi có thể thực hiện việc này bằng cách triển khai các góc bốn.
Chèn hàm
Các chức năng chèn được thực hiện để chèn một nút vào Cây tứ phân hiện có. Trước tiên, chức năng này xác minh xem liệu nút đã cho có nằm trong ranh giới của quad hiện tại hay không. Nếu không, sau đó chúng tôi ngay lập tức hủy bỏ việc chèn. Nếu nó nằm trong ranh giới, chúng tôi chọn nút con thích hợp để chứa nút này dựa trên vị trí của nó. Hàm này là O (Log N) trong đó N cho biết kích thước của khoảng cách.
Chức năng tìm kiếm
Chức năng tìm kiếm được thực hiện để xác định vị trí một nút trong bộ tứ đã cho. Nó cũng có thể được chỉnh sửa để trả về nút gần nhất với điểm đã cho. Hàm này được áp dụng bằng cách lấy điểm đã cho, so sánh với ranh giới của các quads con và đệ quy. Hàm này là O (Log N) trong đó N cho biết kích thước của khoảng cách.
Một số cách sử dụng phổ biến của quadtrees
- Hình ảnh Đại diện cho hình ảnh
- Xử lý hình ảnh của hình ảnh
- Tạo lưới của mắt lưới
- Thực hiện phát hiện va chạm hiệu quả theo hai chiều
- Biểu diễn để tìm giải pháp của trường đa chiều (động lực học chất lỏng tính toán, điện từ học)
- Ước tính trạng thái
- Hình ảnh tứ phân vị cũng được triển khai trong lĩnh vực phân tích hình ảnh fractal