//
//  main.cpp
//  cg5
//
//  Created by Kate Repekh on 3/23/19.
//  Copyright © 2019 Kate Repekh. All rights reserved.
//
#ifdef __APPLE_CC__
#include <GLUT/glut.h>
#else
#include <GL/glut.h>
#endif
#include <iostream>
#include "Point.hpp"

const int maxNumOfPointsToDivide = 6;

void drawPoint(Point p) {
    glColor3f(0.0, 0.0, 1.0);
    glPointSize(5);
    glBegin(GL_POINTS);
    glVertex2f(p.getX(), p.getY());
    glEnd();
    glFlush();
}

void drawPoints(std::vector<Point> points) {
    glColor3f(1.0, 1.0, 1.0);
    glPointSize(2);
    glBegin(GL_POINTS);
    for (int i = 0; i < points.size(); ++i)
        glVertex2f(points[i].getX(),points[i].getY());
    glEnd();
    glFlush();
}

void drawPolygon(std::vector<Point> points, float color) {
    std::cout << "----------------" << std::endl;
    glColor3f(float(rand())/RAND_MAX, float(rand())/RAND_MAX, float(rand())/RAND_MAX);
    glPointSize(3);
    glBegin(GL_LINES);
    for (int i = 0; i < points.size() - 1; ++i) {
        std::cout << points[i].getX() << " " << points[i].getY() << std::endl;
        glVertex2f(points[i].getX(), points[i].getY());
        glVertex2f(points[i+1].getX(), points[i+1].getY());
    }
    std::cout << points[points.size()-1].getX() << " " << points[points.size()-1].getY() << std::endl;
    std::cout << "----------------" << std::endl;
    glEnd();
    glFlush();
}

std::vector<Point> jarvisHull(std::vector<Point> points) {
    std::cout << "---jarvis---" << std::endl;
    for (int i = 0; i < points.size(); ++i)
        points[i].print();
    std::cout << "---" << std::endl;
    Point lowestPoint = Point::getLowestPoint(points);
    Point highestPoint = Point::getHighestPoint(points);
    std::vector<Point> hull;
    hull.push_back(highestPoint);
    if (points.size() == 3) {
        hull.push_back(lowestPoint);
        Point middlePoint = lowestPoint;
        for (int i = 0; i < 3; ++i)
            if (!points[i].equals(highestPoint) && !points[i].equals(lowestPoint))
                middlePoint = points[i];
        hull.push_back(middlePoint);
        if (!Point::isRightPoint(lowestPoint, highestPoint, middlePoint))
            std::swap(hull[1], hull[2]);
        hull.push_back(highestPoint);
        return hull;
    }

    std::vector<Point> leftPoints = Point::getRightPoints(highestPoint, lowestPoint, points);
    leftPoints.push_back(lowestPoint);
    if (leftPoints.size() > 1) {
        leftPoints.push_back(lowestPoint);
        Point curPoint = highestPoint;
        std::cout << "cur point: ";
        curPoint.print();
        while (!curPoint.equals(lowestPoint)) {
            curPoint.print();
            float minPolarAngle = 3 * M_PI;
            Point closestPoint = leftPoints[0];
            for (std::vector<Point>::iterator it = leftPoints.begin(); it != leftPoints.end(); ++it) {
                it->print();
                float polarAngle = it->getPolarAngle(curPoint);
                std::cout << polarAngle << std::endl;
                if (polarAngle < minPolarAngle && curPoint.getY() > it->getY() && !it->equals(curPoint)) {
                    minPolarAngle = polarAngle;
                    closestPoint = *it;
                }
            }
            if (minPolarAngle == 3 * M_PI)
                std::cout << "ERROR: NO CLOSE LEFT POINT FOUND" << std::endl;
            hull.push_back(closestPoint);
            curPoint = closestPoint;
            std::cout << "cur point: ";
            curPoint.print();
        }
    }

    std::vector<Point> rightPoints = Point::getRightPoints(lowestPoint, highestPoint, points);
    rightPoints.push_back(highestPoint);
    if (rightPoints.size() > 1) {
        rightPoints.push_back(highestPoint);
        Point curPoint = lowestPoint;
        std::cout << "cur point: ";
        curPoint.print();
        while (!curPoint.equals(highestPoint)) {
            float minPolarAngle = 3 * M_PI;
            Point closestPoint = rightPoints[0];
            for (std::vector<Point>::iterator it = rightPoints.begin(); it != rightPoints.end(); ++it) {
                it->print();
                float polarAngle = it->getPolarAngle(curPoint);
                std::cout << polarAngle << std::endl;
                if (polarAngle < minPolarAngle && curPoint.getY() < it->getY() && !it->equals(curPoint)) {
                    minPolarAngle = polarAngle;
                    closestPoint = *it;
                }
            }
            if (minPolarAngle == 3 * M_PI)
                std::cout << "ERROR: NO CLOSE RIGHT POINT FOUND" << std::endl;
            hull.push_back(closestPoint);
            curPoint = closestPoint;
            std::cout << "cur point: ";
            curPoint.print();
        }
    }
    return hull;
}

