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

 *

 * GEOS - Geometry Engine Open Source

 * http://geos.osgeo.org

 *

 * Copyright (C) 2009  Sandro Santilli <strk@kbt.io>

 *

 * 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/BufferInputLineSimplifier.java r320 (JTS-1.12)

 *

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

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

#include <geos/geom/CoordinateSequence.h> // for inlines

#include <geos/algorithm/Distance.h> // for use

#include <geos/algorithm/Orientation.h> // for use

#include <geos/util.h>

#include <memory>

#include <cmath>

#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

BufferInputLineSimplifier::BufferInputLineSimplifier(

    const geom::CoordinateSequence& input)

    :

    inputLine(input),

    angleOrientation(Orientation::COUNTERCLOCKWISE)

{}

/*public static*/

std::unique_ptr<geom::CoordinateSequence>

BufferInputLineSimplifier::simplify(const geom::CoordinateSequence& inputLine,

                                    double distanceTol)

{

    BufferInputLineSimplifier simp(inputLine);

    return simp.simplify(distanceTol);

}

/* public */

std::unique_ptr<geom::CoordinateSequence>

BufferInputLineSimplifier::simplify(double nDistanceTol)

{

    distanceTol = fabs(nDistanceTol);

    if(nDistanceTol < 0) {

        angleOrientation = Orientation::CLOCKWISE;

    }

    // rely on fact that boolean array is filled with false value

    static const int startValue = INIT;

    isDeleted.assign(inputLine.size(), startValue);

    bool isChanged = false;

    do {

        isChanged = deleteShallowConcavities();

    }

    while(isChanged);

    return collapseLine();

}

/* private */

bool

BufferInputLineSimplifier::deleteShallowConcavities()

{

    /*

     * Do not simplify end line segments of the line string.

     * This ensures that end caps are generated consistently.

     */

    std::size_t index = 1;

    auto midIndex = findNextNonDeletedIndex(index);

    auto lastIndex = findNextNonDeletedIndex(midIndex);

    bool isChanged = false;

    while(lastIndex < inputLine.size()) {

        // test triple for shallow concavity

        bool isMiddleVertexDeleted = false;

        if(isDeletable(index, midIndex, lastIndex,

                       distanceTol)) {

            isDeleted[midIndex] = DELETE;

            isMiddleVertexDeleted = true;

            isChanged = true;

        }

        // move simplification window forward

        if(isMiddleVertexDeleted) {

            index = lastIndex;

        }

        else {

            index = midIndex;

        }

        midIndex = findNextNonDeletedIndex(index);

        lastIndex = findNextNonDeletedIndex(midIndex);

    }

    return isChanged;

}

/* private */

size_t

BufferInputLineSimplifier::findNextNonDeletedIndex(std::size_t index) const

{

    std::size_t next = index + 1;

    const std::size_t len = inputLine.size();

    while(next < len && isDeleted[next] == DELETE) {

        next++;

    }

    return next;

}

/* private */

std::unique_ptr<geom::CoordinateSequence>

BufferInputLineSimplifier::collapseLine() const

{

    auto coordList = new CoordinateSequence();

    for(std::size_t i = 0, n = inputLine.size(); i < n; ++i) {

        if(isDeleted[i] != DELETE) {

            coordList->add(inputLine[i], false);

        }

    }

    return std::unique_ptr<CoordinateSequence>(coordList);

}

/* private */

bool

BufferInputLineSimplifier::isDeletable(std::size_t i0, std::size_t i1, std::size_t i2,

                                       double p_distanceTol) const

{

    const Coordinate& p0 = inputLine[i0];

    const Coordinate& p1 = inputLine[i1];

    const Coordinate& p2 = inputLine[i2];

    if(! isConcave(p0, p1, p2)) {

        return false;

    }

    if(! isShallow(p0, p1, p2, p_distanceTol)) {

        return false;

    }

    // MD - don't use this heuristic - it's too restricting

    // if (p0.distance(p2) > distanceTol) return false;

    return isShallowSampled(p0, p1, i0, i2, p_distanceTol);

}

/* private */

bool

BufferInputLineSimplifier::isShallowConcavity(const geom::Coordinate& p0,

        const geom::Coordinate& p1,

        const geom::Coordinate& p2,

        double p_distanceTol) const

{

    int orientation = Orientation::index(p0, p1, p2);

    bool isAngleToSimplify = (orientation == angleOrientation);

    if(! isAngleToSimplify) {

        return false;

    }

    double dist = Distance::pointToSegment(p1, p0, p2);

    return dist < p_distanceTol;

}

/* private */

bool

BufferInputLineSimplifier::isShallowSampled(const geom::Coordinate& p0,

        const geom::Coordinate& p2,

        std::size_t i0, std::size_t i2,

        double p_distanceTol) const

{

    // check every n'th point to see if it is within tolerance

    auto inc = (i2 - i0) / NUM_PTS_TO_CHECK;

    if(inc <= 0) {

        inc = 1;

    }

    for(std::size_t i = i0; i < i2; i += inc) {

        if(! isShallow(p0, p2, inputLine[i], p_distanceTol)) {

            return false;

        }

    }

    return true;

}

/* private */

bool

BufferInputLineSimplifier::isShallow(const geom::Coordinate& p0,

                                     const geom::Coordinate& p1,

                                     const geom::Coordinate& p2,

                                     double p_distanceTol) const

{

    double dist = Distance::pointToSegment(p1, p0, p2);

    return dist < p_distanceTol;

}

/* private */

bool

BufferInputLineSimplifier::isConcave(const geom::Coordinate& p0,

                                     const geom::Coordinate& p1,

                                     const geom::Coordinate& p2) const

{

    int orientation = Orientation::index(p0, p1, p2);

    bool p_isConcave = (orientation == angleOrientation);

    return p_isConcave;

}

} // namespace geos.operation.buffer

} // namespace geos.operation

} // namespace geos