POINT findNearestPnt(vector <POINT*> v, int mouse_x, int mouse_y) {
// Post: Finds & returns the nearest point in vector v to the mouse position
// This algorithm searches EVERY elements of v to find the closest pnt which isn't very
// efficient do you know of a faster way to do what I am trying to do?
POINT nearestPoint;
int dist = INT_MAX;
for (int i=0; i<v.size(); i++) {
POINT* tempP = v.at(i);
int myDist = pointDistance(tempP->x,tempP->y,mouse_x,mouse_y); // finds distance tween pnts
if (myDist < dist) {
dist = myDist;
nearestPnt.x = tempP->x;
nearestPnt.y = tempP->y;
}
}
return nearestPnt; // return closest pnt to mouse position
}
Fast & Efficient Way to Find Closest Pnt
Author
Hello
I am trying to write/find a fast & efficient way to find the closest POINT to the mouse position in my graph application. I have an iterative method but to me it seems too inefficient & will be slow for lrg numbers.
I have thought of a binary search but I am not sure it will work when I am trying to find the Closest Point to the mouse position, I know it will work if I am searching to see if the Exact Mouse Point is in the vector but not for what I am trying to do.
Any suggestions for a fast way to do what I am doing?
Here is my iterative method & the POINTS stored in the vector are not sorted or anything either:
This is known as Nearest Neighbor search. Standard approach is a kD-tree, which takes O(n log n) time to build the structure, and O(log n) to query. If you cannot build a structure ahead of time, but have points sorted along an axis, you can use binary search to find an initial guess, and then use that guess as a bound on the interval to linearly search.
Author
Thanks, do I need a special library to use a NNS or is it like a binary search where I just write it myself or use algorithm library?
Any other suggestions of searching methods would be helpful also :)
Any other suggestions of searching methods would be helpful also :)
Since this is in 2d it is really overkill to use a tree. You should be able to get a bounds for the graph and calculate an offset into it. If you don't have the points in any sort of order, well, you're going to have to for any algorithm you use.
Quote:Original post by gretty
Since this is in 2d it is really overkill to use a tree.
Heh, what? Spatial partitioning trees are intended specifically for, and only useful in, lower-dimensional situations. (Once you get into the hundreds of dimensions, they don't work so well.)
Quote:Original post by thatguyfromthething
Since this is in 2d it is really overkill to use a tree. You should be able to get a bounds for the graph and calculate an offset into it. If you don't have the points in any sort of order, well, you're going to have to for any algorithm you use.
It's not overkill if the OP is talking about a large number of points.
Quote:Original post by SneftelQuote:Original post by gretty
Since this is in 2d it is really overkill to use a tree.
Heh, what? Spatial partitioning trees are intended specifically for, and only useful in, lower-dimensional situations. (Once you get into the hundreds of dimensions, they don't work so well.)
A tree requires sorting; it could even be called a sorting. So why not just sort in the first place and avoid need for a tree? If it is dynamic somehow, like it rotates on the screen, a tree is necessary. If not it's overkill.
Quote:Original post by jwezorek
It's not overkill if the OP is talking about a large number of points.
It's actually more overkill, because then you have a tree with a large number of branches.
If this is a simple 2d object drawn on the screen that doesn't rotate, really it's unnecessary. I find it hard to even see how someone could wind up with a bunch of random 'points' that stored unordered in a vector. But maybe I am misreading problem or it was misstated.
Quote:Original post by thatguyfromthethingSorting doesn't address the problem. A sorted list of points will be sorted along one dimension, allowing you to find the closest point to a given point along that dimension, but that's not what the OP was asking for.
A tree requires sorting; it could even be called a sorting. So why not just sort in the first place and avoid need for a tree? If it is dynamic somehow, like it rotates on the screen, a tree is necessary. If not it's overkill.
You should take a look at this article and see how a spatial partitioning tree differs from a linear sorting.
[Edited by - Sneftel on February 11, 2010 8:16:43 PM]
Quote:Original post by SneftelQuote:Original post by thatguyfromthethingSorting doesn't address the problem. A sorted list of points will be sorted along one dimension, allowing you to find the closest point to a given point along that dimension, but that's not what the OP was asking for.
A tree requires sorting; it could even be called a sorting. So why not just sort in the first place and avoid need for a tree? If it is dynamic somehow, like it rotates on the screen, a tree is necessary. If not it's overkill.
You should take a look at this article and see how a spatial partitioning tree differs from a linear sorting.
I have some idea of nearest neighbor problem and trees already (pretend for a minute I once wrote some graphics processing app or something). For sorting you have a concept of postman's sort and index.
For a 2d object this is the natural way to store things anyway, in an array/bitmap/array of arrays/whatever. Like say if you have a bar graph (maybe for a graphing app). It's even kind of hard to wind up with something else to start with, or so I'd think.
I guess for pie chart it might seem wasteful but that's how it is done in say like a picture or something, or any kind of 2d anything that makes much sense. Which is why I wonder about the vector of points thing. Not that I'm judging, and maybe there's some good reason for that.
But anyway it's like a big array. So once it's sorted you just look up the answer directly. If it's a pie chart instead of a bar graph, you probably seeth in rage at the very idea of the wasted array space but the array might have something crazy like run length encoding to deal with that, and it's still an order of magnitude less resource intensive than 99% of all tree implementations.
In fact this works pretty good for 3d, too, and will work quickly on meshes that would be impossible to put in a standard tree due to sheer size. But the problem is when you change perspectives. Then you need to have something like a tree to deal with that.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
