Thinking outside the box

Question

You are trying to fit a sphere into a 5-sided box, but sometimes it does not fit completely. Write a function to calculate how much of the sphere is outside (above the rim of) the box.

There are 3 possible situations:

• The sphere fits completely in the box. The answer will be 0.
• The sphere sits on the rim of the box. The answer will be more than half of the total volume.
• The sphere sits on the bottom of the box.

You can see each situation here:

You must write a program or function to compute this value to at least 4 significant digits.

Input: 4 non-negative real numbers in whatever format is convenient* - width, length, depth of the box (interior measurements), and diameter of the sphere.

Output: 1 non-negative real number in a usable format* - the total volume (not the percentage) of the sphere outside the box.

_{* must be convertible to/from a decimal string}

You are encouraged to limit your use of trigonometry as much as possible.

This is a popularity contest, so think outside the box!

Answer 1

Forth

Please find, below, a sphere outside the box.

The "sphere" is the volume-computing function f. The reference test cases compose the "box".

                     ( x y z d -- v )
                 : f { F: z F: d } d f2/ 
              { F: r } fmin { F: m } m f2/ {
             F: b } d m f<= d z f<= and if 0e
             else r r r f* b b f* f- fsqrt f-
              { F: t } d m f<= t z f> or if d 
               z f- else d t f- then r 3e f* 
                  fover f- pi f* fover f*
                      f* 3e f/ then ;

                     1e                 1e      
                     1e                 1e 
                     f                  f. 
            cr       1e        1e       0e      
            1e       f         f.       cr 
            1e       1e 0.5e 1e f f. cr 1e 
            0.999e 1e          1e     f  
            f.  cr            0.1e 1e   
            1.000e 0.500e f f. cr

Output:

0. 
0.523598775598299 
0.261799387799149 
0.279345334323962 
0.0654299441440212 

Answer 2

Java - integer based

This program does not use pi and does not call any external function - not even sqrt. It only uses simple arithmetic - +, -, * and /. Furthermore, other than a scaling step, it works exclusively with integers. It basically divides the sphere into little cubes and counts the ones that are outside the box.

public class Box {
    private static final int MIN = 10000;
    private static final int MAX = MIN * 2;

    private static final int[] SQ = new int[MAX * MAX + 1];

    static {
        int t = 1;
        for (int i = 1; i <= MAX; ++i) {
            while (t < i * i) SQ[t++] = i - 1;
        }
        SQ[MAX * MAX] = MAX;
    }

    public static long outsideInt(int r, int w, int z) {
        int r2 = r * r;
        int o = z - r + 1;
        if (w < r * 2) {
            int t = 1 - SQ[r2 - w * w / 4];
            if (t < o) o = t;
        }
        long v = 0;
        for (int i = o; i <= r; ++i) {
            int d = r2 - i * i;
            int j0 = SQ[d];
            v += 1 + 3 * j0;
            for (int j = 1; j <= j0; ++j)
                v += 4 * SQ[d - j * j];
        }
        return v;
    }

    public static double outside(double x, double y, double z, double d) {
        double f = 1;
        double w = x < y ? x : y;
        double r = d / 2;
        while (r < MIN) {
            f *= 8;
            r *= 2;
            w *= 2;
            z *= 2;
        }
        while (r > MAX) {
            f /= 8;
            r /= 2;
            w /= 2;
            z /= 2;
        }
        return outsideInt((int) r, (int) w, (int) z) / f;
    }

    public static void main(final String... args) {
        System.out.println(outside(1, 1, 1, 1));
        System.out.println(outside(1, 1, 0, 1));
        System.out.println(outside(1, 1, 0.5, 1));
        System.out.println(outside(1, 0.999, 1, 1));
        System.out.println(outside(0.1, 1, 1, 0.5));
    }
}

Output:

0.0
0.5235867850933005
0.26178140856157484
0.27938608275528054
0.06542839088004015

In this form, the program requires more than 2GB memory (works with -Xmx2300m here) and is prettty slow. It uses the memory to precalculate a bunch of square roots (arithmetically); it's not really necessary, but without that it would be a LOT slower. To improve both memory needs and speed, reduce the value of the MIN constant (that will decrease the accuracy though).

