/********************************************************************** * $Id: geomgraph.h,v 1.7.2.1 2005/06/26 09:40:19 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_GEOMGRAPH_H#define GEOS_GEOMGRAPH_H#include <memory>#include <string>#include <vector>#include <map>#include <geos/geom.h>#include <geos/geomgraphindex.h>#include <geos/geosAlgorithm.h>#include <geos/platform.h>using namespace std;namespace geos {class EdgeSetIntersector;class SegmentIntersector;class MonotoneChainEdge;class Position {public:	enum {		/* An indicator that a Location is <i>on</i> a GraphComponent */		ON,		/* An indicator that a Location is to the <i>left</i> of a GraphComponent */  		LEFT,		/* An indicator that a Location is to the <i>right</i> of a GraphComponent */  		RIGHT	};	/**	* Returns LEFT if the position is RIGHT, RIGHT if the position is LEFT, or the position	* otherwise.	*/	static int opposite(int position);};class TopologyLocation {public:	TopologyLocation();	virtual ~TopologyLocation();	TopologyLocation(const vector<int>* newLocation);	/**	* Constructs a TopologyLocation specifying how points on, to the left of, and to the	* right of some GraphComponent relate to some Geometry. Possible values for the	* parameters are Location.NULL, Location.EXTERIOR, Location.BOUNDARY, 	* and Location.INTERIOR.	* @see Location	*/	TopologyLocation(int on, int left, int right);	TopologyLocation(int on);	TopologyLocation(const TopologyLocation *gl);	int get(int posIndex) const;	bool isNull() const;	bool isAnyNull() const;	bool isEqualOnSide(const TopologyLocation &le, int locIndex) const;	bool isArea() const;	bool isLine() const;	void flip();	void setAllLocations(int locValue);	void setAllLocationsIfNull(int locValue);	void setLocation(int locIndex, int locValue);	void setLocation(int locValue);	const vector<int>* getLocations() const;	void setLocations(int on, int left, int right);	void setLocations(const TopologyLocation &gl);	bool allPositionsEqual(int loc) const;	void merge(const TopologyLocation* gl);	string toString() const;protected:	vector<int>* location;private:	void init(int size);};class Label {public:	static Label* toLineLabel(const Label* label);	Label(int onLoc);	Label(int geomIndex, int onLoc);	Label(int onLoc, int leftLoc, int rightLoc);	Label(const Label *l);	Label();	virtual ~Label();	Label(int geomIndex,int onLoc,int leftLoc,int rightLoc);	Label(int geomIndex,const TopologyLocation* gl);	void flip();	int getLocation(int geomIndex, int posIndex) const;	int getLocation(int geomIndex) const;	void setLocation(int geomIndex, int posIndex, int location);	void setLocation(int geomIndex, int location);	void setAllLocations(int geomIndex, int location);	void setAllLocationsIfNull(int geomIndex, int location);	void setAllLocationsIfNull(int location);	void merge(const Label* lbl);	int getGeometryCount() const;	bool isNull(int geomIndex) const;	bool isAnyNull(int geomIndex) const;	bool isArea() const;	bool isArea(int geomIndex) const;	bool isLine(int geomIndex) const;	bool isEqualOnSide(Label* lbl, int side) const;	bool allPositionsEqual(int geomIndex, int loc) const;	void toLine(int geomIndex);	string toString() const;protected:	TopologyLocation* elt[2];private:	void setGeometryLocation(int geomIndex, const TopologyLocation* tl);};class Depth {public:	static int depthAtLocation(int location);	Depth();	virtual ~Depth();	int getDepth(int geomIndex,int posIndex);	void setDepth(int geomIndex,int posIndex,int depthValue);	int getLocation(int geomIndex,int posIndex);	void add(int geomIndex,int posIndex,int location);	bool isNull();	bool isNull(int geomIndex);	bool isNull(int geomIndex,int posIndex);	int getDelta(int geomIndex);	void normalize();	void add(Label* lbl);	string toString();private:	enum {		DEPTHNULL=-1 //Replaces NULL	};//	static const int DEPTHNULL=-1; //Replaces NULL	int depth[2][3];};/* * Utility functions for working with quadrants, which are numbered as follows: * <pre> * 1 | 0 * --+-- * 2 | 3 * <pre> * */class Quadrant {public:	/**	* Returns the quadrant of a directed line segment (specified as x and y	* displacements, which cannot both be 0).	*/	static int quadrant(double dx, double dy);	/**	* Returns the quadrant of a directed line segment from p0 to p1.	*/	static int quadrant(const Coordinate& p0, const Coordinate& p1);	/**	* Returns true if the quadrants are 1 and 3, or 2 and 4	*/	static bool isOpposite(int quad1, int quad2);	/* 	* Returns the right-hand quadrant of the halfplane defined by the two quadrants,	* or -1 if the quadrants are opposite, or the quadrant if they are identical.	*/	static int commonHalfPlane(int quad1, int quad2);	/**	* Returns whether the given quadrant lies within the given halfplane (specified	* by its right-hand quadrant).	*/	static bool isInHalfPlane(int quad, int halfPlane);	/**	* Returns true if the given quadrant is 0 or 1.	*/	static bool isNorthern(int quad);};//class IntersectionMatrix;class GraphComponent {public:	GraphComponent();	GraphComponent(Label* newLabel); // newLabel is deleted by destructor	virtual ~GraphComponent();	Label* getLabel();	virtual void setLabel(Label* newLabel);	virtual void setInResult(bool isInResult);	virtual bool isInResult();	virtual void setCovered(bool isCovered);	virtual bool isCovered();	virtual bool isCoveredSet();	virtual bool isVisited();	virtual void setVisited(bool isVisited);	//virtual Coordinate& getCoordinate()=0; // strk removed	virtual bool isIsolated()=0;	virtual void updateIM(IntersectionMatrix *im);protected:	Label* label;	virtual void computeIM(IntersectionMatrix *im)=0;private:	bool isInResultVar;	bool isCoveredVar;	bool isCoveredSetVar;	bool isVisitedVar;};class Node;class EdgeIntersectionList;class Edge: public GraphComponent{public:	static void updateIM(Label *lbl,IntersectionMatrix *im);	CoordinateSequence* pts;	EdgeIntersectionList *eiList;	Edge();	Edge(CoordinateSequence* newPts, Label *newLabel);	Edge(CoordinateSequence* newPts);	virtual ~Edge();	virtual int getNumPoints();	virtual void setName(string newName);	virtual const CoordinateSequence* getCoordinates() const;	virtual const Coordinate& getCoordinate(int i);	virtual const Coordinate& getCoordinate(); 	virtual Depth *getDepth();	/**	* The depthDelta is the change in depth as an edge is crossed from R to L	* @return the change in depth as the edge is crossed from R to L	*/	virtual int getDepthDelta();	virtual void setDepthDelta(int newDepthDelta);	virtual int getMaximumSegmentIndex();	virtual EdgeIntersectionList* getEdgeIntersectionList();	virtual MonotoneChainEdge* getMonotoneChainEdge();	virtual bool isClosed();	virtual bool isCollapsed();	virtual Edge* getCollapsedEdge();	virtual void setIsolated(bool newIsIsolated);	virtual bool isIsolated();	virtual void addIntersections(LineIntersector *li,int segmentIndex,int geomIndex);	virtual void addIntersection(LineIntersector *li,int segmentIndex,int geomIndex,int intIndex);	virtual void computeIM(IntersectionMatrix *im);	virtual bool isPointwiseEqual(Edge *e);	virtual string print();	virtual string printReverse();	virtual bool equals(Edge* e);	virtual Envelope* getEnvelope();private:	string name;	MonotoneChainEdge *mce;	Envelope *env;	bool isIsolatedVar;	Depth *depth;	int depthDelta;   // the change in area depth from the R to L side of this edge};class EdgeEnd {friend class Unload;public:	EdgeEnd();	virtual ~EdgeEnd();	EdgeEnd(Edge* newEdge, Coordinate& newP0, Coordinate& newP1);	EdgeEnd(Edge* newEdge, Coordinate& newP0, Coordinate& newP1, Label* newLabel);	virtual Edge* getEdge();	virtual Label* getLabel();	virtual Coordinate& getCoordinate();	virtual Coordinate& getDirectedCoordinate();	virtual int getQuadrant();	virtual double getDx();	virtual double getDy();	virtual void setNode(Node* newNode);	virtual Node* getNode();	virtual int compareTo(EdgeEnd *e);	virtual int compareDirection(EdgeEnd *e);	virtual void computeLabel();	virtual string print();protected://	static CGAlgorithms *cga;	Edge* edge;// the parent edge of this edge end	Label* label;	EdgeEnd(Edge* newEdge);	virtual void init(const Coordinate& newP0, const Coordinate& newP1);private:	Node* node;          // the node this edge end originates at	Coordinate p0,p1;  // points of initial line segment	double dx, dy;      // the direction vector for this edge from its starting point	int quadrant;};struct EdgeEndLT {	bool operator()(EdgeEnd *s1, EdgeEnd *s2) const {		return s1->compareTo(s2)<0;	}};class GeometryGraph;class EdgeEndStar {public:	EdgeEndStar();	virtual ~EdgeEndStar();	virtual void insert(EdgeEnd *e);	virtual Coordinate& getCoordinate();	virtual int getDegree();	virtual vector<EdgeEnd*>::iterator getIterator();	virtual vector<EdgeEnd*>* getEdges();	virtual EdgeEnd* getNextCW(EdgeEnd *ee);	virtual void computeLabelling(vector<GeometryGraph*> *geom); // throw(TopologyException *);	virtual int getLocation(int geomIndex,Coordinate& p,vector<GeometryGraph*> *geom);	virtual bool isAreaLabelsConsistent();	virtual void propagateSideLabels(int geomIndex); // throw(TopologyException *);	virtual int findIndex(EdgeEnd *eSearch);	virtual string print();protected:	map<EdgeEnd*,void*,EdgeEndLT> *edgeMap;	vector<EdgeEnd*> *edgeList;	virtual void insertEdgeEnd(EdgeEnd *e,void* obj);private:	int ptInAreaLocation[2];	virtual void computeEdgeEndLabels();	virtual bool checkAreaLabelsConsistent(int geomIndex);};class DirectedEdge;class EdgeRing;class DirectedEdgeStar: public EdgeEndStar {public:	DirectedEdgeStar();	~DirectedEdgeStar();	void insert(EdgeEnd *ee);	Label *getLabel();	int getOutgoingDegree();	int getOutgoingDegree(EdgeRing *er);	DirectedEdge* getRightmostEdge();	void computeLabelling(vector<GeometryGraph*> *geom); // throw(TopologyException *);	void mergeSymLabels();	void updateLabelling(Label *nodeLabel);	void linkResultDirectedEdges(); // throw(TopologyException *);	void linkMinimalDirectedEdges(EdgeRing *er);	void linkAllDirectedEdges();	void findCoveredLineEdges();	void computeDepths(DirectedEdge *de);	string print();private:	/**	 * A list of all outgoing edges in the result, in CCW order	 */	vector<DirectedEdge*> *resultAreaEdgeList;	Label *label;	vector<DirectedEdge*>* getResultAreaEdges();	enum {		SCANNING_FOR_INCOMING=1,		LINKING_TO_OUTGOING	};//	static const int SCANNING_FOR_INCOMING=1;//	static const int LINKING_TO_OUTGOING=2;	int computeDepths(int startIndex, int endIndex, int startDepth);};class Node: public GraphComponent {public:	Node(Coordinate& newCoord, EdgeEndStar* newEdges);	virtual ~Node();	virtual const Coordinate& getCoordinate() const;	virtual EdgeEndStar* getEdges();	virtual bool isIsolated();	virtual void add(EdgeEnd *e);	virtual void mergeLabel(const Node* n);	virtual void mergeLabel(const Label* label2);	virtual void setLabel(int argIndex, int onLocation);	virtual void setLabelBoundary(int argIndex);	virtual int computeMergedLocation(const Label* label2, int eltIndex);	virtual string print();	virtual const vector<double> &getZ() const;	virtual void addZ(double);	bool isIncidentEdgeInResult() const;