Computer >> Máy Tính >  >> Lập trình >> Lập trình

Bộ tứ vùng trong cấu trúc dữ liệu

Phần tư vùng rất hữu ích để biểu diễn phân vùng không gian theo hai chiều bằng cách chia vùng thành bốn góc phần tư bằng nhau, các tham số con, v.v. với mỗi nút lá chứa dữ liệu tương ứng với một tiểu vùng cụ thể. Mỗi nút trong cây được liên kết với chính xác bốn nút con hoặc không có nút con (một nút lá). Chiều cao của các phần tư tuân theo chiến lược phân tách này (tức là chia nhỏ các khu vực con cho đến khi và trừ khi có dữ liệu thú vị trong khu vực con cần phải tinh chỉnh nhiều hơn) nhạy cảm và phụ thuộc vào sự phân bố không gian của các khu vực thú vị trong không gian bị phá vỡ. Khu vực quadtree được biểu thị là một loại trie.

Một cây tứ phân vùng với độ sâu n có thể được triển khai để biểu thị một hình ảnh bao gồm 2n × 2n pixel, trong đó mỗi giá trị pixel là 0 hoặc 1. Nút gốc hữu ích để đại diện cho toàn bộ vùng hình ảnh. Nếu các pixel trong bất kỳ vùng nào không hoàn toàn là 0 hoặc 1, nó sẽ được chia nhỏ. Trong ứng dụng này, mỗi nút lá hữu ích để đại diện cho một khối pixel có tất cả là 0 hoặc tất cả là 1. Lưu ý khả năng tiết kiệm về không gian khi những cây này được thực hiện để lưu trữ hình ảnh; những hình ảnh này thường có nhiều vùng có kích thước đáng kể có cùng giá trị màu xuyên suốt. Thay vì lưu trữ một mảng lớn 2 Chiều của mỗi pixel trong hình ảnh, quadtree có thể thu thập cùng một thông tin có khả năng có nhiều mức chia lớn hơn các ô có kích thước có độ phân giải pixel mà chúng ta cần. Kích thước pixel và hình ảnh có thể liên kết độ phân giải cây và kích thước tổng thể.

Một quadtree vùng cũng có thể được triển khai dưới dạng đại diện độ phân giải thay đổi của trường dữ liệu. Chẳng hạn, nhiệt độ trong một khu vực có thể được lưu trữ dưới dạng một phần tư, với mỗi nút lá lưu trữ nhiệt độ trung bình trong toàn bộ tiểu vùng mà nó đại diện.

Nếu một quadtree vùng được triển khai để đại diện cho một tập hợp dữ liệu điểm (chẳng hạn như vĩ độ và kinh độ của một tập hợp các thành phố), các vùng sẽ được chia nhỏ cho đến khi và trừ khi mỗi lá chứa tối đa một điểm.