/*
 * PatConvexHull.java
 *
 * Created on October 28, 2005, 10:54 AM
 */

package Current.plot.BilliardLike;

import java.util.*;
import java.awt.geom.GeneralPath;

import Current.basic.*;

/**
 *
 * @author  pat
 */
public class PatConvexHull {
    LinkedList l;
    
    public class RationalTriangle {
        /** Refers to triangle with angles
         * Pi*(x[0]/sum, x[1]/sum, x[2]/sum)
         * where sum=x[0]+x[1]+x[2]
         */
        public int[] x;
        
        public RationalTriangle(int a, int b, int c){
            x=new int[3];
            x[0]=a;
            x[1]=b;
            x[2]=c;
            BasicMath.reduceByGcd(x);
            signReduce();
        }
        
        private RationalTriangle(int[] X){
            x=X;
            BasicMath.reduceByGcd(x);
            signReduce();
        }
        
        /** returns the unique triangle which is zero on both a and b */
        public RationalTriangle(LinearCondition a,
        LinearCondition b){
            x=BasicMath.cross(a.x,b.x);
            BasicMath.reduceByGcd(x);
            signReduce();
        }
        
        private void signReduce(){
            if (x[0]<0)
                x[0]=-x[0];
            if (x[1]<0)
                x[1]=-x[1];
            if (x[2]<0)
                x[2]=-x[2];
        }
        
        public String toString(){
            return "("+x[0]+","+x[1]+","+x[2]+")";
        }
        
        public double getX(){
            return 2.0*x[0]/(x[0]+x[1]+x[2]);
        }
        
        public double getY(){
            return 2.0*x[1]/(x[0]+x[1]+x[2]);
        }
    }
    
    public class LinearCondition{
        public int[] x;
        
        public LinearCondition(int a, int b, int c){
            x=new int[3];
            x[0]=a;
            x[1]=b;
            x[2]=c;
            BasicMath.reduceByGcd(x);
            
        }
        
        private LinearCondition(int[] X){
            x=X;
            BasicMath.reduceByGcd(x);
        }
        
        /** returns a condition which is zero on a and b (there may be a sign
         * descrepency from what you expect) */
        public LinearCondition(RationalTriangle a,
        RationalTriangle b){
            x=BasicMath.cross(a.x,b.x);
            BasicMath.reduceByGcd(x);
        }
        
        public int eval(RationalTriangle t){
            return BasicMath.dot(x,t.x);
        }
        
        public boolean isNonPositiveConstant(){
            return ((x[0]==x[1])&&(x[1]==x[2])&&(x[0]<=0));
        }
    }
    
    /** Creates a new instance of PatConvexHull */
    public PatConvexHull() {
        l=new LinkedList();
        l.add(new RationalTriangle(1,0,0));
        l.add(new RationalTriangle(0,1,0));
        l.add(new RationalTriangle(0,0,1));
    }
    
    /** if adding this linear condition destroys the hull return false */
    public boolean add(int a, int b, int c){
        return add(new LinearCondition(a,b,c));
    }
    
    /** if adding this linear condition destroys the hull return false */
    public boolean add(LinearCondition c){
        if (l.size()==0)
            return false;
        if (c.isNonPositiveConstant())
            return false;
        RationalTriangle prev,cur;
        int prevI,curI;
        
        cur=(RationalTriangle)l.getLast();
        curI=BasicMath.sign(c.eval(cur));
        
        ListIterator it=l.listIterator();
        /** Pass 1 insert any needed vertices */
        while(it.hasNext()){
            prev=cur;
            prevI=curI;
            cur=(RationalTriangle)(it.next());
            curI=BasicMath.sign(c.eval(cur));
            
            if ((prevI==-curI)&&(prevI!=0)){
                it.previous();
                it.add(new RationalTriangle(c,
                new LinearCondition(prev,cur)));
                it.next();
            }
        }
        
        it=l.listIterator();
        while (it.hasNext()){
            cur=(RationalTriangle)(it.next());
            if (c.eval(cur)<0)
                it.remove();
        }
        return l.size()!=0;
    }
    
    public void print(){
        ListIterator it=l.listIterator();
        while (it.hasNext())
            System.out.print(((RationalTriangle)it.next()).toString()+" ");
        System.out.println();
    }
    
    public GeneralPath toGeneralPath(){
        GeneralPath gp=new GeneralPath();
        RationalTriangle t;
        ListIterator it=l.listIterator();
        if (it.hasNext()){
            t=(RationalTriangle)it.next();
            gp.moveTo((float)t.getX(),(float)t.getY());
            //System.out.println("x="+t.getX()+" y="+t.getY());
            while (it.hasNext()) {
                t=(RationalTriangle)it.next();
                gp.lineTo((float)t.getX(),(float)t.getY());
                //System.out.println("x="+t.getX()+" y="+t.getY());
            }
            gp.closePath();
            return gp;
        } else {
            return null;
        }
    }
    
    public Complex[] toComplex(){
        Complex[] v=new Complex[l.size()];
        int i=0;
        RationalTriangle t;
        for (ListIterator it=l.listIterator(); it.hasNext();i++){
            t=(RationalTriangle)it.next();
            v[i]=new Complex(t.getX(),t.getY());
        }
        return v;
    }
}