package compGeo;

import java.awt.Color;
import java.awt.Point;
import java.util.ArrayList;
import java.util.Vector;

public class Qh extends Algorithm {

    boolean done = false;
    GeoComp GeoC;
    ArrayList<Point> points;
    int size, pNum;
    int ii = 0;
    ArrayList<Point> leftSet = new ArrayList<Point>();
    ArrayList<Point> rightSet = new ArrayList<Point>();

    public Qh(GeoComp app) {
        GeoC = app;
    }

    @Override
    public void start(Vector v) {
        size = v.size();
        points = new ArrayList<Point>(size);
        for (int i = 0; i < size; i++) {
            points.add((Point) v.elementAt(i));
        }
        pNum = GeoC.points.size();
        done = false;

    }

    @Override
    public void nextStep() {
        ArrayList<Point> convexHull = new ArrayList<Point>();
        // find extremals
        int minPoint = -1, maxPoint = -1;
        int minX = Integer.MAX_VALUE;
        int maxX = Integer.MIN_VALUE;
        //System.out.println(pNum);
        //System.out.println(points.size());
        for (int i = 0; i < points.size(); i++) {
            // if (i < pNum - 1) {
            // System.out.println(points.size() + " p.size()");
            if (points.get(i).x < minX) {
                minX = points.get(i).x;
                minPoint = i;
                // GeoC.rysujPunkt(points[minPoint], Color.green);
                // System.out.print("minX: " + minX + " minPoint: " + minPoint +
                // "\n");
            }
            if (points.get(i).x > maxX) {
                maxX = points.get(i).x;
                maxPoint = i;
                // GeoC.rysujPunkt(points[maxPoint], Color.green);
                i++;
            }
            // } else {
            // done = true;

        }
        // }

        if (minPoint != -1 && maxPoint != -1) {
            // System.out.print("minPoint: " + minPoint + " maxPoint: " +
            // maxPoint);

            // return;

            // System.out.println("minPoint: " + minPoint + " maxPoint: " +
            // maxPoint);
            if(ii == 0)
                GeoC.rysujLinie(points.get(minPoint), points.get(maxPoint), Color.red);
            Point A = points.get(minPoint);
            Point B = points.get(maxPoint);
            convexHull.add(A);
            convexHull.add(B);

            //points.remove(A);
            //points.remove(B);

            // for (int i = 0; i < pNum; i++) {
            if (ii < points.size()) {
                Point p = points.get(ii);
                if (pointLocation(A, B, p) == -1) {
                    // System.out.print(pointLocation(A, B, p) + "\n");
                    leftSet.add(p);
                    GeoC.rysujPunkt(p, Color.red);
                } else {
                    rightSet.add(p);
                    //GeoC.rysujPunkt(p, Color.blue);
                }
                ii++;


            } else {
                System.out.println("rightSet: " + rightSet.size());
                System.out.println("leftSet: " + leftSet.size());
                hullSet(A, B, rightSet, convexHull);
                hullSet(B, A, leftSet, convexHull);
                ii = 0;
                done = true;
            }

            /*// }
            hullSet(A, B, rightSet, convexHull);
            hullSet(B, A, leftSet, convexHull);*/
        } else {
            ii = 0;
        }

        // done = true;

    }

    @Override
    public boolean isDone() {
        return done;
    }

    /*
     * public ArrayList<Point> quickHull(ArrayList<Point> points) {
     * ArrayList<Point> convexHull = new ArrayList<Point>(); if (points.size() <
     * 3) return (ArrayList) points.clone(); // find extremals int minPoint =
     * -1, maxPoint = -1; int minX = Integer.MAX_VALUE; int maxX =
     * Integer.MIN_VALUE; for (int i = 0; i < points.size(); i++) { if
     * (points.get(i).x < minX) { minX = points.get(i).x; minPoint = i; } if
     * (points.get(i).x > maxX) { maxX = points.get(i).x; maxPoint = i; } }
     * Point A = points.get(minPoint); Point B = points.get(maxPoint);
     * convexHull.add(A); convexHull.add(B); points.remove(A); points.remove(B);
     *
     * ArrayList<Point> leftSet = new ArrayList<Point>(); ArrayList<Point>
     * rightSet = new ArrayList<Point>();
     *
     * for (int i = 0; i < points.size(); i++) { Point p = points.get(i); if
     * (pointLocation(A, B, p) == -1) leftSet.add(p); else rightSet.add(p); }
     * hullSet(A, B, rightSet, convexHull); hullSet(B, A, leftSet, convexHull);
     *
     * return convexHull; }
     */
    /*
     * Computes the square of the distance of point C to the segment defined by
     * points AB
     */
    public int distance(Point A, Point B, Point C) {
        int ABx = B.x - A.x;
        int ABy = B.y - A.y;
        int num = ABx * (A.y - C.y) - ABy * (A.x - C.x);
        if (num < 0)
            num = -num;
        return num;
    }

    public void hullSet(Point A, Point B, ArrayList<Point> set,
            ArrayList<Point> hull) {
        System.out.println(set.size());
        int insertPosition = hull.indexOf(B);
        if (set.size() == 0) {
            // System.out.println("151");
            return;
        }
        if (set.size() == 1) {
            // System.out.println("155");
            Point p = set.get(0);
            set.remove(p);
            hull.add(insertPosition, p);
            return;
        }
        int dist = Integer.MIN_VALUE;
        int furthestPoint = -1;
        for (int i = 0; i < set.size(); i++) {
            Point p = set.get(i);
            int distance = distance(A, B, p);
            if (distance > dist) {
                dist = distance;
                furthestPoint = i;
            }
        }
        Point P = set.get(furthestPoint);
        set.remove(furthestPoint);
        hull.add(insertPosition, P);

        // Determine who's to the left of AP
        ArrayList<Point> leftSetAP = new ArrayList<Point>();

        //System.out.println(set.size());

        for (int i = 0; i < set.size(); i++) {
            // System.out.println("178");
            Point M = set.get(i);
            if (pointLocation(A, P, M) == 1) {
                leftSetAP.add(M);
                GeoC.rysujLinie(M, A, Color.red);
                GeoC.rysujLinie(P, M, Color.red);
                //System.out.println("sgdf");
            }

        }

        // Determine who's to the left of PB
        ArrayList<Point> leftSetPB = new ArrayList<Point>();
        for (int i = 0; i < set.size(); i++) {
            Point M = set.get(i);
            if (pointLocation(P, B, M) == 1) {
                leftSetPB.add(M);
                GeoC.rysujLinie(M, P, Color.red);
                GeoC.rysujLinie(B, M, Color.red);
            }
        }
        hullSet(A, P, leftSetAP, hull);
        hullSet(P, B, leftSetPB, hull);

    }

    public int pointLocation(Point A, Point B, Point P) {
        int cp1 = (A.x - B.x) * (P.y - B.y) - (P.x - B.x) * (A.y - B.y);
        return (cp1 > 0) ? 1 : -1;
    }

}