/**********************************************************************

 *

 * GEOS - Geometry Engine Open Source

 * http://geos.osgeo.org

 *

 * Copyright (C) 2018 Paul Ramsey <pramsey@cleverlephant.ca>

 *

 * This is free software; you can redistribute and/or modify it under

 * the terms of the GNU Lesser General Public Licence as published

 * by the Free Software Foundation.

 * See the COPYING file for more information.

 *

 **********************************************************************

 *

 * Last port: algorithm/Orientation.java @ 2017-09-04

 *

 **********************************************************************/

#include <cassert>

#include <cmath>

#include <vector>

#include <geos/algorithm/Area.h>

#include <geos/algorithm/Orientation.h>

#include <geos/algorithm/CGAlgorithmsDD.h>

#include <geos/geom/CoordinateSequence.h>

#include <geos/geom/Coordinate.h>

#include <geos/util/IllegalArgumentException.h>

using geos::geom::CoordinateXY;

namespace geos {

namespace algorithm { // geos.algorithm

/* public static */

// inlining this method worsened performance slightly

int

Orientation::index(const geom::CoordinateXY& p1, const geom::CoordinateXY& p2,

                   const geom::CoordinateXY& q)

{

    return CGAlgorithmsDD::orientationIndex(p1, p2, q);

}

/* public static */

bool

Orientation::isCCW(const geom::CoordinateSequence* ring)

{

    // # of points without closing endpoint

    int inPts = static_cast<int>(ring->size()) - 1;

    // sanity check

    if (inPts < 3)

        return false;

    uint32_t nPts = static_cast<uint32_t>(inPts);

    /**

     * Find first highest point after a lower point, if one exists

     * (e.g. a rising segment)

     * If one does not exist, hiIndex will remain 0

     * and the ring must be flat.

     * Note this relies on the convention that

     * rings have the same start and end point.

     */

    const CoordinateXY* upHiPt = &ring->getAt<CoordinateXY>(0);

    const CoordinateXY* upLowPt = &CoordinateXY::getNull();

    double prevY = upHiPt->y;

    uint32_t iUpHi = 0;

    for (uint32_t i = 1; i <= nPts; i++) {

        double py = ring->getY(i);

        /**

        * If segment is upwards and endpoint is higher, record it

        */

        if (py > prevY && py >= upHiPt->y) {

            iUpHi = i;

            upHiPt = &ring->getAt<CoordinateXY>(i);

            upLowPt = &ring->getAt<CoordinateXY>(i-1);

        }

        prevY = py;

    }

    /**

     * Check if ring is flat and return default value if so

     */

    if (iUpHi == 0) return false;

    /**

     * Find the next lower point after the high point

     * (e.g. a falling segment).

     * This must exist since ring is not flat.

     */

    uint32_t iDownLow = iUpHi;

    do {

        iDownLow = (iDownLow + 1) % nPts;

    } while (iDownLow != iUpHi && ring->getY(iDownLow) == upHiPt->y );

    const CoordinateXY& downLowPt = ring->getAt<CoordinateXY>(iDownLow);

    uint32_t iDownHi = iDownLow > 0 ? iDownLow - 1 : nPts - 1;

    const CoordinateXY& downHiPt = ring->getAt<CoordinateXY>(iDownHi);

    /**

     * Two cases can occur:

     * 1) the hiPt and the downPrevPt are the same.

     *    This is the general position case of a "pointed cap".

     *    The ring orientation is determined by the orientation of the cap

     * 2) The hiPt and the downPrevPt are different.

     *    In this case the top of the cap is flat.

     *    The ring orientation is given by the direction of the flat segment

     */

    if (upHiPt->equals2D(downHiPt)) {

        /**

        * Check for the case where the cap has configuration A-B-A.

        * This can happen if the ring does not contain 3 distinct points

        * (including the case where the input array has fewer than 4 elements), or

        * it contains coincident line segments.

        */

        if (upLowPt->equals2D(*upHiPt) || downLowPt.equals2D(*upHiPt) || upLowPt->equals2D(downLowPt))

            return false;

        /**

        * It can happen that the top segments are coincident.

        * This is an invalid ring, which cannot be computed correctly.

        * In this case the orientation is 0, and the result is false.

        */

        int orientationIndex = index(*upLowPt, *upHiPt, downLowPt);

        return orientationIndex == COUNTERCLOCKWISE;

    }

    else {

        /**

        * Flat cap - direction of flat top determines orientation

        */

        double delX = downHiPt.x - upHiPt->x;

        return delX < 0;

    }

}

/* public static */

bool

Orientation::isCCWArea(const geom::CoordinateSequence* ring)

{

    return algorithm::Area::ofRingSigned(ring) < 0;

}

} // namespace geos.algorithm

} //namespace geos