/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package algoritmobr;

import java.util.ArrayList;

/**
 * @author Joel
 * @author Cristian
 */
public class regionConvexa {
    public ArrayList<vertice> region;
    public ArrayList<Integer> puntos;
    
    public regionConvexa(){
        this.region=new ArrayList<>();
        this.puntos=new ArrayList<>();
    }
    
    public void addRegion(ArrayList<vertice> B){
        this.region.addAll(B);
    }
    
    public void addPunto(int A){
        this.puntos.add(A);
    }

    public void reset(){
        this.puntos.clear();
        this.region.clear();
    }
    
    public boolean esVacia(){
        if(this.puntos.isEmpty())return true;
        else return false;
    }
    
    public void Particion(vertice desde, vertice hasta){
        int op = 100*Posicion(desde)+Posicion(hasta);
        //System.out.println("op = "+op);
        switch (op){
            case 101:
                //System.out.println("Adentro-Adentro\n");
                partirNoVacia(desde, hasta);
                partirNoVacia(hasta, desde);
                partirVacia(desde, hasta);
                partirVacia(hasta, desde);
                break;
            case 102:
                //System.out.println("Adentro-Borde\n");
                partirNoVacia(desde, hasta);
                partirNoVacia(hasta, desde);
                partirVacia(desde, hasta);
                break;
            case 103:
                //System.out.println("Adentro-Afuera\n");
                vertice A = new vertice(puntoFantasma(hasta, desde));
                partirNoVacia(desde, A);
                partirNoVacia(A, desde);
                partirVacia(desde, A);
                break;
            case 201:
                //System.out.println("Borde-Adentro\n");
                partirNoVacia(desde, hasta);
                partirNoVacia(hasta, desde);
                partirVacia(hasta, desde);
                break;
            case 202:
                //System.out.println("Borde-Borde\n");
                partirNoVacia(desde, hasta);
                partirNoVacia(hasta, desde);
                break;
            case 203:
                //System.out.println("Borde-Afuera\n");
                vertice B = new vertice(puntoFantasma(hasta, desde));
                if(B!=null){
                    partirNoVacia(desde, B);
                    partirNoVacia(B, desde);
                }
                break;
            case 301:
                //System.out.println("Afuera-Dentro\n");
                vertice C = new vertice(puntoFantasma(desde, hasta));
                partirNoVacia(C, hasta);
                partirNoVacia(hasta, C);
                partirVacia(hasta, C);
                break;
            case 302:
                //System.out.println("Afuera-Borde\n");
                vertice D = new vertice(puntoFantasma(desde, hasta));
                if(D!=null){
                    partirNoVacia(D, hasta);
                    partirNoVacia(hasta, D);
                }
                break;
            case 303://CASO ESPECIAL, REVISARLO!!!!!!
                //System.out.println("Afuera-Afuera\n");
                //System.out.println("Región = "+this.region.toString());
                //System.out.println("Segmento cortado = "+desde.toString()+hasta.toString());
                ArrayList<vertice> ghost = new ArrayList<>();
                ghost.addAll(puntoFantasma2(desde, hasta));
                if(ghost.size()==2){
                    partirNoVacia(ghost.get(0), ghost.get(1));
                    partirNoVacia(ghost.get(1), ghost.get(0));
                }
                break;
        }
        //System.out.println("Puntos azules en esta región:\n"+this.puntos.toString());
    }
    