Answer 3

Python 2 (Array-based approach)

It creates an array of arrays with truth-values if a specific square in that grid is inside the circle or outside the circle. It should get more precise the bigger the circle is you draw. It then selects either an area below or above a certain row and counts the amount of squares that belongs to the circle and divides that by the amount of squares that are in the entire circle.

import math as magic
magic.more = magic.pow
magic.less = magic.sqrt

def a( width, length, depth, diameter ):
  precision = 350 #Crank this up to higher values, such as 20000
  
  circle = []
  for x in xrange(-precision,precision):
    row = []
    for y in xrange(-precision,precision):
      if magic.less(magic.more(x, 2.0)+magic.more(y, 2.0)) <= precision:
        row.append(True)
      else:
        row.append(False)
    circle.append(row)

  if min(width,length,depth) >= diameter:
    return 0
  elif min(width,length) >= diameter:
    row = precision*2-int(precision*2*float(depth)/float(diameter))
    total = len([x for y in circle for x in y if x])
    ammo = len([x for y in circle[:row] for x in y if x])
    return float(ammo)/float(total)
  else:
    #Why try to fit a sphere in a box if you can try to fit a box on a sphere
    maxwidth = int(float(precision*2)*float(min(width,length))/float(diameter))
    for row in xrange(0,precision*2):
      rowwidth = len([x for x in circle[row] if x])
      if rowwidth > maxwidth:
        total = len([x for y in circle for x in y if x])
        ammo = len([x for y in circle[row:] for x in y if x])
        return float(ammo)/float(total)

Answer 4

Python 2.7, Spherical Cap Formula

This version will throw a runtime warning in some cases, but still outputs the correct answer.

import numpy as n
x,y,z,d=(float(i) for i in raw_input().split(' '))
r=d/2
V=4*n.pi*r**3/3
a=n.sqrt((d-z)*z)
b=min(x,y)/2
h=r-n.sqrt(r**2-b**2)
c=lambda A,H: (3*A**2+H**2)*n.pi*H/6
print(0 if d<=z and r<=b else c(a,d-z) if r<=b and z>r else V-c(a,z) if r<=b or z<h else V-c(b,h))

For 11 characters more, I can get rid of the warning.

import math as m
x,y,z,d=(float(i) for i in raw_input().split(' '))
r=d/2
V=4*m.pi*r**3/3
if d>z:
    a=m.sqrt((d-z)*z)
b=min(x,y)/2
h=r-m.sqrt(r**2-b**2)
c=lambda A,H: (3*A**2+H**2)*m.pi*H/6
print(0 if d<=z and r<=b else c(a,d-z) if r<=b and z>r else V-c(a,z) if r<=b or z<h else V-c(b,h))

Here are the test cases run on version 1:

$ python spherevolume.py
1 1 1 1
0
$ python spherevolume.py
1 1 0 1
0.523598775598
$ python spherevolume.py
1 1 .5 1
0.261799387799
$ python spherevolume.py
1 .999 1 1        
0.279345334324
$ python spherevolume.py
.1 1 1 0.5
spherevolume.py:65: RuntimeWarning: invalid value encountered in sqrt
  a=n.sqrt((d-z)*z) or b
0.065429944144

Answer 5

Mathematica

Using numerical integration with proper limits.

f[width_, length_, height_, diam_] := 
 With[{r = diam/2, size = Min[width, length]/2},
  Re@NIntegrate[
    Boole[x^2 + y^2 + z^2 < r^2], {x, -r, r}, {y, -r, r}, 
      {z, -r, Max[-r, If[size >= r, r - height, Sqrt[r^2 - size^2]]]}]
  ]

Answer 6

Reference Implementation - C#

using System;

