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

 *

 * GEOS - Geometry Engine Open Source

 * http://geos.osgeo.org

 *

 * Copyright (C) 2022 Paul Ramsey <pramsey@cleverelephant.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.

 *

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

#include <geos/simplify/RingHull.h>

#include <geos/simplify/LinkedRing.h>

#include <geos/simplify/RingHullIndex.h>

#include <geos/algorithm/Orientation.h>

#include <geos/geom/Envelope.h>

#include <geos/geom/Coordinate.h>

#include <geos/geom/CoordinateSequence.h>

#include <geos/geom/GeometryFactory.h>

#include <geos/geom/LineString.h>

#include <geos/geom/LinearRing.h>

#include <geos/geom/Polygon.h>

#include <geos/geom/Triangle.h>

#include <geos/index/VertexSequencePackedRtree.h>

#include <geos/util.h>

using geos::algorithm::Orientation;

using geos::geom::Envelope;

using geos::geom::Coordinate;

using geos::geom::CoordinateSequence;

using geos::geom::GeometryFactory;

using geos::geom::LineString;

using geos::geom::LinearRing;

using geos::geom::Polygon;

using geos::geom::Triangle;

using geos::index::VertexSequencePackedRtree;

namespace geos {

namespace simplify { // geos.simplify

/*

* Creates a new instance.

*

* @param ring the ring vertices to process

* @param isOuter whether the hull is outer or inner

*/

RingHull::RingHull(const LinearRing* p_ring, bool p_isOuter)

    : inputRing(p_ring)

