source: trunk/source/headers/geos/operation/overlay/OverlayOp.h@ 1820

/**********************************************************************
 * $Id: OverlayOp.h 1820 2006-09-06 16:54:23Z mloskot $
 *
 * GEOS - Geometry Engine Open Source
 * http://geos.refractions.net
 *
 * Copyright (C) 2006 Refractions Research 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.
 *
 **********************************************************************/

#ifndef GEOS_OP_OVERLAY_OVERLAYOP_H
#define GEOS_OP_OVERLAY_OVERLAYOP_H

#include <geos/operation/GeometryGraphOperation.h> // for inheritance
#include <geos/geomgraph/EdgeList.h> // for composition
#include <geos/algorithm/PointLocator.h> // for composition
#include <geos/geomgraph/PlanarGraph.h> // for inline (GeometryGraph->PlanarGraph)

#include <vector>

// Forward declarations
namespace geos {
        namespace geom {
                class Geometry;
                class Coordinate;
                class GeometryFactory;
                class Polygon;
                class LineString;
                class Point;
        }
        namespace geomgraph {
                class Label;
                class Edge;
                class Node;
        }
        namespace operation {
                namespace overlay {
                        class ElevationMatrix;
                }
        }
}

namespace geos {
namespace operation { // geos::operation
namespace overlay { // geos::operation::overlay

/// Computes the overlay of two Geometry. 
//
/// The overlay can be used to determine any
/// boolean combination of the geometries.
///
class OverlayOp: public GeometryGraphOperation {

public:

        /// The spatial functions supported by this class.
        //
        /// These operations implement various boolean combinations of
        /// the resultants of the overlay.
        ///
        enum OpCode {
                opINTERSECTION=1,
                opUNION,
                opDIFFERENCE,
                opSYMDIFFERENCE
        };

        static geom::Geometry* overlayOp(const geom::Geometry *geom0,
                        const geom::Geometry *geom1,
                        OpCode opCode);
                //throw(TopologyException *);

        static bool isResultOfOp(geomgraph::Label *label, OpCode opCode);

        /// This method will handle arguments of Location.NULL correctly
        //
        /// @return true if the locations correspond to the opCode
        ///
        static bool isResultOfOp(int loc0, int loc1, OpCode opCode);

        /// Construct an OverlayOp with the given Geometry args.
        // 
        /// Ownership of passed args will remain to caller, and
        /// the OverlayOp won't change them in any way.
        ///
        OverlayOp(const geom::Geometry *g0, const geom::Geometry *g1);

        virtual ~OverlayOp(); // FIXME: virtual ?

        geom::Geometry* getResultGeometry(OpCode funcCode);
                // throw(TopologyException *);

        geomgraph::PlanarGraph& getGraph() { return graph; }

        /** \brief
         * This method is used to decide if a point node should be included
         * in the result or not.
         *
         * @return true if the coord point is covered by a result Line
         * or Area geometry
         */
        bool isCoveredByLA(const geom::Coordinate& coord);

        /** \brief
         * This method is used to decide if an L edge should be included
         * in the result or not.
         *
         * @return true if the coord point is covered by a result Area geometry
         */
        bool isCoveredByA(const geom::Coordinate& coord);

        /*
         * @return true if the coord is located in the interior or boundary of
         * a geometry in the list.
         */

protected:

        /** \brief
         * Insert an edge from one of the noded input graphs.
         *
         * Checks edges that are inserted to see if an
         * identical edge already exists.
         * If so, the edge is not inserted, but its label is merged
         * with the existing edge.
         */
        void insertUniqueEdge(geomgraph::Edge *e);

private:

        algorithm::PointLocator ptLocator;

        const geom::GeometryFactory *geomFact;

        geom::Geometry *resultGeom;

        geomgraph::PlanarGraph graph;

        geomgraph::EdgeList edgeList;

        std::vector<geom::Polygon*> *resultPolyList;

        std::vector<geom::LineString*> *resultLineList;

        std::vector<geom::Point*> *resultPointList;

        void computeOverlay(OpCode opCode); // throw(TopologyException *);

        void insertUniqueEdges(std::vector<geomgraph::Edge*> *edges);

        /*
         * If either of the GeometryLocations for the existing label is
         * exactly opposite to the one in the labelToMerge,
         * this indicates a dimensional collapse has happened.
         * In this case, convert the label for that Geometry to a Line label
         */
        //Not needed
        //void checkDimensionalCollapse(geomgraph::Label labelToMerge, geomgraph::Label existingLabel);

        /** \brief
         * Update the labels for edges according to their depths.
         *
         * For each edge, the depths are first normalized.
         * Then, if the depths for the edge are equal,
         * this edge must have collapsed into a line edge.
         * If the depths are not equal, update the label
         * with the locations corresponding to the depths
         * (i.e. a depth of 0 corresponds to a Location of EXTERIOR,
         * a depth of 1 corresponds to INTERIOR)
         */
        void computeLabelsFromDepths();

        /** \brief
         * If edges which have undergone dimensional collapse are found,
         * replace them with a new edge which is a L edge
         */
        void replaceCollapsedEdges();

        /** \brief
         * Copy all nodes from an arg geometry into this graph.
         *
         * The node label in the arg geometry overrides any previously
         * computed label for that argIndex.
         * (E.g. a node may be an intersection node with
         * a previously computed label of BOUNDARY,
         * but in the original arg Geometry it is actually
         * in the interior due to the Boundary Determination Rule)
         */
        void copyPoints(int argIndex);

