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

 *

 * GEOS - Geometry Engine Open Source

 * http://geos.osgeo.org

 *

 * Copyright (C) 2005-2006 Refractions Research Inc.

 * Copyright (C) 2001-2002 Vivid Solutions Inc.

 *

 * 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: operation/buffer/RightmostEdgeFinder.java r320 (JTS-1.12)

 *

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

#include <geos/algorithm/Orientation.h>

#include <geos/operation/buffer/RightmostEdgeFinder.h>

#include <geos/geomgraph/DirectedEdge.h>

#include <geos/geomgraph/DirectedEdgeStar.h>

#include <geos/geom/Position.h>

#include <geos/geomgraph/Node.h>

#include <geos/geomgraph/Edge.h>

#include <geos/util/TopologyException.h>

#include <geos/util.h>

#include <vector>

#include <cassert>

using namespace geos::algorithm; // Orientation

using namespace geos::geom;

using namespace geos::geomgraph; // DirectedEdge, Position

namespace geos {

namespace operation { // geos.operation

namespace buffer { // geos.operation.buffer

/*public*/

RightmostEdgeFinder::RightmostEdgeFinder()

    :

    minIndex(-1), // FIXME: don't use -1 as a sentinel, or we won't be

    // able to use an unsigned int here

    minCoord(Coordinate::getNull()),

    minDe(nullptr),