namespace thinkoutsidethebox
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine(OutsideTheBox(1, 1, 1, 1));
            Console.WriteLine(OutsideTheBox(1, 1, 0, 1));
            Console.WriteLine(OutsideTheBox(1, 1, 0.5, 1));
            Console.WriteLine(OutsideTheBox(1, 0.999, 1, 1));
            Console.WriteLine(OutsideTheBox(0.1, 1, 1, 0.5));
        }

        static double OutsideTheBox(double x, double y, double z, double d)
        {
            x = Math.Min(x, y);
            double r = d / 2; // radius
            double xr = x / 2; // box 'radius'
            double inside = 0; // distance the sphere sits inside the box
            if (d <= x && d <= z) // it fits
            {
                return 0;
            }
            else if (d <= x || r - Math.Sqrt(r * r - xr * xr) > z) // it sits on the bottom
            {
                inside = z;
            }
            else // it sits on the rim
            {
                inside = r - Math.Sqrt(r * r - xr * xr);
            }
            // now use the formula from Wikipedia
            double h = d - inside;
            return (Math.PI * h * h / 3) * (3 * r - h);
        }
    }
}

Output:

0
0.523598775598299
0.261799387799149
0.279345334323962
0.0654299441440212

Answer 7

Ruby

Let's see...
If the box is fully inside, then width>diameter; length>diameter and height>diameter.
That should be the 1st check to run.

If it's sitting at the bottom, then w>d ; l>d and h V=(pi*h^2 /3)*(3r-h) So in that case, We just get the height and run it through that.

If it's stuck, we use a similar formula (V=(pi*h/6)*(3a^2 + h^2)). In fact our earlier formula is based on this one! Essentially, we use that, and a is simply the smaller one of w and l. (hint, we can get height by doing h=r-a)

Now the code!

def TOTB(wi,le,hi,di)
  if wi>=di and le>=di and hi>=di
    res = 0
  elsif wi>=di and le>=di
    r = di/2
    res = 3*r
    res -= hi
    res *= Math::PI
    res *= hi*hi
    res /= 3
  else
    r = di/2
    if wi>le
      a=le
    else
      a=wi
    end #had issues with the Ternary operator on ruby 2.2dev
    h = r-a
    res = 3*a*a
    res += h*h
    res *= Math::PI
    res *= h
    res /= 6
  end
  res
end

Note** I didn't test it too much, so an error may have crept in, if anyone notices one, do tell!
The math is solid though.
Shorter version:

v1 = ->r,h{(3*r -h)*Math::PI*h*h/3}
v2 = ->r,a{h=r-a;((3*a*a)+(h*h))*h*Math::PI/6}
TOTB = ->wi,le,hi,di{(di<wi&&di<le&&di<hi)?0:((di<wi&&di<le)?v1[di/2,hi]:v2[di/2,((wi>le)?le:wi)])}

(Now I know for sure that getting h for v2 is done differently, but I'll fix it later.

Answer 8

c++

#define _USE_MATH_DEFINES   //so I can use M_PI
#include <math.h>           //so I can use sqrt()
#include <iostream>
#include <algorithm>

using namespace std;


int main()
{
    double w;
    double l;
    double d;
    double sd;
    double min_wl;
    double pdbd;
    double sl;
    cin >> w >> l >> d >> sd;

    min_wl = min(w, l);
    if(sd <= min_wl)
    {
        pdbd = 0.0;
    } else
    {
        pdbd = (sqrt((((sd/2)*(sd/2))-((min_wl/2)*(min_wl/2)))) + (sd/2));
    }
    sl = sd - d;

    if(sd <= min(min_wl, d))
    {
        cout << 0;
        return 0;
    } else if((sl < pdbd) && (pdbd > 0.0))    //sits on lip of box
    {
        cout << (M_PI * (((sd/2) * pdbd * pdbd) - ((pdbd * pdbd * pdbd)/(3))));
        return 0;
    } else                  //sits on bottom of box
    {
        cout << (M_PI * (((sd/2) * sl * sl)-((sl * sl * sl)/(3))));
        return 0;
    }
    return 0;
}

My code finds the volume of the solid of rotation of the graph of some portion of a half-circle. pdbd holds the linear distance of the projection of a point on the surface of the sphere that touches the lip of the box to the diameter of the sphere that, if extended, would be normal to the bottom of the box. The two expressions that contain M_PI are basically the anti-derivative of the integral of pi * -(x^2)+2rx with respect to x (where x is a measure of the length along the above mentioned diameter through the sphere and where r is the radius of the sphere) evaluated at either pdbd or the difference of the sphere diameter and the box depth depending on the particular case that occurs with the different dimensions.