Algorithm design: Track moving points in 3D space

Question

This is a language agnostic question, more algorithm design oriented.

Imagine we have an two arrays of points in 3D space (each looks like [(1, 0, 2), (2, 4, 32), ...])

The first array represents the first state of the points and the second represents a later state where the points have shifted a small amount (not necessarily each by the same distance). Note: A few points could have been removed and some new ones added in the second state.

Problem: Given these two arrays, how could one match (to a reasonable degree of accuracy) each shifted point to its original point, while also identifying which points are new and did not exist in the first state?

---

Ideas: I was thinking that some sort of k-means clustering could be applied, but I'm not sure how it would handle the fact that some points could have been removed/added between the states - so I don't think that approach would work well.

---

Edit:

Points are not necessarily added at any particular place in the array and the order is not necessarily maintained for persisting points between states. The distance the points are shifted between states should be relatively small compared to the distance between unique points - otherwise this problem is basically impossible.

Answer 1

This rests on one assumption: The shift distance is very small (essentially a fuzzy measurement) compared to the distance between unique points between the first and second set.

First off, the general structure of a point set is not significantly affected by translation, rotation or scaling. This provides you with quite a few options.

Take the min/max for each dimension(x,y,z,etc). Translate and rescale the two point sets. The exact scaling doesn't matter, but you might go with it such that all points are positive and between 0 and 100 in every dimension. This allows you to compare the points more consistently. Although it may not be strictly needed and can likely be skipped

Then you should create a bidirectional mapping (a bidirectional graph) between point set A and point set B, which would be O(|A| + |B|) where |A| and |B| are the sizes of the sets. Example of bidirectional mapping: a_to_b[(1.001,2.001)] = [(1.005,1.995)] b_to_a[(1.005,1.995)] = [(1.001,2.001)]

If a_to_b and b_to_a map to each other, then that is the same point with relatively high probability.

If not, then you likely see something like this instead: a_to_b[(1.001,2.007)] = [(1.005,1.995)] b_to_a[(1.005,1.995)] = [(1.500, 2.004)]

a_to_b[(1.500, 2.004)] = [(1.495, 2.009)] b_to_a[(1.495, 2.009)] = [(1.500, 2.004)]

Since there is no longer a 1-1 mapping, it means something has been added or removed. Since the value in a was not mapped back, it was likely removed. In the opposite occurred, it was likely added. If it was added, you'll want to re-run the algorithm to try to determine what the original closest point was.

This can be verified by looking at the different point and seeing if it is part of a 1-1 mapping (and thus accounted for). Basically, you want to account for all of the 1-1 mapping points (which have high probabilities of being the same point), then try to sort out the points that don't match neatly

You may want to get the Delaunay triangulation for both point sets to allow for looking up the nearest neighbor of all points a lot faster due to knowing which points are spatially adjacent to a given point. The number of edges in a Delaunay graph if I recall right is O(V), so the average edge per vertices is O(1). Once you have found the nearest point. You may however need to do some tweaking of delaunary graphs to account for added/removed edges.

Answer 2

Match each point to it's nearest neighbor, unless the distance exceeds a threshold.

If you have more than one possible match, you need to devise a good resolution strategy.

Consider unmatched points as removed or added.

To make this faster, put a octree or a grid file on your data, so that you only need to test adjacent grid cells, rather than comparing every point with every other point.

Answer 3

Under the assumptions that:

1. Points may shift at random angle and length,
2. Points may randomly disappear,
3. Points may randomly be added and at random locations,
4. Points (in each array) are defined solely by their coordinates with no ID of any kind.

If all the above are correct, there is no solution that would provide a reasonable level of reliability.

I can add many examples that will substantiate my assertion, but it looks quite intuitive and hence are not really needed.

EDIT:

Following a discussion with Ted Hopp, I'm including an alternative approach based on two INSERTED CRITICAL assumptions:

1. The points move once and only once,
2. It is possible to state that the minimal initial distance between any two points is known, let's call it Lmin while the maximal distance of any movement is << LMin and we'll call it Mmax.

With these two additional assumptions, you can think of a mechanism as follows (JavaScript-like code - not checked!):

for (i = 0 ; i < Points.Count ; i++) {
    for (j = i + 1 ; j < Points.Count ; j++) {

        if ((ABS(Array1[i].x - Array2[j].x) > Mmax ) ||
            (ABS(Array1[i].y - Array2[j].y) > Mmax ) ||
            (ABS(Array1[i].z - Array2[j].z) > Mmax )    ) {
           // Distance between two points is for sure equal or bigger than max.
           continue ; // Meaning, go to check next point.
        }

        // The check of the distance is split into two stages
        // because, if the first if is true, the actual distance
        // calculation is not needed (and hence time is saved).

        if (Distance_Between_Points(Array1[i],Array2[j]) > Mmax) {
           // Distance between two points is for sure bigger than max.
           continue ; // Meaning, go to check next point.
        }

        // Points appear to be related!!!!!!
        ..........
    }
}