Potatoes in space! - Correlating sets of unordered 4d data

Question

(I asked this question some time back but got no answers or comments. It's a pretty big question so therefore I thought dividing it into several questions might make it easier to answer. The original thread is here: Matching sets of 3d position data)

Imagine a cube filled with air and ~5000 levitating potatoes. The distance between two potatoes is usually an order of magnitude larger than their diameter and their distribution is pretty random but not normal. The size and number of potatoes in the cube is unknown but I have two methods for measuring it: reference method A (assumed to be the truth), and method B. Both methods have given me the x-, y- and z-position of each potato that it found along with it's size.

QUESTION: The two lists of x-, y-, z- and size data are not in the same order. Is there some method that allows me to assess how well method B measures the size and position of the potatoes without having to determine which two entries in list A and B that refers to the same potato?

If I were to make a method up I might imagine that I plotted the potatoes as blue and red spheres in space (size given by size data) and checked how much of the volume was purple compared to blue or red. But I'd rather use a real method than making something up, and I figure this problem can't possibly be a new one.

Answer 1

"Assume a spherical potato" is probably a reasonable thing to do here.

As the blue part space is essentially random, you cannot represent it more efficiently than your list of 5000 spheres. What would be possible is a spatial index that allows for an efficient search, so you don't need 5000*5000 comparisons.

My gut feeling would be to sort the red potato indices in all 3 dimensions. This gives us 3 lists. Now given a blue potato, search for its X coordinate in the red-X list, it's Y coordinate in the red-Y list and its Z coordinate in the red-Z list. As these three lists are essentially projections, all 3 lists of candidates will be mostly wrong. However, there's in all likelyhood going to be only a single common candidate on all 3 lists.

Finding numbers common to N lists is efficient if you first sort the lists. (This is basically just a matter of determining the union of N lists.) Start with x = the smallest number of the first list. Do a binary search for x on the second, third list etc until you don't find x. Keep track of the points where you found x. At that point, set x to the next number from the first list. As you have kept track of the positions in all lists where you found x so far, you know you don't need to search before those points. This means the binary search ranges shrink fairly rapidly.

Note that there may be several candidates if one read potato can overlap more than one blue potato.

There's one slight challenge in the projection phase, and that's that the potatoes all have different sizes. You can solve this by using 3*2 lists, for red-min-X and red-max-X coordinates etc. This will obviously also produce 6 lists of candidates (again:indices), but the lists pairwise will have a lot of commonality. Don't merge those pairs. The union of the min-X and min-Y candidate lists is a lot smaller than the union of the min-X and max-X candidate lists.

Note that you could also add non-orthogonal projections by sorting on X+Y, X+Y-Z etc, but for the simple sphere case with plenty of distance between them this probably does not add value. The list of candidate pairs will be small enough to calculate the overlap% for all of them, and accept that some false pairs turn out to have 0% overlap.