Khi nào sử dụng Kd-Trees?

Question

Tôi đã đọc về Kd-Trees ngày hôm trước và tôi đang tìm kiếm một tình huống cụ thể/đơn giản, nơi một cấu trúc dữ liệu như vậy có thể hữu ích.

Có ai có ví dụ như vậy không?

Xin cảm ơn,

Answer 1

Tôi đã sử dụng chúng như một cách hiệu quả để tìm những người hàng xóm gần nhất của một điểm nhất định cho học máy.

Answer 2

Chúng được sử dụng để tạo khung cảnh để chia nhỏ cảnh thành một vài ô. Nó tăng tốc độ va chạm bởi vì nếu một tia không va chạm với hộp giới hạn, nó chắc chắn không va chạm với nội dung của nó.

Answer 3

VTK có một: http://www.vtk.org/doc/nightly/html/classvtkKdTree.html để biết ví dụ.

Hãy xem các chức năng như "FindClosestPoint". Lớp học mất một thời gian tương đối dài để xây dựng một tập hợp lớn các điểm đầu vào. Nhưng sau khi cây được xây dựng, các chức năng như thế này chạy rất nhanh.

Answer 4

Tôi đã sử dụng chúng trong một dự án định giá. Đối tượng là tìm giá tốt nhất phù hợp với nhiều tiêu chí.

Answer 5

Tôi đã sử dụng cây kd để mô phỏng vận chuyển ánh sáng thông qua phun được tạo ra bởi một wave. Điều này làm cho nó có thể làm cho các giọt phun không chỉ được chiếu sáng bằng đèn, mà còn chiếu sáng gián tiếp từ những giọt nhỏ khác. Tôi đã lưu trữ các điểm phun trong một cây kd và sau đó sử dụng cây kd để nhanh chóng tìm ra những điểm gần nhau, và do đó những giọt nước được chiếu sáng bởi nhau. (Trên thực tế, nó phức tạp hơn một chút, nhưng cấu trúc vẫn là một cây kd.) Điều này làm cho nó có thể tạo ra một ánh sáng đẹp thông qua phun. Đây là một hình ảnh của phương pháp được sử dụng. Không phải cách phun xung quanh ánh sáng phát ra ánh sáng phân tán.