Efficient way to search through points

[kimt]

Hello, I am currently writing an application that involves many (>
1000) points on a (x,y) plane. I am using a struct to contain the
position information, and I have the structs contained in a STL
vector. Given a target coordinate (x,y)_t, I would like to be able to
cycle through the vector of points in order to obtain the closest
point. What would be the most efficient way to implement this?

I have considered keeping the vector sorted by the coordinates, say,
by the x-coordinate and the y-coordinate and to "home-in" on the point
by two successive filters. However, my memory of the STL is not so
great and I would very much appreciate some pointers in implementing
this idea.

Furthermore, it seems like this approach may not always yield the
point that is closest to the point.

Thank you in advance

[Victor Bazarov]

ki**@mit.edu wrote:

Hello, I am currently writing an application that involves many (>
1000) points on a (x,y) plane. I am using a struct to contain the
position information, and I have the structs contained in a STL
vector. Given a target coordinate (x,y)_t, I would like to be able to
cycle through the vector of points in order to obtain the closest
point. What would be the most efficient way to implement this?

Partition your points. Partition searches are the fastest.

I have considered keeping the vector sorted by the coordinates, say,
by the x-coordinate and the y-coordinate and to "home-in" on the point
by two successive filters. However, my memory of the STL is not so
great and I would very much appreciate some pointers in implementing
this idea.

If that's what you want...

All you need is a way to compare two points to put them in order.
Write a function taking two points and returning a bool. It would
return 'true' if the first argument is "less" than the second one.
Whatever "less" means to you. Then pass this function as the third
argument of 'std::sort'. I am sure you could use some decent book
on standard library as well. Try "The C++ Standard Library" by
Josuttis.

Furthermore, it seems like this approach may not always yield the
point that is closest to the point.

I think you need a decent book on graphical algorithms. Finding the
nearest point from a collection of points can be better than N*N.
Read about Kd-trees.

V
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask