#include "PolygonCalculus.h"

namespace PolygonCalculus {
    namespace  {

    } // end anonymous namespace

    /*!
     * \fn int closestVertexIndex(const QPolygonF &polygon, const QPointF &coordinate)
     * Returns the vertex index of \a polygon which has the least distance to \a coordinate.
     *
     * \sa QPointF, QPolygonF
     */
    int closestVertexIndex(const QPolygonF &polygon, const QPointF &coordinate)
    {
        if (polygon.size() == 0) {
            qWarning("Path is empty!");
            return -1;
        }else if (polygon.size() == 1) {
            return 0;
        }else {
            int index = 0; // the index of the closest vertex
            double min_dist = PlanimetryCalculus::distance(coordinate, polygon[index]);
            for(int i = 1; i < polygon.size(); i++){
                double dist = PlanimetryCalculus::distance(coordinate, polygon[i]);
                if (dist < min_dist){
                    min_dist = dist;
                    index = i;
                }
            }
            return index;
        }
    }

    /*!
     * \fn  QPointF closestVertex(const QPolygonF &polygon, const QPointF &coordinate);
     *  Returns the vertex of \a polygon with the least distance to \a coordinate.
     *
     * \sa QPointF, QPolygonF
     */
    QPointF closestVertex(const QPolygonF &polygon, const QPointF &coordinate)
    {
        int index = closestVertexIndex(polygon, coordinate);
        if (index >=0 ) {
            return polygon[index];
        } else {
            return QPointF();
        }
    }

    /*!
     * \fn int nextPolygonIndex(int pathsize, int index)
     * Returns the index of the next vertex (of a polygon), which is \a index + 1 if \a index is smaller than \c {\a pathsize - 1},
     * or 0 if \a index equals \c {\a pathsize - 1}, or -1 if the \a index is out of bounds.
     * \note \a pathsize is usually obtained by invoking polygon.size()
     */
    int nextPolygonIndex(int pathsize, int index)
    {
        if (index >= 0 && index < pathsize-1) {
            return index + 1;
        } else if (index == pathsize-1) {
            return 0;
        } else {
            qWarning("nextPolygonIndex(): Index out of bounds! index:count = %i:%i", index, pathsize);
            return -1;
        }
    }

    /*!
     * \fn int previousPolygonIndex(int pathsize, int index)
     * Returns the index of the previous vertex (of a polygon), which is \a index - 1 if \a index is larger 0,
     * or \c {\a pathsize - 1} if \a index equals 0, or -1 if the \a index is out of bounds.
     * \note pathsize is usually obtained by invoking polygon.size()
     */
    int previousPolygonIndex(int pathsize, int index)
    {
        if (index > 0 && index <pathsize) {
            return index - 1;
        } else if (index == 0) {
            return pathsize-1;
        } else {
            qWarning("previousVertexIndex(): Index out of bounds! index:count = %i:%i", index, pathsize);
            return -1;
        }
    }

