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

/**
 *
 * @author Cristian
 */
import static interfaz.Interfaz.B;
import static interfaz.Interfaz.R;
import java.awt.Color;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.util.Stack;
import java.util.ArrayList;
import java.awt.BasicStroke;

public class AlgoritmoBR {

    /**
     * @param args the command line arguments
     */
    static ArrayList<vertice> VGi;
    ArrayList<vertice> VGe;
    ArrayList<arista> E_no_VGe;
    ArrayList<arista> E_no_VGi;
    ArrayList<arista> uv;
    ArrayList<rectaDual> arrangement;
    static ArrayList<regionConvexa> particiones;
    ArrayList<vertice> ConvexHull;
    long tiempoEjecucion = 0, inicio, fin, tiempoParte1 = 0, tiempoParte2 = 0, tiempoParte3 = 0, tiempoParte4 = 0, tiempoParte5 = 0;
    
    public void init() {
        VGi = new ArrayList<>();
        VGe = new ArrayList<>();
        E_no_VGe = new ArrayList<>();
        E_no_VGi = new ArrayList<>();
        uv = new ArrayList<>();
        arrangement = new ArrayList<>();
        particiones = new ArrayList<>();
        ConvexHull = new ArrayList<>();
        tiempoEjecucion = 0;
        inicio = 0;
        fin = 0;
        tiempoParte1 = 0;
        tiempoParte2 = 0;
        tiempoParte3 = 0;
        tiempoParte4 = 0;
        tiempoParte5 = 0;
    }