std::vector<Point> grahamScan(std::vector<Point> points) {
    points.insert(points.begin(), points[points.size()-1]);
    std::cout << "-----graham scan-----" << std::endl;
    for (int i = 0; i < points.size(); ++i)
        points[i].print();
    int M = 2;
    for (int i = 3; i < points.size(); ++i) {
        while (Point::getSignedTriangleArea(points[M-1], points[M], points[i]) <= 0)
            --M;
        ++M;
        std::cout << "swapping these points " << M << " and " << i << std::endl;
        points[M].print();
        points[i].print();
        std::swap(points[M], points[i]);
    }
    std::cout << "M" << M << std::endl;
    points = std::vector<Point>(points.begin(), points.begin() + M + 1);
    return points;
}

std::vector<Point> mergeHulls(std::vector<Point> s1, std::vector<Point> s2) {
    std::cout << "s1:" << std::endl;
    glLineWidth(3);
    drawPolygon(s1, 0.0);
    std::cout << "s2:" << std::endl;
    drawPolygon(s2, 0.5);
    Point leftPoint1 = Point::getLeftPoint(s1);
    Point leftPoint2 = Point::getLeftPoint(s2);
    if (leftPoint1.getX() > leftPoint2.getX())
        std::swap(s1, s2);
    Point p = Point::getCentroid(s1[0], s1[1], s1[2]);
    std::cout << "centroid: ";
    p.print();
    drawPoint(p);
    if (!p.isInsidePolygon(s2)) {
        std::cout << "centroid is outside of s2" << std::endl;
        for (int i = 0; i < s2.size() - 1; ++i)
            if (Point::getSignedTriangleArea(p, s2[i], s2[i+1]) < 0) {
                s2.erase(s2.begin() + i);
                --i;
            }
    }
    s1.pop_back();
    if (s2[0].equals(s2[s2.size()-1]))
        s2.pop_back();
    s1.insert(s1.end(), s2.begin(), s2.end());
    std::cout << "-----before sort-----" << std::endl;
    for (int i = 0; i < s1.size(); ++i)
        s1[i].print();
    Point lowestPoint = Point::getLowestPoint(s1);
    lowestPoint = Point(lowestPoint.getX(), lowestPoint.getY()-0.01);
    sort(s1.begin(), s1.end(), [lowestPoint](Point &a, Point &b) {
                                return a.getPolarAngle(lowestPoint) <
                                       b.getPolarAngle(lowestPoint);});
    std::cout << "-----after sort-----" << std::endl;
    for (int i = 0; i < s1.size(); ++i)
        s1[i].print();
    return grahamScan(s1);
}

std::vector<Point> divideAndRule(std::vector<Point> points) {
    if (points.size() <= maxNumOfPointsToDivide)
        return jarvisHull(points);
    std::vector<Point> s1, s2;
    for (int i = 0; i < points.size(); ++i)
        if (i % 2 == 0)
            s1.push_back(points[i]);
        else
            s2.push_back(points[i]);
    return mergeHulls(divideAndRule(s1), divideAndRule(s2));
}

void init(std::vector<Point> &points) {
    points = std::vector<Point>();
    points.push_back(Point(0.9, 0.0));//
    points.push_back(Point(0.8, 0.1));
    points.push_back(Point(0.0, 0.21));//
    points.push_back(Point(0.1, 0.15));
    points.push_back(Point(0.3, 0.45));//
    points.push_back(Point(0.6, 0.6));//
    points.push_back(Point(0.2, 0.5));
    points.push_back(Point(0.5, 0.6));
    points.push_back(Point(0.7, 0.7));
    points.push_back(Point(-0.1, 0.8));
    points.push_back(Point(0.4, 0.9));
    drawPoints(points);
}

