/**********************************************************************
*
* GEOS - Geometry Engine Open Source
* http://geos.osgeo.org
*
* 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.
*
***********************************************************************
*
* Last port: operation/overlay/OverlayOp.java r567 (JTS-1.12+)
*
**********************************************************************/
#ifndef GEOS_OP_OVERLAY_OVERLAYOP_H
#define GEOS_OP_OVERLAY_OVERLAYOP_H
#include <geos/export.h>
#include <geos/algorithm/PointLocator.h> // for composition
#include <geos/geom/Dimension.h> // for Dimension::DimensionType
#include <geos/geom/Location.h>
#include <geos/geomgraph/EdgeList.h> // for composition
#include <geos/geomgraph/PlanarGraph.h> // for inline (GeometryGraph->PlanarGraph)
#include <geos/operation/GeometryGraphOperation.h> // for inheritance
#include <vector>
#ifdef _MSC_VER
#pragma warning(push)
#pragma warning(disable: 4251) // warning C4251: needs to have dll-interface to be used by clients of class
#endif
// Forward declarations
namespace geos {
namespace geom {
class Geometry;
class Coordinate;
class Envelope;
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
/// \brief Computes the geometric overlay of two Geometry.
///
/// The overlay can be used to determine any
/// boolean combination of the geometries.
///
class GEOS_DLL OverlayOp: public GeometryGraphOperation {
public:
/// \brief The spatial functions supported by this class.
///
/// These operations implement various boolean combinations of
/// the resultants of the overlay.
///
enum OpCode {
/// The code for the Intersection overlay operation.
opINTERSECTION = 1,
/// The code for the Union overlay operation.
opUNION = 2,
/// The code for the Difference overlay operation.
opDIFFERENCE = 3,
/// The code for the Symmetric Difference overlay operation.
opSYMDIFFERENCE = 4
};
/** \brief
* Computes an overlay operation for the given geometry arguments.
*
* @param geom0 the first geometry argument
* @param geom1 the second geometry argument
* @param opCode the code for the desired overlay operation
* @return the result of the overlay operation
* @throws TopologyException if a robustness problem is encountered
*/
static geom::Geometry* overlayOp(const geom::Geometry* geom0,
const geom::Geometry* geom1,
OpCode opCode);
//throw(TopologyException *);
/** \brief
* Tests whether a point with a given topological [Label](@ref geomgraph::Label)
* relative to two geometries is contained in
* the result of overlaying the geometries using
* a given overlay operation.
*
* The method handles arguments of [Location::NONE](@ref geom::Location::NONE) correctly
*
* @param label the topological label of the point
* @param opCode the code for the overlay operation to test
* @return true if the label locations correspond to the overlayOpCode
*/
static bool isResultOfOp(const geomgraph::Label& label, OpCode opCode);
/// \brief This method will handle arguments of Location.NULL correctly
///
/// @return true if the locations correspond to the opCode
///
static bool isResultOfOp(geom::Location loc0, geom::Location loc1, OpCode opCode);
/// \brief 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);
~OverlayOp() override; // FIXME: virtual ?
/** \brief
* Gets the result of the overlay for a given overlay operation.
*
* Note: this method can be called once only.
*
* @param overlayOpCode the overlay operation to perform
* @return the compute result geometry
* @throws TopologyException if a robustness problem is encountered
*/
geom::Geometry* getResultGeometry(OpCode overlayOpCode);
// throw(TopologyException *);
/** \brief
* Gets the graph constructed to compute the overlay.
*
* @return the overlay graph
*/
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.
*/
/**
* Creates an empty result geometry of the appropriate dimension,
* based on the given overlay operation and the dimensions of the inputs.
* The created geometry is always an atomic geometry,
* not a collection.
*
* The empty result is constructed using the following rules:
*
* * #opINTERSECTION result has the dimension of the lowest input dimension
* * #opUNION - result has the dimension of the highest input dimension
* * #opDIFFERENCE - result has the dimension of the left-hand input
* * #opSYMDIFFERENCE - result has the dimension of the highest input dimension
*/
static std::unique_ptr<geom::Geometry> createEmptyResult(
OverlayOp::OpCode overlayOpCode, const geom::Geometry* a,
const geom::Geometry* b, const geom::GeometryFactory* geomFact);
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, const geom::Envelope* env = nullptr);
/*
* 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(uint8_t argIndex, const geom::Envelope* env = nullptr);
/** \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, uint8_t 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);
/**
* For empty result, what is the correct geometry type to apply to
* the empty?
*/
static geom::Dimension::DimensionType resultDimension(OverlayOp::OpCode overlayOpCode,
const geom::Geometry* g0, const geom::Geometry* g1);
/**
* 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,
OverlayOp::OpCode opCode);
/// 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(uint8_t targetIndex);
static double getAverageZ(const geom::Polygon* poly);
ElevationMatrix* elevationMatrix;
/// Throw TopologyException if an obviously wrong result has
/// been computed.
void checkObviouslyWrongResult(OpCode opCode);
};
} // namespace geos::operation::overlay
} // namespace geos::operation
} // namespace geos
#ifdef _MSC_VER
#pragma warning(pop)
#endif
#endif // ndef GEOS_OP_OVERLAY_OVERLAYOP_H