3D Math - Only keeping positions within a certain amount of yards

Question

I'm trying to determine from a large set of positions how to narrow my list down significantly.

Right now I have around 3000 positions (x, y, z) and I want to basically keep the positions that are furthest apart from each other (I don't need to keep 100 positions that are all within a 2 yard radius from each other).

Besides doing a brute force method and literally doing 3000^2 comparisons, does anyone have any ideas how I can narrow this list down further?

I'm a bit confused on how I should approach this from a math perspective.

Answer 1

Well, I can't remember the name for this algorithm, but I'll tell you a fun technique for handling this. I'll assume that there is a semi-random scattering of points in a 3D environment.

Simple Version: Divide and Conquer

1. Divide your space into a 3D grid of cubes. Each cube will be X yards on each side.
2. Declare a multi-dimensional array [x,y,z] such that you have an element for each cube in your grid.
3. Every element of the array should either be a vertex or reference to a vertex (x,y,z) structure, and each should default to NULL
4. Iterate through each vertex in your dataset, determine which cube the vertex falls in.
   • How? Well, you might assume that the (5.5, 8.2, 9.1) vertex belongs in MyCubes[5,8,9], assuming X (cube-side-length) is of size 1. Note: I just truncated the decimals/floats to determine which cube.
5. Check to see if that relevant cube is already taken by a vertex. Check: If MyCubes[5,8,9] == NULL then (inject my vertex) else (do nothing, toss it out! spot taken, buddy)

Let's save some memory

This will give you a nicely simplified dataset in one pass, but at the cost of a potentially large amount of memory.

So, how do you do it without using too much memory?

I'd use a hashtable such that my key is the Grid-Cube coordinate (5,8,9) in my sample above.

 If MyHashTable.contains({5,8,9}) then DoNothing else InsertCurrentVertex(...)

Now, you will have a one-pass solution with minimal memory usage (no gigantic array with a potentially large number of empty cubes. What is the cost? Well, the programming time to setup your structure/class so that you can perform the .contains action in a HashTable (or your language-equivalent)

Hey, my results are chunky!

That's right, because we took the first result that fit in any cube. On average, we will have achieved X-separation between vertices, but as you can figure out by now, some vertices will still be close to one another (at the edges of the cubes).

So, how do we handle it? Well, let's go back to the array method at the top (memory-intensive!).

Instead of ONLY checking to see if a vertex is already in the cube-in-question, also perform this other check:

 If Not ThisCubeIsTaken()
    For each SurroundingCube
      If not Is_Your_Vertex_Sufficiently_Far_Away_From_Me()
         exit_loop_and_outer_if_statement()
      end if
    Next
    //Ok, we got here, we can add the vertex to the current cube because the cube is not only available, but the neighbors are far enough away from me
 End If

I think you can probably see the beauty of this, as it is really easy to get neighboring cubes if you have a 3D array.

If you do some smoothing like this, you can probably enforce a 'don't add if it's with 0.25X' policy or something. You won't have to be too strict to achieve a noticeable smoothing effect.

Still too chunky, I want it smooth

In this variation, we will change the qualifying action for whether a vertex is permitted to take residence in a cube.

 If TheCube is empty OR if ThisVertex is closer to the center of TheCube than the Cube's current vertex
    InsertVertex (overwrite any existing vertex in the cube
 End If

Note, we don't have to perform neighbor detection for this one. We just optimize towards the center of each cube.

If you like, you can merge this variation with the previous variation.

Cheat Mode

For some people in this situation, you can simply take a 10% random selection of your dataset and that will be a good-enough simplification. However, it will be very chunky with some points very close together. On the bright side, it takes a few minutes max. I don't recommend it unless you are prototyping.