    orientedDe(nullptr)

{

}

/*public*/

void

RightmostEdgeFinder::findEdge(std::vector<DirectedEdge*>* dirEdgeList)

{

#ifndef NDEBUG

    std::size_t checked = 0;

#endif

    /*

     * Check all forward DirectedEdges only.  This is still general,

     * because each edge has a forward DirectedEdge.

     */

    std::size_t dirEdgeListSize = dirEdgeList->size();

    for(std::size_t i = 0; i < dirEdgeListSize; ++i) {

        DirectedEdge* de = (*dirEdgeList)[i];

        assert(de);

        if(!de->isForward()) {

            continue;

        }

        checkForRightmostCoordinate(de);

#ifndef NDEBUG

        ++checked;

#endif

    }

    if(! minDe) {

        // I don't know why, but it looks like this can happen

        // (invalid PlanarGraph, I think)

        // See http://trac.osgeo.org/geos/ticket/605#comment:17

        //

        throw util::TopologyException("No forward edges found in buffer subgraph");

    }

#ifndef NDEBUG

    assert(checked > 0);

    assert(minIndex >= 0);

    assert(minDe);

#endif

    /*

     * If the rightmost point is a node, we need to identify which of

     * the incident edges is rightmost.

     */

    assert(minIndex != 0 || minCoord == minDe->getCoordinate());

    // inconsistency in rightmost processing

    if(minIndex == 0) {

        findRightmostEdgeAtNode();

    }

    else {

        findRightmostEdgeAtVertex();

    }

    /*

     * now check that the extreme side is the R side.

     * If not, use the sym instead.

     */

    orientedDe = minDe;

    int rightmostSide = getRightmostSide(minDe, minIndex);

    if(rightmostSide == Position::LEFT) {

        orientedDe = minDe->getSym();

    }

}

/*private*/

void

RightmostEdgeFinder::findRightmostEdgeAtNode()

{

    Node* node = minDe->getNode();

    assert(node);

    DirectedEdgeStar* star = detail::down_cast<DirectedEdgeStar*>(node->getEdges());

    // Warning! NULL could be returned if the star is empty!

    minDe = star->getRightmostEdge();

    assert(minDe);

    // the DirectedEdge returned by the previous call is not

    // necessarily in the forward direction. Use the sym edge if it isn't.

    if(!minDe->isForward()) {

        minDe = minDe->getSym();

        const Edge* minEdge = minDe->getEdge();

        assert(minEdge);

        const CoordinateSequence* minEdgeCoords =

            minEdge->getCoordinates();

        assert(minEdgeCoords);

        minIndex = (int)(minEdgeCoords->getSize()) - 1;

        assert(minIndex >= 0);

    }

}

/*private*/

void

RightmostEdgeFinder::findRightmostEdgeAtVertex()

{

    /*

     * The rightmost point is an interior vertex, so it has

     * a segment on either side of it.

     * If these segments are both above or below the rightmost

     * point, we need to determine their relative orientation

     * to decide which is rightmost.

     */

    Edge* minEdge = minDe->getEdge();

    assert(minEdge);

    const CoordinateSequence* pts = minEdge->getCoordinates();

    assert(pts);

    // rightmost point expected to be interior vertex of edge

    assert(minIndex > 0);

    assert((std::size_t)minIndex < pts->getSize());

    const Coordinate& pPrev = pts->getAt(static_cast<std::size_t>(minIndex) - 1);

    const Coordinate& pNext = pts->getAt(static_cast<std::size_t>(minIndex) + 1);

    int orientation = Orientation::index(

                          minCoord,

                          pNext,

                          pPrev);

    bool usePrev = false;

    // both segments are below min point

    if(pPrev.y < minCoord.y && pNext.y < minCoord.y

            && orientation == Orientation::COUNTERCLOCKWISE) {

        usePrev = true;

    }

    else if(pPrev.y > minCoord.y && pNext.y > minCoord.y

            && orientation == Orientation::CLOCKWISE) {

        usePrev = true;

    }

    // if both segments are on the same side, do nothing - either is safe

    // to select as a rightmost segment

    if(usePrev) {

        minIndex = minIndex - 1;

    }

}

/*private*/

void

RightmostEdgeFinder::checkForRightmostCoordinate(DirectedEdge* de)

{

    const Edge* deEdge = de->getEdge();

    assert(deEdge);

    const CoordinateSequence* coord = deEdge->getCoordinates();

    assert(coord);

    // only check vertices which are the starting point of

    // a non-horizontal segment

    std::size_t n = coord->getSize() - 1;

    for(std::size_t i = 0; i < n; i++) {

        // only check vertices which are the start or end point

        // of a non-horizontal segment

        // <FIX> MD 19 Sep 03 - NO!  we can test all vertices,

        // since the rightmost must have a non-horiz segment adjacent to it

        if(minCoord.isNull() ||

                coord->getAt(i).x > minCoord.x) {

            minDe = de;

            minIndex = (int)i;

            minCoord = coord->getAt(i);

        }

    }

}

/*private*/

int

RightmostEdgeFinder::getRightmostSide(DirectedEdge* de, int index)

{

    int side = getRightmostSideOfSegment(de, index);

    if(side < 0) {

        side = getRightmostSideOfSegment(de, index - 1);

    }

    if(side < 0) {

        // reaching here can indicate that segment is horizontal

        // Assert::shouldNeverReachHere(

        //  "problem with finding rightmost side of segment");

        minCoord = Coordinate::getNull();

        checkForRightmostCoordinate(de);

    }

    return side;

}

/*private*/

int

RightmostEdgeFinder::getRightmostSideOfSegment(DirectedEdge* de, int i)

{

    assert(de);

    const Edge* e = de->getEdge();

    assert(e);

    const CoordinateSequence* coord = e->getCoordinates();

    assert(coord);

    if(i < 0 || i + 1 >= (int)coord->getSize()) {

        return -1;

    }

    // indicates edge is parallel to x-axis

    const Coordinate& p0 = coord->getAt(static_cast<std::size_t>(i));

    const Coordinate& p1 = coord->getAt(static_cast<std::size_t>(i) + 1);

    if(p0.y == p1.y) {

        return -1;

    }

    int pos = Position::LEFT;

    if(p0.y < p1.y) {

        pos = Position::RIGHT;

    }

    return pos;

}

} // namespace geos.operation.buffer

} // namespace geos.operation

} // namespace geos