CODEWITHSUNDEEP
c#searchnearest-neighbor
Tim
Tim

Reputation: 101

Find nearest Vector2(x,y) in collection

I have a bool[,], and given an input Vector2(x,y), I want to find the indices of the nearest true. I can naively loop through the 2d array and check the distances to the input, but that'll give me a runtime of O(LxW). I'm wondering if there's any faster way of finding the nearest than O(LxW). I'm open to adding all the true coordinates in a Hashset<Vector2> or a sorted List<Vector2> or any other type of collection, if it'll net a quicker lookup.

Performance is more critical than code readability here.

Example:

T, T, F
T, F, T
T, T, T

GetNearestTrue(new Vector2(2, 3)) // returns (1, 2)
GetNearestTrue(new Vector2(1, 1)) // returns (0, 1) or (1, 0) or (1, 2) or (2, 1), since they're equidistant it doesn't matter

Upvotes: 0

Views: 1112

Answers (2)

TilmannZ
TilmannZ

Reputation: 1889

If you you have a significant number of 'false', then there is a faster way. You can optimize from O(L*W)=O(nFalse + nTrue) to about O(log nTrue).

You can use a multidim-index (quadtree, kd-tree, R-Plus-Tree, PH-Tree) and insert for every 'true' at (x,y) a point into the multi-dim index with coordinates (x,y). Now, to find the nearest 'true' for a point 'p', you just do a nearest-neighbor search in the index for point 'p'. For example, this says that there is an algorithm "that claims guaranteed O(log n) complexity."

While kd-tree is possibly the simplest (see here for Java implementation for many indexes), the PH-Tree may make sense because it can work directly with integers as coordinate, rather than floating point values. However, I'm not aware of a C# version of the PH-Tree.

Upvotes: 2

Steve
Steve

Reputation: 11963

if there's any faster way of finding the nearest than O(LxW)?

If the L and W are length and width for the 2d array respectively then the answer is no.

Simple proof: Imagine you have to prove that there is no nearest true in the grid. I.E. the grid consists only false. You can never say there is none until you have visited every single cell of the grid. Which means the run time will always be at least O(LxW).

In order to prove the node (x, y) is the nearest to (a, b) you must prove that there consists only false in the circle around (a,b) with radius |Max(x-a, y-b)| And in the worst case the radius will be the Max(L, W) which makes the worst case run time O(LxW)

Though you could do some optimization by doing a BFS from the center, this will reduce the runtime by some factors but the worse case stays the same.

Upvotes: 1

Related Questions