Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have a data-set that has four columns [X Y Z C]. I would like to find all the C values that are in a given sphere centered at [X, Y, Z] with a radius r. What is the best approach to address this problem? Should I use the clusterdata command?

share|improve this question
It would be good to update this question with the size of the data set. – Bill Barth Dec 8 '12 at 3:22

To collect the required C values I'd make a single pass through the data-set (array?) with some quick checks to eliminate most of the points outside the sphere, and then (only for the points that seem eligible) a check of actual radius.

That is, for a candidate point (x_i,y_i,z_i,c_i), test:

1) Is x_i between X-r and X+r?
2) If so, is y_i between Y-r and Y+r?
3) If so, is z_i between Z-r and Z+r?

Only if all three tests are true is it possible for the point to be in the desired sphere. For the final test, use precomputed r^2 and ask:

4) Is (x_i - X)^2 + (y_i - Y)^2 + (z_i - Z)^2 less than or equal r^2 ?

If the point passes the final test, include c_i in your collected C values.

share|improve this answer
Depending on how big is $r$ compared to the range of possible values, it may be more economical to do only three comparisons, the second and third being $(y_i-Y)^2 \leq r^2 - (x_i-X)^2$ and $(z_i-Z)^2 \leq r^2 - (x_i-X)^2 - (y_i-Y)^2$, which can be computed incrementally. – Jaime Dec 7 '12 at 1:04
@Jaime: Interesting idea. The sphere takes up about 52% of its bounding cube, so assuming uniform distribution the "costly" part of radius testing (multiplications) is avoided about half the time in my scheme, where you do two of three multiplies (squarings) in the 2nd step. Either of our approaches would benefit from having the data-set sorted by (at least) one of the coordinates, so a binary search could be partially used in the first comparison. – hardmath Dec 7 '12 at 1:38

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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