    , vertex(inputRing->getCoordinates())

{

    init(*vertex, p_isOuter);

}

/* public */

void

RingHull::setMinVertexNum(std::size_t minVertexNum)

{

    targetVertexNum = static_cast<double>(minVertexNum);

}

/* public */

void

RingHull::setMaxAreaDelta(double maxAreaDelta)

{

    targetAreaDelta = maxAreaDelta;

}

/* public */

const Envelope*

RingHull::getEnvelope() const

{

    return inputRing->getEnvelopeInternal();

}

/* public */

std::unique_ptr<LinearRing>

RingHull::getHull(RingHullIndex& hullIndex)

{

    compute(hullIndex);

    std::unique_ptr<CoordinateSequence> hullPts = vertexRing->getCoordinates();

    // std::vector<Coordinate> hullPts;

    // std::copy(vrCoords.begin(), vrCoords.end(), hullPts.back_inserter());

    return inputRing->getFactory()->createLinearRing(std::move(hullPts));

}

/* private */

void

RingHull::init(CoordinateSequence& ring, bool isOuter)

{

    /**

     * Ensure ring is oriented according to outer/inner:

     * - outer, CW

     * - inner: CCW

     */

    bool orientCW = isOuter;

    if (orientCW == Orientation::isCCW(inputRing->getCoordinatesRO()))

    {

        ring.reverse();

    }

    vertexRing.reset(new LinkedRing(ring));

    vertexIndex.reset(new VertexSequencePackedRtree(ring));

    //-- remove duplicate final vertex

    vertexIndex->remove(ring.size() - 1);

    for (std::size_t i = 0; i < vertexRing->size(); i++) {

        addCorner(i, cornerQueue);

    }

}

/* private */

void

RingHull::addCorner(std::size_t i, Corner::PriorityQueue& queue)

{

    //-- convex corners are left untouched

    if (isConvex(*vertexRing, i))

      return;

    //-- corner is concave or flat - both can be removed

    Corner corner (i,

        vertexRing->prev(i),

        vertexRing->next(i),

        area(*vertexRing, i));

    queue.push(corner);

}

/* public static */

bool

RingHull::isConvex(const LinkedRing& vertexRing, std::size_t index)

{

    const Coordinate& pp = vertexRing.prevCoordinate(index);

    const Coordinate& p = vertexRing.getCoordinate(index);

    const Coordinate& pn = vertexRing.nextCoordinate(index);

    return Orientation::CLOCKWISE == Orientation::index(pp, p, pn);

}

/* public static */

double

RingHull::area(const LinkedRing& vertexRing, std::size_t index)

{

    const Coordinate& pp = vertexRing.prevCoordinate(index);

    const Coordinate& p = vertexRing.getCoordinate(index);

    const Coordinate& pn = vertexRing.nextCoordinate(index);

    return Triangle::area(pp, p, pn);

}

/* public */

void

RingHull::compute(RingHullIndex& hullIndex)

{

    while (! cornerQueue.empty()

        && vertexRing->size() > 3)

    {

        Corner corner = cornerQueue.top();

        cornerQueue.pop();

        //-- a corner may no longer be valid due to removal of adjacent corners

        if (corner.isRemoved(*vertexRing))

            continue;

        if (isAtTarget(corner)) {

            return;

        }

        //System.out.println(corner.toLineString(vertexList));

        /**

        * Corner is concave or flat - remove it if possible.

        */

        if (isRemovable(corner, hullIndex)) {

            removeCorner(corner, cornerQueue);

        }

    }

}

/* private */

bool

RingHull::isAtTarget(const Corner& corner)

{

    if (targetVertexNum >= 0) {

        double dVertexRingSize = static_cast<double>(vertexRing->size());

        return dVertexRingSize < targetVertexNum;

    }

    if (targetAreaDelta >= 0) {

        //-- include candidate corder to avoid overshooting target

        // (important for very small target area deltas)

        return areaDelta + corner.getArea() > targetAreaDelta;

    }

    //-- no target set

    return true;

}

/**

* Removes a corner by removing the apex vertex from the ring.

* Two new corners are created with apexes

* at the other vertices of the corner

* (if they are non-convex and thus removable).

*

* @param corner the corner to remove

* @param cornerQueue the corner queue

*/

/* private */

void

RingHull::removeCorner(const Corner& corner, Corner::PriorityQueue& queue)

{

    std::size_t index = corner.getIndex();

    std::size_t prev = vertexRing->prev(index);

    std::size_t next = vertexRing->next(index);

    vertexRing->remove(index);

    vertexIndex->remove(index);

    areaDelta += corner.getArea();

    //-- potentially add the new corners created

    addCorner(prev, queue);

    addCorner(next, queue);

}

/* private */

bool

RingHull::isRemovable(const Corner& corner, const RingHullIndex& hullIndex) const

{

    Envelope cornerEnv;

    corner.envelope(*vertexRing, cornerEnv);

    if (hasIntersectingVertex(corner, cornerEnv, this))

        return false;

    //-- no other rings to check

    if (hullIndex.size() == 0)

        return true;

    //-- check other rings for intersections

    std::vector<const RingHull*> queryResult = hullIndex.query(cornerEnv);

    for (const RingHull* hull : queryResult) {

      //-- this hull was already checked above

        if (hull == this)

            continue;

        if (hasIntersectingVertex(corner, cornerEnv, hull))

            return false;

    }

    return true;

}

/**

* Tests if any vertices in a hull intersect the corner triangle.

* Uses the vertex spatial index for efficiency.

*

* @param corner the corner vertices

* @param cornerEnv the envelope of the corner

* @param hull the hull to test

* @return true if there is an intersecting vertex

*/

/* private */

bool

RingHull::hasIntersectingVertex(

    const Corner& corner,

    const Envelope& cornerEnv,

    const RingHull* hull) const

{

    std::vector<std::size_t> result;

    hull->query(cornerEnv, result);

    for (std::size_t index : result)

    {

        //-- skip vertices of corner

        if (hull == this && corner.isVertex(index))

            continue;

        const Coordinate& v = hull->getCoordinate(index);

        //--- does corner triangle contain vertex?

        if (corner.intersects(v, *vertexRing))

            return true;

    }

    return false;

}

/* private */

const Coordinate&

RingHull::getCoordinate(std::size_t index) const

{

    return vertexRing->getCoordinate(index);

}

/* private */

void

RingHull::query(

    const Envelope& cornerEnv,

    std::vector<std::size_t>& result) const

{

    vertexIndex->query(cornerEnv, result);

}

void

RingHull::queryHull(const Envelope& queryEnv, std::vector<Coordinate>& pts)

{

    std::vector<std::size_t> result;

    vertexIndex->query(queryEnv, result);

    for (std::size_t index : result) {

        //-- skip if already removed

        if (! vertexRing->hasCoordinate(index))

            continue;

        const Coordinate& v = vertexRing->getCoordinate(index);

        pts.push_back(v);

    }

}

/* public */

std::unique_ptr<Polygon>

RingHull::toGeometry() const

{

    auto fact = GeometryFactory::create();

    std::unique_ptr<CoordinateSequence> coords = vertexRing->getCoordinates();

    // std::vector<Coordinate> coordCopy;

    // std::copy(coords.begin(), coords.end(), coordCopy.back_inserter());

    return fact->createPolygon(fact->createLinearRing(std::move(coords)));

}

// ------- Corner ------------------------------------------

/* public */

bool

RingHull::Corner::isVertex(std::size_t p_index) const

{

    return p_index == index

        || p_index == prev

        || p_index == next;

}

/* public */

std::size_t

RingHull::Corner::getIndex() const

{

    return index;

}

/* public */

double

RingHull::Corner::getArea() const

{

    return area;

}

/* public */

void

RingHull::Corner::envelope(const LinkedRing& ring, Envelope& env) const

{

    const Coordinate& pp = ring.getCoordinate(prev);

    const Coordinate& p = ring.getCoordinate(index);

    const Coordinate& pn = ring.getCoordinate(next);

    env.init(pp, pn);

    env.expandToInclude(p);

    return;

}

/* public */

bool

RingHull::Corner::intersects(const Coordinate& v, const LinkedRing& ring) const

{

    const Coordinate& pp = ring.getCoordinate(prev);

    const Coordinate& p = ring.getCoordinate(index);

    const Coordinate& pn = ring.getCoordinate(next);

    return Triangle::intersects(pp, p, pn, v);

}

/* public */

bool

RingHull::Corner::isRemoved(const LinkedRing& ring) const

{

    return ring.prev(index) != prev

        || ring.next(index) != next;

}

/* public */

std::unique_ptr<LineString>

RingHull::Corner::toLineString(const LinkedRing& ring)

{

    auto coords = detail::make_unique<CoordinateSequence>();

    coords->add(ring.getCoordinate(prev));

    coords->add(ring.getCoordinate(index));

    coords->add(ring.getCoordinate(next));

    auto gfact = GeometryFactory::create();

    return gfact->createLineString(std::move(coords));

}

} // namespace geos.simplify

} // namespace geos