    public int Posicion(vertice punto)
    {
        int counter = 0;
        int i;
        int n=this.region.size();
        double xinters;
        vertice p1,p2;
        p1 = this.region.get(0);
        for (i=1;i<=n;i++) {
            p2 = this.region.get(i%n);
            //si está en la horizontal
            if(p1.getY()==p2.getY()&&p1.getY()==punto.getY()&&punto.getX()>Math.min(p1.getX(), p2.getX())&&punto.getX()<Math.max(p1.getX(),p2.getX()))
                return 2;
            //if(punto.equals(p1)||punto.equals(p2)) return 2;
            if (punto.getY() > Math.min(p1.getY(),p2.getY())) {
                if (punto.getY() <= Math.max(p1.getY(),p2.getY())) {
                    if (punto.getX() <= Math.max(p1.getX(),p2.getX())) {
                        if (p1.getY() != p2.getY()) {
                            xinters = (punto.getY()-p1.getY())*(p2.getX()-p1.getX())/(p2.getY()-p1.getY())+p1.getX();
                            //si está en el borde de cualquiera distinto al horizontal
                            if(punto.getX() == xinters)
                                return 2;
                            if (p1.getX() == p2.getX() || punto.getX() <= xinters)
                                counter++;
                        }
                    }
                }
            }
            p1 = p2;
        }
        //si las intersecciones son pares, está fuera; si es impar, está dentro
        if (counter % 2 == 0)
            return 3;
        else
            return 1;
    }   
    
    public double distPtoRecta(vertice s, vertice d, vertice h){
        double A = h.getY()-d.getY();
        double B = -1*(h.getX()-d.getX());
        double C = (-1*d.getX()*A)-(d.getY()*B);
        double dPR = Math.abs((A*s.getX())+(B*s.getY())+C)/(Math.sqrt(Math.pow(A, 2)+Math.pow(B, 2)));
        return dPR;
    }
    
    public ArrayList<vertice> puntoFantasma2(vertice a, vertice b){
        ArrayList<vertice> s = new ArrayList<>();
        vertice s1 = new vertice(a);
        vertice s2 = new vertice(b);
        //s.addAll(segmentoCortado(s1, s2));
        ArrayList<vertice> ghost = new ArrayList<>();
        /*ghost.add(new vertice(inter(s.get(0), s.get(1), s1, s2)));
        ghost.add(new vertice(inter(s.get(2), s.get(3), s1, s2)));*/
        for(int i=0; i<this.region.size(); i++){
            vertice X;
            if(i==this.region.size()-1){
                X = new vertice(inter(s1, s2, this.region.get(i), this.region.get(0)));
            }
            else{
                X = new vertice(inter(s1, s2, this.region.get(i), this.region.get(i+1)));
            }
                if(X!=null)
                    if(entrePtos(X, s1, s2))
                        ghost.add(X);
            
        }
        return ghost;
    }
   
    public vertice puntoFantasma(vertice a, vertice b){
        vertice s1 = new vertice(a);
        vertice s2 = new vertice(b);
        vertice ghost;
        for(int i=0; i<this.region.size(); i++){
            if(i==this.region.size()-1){
                ghost = new vertice(inter(s1, s2, this.region.get(i), this.region.get(0)));
            }
            else{
                ghost = new vertice(inter(s1, s2, this.region.get(i), this.region.get(i+1)));
            }
                if(ghost!=null)
                    if(entrePtos(ghost, s1, s2))
                        return ghost;
            
        }
        return null;
    }
    
    public boolean entrePtos(vertice v, vertice s1, vertice s2){
        if((v.getX()>=s1.getX()&&v.getX()<=s2.getX()&&v.getY()<=s1.getY()&&v.getY()>=s2.getY())||(v.getX()>=s2.getX()&&v.getX()<=s1.getX()&&v.getY()<=s2.getY()&&v.getY()>=s1.getY()))
            return true;
        else return false;
    }
    
    public vertice inter(vertice a, vertice b, vertice c, vertice d){
        double A = b.getY()-a.getY();
        double B = -1*(b.getX()-a.getX());
        double C = (a.getX()*A)+(a.getY()*B);
        
        double D = d.getY()-c.getY();
        double E = -1*(d.getX()-c.getX());
        double F = (c.getX()*D)+(c.getY()*E);
        
        if(((A*E)-(B*D))!=0){
        double x = ((C*E)-(B*F))/((A*E)-(B*D));
        double y = ((A*F)-(C*D))/((A*E)-(B*D));
        
        return new vertice(x, y);
        }
        else return null;
    }
    
