// **********************************************************
//   File: Polygon.cpp
//   Description: Implementation of class Polygon
//
//   Author: Carlos Moreno
// **********************************************************

#include "Polygon.h"
#include "Segment.h"
#include "Triangle.h"

Polygon::iterator Polygon::begin() {
    return iterator(vertices.begin(), vertices.end());
}

Polygon::const_iterator Polygon::begin() const {
    return const_iterator(vertices.begin(), vertices.end());
}

void Polygon::push_back(const Point & p) {
    vertices.push_back(p);
}

void Polygon::push_front(const Point & p) {
    vertices.push_front(p);
}

void Polygon::insert(const iterator & i, const Point & p) {
    vertices.insert(i.get_i(), p);
}

Polygon::iterator Polygon::remove(const iterator & target) {
    if (!(vertices.empty())) {
        std::list<Point>::iterator ret_value;

        ret_value = vertices.erase(target.get_i());
        if (ret_value == vertices.end()) {
            return iterator(vertices.begin(), vertices.end());
        }
        else {
            return iterator(ret_value, vertices.end());
        }
    }
    else {
        return iterator(); // return "null" iterator
    }
}

bool Polygon::contains(const Point & p) const {
    // Find a point outside the polygon
    //(point with max x + (1,0))

    const_iterator current = begin();
    Point p_max_x = *current++;

    do {
        if ((*current).get_x() > p_max_x.get_x()) {
            p_max_x = *current;
        }
        current++;
    } while (current != begin());

    Point outside = p_max_x + Point(1, 0);
    Segment line(p, outside);

    // Now check the number of intersections of segment
    // p - outside with the edges of the polygon

    // The loop must start in a vertex that is not exactly
    // on the segment 'line'.

    int intersections = 0;

    current = begin();

    while ((*current).is_on(line))
        current++;

    Polygon::const_iterator first_point = current;

    do {
        Point v = *current++;
        if (Segment(v, *current).intersects(line)) {
            intersections++;
        }

        if ((*current).is_on(line)) {
            while ((*++current).is_on(line))
                ;
            // Skip all the vertices that are on the line

            if (turn(line.get_p1(), line.get_p2(), v) == turn(line.get_p1(), line.get_p2(), *current)) {
                intersections--;
            }
            // If previous and next points are on the same
            // side of line, then line doesn't intersect the
            // polygon;  it merely touches it at the vertex.
            // Since one intersection was counted by the test
            // with the first edge, decrement the count.
        }
    } while (current != first_point);

    if (intersections % 2) // if odd number of intersections
            {
        return true;
    }
    else {
        return false;
    }
}

void Polygon::draw(bool draw_vs, int v_radius) const {
    const_iterator current = begin();

    if (draw_vs) {
        (*current).draw(2 * v_radius);
    }
    do {
        if (draw_vs) {
            (*current).draw(v_radius);
        }
        Point p = *current++;
        Segment(p, *current).draw();
    } while (current != begin());
}

Polygon Polygon::convex_hull() const {
    Polygon hull;
    Polygon::const_iterator input_iter = begin();
    Polygon::iterator hull_iter;

    // The first three points go directly to the output

    Point p1 = *input_iter++;
    Point p2 = *input_iter++;
    Point p3 = *input_iter++;

    // Make sure the output is in counter-clockwise sense
    if (turn(p1, p2, p3) == left_turn) {
        hull.push_back(p1);
        hull.push_back(p2);
        hull.push_back(p3);
        hull.push_front(p3);
    }
    else {
        hull.push_back(p2);
        hull.push_back(p1);
        hull.push_back(p3);
        hull.push_front(p3);
    }
    // The last point has to be always inserted at both ends

    do {
        Polygon::iterator first = hull.begin();
        Polygon::iterator last = first - 1;
        // The list is circular

        Point p = *input_iter++;

        if (turn(*(first + 1), *first, p) == left_turn || turn(*(last - 1), *last, p) == right_turn) {
            hull.push_back(p);
            hull.push_front(p);

            // Now fix the possible concavities after insertion
            // of new point (on both ends of the output list)

            first = hull.begin();
            last = first - 1;

            while (turn(*first, *(first + 1), *(first + 2)) == right_turn) {
                hull.remove(first + 1);
            }

            while (turn(*last, *(last - 1), *(last - 2)) == left_turn) {
                hull.remove(last - 1);
            }
        }
    } while (input_iter != begin());

    hull.remove(hull.begin()); // Remove repeated point  (1st pt. = last pt.)

    return hull;
}

int Polygon::orientation() const {
    const_iterator current = begin();
    bool empty_triangle_found = false;
    Triangle t;

    // Find a triangle (three consecutive vertices of
    // the polygon) that doesn't contain any other
    // vertex of the polygon.

    do {
        t = Triangle(*(current - 1), *current, *(current + 1));
        bool t_is_empty = true;

        const_iterator i = begin();
        do {
            if ((*i).is_inside(t)) {
                t_is_empty = false;
                break;
            }
            i++;
        } while (i != begin());

        if (t_is_empty) {
            empty_triangle_found = true;
        }
        else {
            current++;
        }
    } while (!empty_triangle_found);

    // Now we know that either all the points inside the
    // triangle are inside the polygon, are all are
    // outside the polygon.

    // Given the orientation of t, and checking if a
    // point inside t is also inside the polygon, we
    // determine the orientation of the polygon.

    Point p = (*(current - 1) + *current + *(current + 1)) / 3;

    if (p.is_inside(*this)) // if inside the polygon
            {
        if (t.orientation() == counter_clockwise) {
            return counter_clockwise;
        }
        else {
            return clockwise;
        }
    }
    else {
        if (t.orientation() == counter_clockwise) {
            return clockwise;
        }
        else {
            return counter_clockwise;
        }
    }
}
