4

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?

4
  • 2
    Since there's a C++ tag, I feel I ought to mention that ^ means 'xor', not 'power' (which I'm sure @Balon is already aware of :-)) Jan 22, 2010 at 10:46
  • 1
    We might need a LaTeX formatting thingy like in Wikipedia for math-related topics. Shouldn't be too difficult to merge in the Wikipedia formula image generation code.
    – Thorsten79
    Jan 22, 2010 at 11:02
  • When people complain about proximity determinations being slow, it's usually a matter of doing too many of them. Can you solve your problem using spatial partitioning, such as an octree/quadtree or BSP?
    – drxzcl
    Mar 28, 2010 at 23:19
  • 1
    @JamesHopkin As they say "better later than never" – I've now removed the C++ tag as this question is pretty general and not C++-specific :)
    – kjagiello
    Oct 22, 2019 at 21:48

10 Answers 10

24

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.

14
  • 2
    Why don't you think this is fast? Is there any reason you think this code is going to be a problem, like being run a billion times?
    – Mr. Boy
    Jan 22, 2010 at 10:30
  • 2
    maybe what you need is to store your points inside a spatial structure like a octree to be able to have quite less points to compare. The distance between point is bounded by the distance between their boxes.
    – fa.
    Jan 22, 2010 at 10:41
  • 5
    @darid: Do the maths again. √p < q is equivalent to p < q² as long as p, q are nonnegative. 0.6 = √0.36 < 0.7 and 0.36 < 0.49 = 0.7².
    – kennytm
    Jan 22, 2010 at 10:56
  • 1
    @Balon: have you measured cube distance to be faster or are you just guessing. Because I would assume cube distance (using the formula presented here) to be about equally fast at best, slower at worst. Afterall it basically exchanges additions and multiplication with comparisons and conditional jumps (since && short-circuits). That doesn't really seem like it should improve performance
    – Grizzly
    Jan 22, 2010 at 11:09
  • 1
    @Balon: it would be a unusual machine where abs(x) is faster than (x * x), particularly for non-integers. The general rule, however, for knowing which algorithm is faster is test them both and see for yourself. Jan 22, 2010 at 12:31
10

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.

3
  • And if it's within the cube, you can still refine to spherical distance. +1
    – xtofl
    Jan 22, 2010 at 10:55
  • +1 that's about the most basic way of estimating the distance.
    – ziggystar
    Jan 22, 2010 at 11:07
  • 1
    The third term of the example code should be Math.Abs(z2-z1) < radius. Jan 22, 2010 at 11:09
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
1
  • Whoah, what language is that? |a| being 'absolute value of' is mathmetical notation, but does that also have '&&' ? Jan 22, 2010 at 10:58
2

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.

1

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)

1

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

1

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.

0

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

5
  • 5
    Is that really any faster, with all those conditional logic tests? Multiplication is hardly inefficient on modern CPUs.
    – Mr. Boy
    Jan 22, 2010 at 10:29
  • Conditional Logic is hardly inefficient either! Jan 22, 2010 at 10:59
  • 1
    Actually conditional logic in a tight loop could be less efficient than just calculating everything because of branch misprediction. Jan 22, 2010 at 11:10
  • Do you need conditional logic for double abs(double) and double max(double, double) anyway?
    – MSalters
    Jan 22, 2010 at 13:27
  • Not sure. It's not a standard op IIRC, which makes it risky to assume optimisation.
    – Mr. Boy
    Jan 22, 2010 at 13:37
0

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

0

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);

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.