Câu hỏi lập chỉ mục không gian 2D:Một quadtree vô hạn vô hạn được gọi là gì?
Bạn gọi cấu trúc dữ liệu về cơ bản là một tứ giác vô tận có nút không chứa tọa độ tuyệt đối và tỷ lệ tuyệt đối - trong đó hệ tọa độ của mỗi nút đã được chuẩn hóa cho đơn vị vuông (0,0) - (1,1), và trong đó nút cấp cao nhất không được sửa hoàn toàn?
Đó là một quadtree, tất nhiên - nhưng những gì loại của quadtree là nó? (Có một cái tên phổ biến không? Tôi đã thấy hàng tá loại quadtrees được đặt tên và được định nghĩa trong văn học, nhưng không phải loại này.)
Để hiển thị một cảnh, bạn sẽ có một số nút khởi đầu (không nhất thiết là gốc), kích thước của nó tính bằng pixel và vị trí của nó trên màn hình. Sau đó, bạn vẽ tất cả các đối tượng trong nút bằng cách mở rộng tọa độ của chúng bằng cách sử dụng ma trận chuyển đổi hiện tại, mà bạn đẩy vào ngăn xếp và giảm một nửa khi bạn đi xuống cây. Do đó, các tọa độ tuyệt đối của các nút chỉ có sẵn mặc dù các biến công việc tạm thời trong quá trình dựng hình và không nằm trong chính cấu trúc dữ liệu.
Nếu đối tượng trong một nút di chuyển ra ngoài nút (ví dụ: bên ngoài hình vuông đơn vị), bạn chuyển nó cho phụ huynh để gán lại cho nút khác. Nếu một đối tượng bị phân mảnh (ví dụ, một tiểu hành tinh bị trúng một viên đạn), các phần nhỏ hơn sẽ được chuyển xuống các nút con, những người phải mở rộng tọa độ một cách thích hợp để duy trì bình thường đơn vị vuông trong mỗi nút.
Sự khác biệt chính ở đây từ triển khai quadtree truyền thống được sử dụng trong lập chỉ mục không gian là tọa độ của đối tượng luôn liên quan đến hệ tọa độ của nút trong đó chúng được chứa. Tính tương đối này không chỉ áp dụng cho vị trí mà còn cho quy mô.
* Vô hạn vì thiếu tọa độ tuyệt đối; thậm chí các tọa độ điểm động kép chính xác truyền đạt các giới hạn về vị trí và kích thước khi được sử dụng để định vị tuyệt đối.
Fred? (chỉ đùa thôi). – bmargulies