/********************************************************************** * $Id: opOverlay.h,v 1.8.2.1 2005/06/28 01:07:11 strk Exp $ * * GEOS - Geometry Engine Open Source * http://geos.refractions.net * * Copyright (C) 2001-2002 Vivid Solutions 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_OPOVERLAY_H#define GEOS_OPOVERLAY_H#include <memory>#include <string>#include <vector>#include <set>#include <map>#include <geos/platform.h>#include <geos/operation.h>#include <geos/geomgraph.h>#include <geos/geosAlgorithm.h>using namespace std;namespace geos {class ElevationMatrixCell {public:	ElevationMatrixCell();	~ElevationMatrixCell();	void add(const Coordinate &c);	void add(double z);	double getAvg(void) const;	double getTotal(void) const;	string print() const;private:	set<double>zvals;	double ztot;};/* */class ElevationMatrix {public:	ElevationMatrix(const Envelope &extent, unsigned int rows,		unsigned int cols);	~ElevationMatrix();	void add(const Geometry *geom);	void elevate(Geometry *geom) const;	// set Z value for each cell w/out one	double getAvgElevation() const;	ElevationMatrixCell &getCell(const Coordinate &c);	const ElevationMatrixCell &getCell(const Coordinate &c) const;	string print() const;private:	void add(const CoordinateSequence *cs);	void add(const Coordinate &c);	Envelope env;	unsigned int cols;	unsigned int rows;	double cellwidth;	double cellheight;	mutable bool avgElevationComputed;	mutable double avgElevation;	vector<ElevationMatrixCell>cells;};class ElevationMatrixFilter: public CoordinateFilter{public:	ElevationMatrixFilter(const ElevationMatrix *em);	~ElevationMatrixFilter();	void filter_rw(Coordinate *c);	void filter_ro(const Coordinate *c) {};private:	const ElevationMatrix *em;	double avgElevation;};/* * Computes the overlay of two {@link Geometry}s.  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 {		INTERSECTION=1,		UNION,		DIFFERENCE,		SYMDIFFERENCE	};	static Geometry* overlayOp(const Geometry *geom0, const Geometry *geom1,int opCode); //throw(TopologyException *);	static bool isResultOfOp(Label *label,int 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,int opCode);	OverlayOp(const Geometry *g0, const Geometry *g1);	virtual ~OverlayOp();	Geometry* getResultGeometry(int funcCode);		// throw(TopologyException *);	PlanarGraph* getGraph();	/*	 * 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 Coordinate& coord);	/*	 * 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 Coordinate& coord);	/*	 * @return true if the coord is located in the interior or boundary of	 * a geometry in the list.	 */protected:	/*	 * 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(Edge *e);private:	PointLocator *ptLocator;	const GeometryFactory *geomFact;	Geometry *resultGeom;	PlanarGraph *graph;	EdgeList *edgeList;	vector<Polygon*> *resultPolyList;	vector<LineString*> *resultLineList;	vector<Point*> *resultPointList;	void computeOverlay(int opCode); // throw(TopologyException *);	void insertUniqueEdges(vector<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(Label labelToMerge, Label existingLabel);	/*	 * 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();	/*	 * If edges which have undergone dimensional collapse are found,	 * replace them with a new edge which is a L edge	 */	void replaceCollapsedEdges();	/*	 * 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);	/*	 * 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();	/*	 * Label an isolated node with its relationship to the target geometry.	 */	void labelIncompleteNode(Node *n,int targetIndex);	/*	 * 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(int opCode);	/*	 * If both a dirEdge and its sym are marked as being in the result,	 * cancel them out.	 */	void cancelDuplicateResultEdges();	bool isCovered(const Coordinate& coord,vector<Geometry*> *geomList);	bool isCovered(const Coordinate& coord,vector<Polygon*> *geomList);	bool isCovered(const Coordinate& coord,vector<LineString*> *geomList);	/*	 * Build a Geometry containing all Geometries in the given vectors.	 * Takes element's ownership, vector control is left to caller. 	 */	Geometry* computeGeometry(vector<Point*> *nResultPointList,                              vector<LineString*> *nResultLineList,                              vector<Polygon*> *nResultPolyList);	/* Caches for memory management */	vector<Edge *>dupEdges;	/*	 * Merge Z values of node with those of the segment or vertex in	 * the given Polygon it is on.	 */	int OverlayOp::mergeZ(Node *n, const 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 OverlayOp::mergeZ(Node *n, const LineString *line) const;	/*	 * Average Z of input geometries	 */	double avgz[2];	bool avgzcomputed[2];	double getAverageZ(int targetIndex);	static double getAverageZ(const Polygon *poly);	ElevationMatrix *elevationMatrix;};/* * A ring of {@link Edge}s with the property that no node * has degree greater than 2.  These are the form of rings required * to represent polygons under the OGC SFS spatial data model. * * @see com.vividsolutions.jts.operation.overlay.MaximalEdgeRing */class MinimalEdgeRing: public EdgeRing {public:	MinimalEdgeRing(DirectedEdge *start, const GeometryFactory *geometryFactory,CGAlgorithms *cga);	virtual ~MinimalEdgeRing();	DirectedEdge* getNext(DirectedEdge *de);	void setEdgeRing(DirectedEdge *de,EdgeRing *er);};/* * A ring of {@link edges} which may contain nodes of degree > 2.