Find closest point to mouse from (huge, but static) vector of ofVec2f?

beginners
#1

I’m wondering what the best way would be to search a huge vector (say… 300,000+ elements)
to find the closest ofVec2f to my mouse pos?

I’ve tried pre-sorting the vector by distance to (0,0) in setup() and using binary search to find the closest point -
it sort of works, but prefers points that resemble the mouse’s distance to (0,0), not necessarily choosing the closest point.

Is there a better (fast + accurate) way?

Here’s my binary search code, which searches first by comparing distance of mouse to (0,0) to distance of each vector element to (0,0), then sorting a smaller 100-element temp vector by distance to mouse.

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...)
#2

Hi, you should try some sort of binned search.
try this addon.
works really well.

best

#3

Wow - perfecto. Thanks!