    /*!
     * \fn JoinPolygonError joinPolygon(QPolygonF polygon1, QPolygonF polygon2, QPolygonF &joinedPolygon);
     * Joins \a polygon1 and \a polygon2 such that a \l {Simple Polygon} is created.
     * Stores the result inside \a joinedArea.
     * Returns \c NotSimplePolygon1 if \a polygon1 isn't a Simple Polygon, \c NotSimplePolygon2 if \a polygon2 isn't a Simple Polygon, \c Disjoind if the polygons are disjoint,
     * \c PathSizeLow if at least one polygon has a size samler than 3, or \c PolygonJoined on success.
     * The algorithm will be able to join the areas, if either their edges intersect with each other,
     * or one area is inside the other.
     * The algorithm assumes that \a joinedPolygon is empty.
     */
    JoinPolygonError joinPolygon(QPolygonF polygon1, QPolygonF polygon2, QPolygonF &joinedPolygon)
    {
        if (polygon1.size() >= 3 && polygon2.size() >= 3) {

            if ( !isSimplePolygon(polygon1) || !isSimplePolygon(polygon2)) {
                return JoinPolygonError::NotSimplePolygon;
            }
            if ( !hasClockwiseWinding(polygon1)) {
                reversePath(polygon1);
            }
            if ( !hasClockwiseWinding(polygon2)) {
                reversePath(polygon2);
            }

            const QPolygonF *walkerPoly    = &polygon1; // "walk" on this polygon towards higher indices
            const QPolygonF *crossPoly     = &polygon2; // check for crossings with this polygon while "walking"
                                                        // and swicht to this polygon on a intersection,
                                                        // continue to walk towards higher indices

            // begin with the first index which is not inside crosspoly, if all Vertices are inside crosspoly return crosspoly
            int startIndex = 0;
            bool crossContainsWalker = true;
            for (int i = 0; i < walkerPoly->size(); i++) {
                if ( !crossPoly->contains(walkerPoly->value(i)) ) {
                    crossContainsWalker = false;
                    startIndex = i;
                    break;
                }
            }

            if ( crossContainsWalker == true) {
                joinedPolygon.append(*crossPoly);
                return JoinPolygonError::PolygonJoined;
            }

            QPointF currentVertex    = walkerPoly->value(startIndex);
            QPointF startVertex      = currentVertex;
            // possible nextVertex (if no intersection between currentVertex and protoVertex with crossPoly)
            int nextVertexIndex      = nextPolygonIndex(walkerPoly->size(), startIndex);
            QPointF protoNextVertex  = walkerPoly->value(nextVertexIndex);
            bool switchHappenedPreviously = false; // means switch between crossPoly and walkerPoly
            while (1) {
                //qDebug("nextVertexIndex: %i", nextVertexIndex);
                joinedPolygon.append(currentVertex);

                QLineF walkerPolySegment;
                walkerPolySegment.setP1(currentVertex);
                walkerPolySegment.setP2(protoNextVertex);

                QList<QPair<int, int>> neighbourList;
                QList<QPointF> intersectionList;
                //qDebug("IntersectionList.size() on init: %i", intersectionList.size());
                PlanimetryCalculus::intersects(*crossPoly, walkerPolySegment, intersectionList, neighbourList);

                //qDebug("IntersectionList.size(): %i", intersectionList.size());

                if (intersectionList.size() >= 1) {
                    int minDistIndex = 0;

                    // find the vertex with the least distance to currentVertex
                    if (intersectionList.size() > 1) {
                        double minDist = PlanimetryCalculus::distance(currentVertex, intersectionList[minDistIndex]);
                        for (int i = 1; i < intersectionList.size(); i++) {
                            double currentDist = PlanimetryCalculus::distance(currentVertex, intersectionList[i]);

                            if ( minDist > currentDist ) {
                                minDist         = currentDist;
                                minDistIndex    = i;
                            }
                        }
                    }

                    //qDebug("MinDistIndex: %i", minDistIndex);
                    QPointF protoCurrentVertex = intersectionList.value(minDistIndex);
                    // If the currentVertex is a intersection point a intersection ocisSelfIntersectingcures with the
                    // crossPoly. This would cause unwanted switching of crossPoly and walkerPoly, thus intersections
                    // are only token in to account if they occur beyond a certain distance (_epsilonMeter) or no switching happend in the
                    // previous step.

                    if (switchHappenedPreviously == false){
                            //|| protoCurrentVertex.distanceTo(currentVertex) > _epsilonMeter) {
                        currentVertex                   = protoCurrentVertex;
                        QPair<int, int> neighbours      = neighbourList.value(minDistIndex);
                        protoNextVertex                 = crossPoly->value(neighbours.second);
                        nextVertexIndex                 = neighbours.second;

                        // switch walker and cross poly
                        const QPolygonF *temp   = walkerPoly;
                        walkerPoly              = crossPoly;
                        crossPoly               = temp;

                        switchHappenedPreviously = true;
                    } else {
                        currentVertex   = walkerPoly->value(nextVertexIndex);
                        nextVertexIndex = nextPolygonIndex(walkerPoly->size(), nextVertexIndex);
                        protoNextVertex = walkerPoly->value(nextVertexIndex);

                        switchHappenedPreviously = false;
                    }

                } else {
                    currentVertex   = walkerPoly->value(nextVertexIndex);
                    nextVertexIndex = nextPolygonIndex(walkerPoly->size(), nextVertexIndex);
                    protoNextVertex = walkerPoly->value(nextVertexIndex);
                }

                if (currentVertex == startVertex) {
                    if (polygon1.size() == joinedPolygon.size()) {
                        return JoinPolygonError::Disjoint;
                    } else {
                        return JoinPolygonError::PolygonJoined;
                    }
                }
            }

        } else {
            return JoinPolygonError::PathSizeLow;
        }
    }

