geomgraph.h

一个很好的vc代码

/**********************************************************************
 * $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;