Math puzzle for module arrangement algorithm


(Andrew Belt) #1

Here’s a fun 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 its closest point (x_1, y_1) having integer coordinates, using Euclidean distance. That’s easy, just round the coordinates. Then compute the second closest point (x_2, y_2), 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.