All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Algorithms
Constructing a Sphere (Posted on 2012-02-25) Difficulty: 3 of 5
I would like to construct a sphere by gluing unit cubes together. I'm only attempting to approximate the shape of a sphere as closely as is possible with unit cubes.

Before I get out the glue, how would I go about creating a spreadsheet that would show me the quantity and placement of cubes in each cross-sectional layer? (think of an MRI scan cross-section)

For input, the spreadsheet should ask for the radius of the sphere to be built, as well as which layer of that sphere should be displayed.

There may be more than one way to accomplish this. Any spreadsheet that will allow me to build a sphere by displaying each layer of a sphere for a given radius is considered valid.

Here is an example of output:

Hint: The formula for distance in 3 dimensions is:

d=√[(x2-x1)2+(y2-y1)2+(z2-z1)2]

Bonus question! Adjust your algorithm to display a hollow sphere (think of a ping pong ball, or a beach ball). Note: All cubes must be connected into one contiguous piece.

No Solution Yet Submitted by Dustin    
Rating: 5.0000 (1 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Some Thoughts One passionate solution (without bonus) | Comment 1 of 16
There are, it seems to me, only two basic decisions to be made, and two realistic alternatives for each:

Decision 1) How to determine whether a given cubic cell is or is not in the constructed sphere.
    a) Option 1a: Include a cube if 50% or more of the volume of the cube is within the sphere.  
    b) Option 1b: Include a cube if the center of the cube is within the sphere or on its' surface.  
    Note that these are not the same.  If the center of the cube is on the sphere's surface, then less than 50% of its volume is inside the sphere.  While (1a) is statistically a better model for the volume of the sphere, there is not much difference in practice, and the mathematics of 1a are a little beyond me, so I am going to opt for (1b).

Decision 2) Whether the center of the sphere lies in the middle of a cube or at the intersection of 8 cubes.
   a) Option 2a -- The pictures above all imply that that the center is a single cube.  Note that every row and column of cells has an odd number of cubes.
   b) Option 2b -- Alternatively, the sphere could be constructed so that the center of each layer is a point, and so that every row and column of cells in each layer has an even number of cubes.  If done this way, the sphere could be divided into 8 equal octants without cutting through cells.
   c) Option 2c.  Actually, there is a third option, which I will not consider.  The layers could alternate: with even rows and columns in one layer and odd rows and columns in the layer above and below.  I am rejecting this outright, principally because it does not lead to symmetry across all three planes, and will therefore not be a pleasing model.  But also, because it will not implement well in a spreadsheet.

Under option 2a, label the central x, y and z axes with a 0.  Let z be the level.  Then cells are included if x^2 + y^2 + z^2 <= 81
Here is 1/4 of level 0:

   0 1 2 3  4 5 6 7  8 9
0 X X X X X X X X X X
1 X X X X X X X X X
2 X X X X X X X X X
3 X X X X X X X X X
4 X X X X X X X X X
5 X X X X X X X X
6 X X X X X X X
7 X X X X X X
8 X X X X X
9 X

This is a little too pointy at the poles for my taste, so I prefer option 2b, where the two central rows and columns and layers are both labeled as a zero.  Now, include a cell if (X + .5)^2 + (Y + .5)^2 + (Z + .5)^2  <= 81

Here is more than 1/4 of one of the level 0's.

   0I0 1  2 3 4 5  6 7 8
0 XIX X X X X X X X X
0 XIX X X X X X X X X
1 XIX X X X X X X X X
2 XIX X X X X X X X
3 XIX X X X X X X X
4 XIX X X X X X X
5 XIX X X X X X 
6 XIX X X X X 
7 XIX X X X 
8 XIX X

Aesthetically, I prefer this approach.  Both because it is less pointy at the poles and because of the eight-fold symmetry.  I have not determined which better approximates the sphere's volume when d = 9.

I introduced the notion of two columns labeled 0 just to make the illustration, but it is not necessary.  Let's consider cube (x,y,z) to be the unit cube whose center in a three-axis coordinate system is at (x,y,z) where z, y and z are integers.  Then we could, for instance include any cube (x,y,z) for which d=√[(x-x1)2+(y-y1)2+(z-z1)2] where x1, y1, z1 end in .5.
For instance, x1 = 9.5, y1 = 10.5, z1 = 17.5  results in a sphere-like block of cubes centered at point (9.5, 10.5, 17.5).   Each "layer" corresponds to a different integral value of z. 


Edited on February 26, 2012, 1:05 pm
  Posted by Steve Herman on 2012-02-26 00:55:31

Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (2)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information