Is point A nearby point B in 3D - distance check

Question

I am looking for efficent algorithm for checking if one point is nearby another in 3D.

sqrt((x2-x1)^2 + (y2-y1)^2 + (z2-z1)^2) < radius

This doesn't seem to be too fast and actually I don't need such a big accuracy. How else could I do this?

Answer 1

Square the distance, and drop the call to sqrt(), that's much faster:

(((x2-x1)^2 + (y2-y1)^2 + (z2-z1)^2 < radius * radius

Of course, in many cases at least radius * radius can be computed ahead of time and stored as e.g. squaredRadius.

Answer 2

Well if you can be content with a cube distance rather than a spherical distance a pretty naive implementation would be like this:

Math.Abs(x2-x1) < radius && Math.Abs(y2-y1) < radius && Math.Abs(z2-z1) < radius 

You can use your own favourite methods of optimising Math.Abs if it proves a bottleneck.

I should also add that if one of the dimensions generally varies less than other dimensions then putting that one last should lead to a performance gain. For example if you are mainly dealing with objects on a "ground" x-y plane then check the z axis last, as you should be able to rule out collisions earlier by using the x and y checks.

Answer 3

If you do not need big accuracy maybe you can check if 2nd point is inside cube (side length '2a'), not sphere, where the 1st point is in center:

|x2-x1|<a && |y2-y1|<a && |z2-z1|<a

Answer 4

Because of the pipelined processor architectures it is - nowadays - in most cases more efficient to do the FPU calculation twice, as branching once. In case of a branch mis-prediction you are stalling for ages ( in cpu-terms ).

So, I would rather go the calculation-way, not the branching-way.

Answer 5

if you don't need the accuracy you can check whether you are in a cube rather than a sphere.

there are options here as well you can pick the cube that enclose the sphere (no false negatives) the cube with the same volume as the sphere (some false positives and negatives, but max error is minimized), the cube that is contained within the sphere (no false positives).

this technique also extends well to higher dimensions.

if you want to get all the points near another one some form of spacial indexing may also be appropriate (kd-tree perhaps)

Answer 6

If you have to check against many other points, you could consider using a spatial ordering method to quickly discover points, that are near a certain location. Have a look at this link: wiki link

Answer 7

Use max(abs(x1-x2), abs(y1-y2), abs(z1-z2))

Answer 8

After dropping the square root, if the values gets larger, its better to apply log.

Answer 9

If we were going to optimise this because it was being run billions of times, I would solve this by using unwind's method, and then parallelizing it using SIMD. There's a few different ways to do that. You might simply do all the subtractions (x2-x1,y2-y1,z2-z1) in one op, and then the multiplies in one op also. That way you parallize inside the method without re-designing your algorithm.

Or you could write a bulk version which calculates (x2-x1)^2+(y2-y1)^2+(z2-z1)^2 - r^2 on many elements and stores the results in an array. You can maybe get better throughput, but it means re-designing your algorithm and depends what the tests are used for.

You could also easily optimize this using something like OpenMP if you were really doing lots of tests in a row.

Answer 10

This does the cube-distance, and if you are doing a lot of points, most of the time it only does the first test.

close = (abs(x2-x1) < r && abs(y2-y1) < r && abs(z2-z1) < r);