    public ArrayList<vertice> segmentoCortado(vertice s1, vertice s2){
        ArrayList<vertice> v = new ArrayList<>();
        ArrayList<vertice> segmento = new ArrayList<>();
        if((estaIzquierda(this.region.get(0), s1, s2)&&!estaIzquierda(this.region.get(this.region.size()-1),s1, s2))||(estaIzquierda(this.region.get(this.region.size()-1),s1, s2)&&!estaIzquierda(this.region.get(0),s1, s2))||(entrePtos(this.region.get(0),s1,s2)&&entrePtos(this.region.get(this.region.size()-1),s1,s2))){
            v.add(new vertice(this.region.get(0).getX(), this.region.get(0).getY()));
            v.add(new vertice(this.region.get(this.region.size()-1).getX(), this.region.get(this.region.size()-1).getY()));
        }
        for(int i=0; i<this.region.size()-1; i++){
            if((estaIzquierda(this.region.get(i),s1, s2)&&!estaIzquierda(this.region.get(i+1),s1, s2))||(estaIzquierda(this.region.get(i+1),s1, s2)&&!estaIzquierda(this.region.get(i),s1, s2))||(entrePtos(this.region.get(i),s1,s2)&&entrePtos(this.region.get(i+1),s1,s2))){
                v.add(new vertice(this.region.get(i).getX(), this.region.get(i).getY()));
                v.add(new vertice(this.region.get(i+1).getX(), this.region.get(i+1).getY()));
            }
        }
        for(int i=0; i<v.size(); i++){
            segmento.add(v.get(i));
        }
        return segmento;
    }
    
    public void partirVacia(vertice a, vertice b){
        ArrayList<vertice> part = new ArrayList<>();
        ArrayList<vertice> v = new ArrayList<>();
        vertice s1 = new vertice(a.getX(), a.getY());
        vertice s2 = new vertice(b.getX(), b.getY());
        v.addAll(segmentoCortado(s1, s2));
        if((estaIzquierda(v.get(0), s1, s2)&&estaDerecha(v.get(1), s1, s2) || estaIzquierda(v.get(1), s1, s2)&&estaDerecha(v.get(0), s1, s2))&&distPtoRecta(s1, v.get(0), v.get(1))<distPtoRecta(s2, v.get(0), v.get(1))){
            part.add(v.get(0));
            part.add(v.get(1));
        }
        else{
            part.add(v.get(2));
            part.add(v.get(3));
        }
        if(!enLinea(s1, s2, part.get(0))&&!enLinea(s1, s2, part.get(1))){
            part.add(s1);
            mergesort(part, 0, part.size(), PuntoMenorOrdenada(part));
            AlgoritmoBR.particiones.add(new regionConvexa());
            AlgoritmoBR.particiones.get(AlgoritmoBR.particiones.size()-1).addRegion(part);
        }
        part.clear();
    }
    
    public void partirNoVacia(vertice a, vertice b){
        boolean addS1=true;
        boolean addS2=true;
        ArrayList<vertice> part = new ArrayList<>();
        vertice s1 = new vertice(a.getX(), a.getY());
        vertice s2 = new vertice(b.getX(), b.getY());
        part.addAll(this.region);
        for(int i=0; i<part.size(); i++){
            if(estaIzquierda(s1, s2, part.get(i))){
                part.remove(i);
                i--;
            }
            else
            {
                if(enLinea(s1, s2, part.get(i))){
                    if(distPtoPto(s1, part.get(i))<distPtoPto(s2, part.get(i)))
                        addS1=false;
                    else addS2=false;
                }
            }
        }
        if(addS1)part.add(s1);
        if(addS2)part.add(s2);
        mergesort(part, 0, part.size(), PuntoMenorOrdenada(part));
        AlgoritmoBR.particiones.add(new regionConvexa());
        AlgoritmoBR.particiones.get(AlgoritmoBR.particiones.size()-1).addRegion(part);
        
        for(int i=0; i<this.puntos.size(); i++){
            if(AlgoritmoBR.particiones.get(AlgoritmoBR.particiones.size()-1).Posicion(AlgoritmoBR.VGi.get(this.puntos.get(i)))!=3){
                AlgoritmoBR.particiones.get(AlgoritmoBR.particiones.size()-1).addPunto(this.puntos.get(i));
                //this.puntos.remove(i);
            }
        }
        part.clear();
    }
    