void drawCoordinates() {
    glColor3f(1.0, 1.0, 1.0);
    for(float i = -1.0; i < 1.0; i+=0.1) {
        glBegin(GL_LINES);

        glVertex2f(i, 0.01f);
        glVertex2f(i, -0.01f);

        glVertex2f(0.01f,  i);
        glVertex2f(-0.01f, i);
        glEnd();
        glFlush();
    }
}

void display() {

    glClear(GL_COLOR_BUFFER_BIT);

    glColor3f(1.0, 0.0, 0.0);
    glBegin(GL_LINES);

    glVertex2f(-4.0, 0.0f);
    glVertex2f(4.0, 0.0f);

    glVertex2f(4.0, 0.0f);
    glVertex2f(3.0, -1.0f);
    glEnd();
    glFlush();

    glColor3f(0.0, 1.0, 0.0);
    glBegin(GL_LINES);
    glVertex2f(0.0, -4.0f);
    glVertex2f(0.0, 4.0f);

    glVertex2f(0.0, 4.0f);
    glVertex2f(1.0, 3.0f);

    glVertex2f(0.0, 4.0f);
    glVertex2f(-1.0, 3.0f);
    glEnd();
    glFlush();

    drawCoordinates();
    std::vector<Point> points;
    init(points);
    std::vector<Point> hull = divideAndRule(points);
    glLineWidth(2);
    drawPolygon(hull, 1.0);
    init(points);
}

int main(int argc, char** argv) {
    srand(time(0));

    glutInit(&argc, argv);
    glutInitDisplayMode(GLUT_SINGLE | GLUT_RGB);

    glutInitWindowPosition(80, 80);
    glutInitWindowSize(800, 800);
    glutCreateWindow("Quick Hull");

    glutDisplayFunc(display);

    glutMainLoop();
}


//
//  Point.hpp
//  cg6
//
//  Created by Kate Repekh on 3/23/19.
//  Copyright © 2019 Kate Repekh. All rights reserved.
//

#ifndef Point_hpp
#define Point_hpp

#include <vector>
#include <cmath>
#include <iostream>

class Point {

private:
    float x;
    float y;

public:
    Point (float x, float y);
    float getX();
    float getY();
    float getPolarAngle(Point zero);
    static Point getCentroid(Point a, Point b, Point c);
    bool equals(Point anotherPoint);
    bool isInsidePolygon(std::vector<Point> vertices);
    void print();
    static float getSignedTriangleArea(Point a, Point b, Point c);
    static Point getLeftPoint(std::vector<Point> points);
    static Point getRightPoint(std::vector<Point> points);
    static Point getHighestPoint(std::vector<Point> points);
    static Point getLowestPoint(std::vector<Point> points);
    static Point getPointFarthestFromLine(Point a, Point b, std::vector<Point> points);
    static std::vector<Point> getRightPoints(Point a, Point b, std::vector<Point> points);
    static bool isRightPoint(Point a, Point b, Point point);
};

#endif /* Point_hpp */


//
//  Point.cpp
//  cg6
//
//  Created by Kate Repekh on 3/23/19.
//  Copyright © 2019 Kate Repekh. All rights reserved.
//

#include "Point.hpp"

Point::Point(float _x, float _y) {
    x = _x;
    y = _y;
}

float Point::getX() {
    return x;
}

float Point::getY() {
    return y;
}

float Point::getPolarAngle(Point zero) {
    float newx = x - zero.getX();
    float newy = y - zero.getY();
    if (newx > 0) {
        if (newy >= 0)
            return atan(newy/newx);
        else
            return atan(newy/newx) + 2 * M_PI;
    }
    else if (newx < 0)
        return atan(newy/newx) + M_PI;
    else if (newy > 0)
        return M_PI / 2;
    else return 3 * M_PI / 2;
}

