Vector of random ofVec2fs - best way to find element closest to mouse?

beginners
#1

Hi - the title says most of it. This may be more intermediate than beginner? Kind of a general C++ question more than just oF.

I have a pre-defined vector of > 5000 random ofVec2f 2d points in screen space.
Out of that vector I want to find the element closest to mouse x,y (or any given screen coords) at every frame.
I’m trying to find the most elegant/accurate/quickest solution - that could work with say, a vector of 300,000 elements as well as with 5000.

I can pre-sort the vector during setup() since it won’t really change (or I can insert new elements in the correct order if it does) - so I can use binary search for speed…

What I have now:

So far I have code that pre-sorts the vector by distance from (0,0) during setup().

  1. During update() it uses a binary search to find the upper_bound element with distance to (0,0) closest to the mouse’s distance to 0,0.

  2. Then it finds 50 elements on either side of that element, and copies the resulting 101 elements to a new temporary vector.

  3. Then it sorts that small vector by distance to mouse x,y - and index [0] of that vector is the result.

It’s quite fast and works fairly well but since it’s sorting by radial distance to 0,0 it doesn’t always get the actual closest point - it prefers points along the radius of mouse’s distance to 0,0.

Anyone have a better way to get faster/more accurate results?

Thanks!

Here’s my search function:

ofVec2f mouse(ofGetMouseX(),ofGetMouseY());

vector<ofVec2f>::iterator it =
	upper_bound(posVector.begin(), posVector.end(), mouse, DistComp(ofVec2f(0,0)));
 		// DistComp is custom binary operator that sorts vector by distance to a given ofVec2f


// grab 101 items for new vector
int index = it - posVector.begin(); // index of search result
int dFirst = 50; // distance to first index
int dLast = 50; // distance to last index

// fix if index is too close to beginning or end of vector
if (index < 50){
    dFirst = index;
    dLast = 100 - dFirst;
}
else if (index + 50 >= eyePositionsOrdered.size()){
    dLast = (int)eyePositionsOrdered.size()-1 - index;
    dFirst = 100 - dLast;
}

vector<ofVec2f>::iterator fIt = it-dFirst; // first iterator
vector<ofVec2f>::iterator lIt = it+dLast; // last iterator

vector<ofVec2f> tmpVec(101); // temporary vector
vector<ofVec2f>::iterator tmpIt = tmpVec.begin(); // iterator for copy position

copy(fIt,lIt, tmpIt); // copy into temp vector

sort(tmpVec.begin(),tmpVec.end(),DistComp(mouse)); // sort by distance to mouse

return tmpVec[0]; // closest ofVec2f to mouse (sort of...)`