CODEWITHSUNDEEP
performancegraphicsdata-structuresdistancepoint
jmacedo
jmacedo

Reputation: 783

Finding closest points to given coordinates - data structure

What is a good data structure to keep a collection of 2d points so that later I can call a method like collection.pointsCloserThanDistance(float d, float[] coordinates) efficiently? - This method would return a list in which every point's distance to the given coordinates is less or equal to d.

(Also how would be the implementation of that method?)

The simplest and probably not so good solution would be a standard array, and then compare every point with the given coordinates .This is O(n), n = number of points. But it might be possible to have O(m), m = number of points whose distance to given coordinates is less or equal to the given value.

Upvotes: 0

Views: 985

Answers (1)

Petar Ivanov
Petar Ivanov

Reputation: 93030

You need a "space-partitioning" data structure like a k-d tree.

Upvotes: 4

Related Questions