import java.awt.*;
import java.awt.event.*;
import java.applet.*;
import java.awt.geom.*;
import java.math.*;


/**This class defines the separation functions from the paper.  These are lower and upper bounds
   on the distance between pairs of points in two spherical patches.  We have to be careful that our 
   boxes do not cross the coordinate axes. So, we eliminate the initial boxes.**/


public class Separation {

    /**The lower bound on distance**/

    public static double psiMin(Box B1,Box B2) {
	double bound=0;	 
                  if((B1.k==-2)||(B2.k==-2)) return(0);	
	if(B1.type==2) bound=perfectLowerBound(B2,B1);
	if(B2.type==2) bound=perfectLowerBound(B1,B2);
	if(bound>0) return(bound);
	return(lowerBound(B1,B2));
    }

    /**The upper bound on distance**/

    public static double psiMax(Box B1,Box B2) {
	double bound=2;
	if((B1.k==-2)||(B2.k==-2)) return(bound);	
	if(B1.type==2) bound=perfectUpperBound(B2,B1);
	if(B2.type==2) bound=perfectUpperBound(B1,B2);
	if(bound<2) return(bound);
	return(upperBound(B1,B2));
    }

    /**The general purpose upper bound from the paper.   
          If the value of D1 is very small, we return a bigger
         upper bound, so as to avoid using the square root
         function on very small numbers.**/

  
    public static double sqrtUpperBound(double d) {
	if(d<1/1024.0) return(1/32.0);
	return(Math.sqrt(d));
    }


    public static double upperBound(Box B1,Box B2) {
	double D0=DVAL(B1,B2);
	 double d=delta(B1,B2);
	 double D1=sqrtUpperBound(4-D0*D0);
	 double s=D0+ D1*d;
	if(s>2) return(2);
	return(s);
    }


    /**The general purpose lower bound from the paper.**/

    public static double lowerBound(Box B1,Box B2) {
	double D0=DVAL(B1,B2);
	double d=delta(B1,B2);
	double D1=sqrtUpperBound(4-D0*D0);
	 double s=D0*(1-d*d/2) - D1*d;
	if(s<0) return(0);
	return(s);
    }






    /**Estimate on the average radius of the caps containing the spherical patches**/

    public static double delta(Box B1,Box B2) {
	double x=B1.delta()*B1.tau()+B2.delta()*B2.tau();
	return(x/4);
    }


    /**Distance between the inverse stereo images of the box centers.**/

    public static double DVAL(Box B1,Box B2) {	
	Vector V1=B1.getCenter();
	Vector V2=B2.getCenter();
	return(Vector.dist(V1,V2));
    }



    /**The sharp upper bound, used only in case the second box is the
       point at infinity.*/


    public static double perfectUpperBound(Box B1,Box B2) {	
        if(B1.k<-1) return(2);
        if(B2.k<-1) return(2);
        Vector[] V1=B1.toVectors();
        Vector[] V2=B2.toVectors();
        double max=0;
        double test=0;
        for(int i=0;i<V1.length;++i) {
            for(int j=0;j<V2.length;++j) {
                test=Vector.dist(V1[i],V2[j]);
                if(max<test) max=test;
            }
        }
        return(max);
    }

    public static double perfectLowerBound(Box B1,Box B2) {	
        if(B1.k<-1) return(0);
        if(B2.k<-1) return(0);
        Vector[] V1=B1.toVectors();
        Vector[] V2=B2.toVectors();
        double min=2;
        double test=0;
        for(int i=0;i<V1.length;++i) {
            for(int j=0;j<V2.length;++j) {
                test=Vector.dist(V1[i],V2[j]);
                if(min>test) min=test;
            }
        }
        return(min);
    }





}