Thuật toán cho Octree để tìm kiếm hàng xóm gần nhất

Question

Báo cáo vấn đề: Để tìm ID GRID gần nhất của từng hạt bằng Octree.

Hình [1]:

hình [2]:

tôi có một hệ thống của các hạt (~ 6k, di chuyển) mà tôi cần phải kiểm tra thời điểm đó lưới (cứng nhắc; trong ảnh) là gần nhất. Ai đó đã đề nghị tôi đi cho Octree vì nó là nhanh (est) cho lưới 3D.

Đây có phải là Thuật toán chính xác cho Octree đệ quy để có được điểm lưới gần nhất của lưới không?

1. Nhận một đầu vào như điểm P Bắt đầu phối hợp C (lần đầu tiên nó [0,0,0])
2. Bắt đầu Kích thước = [Sx, Sy, Sz]
3. Nhận tất cả 8 điểm giữa Mi = {M1, .., M8} nhận khoảng cách tối thiểu của Mi và P

4. Giả sử M có được vị trí bắt đầu của M là kích thước thiết lập Cn Sn = [Sx/8, Sy/8, Sz/8]

5. nếu khoảng cách của M và P nhỏ hơn 2 * (Lưới Space G):

   5.1. Lặp lại tất cả các điểm lưới từ Cn đến Sn

   5.2. In ít nhất là kết quả

6. khác

   6,1. đặt Bắt đầu tọa độ dưới dạng Cn

   6.2. đặt Kích thước là Sn

   6.3. Goto 1

Vấn đề: Sự lặp cuối cùng ăn tất cả tốc độ nếu hạt được ra ngoài hoặc gần trên biên giới vì nó kiểm tra tất cả A x B x C.

Xin gợi ý nếu bạn có một cách tốt hơn để giải quyết vấn đề này.

Answer 1

Không cần sử dụng chữ octree tại đây. Octree là hữu ích cho vấn đề ngược lại (được đưa ra một điểm lưới, tìm các hạt gần nhất) nhưng hoàn toàn vô dụng ở đây.

Giả sử kích thước ô lưới là (a, b, c), thì điểm lưới gần nhất từ ​​(x, y, z) là (a*floor(x/a+0.5), b*floor(y/b+0.5), c*floor(z/c+0.5)).