Given a set of two sets of points in two dimensions, is there an algorithm that matches the members of set 1 to the same number of coordinate pairs on set 2 with the following conditions:
- Along the continuous, direct, and evenly taken (like an animation tween) paths with which the points are transformed to their new coordinates, collisions (and near collisions) are avoided
- The distance between a point’s set 1 (leftmost graph in Figure 1) coordinates and set 2 (rightmost graph in Figure 1) coordinates average similar lengths
To put it another way, there are some (N) number of points that are graphed in two dimensions. Another set of N points are graphed a future plot. Can I algorithmically assign points from set 1 to to set 2 to fulfill the previous constraints?
I’ve provided a visual example as this may be a pretty abstract problem and I’m 90% sure I don’t even know what domain of problem solving I need to look at. My “answer” of plotting the points A’, B’, C’, and D’ in their given assignments, rather than some other arrangement, is from a sort of trial and error; essentially animating the points to find a nice transition from set 1 to set 2. Notice how in the middle diagram, I’ve roughly plotted the points in between their sets to show that the correct result (diagram on the right) is a valid answer because the closest transit of the points along a continuous line from set 1 to set 2 is not very close (doesn’t approximate a collision). Helpful answers would either include a known algorithm or an area of math to further my studies.
Edit: To help add some clarity, here are a few points:
- The coordinates in set 2 are take as inputs to the problem, but I would not know in advance which points on the left move to which on the right (this is what the algorithm would suggest as answers)
- the movement happens uniformly from set 1 to set 2 (like an animation on a time series) and the collisions would be checked at some discreet interval along the time series (does not have to be continuous)
- Yes I could put this all into a program which allows me to move or animate along the time series and manually check for collisions, but this is what the algorithm I'm imagining would automate
shows the input state, one possible incorrect output of the algorithm, and one possible correct output of the algorithm
Link to Figure 1 because apparently my stackoverflow reputation doesn't transfer.