    /*!
     * \fn bool isSimplePolygon(const QPolygonF &polygon);
     * Returns \c true if \a polygon is a \l {Simple Polygon}, \c false else.
     * \note A polygon is a Simple Polygon iff it is not self intersecting.
     */
    bool isSimplePolygon(const QPolygonF &polygon)
    {
        int i = 0;
        if (polygon.size() > 3) {
            // check if any edge of the area (formed by two adjacent vertices) intersects with any other edge of the area
            while(i < polygon.size()-1) {
                QPointF refBeginCoordinate = polygon[i];
                QPointF refEndCoordinate = polygon[nextPolygonIndex(polygon.size(), i)];
                QLineF refLine;
                refLine.setP1(refBeginCoordinate);
                refLine.setP2(refEndCoordinate);
                int j = nextPolygonIndex(polygon.size(), i);
                while(j < polygon.size()) {

                    QPointF intersectionPt;
                    QLineF iteratorLine;
                    iteratorLine.setP1(polygon[j]);
                    iteratorLine.setP2(polygon[nextPolygonIndex(polygon.size(), j)]);
                    if (    PlanimetryCalculus::intersects(refLine, iteratorLine, intersectionPt)
                         == PlanimetryCalculus::InteriorIntersection){
                            return false;
                    }
                    j++;
                }
                i++;
            }
        }
        return true;
    }

    /*!
     * \fn bool hasClockwiseWinding(const QPolygonF &polygon)
     * Returns \c true if \a path has clockwise winding, \c false else.
     */
    bool hasClockwiseWinding(const QPolygonF &polygon)
    {
        if (polygon.size() <= 2) {
            return false;
        }

        double sum = 0;
        for (int i=0; i <polygon.size(); i++) {
            QPointF coord1 = polygon[i];
            QPointF coord2 = polygon[nextPolygonIndex(polygon.size(), i)];

            sum += (coord2.x() - coord1.x()) * (coord2.y() + coord1.y());
        }

        if (sum < 0.0)
            return false;

        return true;
    }

    /*!
     * \fn void reversePath(QPolygonF &polygon)
     * Reverses the path, i.e. changes the first Vertex with the last, the second with the befor last and so forth.
     */
    void reversePath(QPolygonF &polygon)
    {
        QPolygonF pathReversed;
        for (int i = 0; i < polygon.size(); i++) {
            pathReversed.prepend(polygon[i]);
        }
        polygon.clear();
        polygon.append(pathReversed);
    }

    bool offsetPolygon(QPolygonF &polygon, double offset)
    {

    }

    /*!
     * \fn double distanceInsidePolygon(const QGeoCoordinate &c1, const QGeoCoordinate &c2, QList<QGeoCoordinate> polygon)
     * Returns the distance between the coordinate \a c1 and coordinate \a c2, or infinity if the shortest path between
     * the two coordinates is not fully inside the \a area.
     *
     * \sa QGeoCoordinate
     */
    double distanceInsidePolygon(const QPointF &c1, const QPointF &c2, QPolygonF polygon)
    {
        offsetPolygon(polygon, 0.1);// hack to compensate for numerical issues, migh be replaced in the future...
        if ( polygon.contains(c1) && polygon.contains(c2)) {
            QList<QPointF>   intersectionList;
            QList<QPair<int, int>>  neighbourlist;
            QLineF line;

            line.setP1(c1);
            line.setP2(c2);
            PlanimetryCalculus::intersects(polygon, line, intersectionList, neighbourlist);

            if ( intersectionList.size() == 0 ){ // if an intersection was found the path between c1 and c2 is not fully inside polygon.
                return PlanimetryCalculus::distance(c1, c2);
            } else {
                return std::numeric_limits<qreal>::infinity();
            }

        } else {
            return std::numeric_limits<qreal>::infinity();
        }
    }
} // end PolygonCalculus namespace