CODEWITHSUNDEEP
c++optimizationsearchspatial
Jon Purdy
Jon Purdy

Reputation: 55069

Finding a Subset of Points by Relative Distances

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.

Upvotes: 1

Views: 191

Answers (2)

Alejandro
Alejandro

Reputation: 1044

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."

Upvotes: 1

matt-dot-net
matt-dot-net

Reputation: 4244

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.

Upvotes: 0

Related Questions