I'm currently writing a web application for creating and manipulating graphs (in the graph theory sense, not charts). For this, I want to implement a number of "arrange as ..." functions that take the selected vertices and arrange them into certain shapes (you can ignore the edges).
Now writing simple algorithms to arrange the vertices into a grid or circle is trivial. What I want to do though is to find a general algorithm for taking n actual vertex coordinates and n destination vertex coordinates, and finding an optimal (or near optimal) mapping from the former to the latter so that the sum or average (whichever is easiest) of distances the vertices need to be moved is minimized. The idea is that these functions should mostly just "clean up" an existing arrangement without fundamentally altering relative positions if the vertices are somewhat similar to the desired arrangement already.
For example, if I have 12 vertices arranged in a rough circle, labeled 1-12 like the hours on a clock, I would like my "arrange as circle" algorithm to snap them to a perfect circle with the same ordering 1-12 like the hours on a clock. If I have 25 vertices arranged in a rough 5x5 grid, I would like my "arrange as grid" algorithm to snap them to a perfect 5x5 grid with the same ordering.
Of course I could theoretically use a generalized constraints-optimization / hill-climbing algorithm or brute-force the permutation, but both are too inefficient to perform client-side in the browser. Is there a more specific, known method for finding good "low-energy" 1:1 mappings between lists of 2d coordinates?
This is known as the assignment problem. Or more specifically, the linear assignment problem (since the number of objects and destinations are the same). There are various algorithms to solve it. Most notably, the Hungarian algorithm.
See https://en.wikipedia.org/wiki/Assignment_problem
Your cost function C(i,j) will be simply
C(i,j) = distance between points i and j
Where the i points are your current locations and the j points are your destination locations.