    /**
     * Este método permite reportar a todos los segmentos de un grafo (B) que se
     * intersecan por lo menos con algun segmento de un grafo distinto (R) en
     * complejidad de tiempo O(n^2) MENTIRA!!!! xD
     *
     * @param R - Grafo Rojo (RED)
     * @param B - Grafo Azul (BLUE)
     */
    public void BR(Grafo R, Grafo B) {
        init();
        //Grafos en consulta
        //interfaz.Interfaz.jTextArea1.append("\n" + R.toString() + "\n");
        //interfaz.Interfaz.jTextArea1.append("\n" + B.toString() + "\n");
        //Parte 1
        inicio = System.nanoTime();
        ConvexHull = R.GrahamScan();
        fin = System.nanoTime();
        tiempoParte1 = fin - inicio;

        //interfaz.Interfaz.jTextArea1.append("\nCH(R):\n");
        //interfaz.Interfaz.jTextArea1.append(ConvexHull.toString() + " ");
        //interfaz.Interfaz.jTextArea1.append("\n");


        inicio = System.nanoTime();
        setV(ConvexHull, B.vertices);
        fin = System.nanoTime();
        tiempoParte1 = tiempoParte1 + (fin - inicio);

        //interfaz.Interfaz.jTextArea1.append("\nV(Gi):\n");
        //interfaz.Interfaz.jTextArea1.append(VGi.toString());
        //interfaz.Interfaz.jTextArea1.append("\nV(Ge):\n");
        //interfaz.Interfaz.jTextArea1.append(VGe.toString());
        interfaz.Interfaz.jTextArea1.append("\nTiempo de Ejecución Parte 1: " + (float) tiempoParte1 / 1000000 + "(ms)");
        interfaz.Interfaz.jTextArea1.append("\n\n\n");


        //Parte 2
        // (a)
        if (!VGe.isEmpty()) {
            inicio = System.nanoTime();

            ArrayList<tangente> tngt = new ArrayList();
            tngt = tangentes(VGe, ConvexHull);
            tngt = OrdenRotacional(tngt);
            
            // (b)

            E_no_VGe = obtenerEGVe(tngt, ConvexHull, B);
            fin = System.nanoTime();

            tiempoParte2 = fin - inicio;
            interfaz.Interfaz.jTextArea1.append("\n\nLos Segmentos Externos: " + E_no_VGe.size());
            //  interfaz.Interfaz.jTextArea1.append("\n\nLos Segmentos Externos: " + E_no_VGe.toString());
            interfaz.Interfaz.jTextArea1.append("\nTiempo de Ejecución Parte 2: " + (float) tiempoParte2 / 1000000 + "(ms)");
        }

        //Parte 3
        if (!VGi.isEmpty()) {

            inicio = System.nanoTime();
            E_no_VGi = obtenerEGi(this.VGi, ConvexHull, R, B);
            fin = System.nanoTime();

            tiempoParte3 = fin - inicio;
            interfaz.Interfaz.jTextArea1.append("\n\nLos Segmentos Internos: " + E_no_VGi.size());
            //interfaz.Interfaz.jTextArea1.append("\n\nLos Segmentos Internos: " + E_no_VGi.toString());
            interfaz.Interfaz.jTextArea1.append("\nTiempo de Ejecución Parte 3: " + (float) tiempoParte3 / 1000000 + "(ms)");
        }

        //Parte 4

        inicio = System.nanoTime();
        uv = obtenerUv(R, B);
        fin = System.nanoTime();

        tiempoParte4 = fin - inicio;
        interfaz.Interfaz.jTextArea1.append("\n\nLos Segmentos Mixtos: " + uv.size());
        //interfaz.Interfaz.jTextArea1.append("\n\nLos Segmentos Mixtos: " + uv.toString());
        interfaz.Interfaz.jTextArea1.append("\nTiempo de Ejecución Parte 4: " + (float) tiempoParte4/1000000  + "(ms)");
        
        tiempoEjecucion=tiempoParte1+tiempoParte2+tiempoParte3+tiempoParte4;
        interfaz.Interfaz.jTextArea1.append("\n\n\n\nTiempo de Ejecución Parte 1: " + (float) tiempoParte1 / 1000000 + "(ms)");
        interfaz.Interfaz.jTextArea1.append("\nTiempo de Ejecución Parte 2: " + (float) tiempoParte2 / 1000000 + "(ms)");
        interfaz.Interfaz.jTextArea1.append("\nTiempo de Ejecución Parte 3: " + (float) tiempoParte3 / 1000000 + "(ms)");
        interfaz.Interfaz.jTextArea1.append("\nTiempo de Ejecución Parte 4: " + (float) tiempoParte4 / 1000000 + "(ms)");
        interfaz.Interfaz.jTextArea1.append("\n\nTiempo de Ejecución Total: " + (float) tiempoEjecucion / 1000000 + "(ms)");
        
        //Parte 5 
        //Ejecución del algoritmo con Conjuntos 
        if(interfaz.Interfaz.frameDibujo.isVisible()){
            Graphics g = interfaz.Interfaz.frameDibujo.getGraphics();
            Graphics2D g2=(Graphics2D) g;
            if(B.nombre=="B")g2.setColor(Color.BLUE);
            if(B.nombre=="R")g2.setColor(Color.RED);
            g2.setStroke(new BasicStroke(4));
            for(int i=0; i<this.E_no_VGe.size();i++)
            g2.drawLine((int)this.E_no_VGe.get(i).getDesde().getX()+10, (int)this.E_no_VGe.get(i).getDesde().getY()+25, (int)this.E_no_VGe.get(i).getHasta().getX()+10, (int)this.E_no_VGe.get(i).getHasta().getY()+25);
            for(int i=0; i<this.E_no_VGi.size();i++)
            g2.drawLine((int)this.E_no_VGi.get(i).getDesde().getX()+10, (int)this.E_no_VGi.get(i).getDesde().getY()+25, (int)this.E_no_VGi.get(i).getHasta().getX()+10, (int)this.E_no_VGi.get(i).getHasta().getY()+25);
            for(int i=0; i<this.uv.size();i++)
            g2.drawLine((int)this.uv.get(i).getDesde().getX()+10, (int)this.uv.get(i).getDesde().getY()+25, (int)this.uv.get(i).getHasta().getX()+10, (int)this.uv.get(i).getHasta().getY()+25);
        
        }

    }