        /** \brief
         * Compute initial labelling for all DirectedEdges at each node.
         *
         * In this step, DirectedEdges will acquire a complete labelling
         * (i.e. one with labels for both Geometries)
         * only if they
         * are incident on a node which has edges for both Geometries
         */
        void computeLabelling(); // throw(TopologyException *);

        /** 
         * For nodes which have edges from only one Geometry incident on them,
         * the previous step will have left their dirEdges with no
         * labelling for the other Geometry. 
         * However, the sym dirEdge may have a labelling for the other
         * Geometry, so merge the two labels.
         */
        void mergeSymLabels();

        void updateNodeLabelling();

        /** 
         * Incomplete nodes are nodes whose labels are incomplete.
         *
         * (e.g. the location for one Geometry is NULL).
         * These are either isolated nodes,
         * or nodes which have edges from only a single Geometry incident
         * on them.
         *
         * Isolated nodes are found because nodes in one graph which
         * don't intersect nodes in the other are not completely
         * labelled by the initial process of adding nodes to the nodeList.
         * To complete the labelling we need to check for nodes that
         * lie in the interior of edges, and in the interior of areas.
         * 
         * When each node labelling is completed, the labelling of the
         * incident edges is updated, to complete their labelling as well.
         */
        void labelIncompleteNodes();

        /** \brief
         * Label an isolated node with its relationship to the target geometry.
         */
        void labelIncompleteNode(geomgraph::Node *n, int targetIndex);

        /** \brief
         * Find all edges whose label indicates that they are in the result
         * area(s), according to the operation being performed. 
         *
         * Since we want polygon shells to be
         * oriented CW, choose dirEdges with the interior of the result
         * on the RHS.
         * Mark them as being in the result.
         * Interior Area edges are the result of dimensional collapses.
         * They do not form part of the result area boundary.
         */
        void findResultAreaEdges(OpCode opCode);

        /**
         * If both a dirEdge and its sym are marked as being in the result,
         * cancel them out.
         */
        void cancelDuplicateResultEdges();

        /**
         * @return true if the coord is located in the interior or boundary of
         * a geometry in the list.
         */
        bool isCovered(const geom::Coordinate& coord,
                        std::vector<geom::Geometry*> *geomList);

        /**
         * @return true if the coord is located in the interior or boundary of
         * a geometry in the list.
         */
        bool isCovered(const geom::Coordinate& coord,
                        std::vector<geom::Polygon*> *geomList);

        /**
         * @return true if the coord is located in the interior or boundary of
         * a geometry in the list.
         */
        bool isCovered(const geom::Coordinate& coord,
                        std::vector<geom::LineString*> *geomList);

        /**
         * Build a Geometry containing all Geometries in the given vectors.
         * Takes element's ownership, vector control is left to caller. 
         */
        geom::Geometry* computeGeometry(
                        std::vector<geom::Point*> *nResultPointList,
                        std::vector<geom::LineString*> *nResultLineList,
                        std::vector<geom::Polygon*> *nResultPolyList);

        /// Caches for memory management 
        std::vector<geomgraph::Edge *>dupEdges;

        /** \brief
         * Merge Z values of node with those of the segment or vertex in
         * the given Polygon it is on.
         */
        int mergeZ(geomgraph::Node *n, const geom::Polygon *poly) const;

        /**
         * Merge Z values of node with those of the segment or vertex in
         * the given LineString it is on.
         * @returns 1 if an intersection is found, 0 otherwise.
         */
        int mergeZ(geomgraph::Node *n, const geom::LineString *line) const;

        /**
         * Average Z of input geometries
         */
        double avgz[2];
        bool avgzcomputed[2];

        double getAverageZ(int targetIndex);
        static double getAverageZ(const geom::Polygon *poly);

        ElevationMatrix *elevationMatrix;

        /// Throw TopologyException if an obviously wrong result has
        /// been computed.
        void checkObviouslyWrongResult(OpCode opCode);

};

/** \brief
 * OverlayOp::overlayOp Adapter for use with geom::BinaryOp
 */
struct overlayOp {

        OverlayOp::OpCode opCode;

        overlayOp(OverlayOp::OpCode code)
                :
                opCode(code)
        {}

        geom::Geometry* operator() (const geom::Geometry* g0,
                        const geom::Geometry* g1)
        {
                return OverlayOp::overlayOp(g0, g1, opCode);
        }

};

} // namespace geos::operation::overlay
} // namespace geos::operation
} // namespace geos

#endif // ndef GEOS_OP_OVERLAY_OVERLAYOP_H

/**********************************************************************
 * $Log$
 * Revision 1.6  2006/07/05 20:19:29  strk
 * added checks for obviously wrong result of difference and intersection ops
 *
 * Revision 1.5  2006/06/05 15:36:34  strk
 * Given OverlayOp funx code enum a name and renamed values to have a lowercase prefix. Drop all of noding headers from installed header set.
 *
 * Revision 1.4  2006/05/24 15:17:44  strk
 * Reduced number of installed headers in geos/operation/ subdir
 *
 * Revision 1.3  2006/04/14 15:04:36  strk
 * fixed missing namespace qualification in overlay::overlayOp
 *
 * Revision 1.2  2006/04/14 14:35:47  strk
 * Added overlayOp() adapter for use in templates expecting binary ops
 *
 * Revision 1.1  2006/03/17 13:24:59  strk
 * opOverlay.h header splitted. Reduced header inclusions in operation/overlay implementation files. ElevationMatrixFilter code moved from own file to ElevationMatrix.cpp (ideally a class-private).
 *
 **********************************************************************/