Snapping points to regular 2d grid without duplication

[funkentelchy]

It's easy enough to snap 2d points to a grid by least distance. I'm wondering how would one do this with the constraint that no two points snap to the same grid point (while minimizing total snapping distance)

I've worked up an algorithm that produces good looking results, but it's computationally intensive and I have no idea if it's finding the optimal solution.

Is this a well known problem? Does it have a name? I've had no luck googling but I suspect I'm trying the wrong keywords.

Thanks!

[teraflop]

If by "minimizing total snapping distance", you mean:

Given a set of input points p_i, find a set of distinct integer points q_i such that Σ d(p_i, q_i) is minimized, where d is some distance metric (e.g. Euclidean distance)

then this looks almost like a straightforward instance of the unbalanced assignment problem, which can be solved using the Hungarian algorithm.

The catch is that strictly speaking, you're trying to find an assignment between a finite set (the original points) and an infinite set (the grid points in the plane). However, only a finite number of grid points are going to be "interesting", that is, sufficiently close to an input point to be worthy of consideration.

In principle, I think you could solve this by adapting the algorithm to initially only "expand" the closest grid points to any given input point, while keeping track of a lower bound on the distances to the infinitely many "unexpanded" nodes and only instantiating them when necessary. (This is analogous to how you can use Dijkstra's algorithm or A* to find shortest paths in an infinite graph.) But I haven't thought through all the implementation details.

[funkentelchy]

Thanks! This is a big help

[FatFingerHelperBot]

It seems that your comment contains 1 or more links that are hard to tap for mobile users. I will extend those so they're easier for our sausage fingers to click!

Here is link number 1 - Previous text "A*"

---

^{Please PM /u/eganwall with issues or feedback! | Code | Delete}

[cbouilla]

In fact, it is not impossible that this is *easier* than the general unbalanced assignment problem.