In general, if we scope the problem to find the nearest nearby point in N-Space with some upper bound defining 'nearby' we can create a shell at radius r and do a binary search to find points and keep cutting in half till we find matches and redo binary search inside the new upper bound till we exhaust a given search space making a sphere.
If you are in a game though, have a canvas and have the points defined in memory it'd be better to either do a linear search any time, or do some kind of sorting from frame to frame that isn't expensive every sort (ie the sort order from origin doesnt change much from frame to frame so re-sorting each frame is fast and you can prune the list) - if sorted the nearest point is instant lookup. Otherwise if the camera can 'jump' around, a linear search each time will probably yield the best performance because it will be too slow to sort each time. Scanning radially out seems waateful if you are rendering the points anyway and have their coords in memory somewhere.
How’s it going, I'm a Adam, a Full-Stack Engineer, actively searching for work. I'm all about JavaScript. And Frontend but don't let that fool you - I've also got some serious Backend skills.
Location
City of Bath, UK 🇬🇧
Education
10 plus years* active enterprise development experience and a Fine art degree 🎨
So I should mention in my implimentation I'm using a kdTree and although the dots are randomly placed, for each random point there will be a dot placed anywhere within a radius of 100 from that point. This gives me a garentee that my search should do no more than 10 steps to find a point, the desert the plot the more efficient it should be. However I agree it's wasteful, I will look at what your suggesting in greater detail and see if I can change my method.
For further actions, you may consider blocking this person and/or reporting abuse
We're a place where coders share, stay up-to-date and grow their careers.
In general, if we scope the problem to find the nearest nearby point in N-Space with some upper bound defining 'nearby' we can create a shell at radius r and do a binary search to find points and keep cutting in half till we find matches and redo binary search inside the new upper bound till we exhaust a given search space making a sphere.
If you are in a game though, have a canvas and have the points defined in memory it'd be better to either do a linear search any time, or do some kind of sorting from frame to frame that isn't expensive every sort (ie the sort order from origin doesnt change much from frame to frame so re-sorting each frame is fast and you can prune the list) - if sorted the nearest point is instant lookup. Otherwise if the camera can 'jump' around, a linear search each time will probably yield the best performance because it will be too slow to sort each time. Scanning radially out seems waateful if you are rendering the points anyway and have their coords in memory somewhere.
So I should mention in my implimentation I'm using a kdTree and although the dots are randomly placed, for each random point there will be a dot placed anywhere within a radius of 100 from that point. This gives me a garentee that my search should do no more than 10 steps to find a point, the desert the plot the more efficient it should be. However I agree it's wasteful, I will look at what your suggesting in greater detail and see if I can change my method.