    public void setV(ArrayList<vertice> poligono, ArrayList<vertice> puntos) {
        for (int i = 0; i < puntos.size(); i++) {
            if (estaDentro(poligono, puntos.get(i))) {
                this.VGi.add(puntos.get(i));
            } else {
                this.VGe.add(puntos.get(i));
            }
        }
    }

    public boolean estaDentro(ArrayList<vertice> poligono, vertice punto) {
        int counter = 0;
        int i;
        int n = poligono.size();
        double xinters;
        vertice p1, p2;
        p1 = poligono.get(0);
        for (i = 1; i <= n; i++) {
            p2 = poligono.get(i % n);
            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();
                            //OBS: Si los puntos en linea se cuentan dentro, se hace < xinters
                            if (p1.getX() == p2.getX() || punto.getX() <= xinters) {
                                counter++;
                            }
                        }
                    }
                }
            }
            p1 = p2;
        }
        if (counter % 2 == 0) {
            return false;
        } else {
            return true;
        }
    }

    // para paso 2
    /**
     * método de ordenamiento optimizado, modificado para almacenar el contenido
     * del ordenamiento en una Lista de indices
     *
     * @param data - Lista de datos
     * @param origin - Lista de datos originales
     * @param first - indice del primer elemento de la lista
     * @param n - tamaño de la Lista
     * @param indice - Lista de indices resultante
     */
    public void mergesort(ArrayList<vertice> data, ArrayList<vertice> origin, int first, int n, ArrayList<Integer> indice) {
        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, origin, first, n1, indice);      // Sort data[first] through data[first+n1-1]
            mergesort(data, origin, first + n1, n2, indice); // Sort data[first+n1] to the end

            // Merge the two sorted halves.
            merge(data, origin, first, n1, n2, indice);
        }
    }

    /**
     * método de ordenamiento de apoyo al método mergesort
     *
     * @param data - Lista de datos
     * @param origin - Lista de datos Originales
     * @param first - el primero de la Lista
     * @param n1 - el inicio del segmento
     * @param n2 - el final del segmento
     * @param indice - la lista de los indices resultantes
     */
    private void merge(ArrayList<vertice> data, ArrayList<vertice> origin, int first, int n1, int n2, ArrayList<Integer> indice) {
        ArrayList<vertice> temp = new ArrayList(); // Allocate the temporary array
        ArrayList<Integer> tempI = 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 (data.get(first + copied1).getX() < data.get(first + n1 + copied2).getX()) {
                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));
            indice.set(first + i, origin.indexOf(temp.get(i)));
        }

    }

    /**
     * Consulta si un vertice dado está o no a la izquierda de una recta
     *
     * @param A - primer vertice de la recta
     * @param B - segundo vertice de la recta
     * @param C - vertice a consulta
     * @return true si está a la izquierda, false si no lo está.
     */
    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;
        }
    }

    /**
     * Calcula los vertices tangententes del conjunto VGe con respecto a CH.
     *
     * @param VGe - Lista del conjunto de vertices VGe
     * @param CH - Lista de vertices que componen el CH
     * @return la Lista de tangentes izquierdas y derechas de VGe con repecto a
     * CH.
     */
    private ArrayList<tangente> tangentes(ArrayList<vertice> VGe, ArrayList<vertice> CH) {

        ArrayList<tangente> tngt = new ArrayList();

        int fila = 0;
        int i, j, k;

        ArrayList<Integer> indices = new ArrayList();

        for (i = 0; i < CH.size(); i++) {
            indices.add(i);
        }

        for (i = 0; i < VGe.size(); i++) {
            tngt.add(new tangente());
        }

        mergesort((ArrayList<vertice>) CH.clone(), CH, 0, CH.size(), indices);
        //indices con las posiciones de los puntos ordenados por el eje X
        double suma = 0;
        for (i = 0; i < CH.size(); i++) {
            suma = suma + CH.get(indices.get(i)).getX();
        }
        suma = suma / i;

        for (int p = 0; p < VGe.size(); p++) {
            //resguardos para los indices ordenados por eje X
            if (VGe.get(p).getX() <= suma) {
                for (i = 0; i < CH.size(); i++) {
                    //resguardos para hacer los calculos en el array lineal
                    if (indices.get(i) == 0) {
                        j = CH.size();
                        k = indices.get(i);
                    } else {
                        if (indices.get(i) == CH.size() - 1) {
                            j = indices.get(i);
                            k = -1;
                        } else {
                            j = indices.get(i);
                            k = indices.get(i);
                        }
                    }


                    if (estaIzquierda(CH.get(j - 1), CH.get(indices.get(i)), VGe.get(p)) && !estaIzquierda(CH.get(indices.get(i)), CH.get(k + 1), VGe.get(p))) {
                        tngt.get(fila).setP(VGe.get(p));
                        tngt.get(fila).setTan_der(CH.get(indices.get(i)));
                    } else {
                        if (!estaIzquierda(CH.get(j - 1), CH.get(indices.get(i)), VGe.get(p)) && estaIzquierda(CH.get(indices.get(i)), CH.get(k + 1), VGe.get(p))) {
                            tngt.get(fila).setP(VGe.get(p));
                            tngt.get(fila).setTan_izq(CH.get(indices.get(i)));
                        }
                    }
                    if (tngt.get(fila).estaCompleto()) {
                        i = CH.size();
                    }
                }
            } else {
                for (i = CH.size() - 1; i >= 0; i--) {
                    //resguardos para hacer los calculos en el array lineal
                    if (indices.get(i) == 0) {
                        j = CH.size();
                        k = indices.get(i);
                    } else {
                        if (indices.get(i) == CH.size() - 1) {
                            j = indices.get(i);
                            k = -1;
                        } else {
                            j = indices.get(i);
                            k = indices.get(i);
                        }
                    }

                    if (estaIzquierda(CH.get(j - 1), CH.get(indices.get(i)), VGe.get(p)) && !estaIzquierda(CH.get(indices.get(i)), CH.get(k + 1), VGe.get(p))) {
                        tngt.get(fila).setP(VGe.get(p));
                        tngt.get(fila).setTan_der(CH.get(indices.get(i)));
                    } else {
                        if (!estaIzquierda(CH.get(j - 1), CH.get(indices.get(i)), VGe.get(p)) && estaIzquierda(CH.get(indices.get(i)), CH.get(k + 1), VGe.get(p))) {
                            tngt.get(fila).setP(VGe.get(p));
                            tngt.get(fila).setTan_izq(CH.get(indices.get(i)));
                        }
                    }

                    if (tngt.get(fila).estaCompleto()) {
                        i = -1;
                    }
                }
            }
            if (tngt.get(fila).estaCompleto()) {
                fila++;
            }

        }
        return tngt;
    }

    /**
     * Método de ordenamiento optimizado, modificado para ordenar una lista de
     * tangentes
     *
     * @param data - Lista de datos
     * @param first - el indice del primer elemento
     * @param n - cantidad de elementos de la Lista
     */
    public void mergesort(ArrayList<tangente> data, int first, int n) {
        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);      // Sort data[first] through data[first+n1-1]
            mergesort(data, first + n1, n2); // Sort data[first+n1] to the end

            // Merge the two sorted halves.
            merge(data, first, n1, n2);
        }
    }

    /**
     * Método de Ordenamiento Optimizado de apoyo a mergesort
     *
     * @param data - Lista de datos
     * @param first - el primer elemento de la Lista
     * @param n1 - indice de inicio del segmento
     * @param n2 - indice de termino del segmento
     */
    private void merge(ArrayList<tangente> data, int first, int n1, int n2) {
        ArrayList<tangente> 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 (data.get(first + copied1).getM() < data.get(first + n1 + copied2).getM()) {
                if (data.get(first + copied1).getM() == 0 && data.get(first + copied1).esInfinita()) {
                    temp.add(copied++, data.get(first + n1 + (copied2++)));
                } else {
                    temp.add(copied++, data.get(first + (copied1++)));
                }
            } else {
                if (data.get(first + n1 + copied2).getM() == 0 && data.get(first + n1 + copied2).esInfinita()) {
                    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));
        }

    }

    /**
     * Método que obtiene el orden rotacional de VGe con respecto a CH, en
     * concreto
     *
     * @param origen
     * @return
     */
    private ArrayList<tangente> OrdenRotacional(ArrayList<tangente> origen) {
        //acomodo de los datos del arreglo
        //System.out.println("Origen (kisawea xd) = "+origen.toString());
        int n = origen.size();
        for (int i = 0; i < n; i++) {
            tangente a = new tangente();
            a.setP(origen.get(i).getP());
            a.setTan_izq(origen.get(i).getTan_der());
            origen.add(i + n, a);
        }
        //ordenamientos
        mergesort(origen, 0, origen.size());

        //reacomodo de lista (a partir de cero)
        n = origen.size();
        while (origen.get(0).getM() < 0) {
            origen.add(n, origen.get(0));
            origen.remove(0);
        }

        return origen;
    }

    /**
     * Este método realiza una comparación de los puntos externos con la
     * cerradura convexa para determinar los segmentos azules que intersecan a
     * la cerradura convexa. para ello utiliza un cáliper Rotatorio que gira
     * bajo el orden rotacional dado determinando los puntos que estan de un
     * lado al otro dentro de las líneas paralelas de soporte del Cáliper
     * Rotatorio.
     *
     * @param OR Orden Rotacional de los Puntos Azules Externos con respecto a
     * CH(R)
     * @param CH la Cerradura Convexa del Grafo Rojo
     * @param B El Grafo Azul.
     * @return Un Arreglo de los segmentos azules externos que atraviesan a
     * CH(R).
     */
    public ArrayList<arista> obtenerEGVe(ArrayList<tangente> OR, ArrayList<vertice> CH, Grafo B) {
        ArrayList<arista> EGVe = new ArrayList();
        boolean mediaVuelta = false;

        CaliperRotatorio CR = new CaliperRotatorio();
        //busca caliper horizontal
        CR.buscarAntipodal(CH.get(0), CH);

        for (int i = 0; i < OR.size(); i++) {
            CR.ingresa(OR.get(i).getP());

            //mover caliper
            CR.girar(OR.get(i), CH);

            for (int k = 0; k < CR.elementosDentro() - 1; k++) {
                if (CR.estaDentro(CR.getElementoDentro(k), OR.get(i))) {
                    arista aIntersectar = B.esArista(CR.getElementoDentro(k), CR.getElementoDentro(CR.elementosDentro() - 1));
                    if (aIntersectar != null) {
                        if (CR.intersectaCon(aIntersectar)) {
                            if (!EGVe.contains(aIntersectar)) {
                                EGVe.add(aIntersectar);
                            }

                            if (CH.size() == 2) {
                                return EGVe;
                            }
                        }
                    }
                } else {
                    CR.saleDentro(k);
                    k--;
                }
            }

            if (i == OR.size() - 1 && mediaVuelta == false) {
                i = -1;
                mediaVuelta = true;
            }
        }
        return EGVe;
    }

    public ArrayList<arista> obtenerEGi(ArrayList<vertice> VGi, ArrayList<vertice> CH, Grafo R, Grafo B) {
        //(a)
        crearArrangement(R.vertices, VGi);
        int pos;
        this.particiones.add(new regionConvexa());
        this.particiones.get(0).addRegion(CH);
        this.particiones.get(0).addPunto(0);
        //(b)
        ArrayList<dualRojo> OR = new ArrayList<>();
        for (int k = 1; k < VGi.size(); k++) {
            //(i)
            pos = buscaRegion(VGi.get(k), this.particiones);
            //(ii)
            if (this.particiones.get(pos).esVacia()) {
                this.particiones.get(pos).addPunto(k);
            } else {
                OR.addAll(getOR(arrangement.get(particiones.get(pos).puntos.get(0)).getRojo(), arrangement.get(k).getRojo()));
                ArrayList<tangente> tngt = new ArrayList<>();
                for (int i = 0; i < OR.size(); i++) {
                    tngt.add(new tangente());
                    tngt.get(i).setP(OR.get(i).getROJO());
                    tngt.get(i).setTan_izq(OR.get(i).getAzul());
                    tngt.get(i).setM_izq(OR.get(i).getInter().getX());
                }
                OR.clear();
                ArrayList<vertice> blue = new ArrayList<>();
                blue.add(arrangement.get(particiones.get(pos).puntos.get(0)).getAzul());
                blue.add(arrangement.get(k).getAzul());
                //(B)
                ArrayList<arista> div = new ArrayList<>();
                div = obtenerEGVe(tngt, blue, R);
                //(C)
                if (!div.isEmpty()) {
                    particiones.get(pos).addPunto(k);
                    particiones.get(pos).Particion(div.get(0).getDesde(), div.get(0).getHasta());
                    particiones.remove(pos);
                } else {
                    particiones.get(pos).addPunto(k);
                }
            }
        }
        ArrayList<arista> EGi = new ArrayList<>();
        for (int i = 0; i < VGi.size(); i++) {
            for (int j = i; j < VGi.size(); j++) {
                if ((buscaRegion(VGi.get(i), this.particiones) != buscaRegion(VGi.get(j), this.particiones)) && B.esArista(VGi.get(i), VGi.get(j)) != null) {
                    EGi.add(new arista(VGi.get(i), VGi.get(j)));
                }
            }
        }
        this.particiones.clear();
        return EGi;
    }

    public ArrayList<arista> obtenerUv(Grafo R, Grafo B) {
        ArrayList<arista> uv = new ArrayList<>();
        ArrayList<arista> azulUv = new ArrayList<>();
        ArrayList<arista> rojoUv = new ArrayList<>();
        //obtención segmentos mixtos
        for (int i = 0; i < VGe.size(); i++) {
            for (int j = 0; j < VGi.size(); j++) {
                if (B.esArista(VGe.get(i), VGi.get(j)) != null) {
                    azulUv.add(new arista(VGe.get(i), VGi.get(j)));
                }
            }
        }
        //obtencion segmentos rojos
        for (int i = 0; i < R.vertices.size(); i++) {
            for (int j = i; j < R.vertices.size(); j++) {
                if (R.esArista(R.vertices.get(i), R.vertices.get(j)) != null) {
                    rojoUv.add(new arista(R.vertices.get(i), R.vertices.get(j)));
                }
            }
        }
        for (int i = 0; i < azulUv.size(); i++) {
            for (int j = 0; j < rojoUv.size(); j++) {
                if (!uv.contains(azulUv.get(i))) {
                    if ((estaIzquierda(azulUv.get(i).getDesde(), azulUv.get(i).getHasta(), rojoUv.get(j).getDesde()) && !estaIzquierda(azulUv.get(i).getDesde(), azulUv.get(i).getHasta(), rojoUv.get(j).getHasta())) || (estaIzquierda(azulUv.get(i).getDesde(), azulUv.get(i).getHasta(), rojoUv.get(j).getHasta()) && !estaIzquierda(azulUv.get(i).getDesde(), azulUv.get(i).getHasta(), rojoUv.get(j).getDesde()))) {
                        if ((estaIzquierda(rojoUv.get(j).getDesde(), rojoUv.get(j).getHasta(), azulUv.get(i).getDesde()) && !estaIzquierda(rojoUv.get(j).getDesde(), rojoUv.get(j).getHasta(), azulUv.get(i).getHasta())) || (estaIzquierda(rojoUv.get(j).getDesde(), rojoUv.get(j).getHasta(), azulUv.get(i).getHasta()) && !estaIzquierda(rojoUv.get(j).getDesde(), rojoUv.get(j).getHasta(), azulUv.get(i).getDesde()))) {
                            uv.add(azulUv.get(i));
                        }
                    }
                }
            }
        }

        return uv;
    }

    public static int buscaRegion(vertice azul, ArrayList<regionConvexa> particiones) {
        for (int i = 0; i < particiones.size(); i++) {
            if (particiones.get(i).Posicion(azul) == 1 || particiones.get(i).Posicion(azul) == 2) {
                return i;
            }
        }
        return 0;
    }

    public ArrayList<dualRojo> getOR(ArrayList<dualRojo> bj, ArrayList<dualRojo> bk) {
        ArrayList<dualRojo> OR = new ArrayList<>();
        ArrayList<dualRojo> Pos = new ArrayList<>();
        ArrayList<dualRojo> Neg = new ArrayList<>();
        ArrayList<dualRojo> IP = new ArrayList<>();
        ArrayList<dualRojo> IN = new ArrayList<>();
        for (int i = 0; i < bj.size(); i++) {
            if (bj.get(i).interAzul.getX() < 0) {
                if (bj.get(i).interAzul.getX() == Double.NEGATIVE_INFINITY) {
                    IN.add(bj.get(i));
                } else {
                    Neg.add(bj.get(i));
                }
            } else {
                if (bj.get(i).interAzul.getX() == Double.POSITIVE_INFINITY) {
                    IP.add(bj.get(i));
                } else {
                    Pos.add(bj.get(i));
                }
            }
        }
        for (int i = 0; i < bk.size(); i++) {
            if (bk.get(i).interAzul.getX() < 0) {
                if (bk.get(i).interAzul.getX() == Double.NEGATIVE_INFINITY) {
                    IN.add(bk.get(i));
                } else {
                    Neg.add(bk.get(i));
                }
            } else {
                if (bk.get(i).interAzul.getX() == Double.POSITIVE_INFINITY) {
                    IP.add(bk.get(i));
                } else {
                    Pos.add(bk.get(i));
                }
            }
        }
        mergesort2(Pos, 0, Pos.size());
        mergesort2(Neg, 0, Neg.size());
        OR.addAll(Neg);
        OR.addAll(IN);
        OR.addAll(IP);
        OR.addAll(Pos);



        //Ordenar OR
        return OR;
    }

    /**
     * Método que crea un arreglo dual de líneas a partir de los puntos rojos y
     * VGi
     *
     * @param R
     * @param VGi
     */
    public void crearArrangement(ArrayList<vertice> R, ArrayList<vertice> VGi) {

        for (int i = 0; i < VGi.size(); i++) {
            rectaDual aux = new rectaDual(VGi.get(i), R);
            arrangement.add(aux);
        }
    }

    public void mergesort2(ArrayList<dualRojo> data, int first, int n) {
        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;

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

            // Merge the two sorted halves.
            merge2(data, first, n1, n2);
        }
    }

    private void merge2(ArrayList<dualRojo> data, int first, int n1, int n2) {
        ArrayList<dualRojo> 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 ((data.get(first + copied1).getInter().getX() > data.get(first + n1 + copied2).getInter().getX()) || ((data.get(first + copied1).getInter().getX() == data.get(first + n1 + copied2).getInter().getX()) && (data.get(first + copied1).getInter().getY() < data.get(first + n1 + copied2).getInter().getY()))) {
                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 long gettiempo()
    {
        return tiempoEjecucion;
    }

    public void destruir() {
        E_no_VGe = null;
        E_no_VGi = null;
        VGe = null;
        VGi = null;
        arrangement.clear();
        particiones.clear();
        uv.clear();
        tiempoEjecucion = 0;
        inicio = 0;
        fin = 0;
        tiempoParte1 = 0;
        tiempoParte2 = 0;
        tiempoParte3 = 0;
        tiempoParte4 = 0;
        tiempoParte5 = 0;
    }
}
