CODEWITHSUNDEEP
javaalgorithm3dgeometry
padawan
padawan

Reputation: 1315

Sphere-Sphere intersection and Circle-Sphere intersection

I have the code for circle-circle intersection. But I need to expand it to 3-D. Could you please help me to write the functions?

static class Point{

    double x, y, z;
    int dimension;
    Point(double x, double y, double z) {
        this.x = x;
        this.y = y;
        this.z = z;
        dimension = 3;
    }

    Point sub(Point p2) {
        return new Point(x - p2.x, y - p2.y, z - p2.z);
    }
    Point add(Point p2) {
        return new Point(x + p2.x, y + p2.y, z + p2.z);
    }
    double distance(Point p2) {
        return Math.sqrt((x - p2.x)*(x - p2.x) + (y - p2.y)*(y - p2.y) + (z - p2.z)*(z - p2.z));
    }
    Point normal() {
        double length = Math.sqrt(x*x + y*y + z*z);
        return new Point(x/length, y/length, z/length);
    }
    Point scale(double s) {
        return new Point(x*s, y*s, z*s);
    }

    double[] array()
    {
        return new double[]{x,y,z};
    }
}

static class Circle {

    double x, y, r, left;
    Circle(double x, double y, double r) {
        this.x = x;
        this.y = y;
        this.r = r;
        left = x - r;
    }
    Circle(double[] c, double r) {
        this(c[0], c[1], r); 
    }
    Circle(Point c, double r)
    {
        this(c.x, c.y, r);
    }
    Point[] intersections(Circle c) 
    {
        Point P0 = new Point(x, y,0);
        Point P1 = new Point(c.x, c.y,0);
        double d, a, h;
        d = P0.distance(P1);
        a = (r*r - c.r*c.r + d*d)/(2*d);
        h = Math.sqrt(r*r - a*a);
        if(Double.isNaN(h))
            return null;

        Point P2 = P1.sub(P0).scale(a/d).add(P0);
        double x3, y3, x4, y4;
        x3 = P2.x + h*(P1.y - P0.y)/d;
        y3 = P2.y - h*(P1.x - P0.x)/d;
        x4 = P2.x - h*(P1.y - P0.y)/d;
        y4 = P2.y + h*(P1.x - P0.x)/d;

        return new Point[]{new Point(x3, y3, 0), new Point(x4, y4, 0)};
    }

}

static class Sphere
{
    double x,y,z,r,left;
    Sphere(double x, double y, double z, double r)
    {
        this.x = x;
        this.y = y;
        this.z = z;
        this.r = r;
        left = x-r;
    }

    Circle intersection(Sphere s) 
    {
        Point P0 = new Point(x, y, z);
        Point P1 = new Point(s.x, s.y, s.z);

        double d, a, h;
        d = P0.distance(P1);
        a = (r*r - s.r*s.r + d*d)/(2*d);
        h = Math.sqrt(r*r - a*a);
        if(Double.isNaN(h))
            return null;

        Point P2 = P1.sub(P0).scale(a/d).add(P0);
        return new Circle(P2, h);
    }

    Point[] intersections(Circle c)
    {
        Point P0 = new Point(0,0,0);
        Point P1 = new Point(0,0,0);
        //...
        return new Point[]{P0, P1};
    }

}

I have checked this link and this link, but I could not understand the logic behind them and how to code them.

I tried ProGAL library for sphere-sphere-sphere intersection, but the resulting coordinates are rounded. I need precise results.

Upvotes: 1

Views: 2375

Answers (1)

Sachamora
Sachamora

Reputation: 489

To be sure , what you need is how to intersect 3 spheres? if so , your current data structure for circle is useless. let say you want to intersect 3 spheres : s1 , s2 , s3, intersection of s1 and s2 will be a circle that you will intersect with s3 for final results, BUT keep it mind that the circle is not on XoY plane , it's center may be on any 3D coordinate and it will face a direction in the 3D space. to store information of such a circle you need , centerX , centerY , centerZ , radius and a 3d vector called normal.

class Circle3D
{
    Point center;
    double r;
    Point normal;
    ...
}

after you completed this new class, you can use it to store information about Sphere-Sphere intersection. after that you must implement Sphere-Circle3D intersection:

Circle3D Intersect(Sphere s1 , Sphere s2)
{
     double d = dist(s1.center , center)
     double x = (d*d + s1.r*s1.r - s2.r*s2.r)/(2*d)
     Point normal = normalize(s2.Center - s1.Center)
     Point center = s1.center + x*normal;
     double radius = sqrt(s1.r*s1.r - x*x)

     return new Circle3D(center , radius , normal);
}

don't panic if math seems chaotic , read this Page

now it is timee ofr sphere-circle3D intersection, for that:

point[] Intersect(Sphere s , Circle3D c)
{
    /*
      first we check if sphere even intersects with plane of c
      I assume you know how to implement some if these functions
    */
    if(GetDistanceOfPointFromPlane(s.center , new Plane(c.center , normal))>s.radius)
         return NULL;

    /*
      again we check possibility of avoiding math of intersection
    */
    point dir = Normalize(s.center - c.center);
    if(!DoesRayIntersectWithSphere(s , new Ray(c.center , c.radius*dir)))
        return NULL;

    /*
      this is the ugly part of code that unfortunately is deep trig math.
      you must describe sphere and circle equations in polar system , then
      you must solve sphere = circle
      I hope the link below be helpful 
    */  

}

here is the link mentioned in cemments above

http://mathworld.wolfram.com/SphericalCoordinates.html

Upvotes: 2

Related Questions