When I was growing up I loved to draw dot to dots, now that I'm older, I just draw more complex ones.
I'm delving into procedural generation, so picture the scene you have 20 dots randomly placed across a canvas, how can you find the nearest neighbor? Simple you might think, a simple sort of an array from smallest X to largest then for a given point you could find the index next to that point, in 1D space that would work yep but now add a Y axis. A closest point could have a similar Y and a larger X. So I got to thinking about this problem, how about a Radial search?
If I plan to have a dynamic scene of points that could be added to and removed from view by moving a camera around, it's not going to be possible to index everything and retain good performance I need to look at a given point and search outwards until I find a neighbor. The plan then is to draw a line connecting the points symbolically and physically. Point A knows about Point B and Point B knows about Point A, this is so we can skip both points and find Point C when Point B is found. The goal is to create a bunch of teselating triangles.
Is my idea horrible, how would you solve it?
Top comments (6)
The perfect method to compare distance between points is to calculate the euclidean distance between all of them, that is the square root of the sum squared differences between their X and Y components. However, if you just need to know which one is the nearest, you do not need to calculate the exact distance, but you could just compare the squared sums. However, I think you really should calculate at least this to be certain about the results.
I'd say this is the most inefficient way to do this, but a way none the less, the goal would be to reduce the scope down to a few points, then use euclidian dist. The trouble with checking 10000 points is without scoping, that would be 10000 x 10000 checks. A KDTree helps solve this.
Ok, in that case you'd better calculate the taxicab distance, which is never lower than the euclidean distance to calculate the bounding box you need, and then compare distances of the points within that box
Thank you sir :)
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.