Tôi muốn làm một số mô phỏng đổ xô, như mô tả here.2D tìm kiếm lân cận gần nhất cho các điểm di chuyển
Đối với điều này, tôi cần phải tìm kiếm những người hàng xóm gần nhất của mỗi điểm 2D của tôi. Tuy nhiên, tôi không thể sử dụng cấu trúc dữ liệu tĩnh như cây k-d vì các điểm luôn di chuyển ...
Cơ sở hạ tầng/thư viện tốt (dễ) có thể đạt được điều này là gì? Tôi đang làm việc với C++ ...
Có thể bạn muốn thử một chỉ số quadtree hoặc không gian? Vấn đề với cây k-d là gì? Về cơ bản khi có các cạnh đàn/điểm bạn có thể bỏ qua kiểm tra va chạm với các cạnh xa. Một chỉ số không gian có thể là cây quadtree, r-tree, kd-tree hoặc hilbert r-tree. Một câu trả lời hay hơn có thể được đọc ở đây: Approximate, incremental nearest-neighbour algorithm for moving bodies
"Đó là, phân tích đệ quy" thế giới "thành một biểu đồ với bốn mã con mỗi. Cây có thể nhanh chóng kiểm tra xem đối tượng nào nằm trong một ô vuông cụ thể trên thế giới và loại bỏ Một kỹ thuật culling rất hiệu quả thường được sử dụng để cải thiện hiệu suất phát hiện va chạm trong trò chơi. "
Không phải là cây kd (hoặc một quadtree, cho vấn đề đó) tĩnh? Có nghĩa là bạn phải xây dựng lại nó trong mỗi bước, sau khi tất cả các điểm đã di chuyển? –
Ý tưởng về quadtree là giảm độ phức tạp 2d thành độ phức tạp 1d. Khi bạn recursivley đi qua cây sâu đầu tiên hoặc bề rộng đầu tiên nó trở thành một nhiệm vụ đơn giản để điền vào cây đầy đủ? – Bytemain
Tôi đoán một quadtree sẽ làm việc, loại. Tuy nhiên, việc lặp lại qua tất cả các nước láng giềng dường như đủ nhanh cho tôi ... –
Mọi người có studied vấn đề này. Từ khóa quan trọng là động lực, khi tìm kiếm công việc trong ares này.
Bạn có thể nhận được một số ý tưởng từ http://stackoverflow.com/questions/6871682/approximate-nearest-neighbour-algorithm-for-moving-bodies –