Нахождение подмножества точек по относительным расстояниям

Question

Я пишу игру, в которой игрок может манипулировать множеством объектов одновременно.Я бы хотел, чтобы игрок мог выбирать объекты в соответствии с расстояниями между ними.

Учитывая местоположение всех объектов, начальный объект и порог расстояния, какой самый быстрый способ найти подмножество, содержащее исходный объект, для которого расстояние между любыми двумя объектами не превышает пороговое значение?Эвристические решения вполне приемлемы.

Answer 1

Эта библиотека , кажется, делает свое дело:

"ANN - это библиотека, написанная на языке программирования C ++ для поддержки как точного, так и приблизительного поиска ближайшего соседа в пространствах различных измерений.

[...]

В задаче о ближайшем соседе задан набор точек данных P в d-мерном пространстве. Эти точки предварительно обрабатываются в структуру данных, так что для любой точки запросаq, о ближайших (или вообще k ближайших) точках от P до q можно сообщать эффективно. "

Answer 2

Зависит от вашей структуры данных. Прежде всего, ваши объекты уже отсортированы / разделены по расстоянию? Я не могу думать о какой-либо эвристической дистанции ... но вы могли бы сделать это параллельно, что должно помочь.