grid point algorithm (finding the point in grid)

Question

I am searching for an algorithm such as the closest pair of points algorithm

Instead of an arbitrary distance between all of the points, I have a grid system set up with the 4 points being the top-right, bottom-right, top-left, and bottom-left respectively. This keeps the distance between all the points constant.

say for example if I were to put an outside point on this grid, I need to find which grid square it would be in, assuming by finding the closest 4 points (giving me the end points of the grid square).

I was going to implement the algorithm for closest points, but since the points are all the same distance away from each other all the time I didn't know if this would merit a different more efficient algorithm.

I don't really need a detailed explanation of the answer, just a point in the right direction.

Answer 1

I assume this is in 2 dimensions? Very simply, you could do this -- I used a similar technique to quickly optimize spatial clustering in a large scale data mining project.

Divide your coordinate space into a fixed number of grid lines in the X and Y directions (which it seems you have already done, by equally spacing these 4 points).

When you insert a point, divide its distance (integer division) from the origin in the X and Y direction by your grid step interval. Then you're left with two coordinates that identify the nearest X/Y grid intersection. Use the remainder to establish which side of the grid intersection your point belongs in.

If you want to get really complicated you could start using kD-Trees, etc... but I think this example is simple enough not to warrant any more complicated spatial partitioning.