Find the closest point in a point cloud in a near equivalent point cloud

Question

I'm having a hard time wrapping my head around an algorithm, and not really sure if such a problem is known, common and possibly named, or if this is somewhat unique.

I have 2 different clouds of points (2D). I need to generate an index map from one to the other by proximity. Points that are closest should map to each other. This part isn't that hard.

The hard part is that each "to" point should only be used by one "from" point.

For example, let's say these are my "from" points: ([x, y] // index)

[
  [1, 10],  // 0
  [10, 10], // 1
  [19, 10], // 2
]

And these are my "to" points:

[
  [11, 10], // 0
  [9, 10],  // 1
  [10, 10], // 2
]

Then I would expect the following index mapping (fromIndex: toIndex)

{
  0: 1, // [1,10] -> [9,10]
  1: 2, // [10,10 -> [10,10]
  2: 0, // [19,10] -> [11,10]
}

In this example, all three new points are closest to [10,10], but...

• The new point [10,10] (index 2) is zero distance from to old point [10,10] (index 1), so it just be assigned that index.
• The new point [11,10] (index 0) is 1 distance to the old point [10,10] (index 1), and 8 distance from the old point [19,10] (index 2). index 1 is closest, but since another point is closer, the second closest point is chosen (index 2).

Finding the closest point is easy, but how would I go about finding the closest point that doesn't also have another point that's even closer, and so it should find the next closest point, which also doesn't have another point closer to that, and if does find the next closest point which... (did I go recursive?)

And obviously this would be run on point clouds of large number (up to about a max of about 50,000 at the moment)

How would I go about developing this algorithm?

Answer 1

This problem is known as Euclidean minimum cost perfect matching, I have linked a survey by Sayan Bhattacharya that contains various references to algorithms, both exact and approximations.

If you wish to solve this problem for $n \approx 50000$, I would skip the exact solutions entirely and go straight to the approximations.

Answer 2

I was able to come up with a solution, and I don't claim that it is good or fast, but it does seem to work:

1. Find the indices of the closest points in the two clouds, ignoring any invalid solutions. There will be some points that are referenced multiple times in this data.
2. Find all pairs that share the same destination indices and lock in the closest one of those.
3. Add the rest of the pairs to a set of invalid solutions.
4. Find the closest points again, ignoring any pairs previously marked invalid.
5. Repeat until each destination index is only used once.