    public double distPtoPto(vertice A, vertice B){
        return Math.sqrt(Math.pow((B.getX()-A.getX()), 2)+Math.pow((B.getY()-A.getY()), 2));
    }
    
    public void mergesort(ArrayList<vertice> data, int first, int n, vertice m)
   {
      int n1; // Size of the first half of the array
      int n2; // Size of the second half of the array

      if (n > 1)
      {
         // Compute sizes of the two halves
         n1 = n / 2;
         n2 = n - n1;

         mergesort(data, first, n1, m);      // Sort data[first] through data[first+n1-1]
         mergesort(data, first + n1, n2, m); // Sort data[first+n1] to the end

         // Merge the two sorted halves.
         merge(data, first, n1, n2, m);
      }
   } 
  
   private void merge(ArrayList<vertice> data, int first, int n1, int n2, vertice m)
   {
      ArrayList<vertice> temp = new ArrayList(); // Allocate the temporary array
      int copied  = 0; // Number of elements copied from data to temp
      int copied1 = 0; // Number copied from the first half of data
      int copied2 = 0; // Number copied from the second half of data
      int i;           // Array index to copy from temp back into data

      // Merge elements, copying from two halves of data to the temporary array.
      while ((copied1 < n1) && (copied2 < n2))
      {
         if (Angulo(m,data.get(first + copied1)) < Angulo(m, data.get(first + n1 + copied2)))
            temp.add(copied++,data.get(first + (copied1++)));
         else
            temp.add(copied++,data.get(first + n1 + (copied2++)));
      }
      // Copy any remaining entries in the left and right subarrays.
      while (copied1 < n1)
         temp.add(copied++,data.get(first + (copied1++)));
      while (copied2 < n2)
         temp.add(copied++,data.get(first + n1 + (copied2++)));

      // Copy from temp back to the data array.
      for (i = 0; i < n1+n2; i++)
         data.set(first + i, temp.get(i));
   }
    
    public double Angulo(vertice A, vertice B){
        double my, mx, mb, angulo;
        my = B.getY()-A.getY();
        mx = B.getX()-A.getX();
        if(mx==0){
            if(my>0) return 90;
            else if(my<0) return 270;
            else {
                //El punto A y C son los mismos
                return 0;
            }
        }
        else if(my==0){
            if(mx>0) return 0;
            else return 180;
        }
        else{
            mb=my/mx;
            angulo=Math.atan(mb)*(180/Math.PI);
            if(mx>0){
                if(my<0) return angulo + 360;
                else return angulo;
            }
            else return angulo + 180;
        }
    }
    
    public boolean estaIzquierda(vertice A, vertice B, vertice C){
        if((((B.getX()-A.getX())*(C.getY()-A.getY()))-((B.getY()-A.getY())*(C.getX()-A.getX())))>0)
            return true;
        else return false;
    }
    public boolean estaDerecha(vertice A, vertice B, vertice C){
        if((((B.getX()-A.getX())*(C.getY()-A.getY()))-((B.getY()-A.getY())*(C.getX()-A.getX())))<0)
            return true;
        else return false;
    }
    
    public boolean enLinea(vertice A, vertice B, vertice C){
        if((((B.getX()-A.getX())*(C.getY()-A.getY()))-((B.getY()-A.getY())*(C.getX()-A.getX())))==0)
            return true;
        else return false;
    }

    public vertice PuntoMenorOrdenada(ArrayList <vertice> puntos){
        vertice menor;
        menor=puntos.get(0);
        for(int i=1; i<puntos.size(); i++){
            if(puntos.get(i).getY()<menor.getY()||((puntos.get(i).getY()==menor.getY())&&(puntos.get(i).getX()>menor.getX())))
                menor=puntos.get(i);
        }
        return menor;
    }
    public String toString(){
        String m="";
        m=m+this.region.toString()+"\nContenido = ";
        for(int i=0; i<this.puntos.size(); i++)
            m=m+AlgoritmoBR.VGi.get(this.puntos.get(i));
        return m;
    }
    
}
