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

 *

 * GEOS - Geometry Engine Open Source

 * http://geos.osgeo.org

 *

 * Copyright (C) 2020 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.

 *

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

 *

 * Last port: operation/overlayng/EdgeNodingBuilder.java 6ef89b096

 *

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

#include <geos/algorithm/Orientation.h>

#include <geos/geom/CompoundCurve.h>

#include <geos/geom/CircularString.h>

#include <geos/noding/ValidatingNoder.h>

#include <geos/noding/NodedSegmentString.h>

#include <geos/noding/MCIndexNoder.h>

#include <geos/noding/NodableArcString.h>

#include <geos/noding/SimpleNoder.h>

#include <geos/noding/snapround/SnapRoundingNoder.h>

#include <geos/operation/overlayng/EdgeNodingBuilder.h>

#include <geos/operation/overlayng/EdgeMerger.h>

#include <geos/operation/valid/RepeatedPointRemover.h>

#include <geos/operation/overlayng/OverlayUtil.h>

#include <geos/util.h>

namespace geos {      // geos

namespace operation { // geos.operation

namespace overlayng { // geos.operation.overlayng

using namespace geos::geom;

using geos::operation::valid::RepeatedPointRemover;

using geos::noding::snapround::SnapRoundingNoder;

using geos::noding::Noder;

using geos::noding::NodableArcString;

using geos::noding::MCIndexNoder;

using geos::noding::ValidatingNoder;

using geos::noding::SegmentString;

using geos::noding::SimpleNoder;

using geos::noding::NodedSegmentString;

using geos::noding::PathString;

EdgeNodingBuilder::~EdgeNodingBuilder()

{

    for (auto* ss: inputEdges) {

        delete ss;

    }

}

/*private*/

Noder*

EdgeNodingBuilder::getNoder()

{

    if (customNoder != nullptr) {

        return customNoder;

    }

    if (OverlayUtil::isFloating(pm)) {

        internalNoder = createFloatingPrecisionNoder(IS_NODING_VALIDATED);

    }

    else {

        internalNoder = createFixedPrecisionNoder(pm);

    }

    return internalNoder.get();

}

/*private*/

std::unique_ptr<Noder>

EdgeNodingBuilder::createFixedPrecisionNoder(const PrecisionModel* p_pm)

{

    std::unique_ptr<Noder> srNoder(new SnapRoundingNoder(p_pm));

    return srNoder;

}

/*private*/

std::unique_ptr<Noder>

EdgeNodingBuilder::createFloatingPrecisionNoder(bool doValidation)

{

    std::unique_ptr<Noder> ret;

    if (inputHasCurves) {

        auto simpleNoder = std::make_unique<SimpleNoder>();

        simpleNoder->setArcIntersector(arcIntAdder);

        ret = std::move(simpleNoder);

    } else {

        auto mcNoder = std::make_unique<MCIndexNoder>();

        mcNoder->setSegmentIntersector(&intAdder);

        ret = std::move(mcNoder);

    }

    // TODO: Support arcs in ValidatingNoder

    if (doValidation && !inputHasCurves) {

        spareInternalNoder = std::move(ret);

        std::unique_ptr<Noder> validNoder(new ValidatingNoder(*spareInternalNoder));

        return validNoder;

    }

    return ret;

}

/*public*/

void

EdgeNodingBuilder::setClipEnvelope(const Envelope* p_clipEnv)

{

    clipEnv = p_clipEnv;

    clipper.reset(new RingClipper(p_clipEnv));

    limiter.reset(new LineLimiter(p_clipEnv));

}

/*public*/

std::vector<Edge*>

EdgeNodingBuilder::build(const Geometry* geom0, const Geometry* geom1)

{

    inputHasZ = geom0->hasZ() || (geom1 != nullptr && geom1->hasZ());

    inputHasM = geom0->hasM() || (geom1 != nullptr && geom1->hasM());

    inputHasCurves = geom0->hasCurvedComponents() || (geom1 != nullptr && geom1->hasCurvedComponents());

    add(geom0, 0);

    add(geom1, 1);

    std::vector<Edge*> nodedEdges = node(inputEdges);

    /**

     * Merge the noded edges to eliminate duplicates.

     * Labels are combined.

     */

    return EdgeMerger::merge(nodedEdges);

}

/*private*/

std::vector<Edge*>

EdgeNodingBuilder::node(const std::vector<PathString*>& segStrings)

{

    std::vector<Edge*> nodedEdges;

    Noder* noder = getNoder();

    noder->computePathNodes(segStrings);

    auto nodedSS = noder->getNodedPaths();

    nodedEdges = createEdges(nodedSS);

    return nodedEdges;

}

/*private*/

std::vector<Edge*>

EdgeNodingBuilder::createEdges(std::vector<std::unique_ptr<PathString>>& segStrings)

{

    std::vector<Edge*> createdEdges;

    for (auto& ss : segStrings) {

        const auto& pts = ss->getCoordinates();

        const bool isCurved = dynamic_cast<const noding::ArcString*>(ss.get());

        // don't create edges from collapsed lines

        if (Edge::isCollapsed(pts.get())) continue;

        // This EdgeSourceInfo is already managed locally in a std::deque

        const EdgeSourceInfo* info = static_cast<const EdgeSourceInfo*>(ss->getData());

        // Record that a non-collapsed edge exists for the parent geometry

        hasEdges[info->getIndex()] = true;

        // Allocate the new Edge locally in a std::deque

        edgeQue.emplace_back(ss->getCoordinates(), info, isCurved);

        Edge* newEdge = &(edgeQue.back());

        createdEdges.push_back(newEdge);

    }

    return createdEdges;

}

/*public*/

bool

EdgeNodingBuilder::hasEdgesFor(uint8_t geomIndex) const

{

    assert(geomIndex < 2);

    return hasEdges[geomIndex];

}

/*private*/

void

EdgeNodingBuilder::add(const Geometry* g, uint8_t geomIndex)

{

    if (g == nullptr || g->isEmpty())

        return;

    if (isClippedCompletely(g->getEnvelopeInternal()))

        return;

    switch (g->getGeometryTypeId())

    {

        case GEOS_POLYGON:

        case GEOS_CURVEPOLYGON:

            return addPolygon(static_cast<const Surface*>(g), geomIndex);

        case GEOS_LINESTRING:

        case GEOS_LINEARRING:

        case GEOS_CIRCULARSTRING:

            return addSimpleCurve(static_cast<const SimpleCurve*>(g), geomIndex);

        case GEOS_COMPOUNDCURVE:

            return addCompoundCurve(static_cast<const CompoundCurve*>(g), geomIndex);

        case GEOS_MULTILINESTRING:

        case GEOS_MULTIPOLYGON:

        case GEOS_MULTICURVE:

        case GEOS_MULTISURFACE:

            return addCollection(static_cast<const GeometryCollection*>(g), geomIndex);

        case GEOS_GEOMETRYCOLLECTION:

            return addGeometryCollection(static_cast<const GeometryCollection*>(g), geomIndex, g->getDimension());

        case GEOS_POINT:

        case GEOS_MULTIPOINT:

            return; // do nothing

        default:

            throw util::IllegalArgumentException("Unexpected geometry type: " + g->getGeometryType());

            return; // do nothing

    }

}

/*private*/

void

EdgeNodingBuilder::addCollection(const GeometryCollection* gc, uint8_t geomIndex)

{

    for (std::size_t i = 0; i < gc->getNumGeometries(); i++) {

        const Geometry* g = gc->getGeometryN(i);

        add(g, geomIndex);

    }

}

/*private*/

void

EdgeNodingBuilder::addGeometryCollection(const GeometryCollection* gc, uint8_t geomIndex, int expectedDim)

{

    for (std::size_t i = 0; i < gc->getNumGeometries(); i++) {

        const Geometry* g = gc->getGeometryN(i);

        if (g->getDimension() != expectedDim) {

            throw geos::util::IllegalArgumentException("Overlay input is mixed-dimension");

        }

        add(g, geomIndex);

    }

}

/*private*/

void

EdgeNodingBuilder::addPolygon(const Surface* poly, uint8_t geomIndex)

{

    const Curve* shell = poly->getExteriorRing();

    addPolygonRing(shell, false, geomIndex);

    for (std::size_t i = 0; i < poly->getNumInteriorRing(); i++) {

        const Curve* hole = poly->getInteriorRingN(i);

        // Holes are topologically labelled opposite to the shell, since

        // the interior of the polygon lies on their opposite side

        // (on the left, if the hole is oriented CW)

        addPolygonRing(hole, true, geomIndex);

    }

}

/*private*/

void

EdgeNodingBuilder::addPolygonRing(const Curve* ring, bool isHole, uint8_t geomIndex)

{

    // don't add empty rings

    if (ring->isEmpty()) return;

    if (isClippedCompletely(ring->getEnvelopeInternal()))

      return;

    const auto type = ring->getGeometryTypeId();

    if (type == GEOS_COMPOUNDCURVE) {

        const CompoundCurve* cc = static_cast<const CompoundCurve*>(ring);

        const auto coords = ring->getCoordinates();

        const int depthDelta = computeDepthDelta(coords.get(), isHole);

        const EdgeSourceInfo* eso = createEdgeSourceInfo(geomIndex, depthDelta, isHole);

        for (std::size_t i = 0; i < cc->getNumCurves(); i++) {

            const SimpleCurve* section = cc->getCurveN(i);

            if (section->getNumPoints() >= 2) {

                if (section->getGeometryTypeId() == GEOS_CIRCULARSTRING) {

                    const CircularString* cs = static_cast<const CircularString*>(section);

                    addCurvedEdge(cs->getSharedCoordinates(), cs->getArcs(), eso);

                } else {

                    addEdge(section->getSharedCoordinates(), eso);

                }

            }

        }

        return;

    }

    const SimpleCurve* scRing = static_cast<const SimpleCurve*>(ring);

    const int depthDelta = computeDepthDelta(scRing->getCoordinatesRO(), isHole);

    const EdgeSourceInfo* esInfo = createEdgeSourceInfo(geomIndex, depthDelta, isHole);

    if (ring->getGeometryTypeId() == GEOS_LINEARRING || ring->getGeometryTypeId() == GEOS_LINESTRING) {

        // TODO: Support CircularString in RingClipper

        std::shared_ptr<const CoordinateSequence> pts = clip(static_cast<const LineString*>(ring));

        /**

        * Don't add edges that collapse to a point

        */

        if (pts->size() < 2) {

            return;

        }

        addEdge(pts, esInfo);

    } else {

        assert(ring->getGeometryTypeId() == GEOS_CIRCULARSTRING);

        const CircularString* cs = static_cast<const CircularString*>(ring);

        addCurvedEdge(cs->getSharedCoordinates(), cs->getArcs(), esInfo);

    }

}

/*private*/

const EdgeSourceInfo*

EdgeNodingBuilder::createEdgeSourceInfo(uint8_t index)

{

    // Concentrate small memory allocations via std::deque and

    // retain ownership of the EdgeSourceInfo* in the EdgeNodingBuilder

    edgeSourceInfoQue.emplace_back(index);

    return &(edgeSourceInfoQue.back());

}

/*private*/

const EdgeSourceInfo*

EdgeNodingBuilder::createEdgeSourceInfo(uint8_t index, int depthDelta, bool isHole)

{

    // Concentrate small memory allocations via std::deque and

    // retain ownership of the EdgeSourceInfo* in the EdgeNodingBuilder

    edgeSourceInfoQue.emplace_back(index, depthDelta, isHole);

    return &(edgeSourceInfoQue.back());

}

/*private*/

void

EdgeNodingBuilder::addEdge(const std::shared_ptr<const CoordinateSequence>& cas, const EdgeSourceInfo* info)

{

    // TODO: manage these internally to EdgeNodingBuilder in a std::deque,

    // since they do not have a life span longer than the EdgeNodingBuilder

    // in OverlayNG::buildGraph()

    NodedSegmentString* ss = new NodedSegmentString(cas, inputHasZ, inputHasM, reinterpret_cast<const void*>(info));

    inputEdges.push_back(ss);

}

void

EdgeNodingBuilder::addCurvedEdge(const std::shared_ptr<const CoordinateSequence>& cas, const std::vector<CircularArc>& arcs, const EdgeSourceInfo* info)

{

    NodableArcString* as = new NodableArcString(arcs, cas, inputHasZ, inputHasM, reinterpret_cast<const void*>(info));

    inputEdges.push_back(as);

}

/*private*/

bool

EdgeNodingBuilder::isClippedCompletely(const Envelope* env) const

{

    if (clipEnv == nullptr) return false;

    return clipEnv->disjoint(env);

}

/* private */

std::shared_ptr<const CoordinateSequence>

EdgeNodingBuilder::clip(const LineString* ring) const

{

    const Envelope* env = ring->getEnvelopeInternal();

    /**

     * If no clipper or ring is completely contained then no need to clip.

     * We also cannot clip if any input contains curves, because curved

     * rings are not currently clipped and clipping only some rings could

     * disrupt the polygon topology.

     * But repeated points must be removed to ensure correct noding.

     */

    if (clipper == nullptr || clipEnv->covers(env) || inputHasCurves) {

        return removeRepeatedPoints(ring);

    }

    return clipper->clip(ring->getCoordinatesRO());

}

/*private*/

std::shared_ptr<const CoordinateSequence>

EdgeNodingBuilder::removeRepeatedPoints(const LineString* line)

{

    const std::shared_ptr<const CoordinateSequence>& pts = line->getSharedCoordinates();

    if (pts->hasRepeatedPoints()) {

        return RepeatedPointRemover::removeRepeatedPoints(pts.get());

    } else {

        return pts;

    }

}

/*private*/

int

EdgeNodingBuilder::computeDepthDelta(const CoordinateSequence* ringCoords, bool isHole)

{

    /**

     * Compute the orientation of the ring, to

     * allow assigning side interior/exterior labels correctly.

     * JTS canonical orientation is that shells are CW, holes are CCW.

     *

     * It is important to compute orientation on the original ring,

     * since topology collapse can make the orientation computation give the wrong answer.

     */

    const bool isCCW = algorithm::Orientation::isCCW(ringCoords);

    /**

     * Compute whether ring is in canonical orientation or not.

     * Canonical orientation for the overlay process is

     * Shells : CW, Holes: CCW

     */

    bool isOriented = true;

    if (!isHole) {

        isOriented = !isCCW;

    }

    else {

        isOriented = isCCW;

    }

    /**

     * Depth delta can now be computed.

     * Canonical depth delta is 1 (Exterior on L, Interior on R).

     * It is flipped to -1 if the ring is oppositely oriented.

     */

    int depthDelta = isOriented ? 1 : -1;

    return depthDelta;

}

/*private*/

void

EdgeNodingBuilder::addSimpleCurve(const SimpleCurve* curve, uint8_t geomIndex)

{

    // don't add empty lines

    if (curve->isEmpty()) return;

    if (isClippedCompletely(curve->getEnvelopeInternal()))

        return;

    if (curve->getGeometryTypeId() == GEOS_CIRCULARSTRING) {

        // TODO: Support CircularString in LineLimiter

        const CircularString* cs = static_cast<const CircularString*>(curve);

        addCurve(cs->getSharedCoordinates(), cs->getArcs(), geomIndex);

        return;

    }

    const LineString* line = detail::down_cast<const LineString*>(curve);

    if (isToBeLimited(line)) {

        std::vector<std::unique_ptr<CoordinateSequence>>& sections = limit(line);

        for (auto& pts : sections) {

            addLine(std::move(pts), geomIndex);

        }

    }

    else {

        const auto ptsNoRepeat = removeRepeatedPoints(line);

        addLine(ptsNoRepeat, geomIndex);

    }

}

void

EdgeNodingBuilder::addCompoundCurve(const CompoundCurve* curve, uint8_t geomIndex)

{

    for (std::size_t i = 0; i < curve->getNumCurves(); i++) {

        addSimpleCurve(curve->getCurveN(i), geomIndex);

    }

}

/*private*/

void

EdgeNodingBuilder::addLine(const std::shared_ptr<const CoordinateSequence>& pts, uint8_t geomIndex)

{

    /**

     * Don't add edges that collapse to a point

     */

    if (pts->size() < 2) {

        return;

    }

    addEdge(pts, createEdgeSourceInfo(geomIndex));

}

/*private*/

void

EdgeNodingBuilder::addCurve(const std::shared_ptr<const CoordinateSequence>& pts, const std::vector<CircularArc>& arcs, uint8_t geomIndex)

{

    /**

     * Don't add edges that collapse to a point

     */

    if (pts->size() < 2) {

        return;

    }

    addCurvedEdge(pts, arcs, createEdgeSourceInfo(geomIndex));

}

/*private*/

bool

EdgeNodingBuilder::isToBeLimited(const LineString* line) const

{

    const CoordinateSequence* pts = line->getCoordinatesRO();

    if (limiter == nullptr || pts->size() <= MIN_LIMIT_PTS) {

        return false;

    }

    const Envelope* env = line->getEnvelopeInternal();

    /**

     * If line is completely contained then no need to limit

     */

    if (clipEnv->covers(env)) {

        return false;

    }

    return true;

}

/*private*/

std::vector<std::unique_ptr<CoordinateSequence>>&

EdgeNodingBuilder::limit(const LineString* line) const

{

    const CoordinateSequence* pts = line->getCoordinatesRO();

    return limiter->limit(pts);

}

} // namespace geos.operation.overlayng

} // namespace geos.operation

} // namespace geos