Point Point::getLowestPoint(std::vector<Point> points) {
    Point lowestPoint = points[0];
    for (std::vector<Point>::iterator it = points.begin() + 1; it != points.end(); ++it)
        if (it->getY() < lowestPoint.getY())
            lowestPoint = *it;
    std::cout << "lowest point: " << lowestPoint.getX() << " " << lowestPoint.getY() << std::endl;
    return lowestPoint;
}

Point Point::getHighestPoint(std::vector<Point> points) {
    Point highestPoint = points[0];
    for (std::vector<Point>::iterator it = points.begin() + 1; it != points.end(); ++it)
        if (it->getY() > highestPoint.getY())
            highestPoint = *it;
    std::cout << "highest point: " << highestPoint.getX() << " " << highestPoint.getY() << std::endl;
    return highestPoint;
}

Point Point::getLeftPoint(std::vector<Point> points) {
    Point leftPoint = points[0];
    for (std::vector<Point>::iterator it = points.begin() + 1; it != points.end(); ++it)
        if (it->getX() < leftPoint.getX())
            leftPoint = *it;
    std::cout << "left point: " << leftPoint.getX() << " " << leftPoint.getY() << std::endl;
    return leftPoint;
}

Point Point::getRightPoint(std::vector<Point> points) {
    Point rightPoint = points[0];
    for (std::vector<Point>::iterator it = points.begin() + 1; it != points.end(); ++it)
        if (it->getX() > rightPoint.getX())
            rightPoint = *it;
    std::cout << "right point: " << rightPoint.getX() << " " << rightPoint.getY() << std::endl;
    return rightPoint;
}

Point Point::getPointFarthestFromLine(Point a, Point b, std::vector<Point> points) {
    float A = (a.getY() - b.getY()) / (b.getX() - a.getX());
    float C = - A * a.getX() - a.getY();
    Point farthestPoint = points[0];
    float maxDistance = fabs(A * farthestPoint.getX() + farthestPoint.getY() + C) / sqrt(A*A + 1);
    for (std::vector<Point>::iterator it = points.begin()+1; it != points.end(); ++it) {
        float curDistance = fabs(A * it->getX() + it->getY() + C) / sqrt(A*A + 1);
        if (curDistance > maxDistance) {
            farthestPoint = *it;
            maxDistance = curDistance;
        }
    }
    std::cout << "farthest point: " << farthestPoint.getX() << " " << farthestPoint.getY() << std::endl;
    return farthestPoint;
}

bool Point::isRightPoint(Point a, Point b, Point point) {
    float K = (a.getY() - b.getY()) / (a.getX() - b.getX());
    float B = a.getY() - K * a.getX();
    float x = (point.getY() - B) / K;
    if (a.getY() > b.getY())
        return x > point.getX();
    else return x < point.getX();
}

bool Point::equals(Point anotherPoint) {
    return (x == anotherPoint.getX() && y == anotherPoint.getY());
}

std::vector<Point> Point::getRightPoints(Point a, Point b, std::vector<Point> points) {
    std::cout << "line:\nfrom " << a.getX() << " " << a.getY() << "\nto " << b.getX() << " " << b.getY() << std::endl;
    std::vector<Point> rightPoints;
    for (std::vector<Point>::iterator it = points.begin(); it != points.end(); ++it)
        if (isRightPoint(a, b, *it) && !it->equals(a) && !it->equals(b)) {
            std::cout << it->getX() << it->getY() << std::endl;
            rightPoints.push_back(*it);
        }
    std::cout << "that were all right points" << std::endl;
    return rightPoints;
}

void Point::print() {
    std::cout << x << " " << y << std::endl;
}

Point Point::getCentroid(Point a, Point b, Point c) {
    return Point((a.getX() + b.getX() + c.getX()) / 3.0,
                 (a.getY() + b.getY() + c.getY()) / 3.0);
}

float Point::getSignedTriangleArea(Point p1, Point p2, Point p3) {
    return (p2.getX() - p1.getX())*(p3.getY() - p1.getY()) - (p2.getY() - p1.getY())*(p3.getX() - p1.getX());
}

bool Point::isInsidePolygon(std::vector<Point> vertices) {
    for (int i = 0; i < vertices.size() - 1; ++i) {
        float area = getSignedTriangleArea(*this, vertices[i], vertices[i+1]);
        if (area < 0)
            return false;
    }
    return true;
}