Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

In the Cartesian coordinate system, given 3 geometrical solid objects (interior plus boundary): spheres S1(x1,y1,z1, R1), S2(x2,y2,z2, R2) and a cube (which is orthogonal with coordinate system) at the center C (x3,y3,z3) with size L x L x L. The question is “Whether the 3 objects have any common volumetric intersection (Yes or No) ” ? I need a math solution or computing algorithm for this problem.

share|improve this question
    
It depends on the values of your parameters. –  Ronaldo Apr 4 '11 at 17:33
3  
"Sphere" and "cube" could refer to either the solid object (interior plus boundary) or the surface (boundary only). Which specific type of intersection are you looking for? –  mjqxxxx Apr 4 '11 at 17:45

2 Answers 2

At first we need to check whether 2 spheres intersect or not. if (x1-x2)^2+ (y1-y2)^2+ (z1-y2)^2 > (R1+R2)^2 ---> flag of intersection=FALSE. else
( (i) Define x4=(x1*R2+x2*R1)/(R1+R2) y4=(y1*R2+y2*R1)/(R1+R2) z4=(z1*R2+z2*R1)/(R1+R2)

(ii) if ( (abs(x4-x3)<=L/2) & ( abs(y4-y3)<=L/2) & ( abs(z4-z3)<=L/2) & ---->flag of intersection=TRUE ) else ( // they have intersection if and only if the volumetric intersection of the 2 spheres intersects with at least one of 6 faces of the cube ( e.g. bottom face z= x3-L/2, x3-L/2<= x <= x3+L/2 & y3-L/2<= y <= y3+L/2) // this criteria is quite straightforward to check since it is only in the plane ( e.g. bottom face z= x3-L/2) ) )

share|improve this answer

Probably the easiest way to solve this problem is to reduce it to linear programming. Note that this formulation would work for checking if the intersection of any number of spheres/convex polytopes is non-empty. To begin with, we would first rewrite the cube as an intersection of halfspaces.

Next we need to replace the spheres with linear halfspaces as well. This is done by lifting them along the map from $\mathbb{R}^3$ to $\mathbb{R}^{4,1}$ where,

$ (x, y, z) \mapsto (1, x, y, z, \frac{1}{2} ( x^2 + y^2 + z^2 ) )$

Where we fix the metric that,

$ \langle (o_1, x_1, y_1, z_1, n_1), (o_2, x_2, y_2, z_2, n_2) \rangle = x_1 x_2 + y_1 y_2 + z_1 z_2 - o_1 n_2 - n_1 o_2$

So, a linear halfspace of the form,

$a x + b y + c z \leq d$

Can be written as:

$ \langle (0, a, b, c, d), (1, x, y, z, \frac{1}{2}(x^2 + y^2 + z^2) ) \rangle \leq 0 $

And a spherical halfspace,

$ (x - a)^2 + (y - b)^2 + (z - c)^2 \leq r^2 $

Becomes:

$ \langle (1, a, b, c, \frac{1}{2} (a^2 + b^2 + c^2 - r^2) ), (1, x, y, z, \frac{1}{2}(x^2 + y^2 + z^2) ) \rangle \leq 0$

As a result, our problem is now to determine if a system of linear inequalities has a solution. This is of course linear programming, and you can resolve it either by a brute-force determinant test (aka apply Helly's theorem), or use whatever efficient algorithm you would prefer. In this instance, since it is so small, brute force may be preferrable. For larger numbers of primitives, Seidel's algorithm should perform better.

share|improve this answer
    
Hi Mikola, thank you your answer, however I need only an algorithm in this particular case ( 2 spheres and 1 cube) and easy to be implemented for computer code. –  user9107 Apr 5 '11 at 10:05

Your Answer

 
discard

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