通过相对距离查找点的子集
我正在编写一款游戏，玩家可以同时操纵大量物体。我希望玩家能够根据对象之间的距离来选择对象。
给定所有对象的位置、起始对象和距离阈值，找到包含起始对象且任意两个对象之间的距离不超过阈值的子集的最快方法是什么？启发式解决方案是完全可以接受的。
I'm writing a game in which the player may manipulate a great many objects at one time. I would like the player to be able to select objects according to the distances between them.
Given the locations of all objects, a starting object, and a distance threshold, what is the fastest way to find the subset containing the starting object for which the distance between any two objects does not exceed the threshold? Heuristic solutions are perfectly acceptable.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
这个库似乎可以解决这个问题：
“ANN是用 C++ 编程语言编写的库，支持各种维度空间中的精确和近似最近邻搜索
[...]
在最近邻问题中，给出了 d 维空间中的一组数据点。预处理成数据结构，以便给定任何查询点 q，可以有效地报告 P 到 q 的最近（或通常 k 个最近）点。”
This library seems to do the trick:
"ANN is a library written in the C++ programming language to support both exact and approximate nearest neighbor searching in spaces of various dimensions.
[...]
In the nearest neighbor problem a set P of data points in d-dimensional space is given. These points are preprocessed into a data structure, so that given any query point q, the nearest (or generally k nearest) points of P to q can be reported efficiently."
取决于你的数据结构。首先，您的对象是否已按距离排序/分区？我想不出任何距离启发式......但你当然可以并行执行此操作，这应该会有所帮助。
Depends on your data structure. Primarily, are your objects already sorted / partitioned by distance? I can't think of any distance heuristic... but you could certainly do this in parallel which should help.