Cấu trúc dữ liệu phân vùng không gian nhị phân Đối với không gian 2D Donut

Question

Tôi có bản đồ 2D bao quanh các cạnh. Vì vậy, nếu bạn di chuyển khỏi cạnh phải, bạn sẽ xuất hiện lại ở phía bên trái của bản đồ. Tương tự như vậy với ba cạnh khác.

Đây là vấn đề có thể kế thừa đối với KDTree mà tôi sử dụng để tìm các phần tử trong phạm vi điểm. Thông thường, bạn sẽ kiểm tra xem quả cầu siêu va chạm với mặt phẳng siêu để xem bạn có nên tiếp tục tìm kiếm phía bên kia của cây không, nhưng kiểm tra này không hoạt động với các cạnh gói.

Có cách nào để sửa đổi cây KD để làm việc với không gian 2D không?

Answer 1

Hình tứ giác là cây KD có 4 lá. Một quadtree không giúp đỡ để bọc bởi vì cấu trúc dữ liệu của nó là một bọc chính nó. Bạn chỉ cần sử dụng một kích thước gấp đôi 2x của cấu trúc của bạn.

Answer 2

Jitamaro đề xuất nhưng không giải thích phương pháp dựa trên quadtree "2x kích thước". Đó là một gợi ý hợp lý, ngoại trừ quadtree sử dụng bốn lần như nhiều nút thay vì hai, như tôi sẽ giải thích dưới đây trước khi dự kiến ​​đề xuất một phương pháp thay thế.

Giả sử mỗi tọa độ (x, y) có -.5 < x <= .5 và -.5 < y <= .5 và bất cứ khi nào j, k là số nguyên, điểm (x + j, y + k) giống hệt với điểm (x, y). Hãy để quadtree T bao gồm các điểm với các tọa độ trong phạm vi -1 < x,y <= 1. Mỗi lần bạn thêm một mục tại (x, y) vào T, trong đó -.5 < x,y <= .5, hãy x' = {x-1 nếu x>0 khác x+1} và y' = {y-1 nếu y>0 else y+1}. Ngoài ra, hãy thêm mục tại (x, y '), (x', y ') và (x', y). [Khi bạn xóa các điểm sau đó, hãy tính lại (x ', y') et al và xóa chúng.] Dễ dàng thấy rằng các điểm tra cứu gần nhất sẽ hoạt động chính xác, miễn là bất kỳ tọa độ tra cứu nào bên ngoài khoảng thời gian (-.5,.5] được điều chỉnh đúng cách.

Nếu số lượng nút bốn lần là bộ chia đối số, hãy lưu ý rằng nếu các tọa độ như được mô tả ở trên được sử dụng trong các phụ đề ở trên mức k=3 và tọa độ tương đối được lưu dưới mức k, có thể duy trì duy nhất bản sao của các subtrees dưới mức k. Nghĩa là, mỗi cây con ở cấp độ k sẽ có bốn cha mẹ. (Tôi đã không nghĩ về điều này đủ để biết nếu điều này hoàn toàn hoạt động, sẽ chỉnh sửa câu trả lời nếu tôi tìm thấy nó không.)

Answer 3

Cấu trúc dữ liệu không phải thay đổi, nhưng thủ tục tìm kiếm. Biểu thị mỗi điểm theo tọa độ (x, y) trong [0, w) * [0, h), trong đó w là chiều rộng của bản đồ, h là chiều cao và * biểu thị một sản phẩm Descartes. Lưu trữ những điểm này trong một cây KD bình thường.

Nguyên thủy cơ bản để tìm kiếm cây KD, được cho điểm (x, y) và hình chữ nhật [a, b] * [c, d], xác định khoảng cách (bình phương) từ điểm đến hình chữ nhật. Thông thường đây là g (x, a, b) + g (y, c, d) , nơi

g(z, e, f) = e - z if z < e 
      0  if e <= z <= f 
      z - f if f < z 

là khoảng cách một chiều của z để [e, f]. Trong một không gian hình xuyến, chúng ta sửa đổi g một chút để giải thích cho sự bao bọc.

g(z, e, f, v) = min(e - z, (z + v) - f) if z < e 
       0      if e < z < f 
       min(z - f, (e + v) - z) if f < z. 

và khoảng cách bình phương là g (x, a, b, w) + g (y, c, d, h) . Tôi hy vọng rằng thời gian chạy sẽ được so sánh với biến thể này.(Tôi muốn làm lại các trường hợp tái phát, nhưng trường hợp xấu nhất đối với cây KD thông thường tệ hơn nhiều so với thực hành hầu hết thời gian - O (n ^1/2) để xác định hàng xóm gần nhất ở dạng 2D trong số n điểm.)