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

 *

 * GEOS - Geometry Engine Open Source

 * http://geos.osgeo.org

 *

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

 * 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/OverlayNG.java 4c88fea52

 *

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

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

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

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

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

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

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

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

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

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

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

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

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

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

#include <geos/geom/CoordinateSequence.h>

#include <geos/geom/Envelope.h>

#include <geos/geom/Location.h>

#include <geos/geom/Geometry.h>

#include <geos/util/Interrupt.h>

#include <geos/util/TopologyException.h>

#include <algorithm>

#ifndef GEOS_DEBUG

#define GEOS_DEBUG 0

#endif

#if GEOS_DEBUG

# include <iostream>

# include <geos/io/WKTWriter.h>

#endif

namespace geos {      // geos

namespace operation { // geos.operation

namespace overlayng { // geos.operation.overlayng

using namespace geos::geom;

/*public static*/

bool

OverlayNG::isResultOfOpPoint(const OverlayLabel* label, int opCode)

{

    Location loc0 = label->getLocation(0);

    Location loc1 = label->getLocation(1);

    return isResultOfOp(opCode, loc0, loc1);

}

/*public static*/

bool

OverlayNG::isResultOfOp(int overlayOpCode, Location loc0, Location loc1)

{

    if (loc0 == Location::BOUNDARY) loc0 = Location::INTERIOR;

    if (loc1 == Location::BOUNDARY) loc1 = Location::INTERIOR;

    switch (overlayOpCode) {

        case INTERSECTION:

            return loc0 == Location::INTERIOR

                && loc1 == Location::INTERIOR;

        case UNION:

            return loc0 == Location::INTERIOR

                || loc1 == Location::INTERIOR;

        case DIFFERENCE:

            return loc0 == Location::INTERIOR

                && loc1 != Location::INTERIOR;

        case SYMDIFFERENCE:

            return   (loc0 == Location::INTERIOR && loc1 != Location::INTERIOR)

                  || (loc0 != Location::INTERIOR && loc1 == Location::INTERIOR);

    }

    return false;

}

/*public static*/

std::unique_ptr<Geometry>

OverlayNG::overlay(const Geometry* geom0, const Geometry* geom1,

        int opCode, const PrecisionModel* pm)

{

    OverlayNG ov(geom0, geom1, pm, opCode);

    return ov.getResult();

}

/*public static*/

std::unique_ptr<Geometry>

OverlayNG::overlay(const Geometry* geom0, const Geometry* geom1,

        int opCode, const PrecisionModel* pm, noding::Noder* noder)

{

    OverlayNG ov(geom0, geom1, pm, opCode);

    ov.setNoder(noder);

    return ov.getResult();

}

/*public static*/

std::unique_ptr<Geometry>

OverlayNG::overlay(const Geometry* geom0, const Geometry* geom1,

        int opCode, noding::Noder* noder)

{

    OverlayNG ov(geom0, geom1, static_cast<PrecisionModel*>(nullptr), opCode);

    ov.setNoder(noder);

    return ov.getResult();

}

/*public static*/

std::unique_ptr<Geometry>

OverlayNG::overlay(const Geometry* geom0, const Geometry* geom1, int opCode)

{

    OverlayNG ov(geom0, geom1, opCode);

    return ov.getResult();

}

/*public static*/

std::unique_ptr<Geometry>

OverlayNG::geomunion(const Geometry* geom, const PrecisionModel* pm)

{

    OverlayNG ov(geom, pm);

    return ov.getResult();

}

/*public static*/

std::unique_ptr<Geometry>

OverlayNG::geomunion(const Geometry* geom, const PrecisionModel* pm, noding::Noder* noder)

{

    OverlayNG ov(geom, pm);

    ov.setNoder(noder);

    ov.setStrictMode(true);

    return ov.getResult();

}

/*public*/

std::unique_ptr<Geometry>

OverlayNG::getResult()

{

    const Geometry *ig0 = inputGeom.getGeometry(0);

    const Geometry *ig1 = inputGeom.getGeometry(1);

    if ( OverlayUtil::isEmptyResult(opCode, ig0, ig1, pm) )

    {

        return createEmptyResult();

    }

    /**

     * The elevation model is only computed if the input geometries have Z values.

     */

    std::unique_ptr<ElevationModel> elevModel;

    if ( ig1 ) {

        elevModel = ElevationModel::create(*ig0, *ig1);

    } else {

        elevModel = ElevationModel::create(*ig0);

    }

    std::unique_ptr<Geometry> result;

    if (inputGeom.isAllPoints()) {

        // handle Point-Point inputs

        result = OverlayPoints::overlay(opCode, ig0, ig1, pm);

    }

    else if (! inputGeom.isSingle() &&  inputGeom.hasPoints()) {

        // handle Point-nonPoint inputs

        result = OverlayMixedPoints::overlay(opCode, ig0, ig1, pm);

    }

    else {

        // handle case where both inputs are formed of edges (Lines and Polygons)

        result = computeEdgeOverlay();

    }

#if GEOS_DEBUG

    io::WKTWriter w;

    std::cerr << "Before populatingZ: " << w.write(result.get()) << std::endl;

#endif

    /**

     * This is a no-op if the elevation model was not computed due to

     * Z not present

     */

    elevModel->populateZ(*result);

#if GEOS_DEBUG

    std::cerr << " After populatingZ: " << w.write(result.get()) << std::endl;

#endif

    return result;

}

/*private*/

std::unique_ptr<Geometry>

OverlayNG::computeEdgeOverlay()

{

    /**

     * Node the edges, using whatever noder is being used

     * Formerly in nodeEdges())

     */

    EdgeNodingBuilder nodingBuilder(pm, noder);

    // clipEnv not always used, but needs to remain in scope

    // as long as nodingBuilder when it is.

    Envelope clipEnv;

    GEOS_CHECK_FOR_INTERRUPTS();

    if (isOptimized) {

        bool gotClipEnv = OverlayUtil::clippingEnvelope(opCode, &inputGeom, pm, clipEnv);

        if (gotClipEnv) {

            nodingBuilder.setClipEnvelope(&clipEnv);

        }

    }

    std::vector<Edge*> edges = nodingBuilder.build(

        inputGeom.getGeometry(0),

        inputGeom.getGeometry(1));

    GEOS_CHECK_FOR_INTERRUPTS();

    /**

     * Record if an input geometry has collapsed.

     * This is used to avoid trying to locate disconnected edges

     * against a geometry which has collapsed completely.

     */

    inputGeom.setCollapsed(0, ! nodingBuilder.hasEdgesFor(0));

    inputGeom.setCollapsed(1, ! nodingBuilder.hasEdgesFor(1));

    /**

    * Inlined buildGraph() method here for memory purposes, so the

    * Edge* list allocated in the EdgeNodingBuilder survives

    * long enough to be copied into the OverlayGraph

    */

    // Sort the edges first, for comparison with JTS results

    // std::sort(edges.begin(), edges.end(), EdgeComparator);

    OverlayGraph graph;

    for (Edge* e : edges) {

        // Write out edge coordinates

        // std::cout << *e->getCoordinatesRO() << std::endl;

        graph.addEdge(e);

    }

    if (isOutputNodedEdges) {

        return OverlayUtil::toLines(&graph, isOutputEdges, geomFact);

    }

    GEOS_CHECK_FOR_INTERRUPTS();

    labelGraph(&graph);

    // std::cout << std::endl << graph << std::endl;

    if (isOutputEdges || isOutputResultEdges) {

        return OverlayUtil::toLines(&graph, isOutputEdges, geomFact);

    }

    GEOS_CHECK_FOR_INTERRUPTS();

    std::unique_ptr<Geometry> result = extractResult(opCode, &graph);

    /**

     * Heuristic check on result area.

     * Catches cases where noding causes vertex to move

     * and make topology graph area "invert".

     */

    if (OverlayUtil::isFloating(pm)) {

        bool isAreaConsistent = OverlayUtil::isResultAreaConsistent(

            inputGeom.getGeometry(0),

            inputGeom.getGeometry(1),

            opCode, result.get());

        if (! isAreaConsistent)

            throw util::TopologyException("Result area inconsistent with overlay operation");

    }

    return result;

}

/*private*/

void

OverlayNG::labelGraph(OverlayGraph* graph)

{

    OverlayLabeller labeller(graph, &inputGeom);

    labeller.computeLabelling();

    labeller.markResultAreaEdges(opCode);

    labeller.unmarkDuplicateEdgesFromResultArea();

}

/*private*/

std::unique_ptr<Geometry>

OverlayNG::extractResult(int p_opCode, OverlayGraph* graph)

{

#if GEOS_DEBUG

    std::cerr << "OverlayNG::extractResult: graph: " << *graph << std::endl;

#endif

    bool isAllowMixedIntResult = ! isStrictMode;

    //--- Build polygons

    std::vector<OverlayEdge*> resultAreaEdges = graph->getResultAreaEdges();

    PolygonBuilder polyBuilder(resultAreaEdges, geomFact);

    std::vector<std::unique_ptr<Polygon>> resultPolyList = polyBuilder.getPolygons();

    bool hasResultAreaComponents = (!resultPolyList.empty());

    std::vector<std::unique_ptr<LineString>> resultLineList;

    std::vector<std::unique_ptr<Point>> resultPointList;

    GEOS_CHECK_FOR_INTERRUPTS();

    if (!isAreaResultOnly) {

        //--- Build lines

        bool allowResultLines = !hasResultAreaComponents ||

                                isAllowMixedIntResult ||

                                opCode == SYMDIFFERENCE ||

                                opCode == UNION;

        if (allowResultLines) {

            LineBuilder lineBuilder(&inputGeom, graph, hasResultAreaComponents, p_opCode, geomFact);

            lineBuilder.setStrictMode(isStrictMode);

            resultLineList = lineBuilder.getLines();

        }

        /**

         * Operations with point inputs are handled elsewhere.

         * Only an intersection op can produce point results

         * from non-point inputs.

         */

        bool hasResultComponents = hasResultAreaComponents || (!resultLineList.empty());

        bool allowResultPoints = ! hasResultComponents || isAllowMixedIntResult;

        if (opCode == INTERSECTION && allowResultPoints) {

            IntersectionPointBuilder pointBuilder(graph, geomFact);

            pointBuilder.setStrictMode(isStrictMode);

            resultPointList = pointBuilder.getPoints();

        }

    }

    if (resultPolyList.empty() &&

        resultLineList.empty() &&

        resultPointList.empty())

    {

        return createEmptyResult();

    }

    std::unique_ptr<Geometry> resultGeom = OverlayUtil::createResultGeometry(resultPolyList, resultLineList, resultPointList, geomFact);

    return resultGeom;

}

/*private*/

std::unique_ptr<Geometry>

OverlayNG::createEmptyResult()

{

    uint8_t coordDim = OverlayUtil::resultCoordinateDimension(

                            inputGeom.getCoordinateDimension(0), 

                            inputGeom.getCoordinateDimension(1));

    return OverlayUtil::createEmptyResult(

                OverlayUtil::resultDimension(opCode,

                    inputGeom.getDimension(0),

                    inputGeom.getDimension(1)),

                    coordDim,

                    geomFact);

}

} // namespace geos.operation.overlayng

} // namespace geos.operation

} // namespace geos