Here’s a math/programming problem if anyone’s in to that, with a potential application in cleaning up VCV Rack module arrangement code.
Given two real coordinates x and y, compute the closest point (x_1, y_1) having integer coordinates to (x, y), using Euclidean distance. That’s easy, just round the coordinates. Then compute the second closest point (x_2, y_2) to (x, y), and so on. If multiple points are a tie, the order between them doesn’t matter.
I haven’t done any research on this, but I imagine it’s possible to come up with a constant-time generator algorithm.
I don’t think that’s it because the Hilbert curve is a connected path. My desired list of points is definitely not connected, because the 107th closest point from (x,y) might be to the top-left of it by 10.1 distance units, and the 108th might be to the bottom-right by 10.2.
My friend mentioned that Dijkstra’s algorithm solves this in O(\log d) per generated vector where d is the distance from that vector. Start with (\operatorname{round}(x), \operatorname{round}(y)), and add the 8 surrounding (or maybe just 4 surrounding) vectors to a priority queue, with the distance away from (x, y) as their priority. Pop the lowest priority vector (x_n, y_n) off the queue, and repeat.
That’s definitely good enough for this application, but there still might be a more direct method.
