Math puzzle for module arrangement algorithm


(Andrew Belt) #1

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.


(David O'Rourke) #2

The existing module arrangement algorithm is a little gnarly, but it does the job.

Is there a strong need for a better approach?


(Andrew Belt) #3

No, not really, but it’s an isolated problem that I can’t think of a solution for.


(David O'Rourke) #4

:grin:


(Adrian Likins) #5

Could a 2D Hilbert curve work? Something like d2xy() from the examples at https://en.wikipedia.org/wiki/Hilbert_curve#Applications_and_mapping_algorithms .


(Andrew Belt) #6

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.


(Andrew Belt) #7

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.