Main Page | Namespace List | Class Hierarchy | Class List | Directories | File List | Namespace Members | Class Members

geomgraph.h

00001 /**********************************************************************
00002  * $Id: geomgraph.h,v 1.7 2004/11/20 15:46:45 strk Exp $
00003  *
00004  * GEOS - Geometry Engine Open Source
00005  * http://geos.refractions.net
00006  *
00007  * Copyright (C) 2001-2002 Vivid Solutions Inc.
00008  *
00009  * This is free software; you can redistribute and/or modify it under
00010  * the terms of the GNU Lesser General Public Licence as published
00011  * by the Free Software Foundation. 
00012  * See the COPYING file for more information.
00013  *
00014  **********************************************************************/
00015 
00016 
00017 #ifndef GEOS_GEOMGRAPH_H
00018 #define GEOS_GEOMGRAPH_H
00019 
00020 #include <memory>
00021 #include <string>
00022 #include <vector>
00023 #include <map>
00024 #include <geos/geom.h>
00025 #include <geos/geomgraphindex.h>
00026 #include <geos/geosAlgorithm.h>
00027 #include <geos/platform.h>
00028 
00029 using namespace std;
00030 
00031 namespace geos {
00032 
00033 class EdgeSetIntersector;
00034 class SegmentIntersector;
00035 class MonotoneChainEdge;
00036 
00037 
00038 class Position {
00039 public:
00040         enum {
00041                 /* An indicator that a Location is <i>on</i> a GraphComponent */
00042                 ON,
00043                 /* An indicator that a Location is to the <i>left</i> of a GraphComponent */  
00044                 LEFT,
00045                 /* An indicator that a Location is to the <i>right</i> of a GraphComponent */  
00046                 RIGHT
00047         };
00052         static int opposite(int position);
00053 };
00054 
00055 class TopologyLocation {
00056 public:
00057         TopologyLocation();
00058         virtual ~TopologyLocation();
00059         TopologyLocation(const vector<int>* newLocation);
00067         TopologyLocation(int on, int left, int right);
00068         TopologyLocation(int on);
00069         TopologyLocation(const TopologyLocation *gl);
00070         int get(int posIndex) const;
00071         bool isNull() const;
00072         bool isAnyNull() const;
00073         bool isEqualOnSide(const TopologyLocation &le, int locIndex) const;
00074         bool isArea() const;
00075         bool isLine() const;
00076         void flip();
00077         void setAllLocations(int locValue);
00078         void setAllLocationsIfNull(int locValue);
00079         void setLocation(int locIndex, int locValue);
00080         void setLocation(int locValue);
00081         const vector<int>* getLocations() const;
00082         void setLocations(int on, int left, int right);
00083         void setLocations(const TopologyLocation &gl);
00084         bool allPositionsEqual(int loc) const;
00085         void merge(const TopologyLocation* gl);
00086         string toString() const;
00087 protected:
00088         vector<int>* location;
00089 private:
00090         void init(int size);
00091 };
00092 
00093 class Label {
00094 public:
00095         static Label* toLineLabel(const Label* label);
00096         Label(int onLoc);
00097         Label(int geomIndex, int onLoc);
00098         Label(int onLoc, int leftLoc, int rightLoc);
00099         Label(const Label *l);
00100         Label();
00101         virtual ~Label();
00102         Label(int geomIndex,int onLoc,int leftLoc,int rightLoc);
00103         Label(int geomIndex,const TopologyLocation* gl);
00104         void flip();
00105         int getLocation(int geomIndex, int posIndex) const;
00106         int getLocation(int geomIndex) const;
00107         void setLocation(int geomIndex, int posIndex, int location);
00108         void setLocation(int geomIndex, int location);
00109         void setAllLocations(int geomIndex, int location);
00110         void setAllLocationsIfNull(int geomIndex, int location);
00111         void setAllLocationsIfNull(int location);
00112         void merge(const Label* lbl);
00113         int getGeometryCount() const;
00114         bool isNull(int geomIndex) const;
00115         bool isAnyNull(int geomIndex) const;
00116         bool isArea() const;
00117         bool isArea(int geomIndex) const;
00118         bool isLine(int geomIndex) const;
00119         bool isEqualOnSide(Label* lbl, int side) const;
00120         bool allPositionsEqual(int geomIndex, int loc) const;
00121         void toLine(int geomIndex);
00122         string toString() const;
00123 protected:
00124         TopologyLocation* elt[2];
00125 private:
00126         void setGeometryLocation(int geomIndex, const TopologyLocation* tl);
00127 };
00128 
00129 class Depth {
00130 public:
00131         static int depthAtLocation(int location);
00132         Depth();
00133         virtual ~Depth();
00134         int getDepth(int geomIndex,int posIndex);
00135         void setDepth(int geomIndex,int posIndex,int depthValue);
00136         int getLocation(int geomIndex,int posIndex);
00137         void add(int geomIndex,int posIndex,int location);
00138         bool isNull();
00139         bool isNull(int geomIndex);
00140         bool isNull(int geomIndex,int posIndex);
00141         int getDelta(int geomIndex);
00142         void normalize();
00143         void add(Label* lbl);
00144         string toString();
00145 private:
00146         enum {
00147                 DEPTHNULL=-1 //Replaces NULL
00148         };
00149 //      static const int DEPTHNULL=-1; //Replaces NULL
00150         int depth[2][3];
00151 };
00152 
00153 /*
00154  * Utility functions for working with quadrants, which are numbered as follows:
00155  * <pre>
00156  * 1 | 0
00157  * --+--
00158  * 2 | 3
00159  * <pre>
00160  *
00161  */
00162 class Quadrant {
00163 public:
00168         static int quadrant(double dx, double dy);
00172         static int quadrant(const Coordinate& p0, const Coordinate& p1);
00176         static bool isOpposite(int quad1, int quad2);
00177         /* 
00178         * Returns the right-hand quadrant of the halfplane defined by the two quadrants,
00179         * or -1 if the quadrants are opposite, or the quadrant if they are identical.
00180         */
00181         static int commonHalfPlane(int quad1, int quad2);
00186         static bool isInHalfPlane(int quad, int halfPlane);
00190         static bool isNorthern(int quad);
00191 };
00192 
00193 //class IntersectionMatrix;
00194 class GraphComponent {
00195 public:
00196         GraphComponent();
00197         GraphComponent(Label* newLabel); // newLabel is deleted by destructor
00198         virtual ~GraphComponent();
00199         Label* getLabel();
00200         virtual void setLabel(Label* newLabel);
00201         virtual void setInResult(bool isInResult);
00202         virtual bool isInResult();
00203         virtual void setCovered(bool isCovered);
00204         virtual bool isCovered();
00205         virtual bool isCoveredSet();
00206         virtual bool isVisited();
00207         virtual void setVisited(bool isVisited);
00208         //virtual Coordinate& getCoordinate()=0; // strk removed
00209         virtual bool isIsolated()=0;
00210         virtual void updateIM(IntersectionMatrix *im);
00211 protected:
00212         Label* label;
00213         virtual void computeIM(IntersectionMatrix *im)=0;
00214 private:
00215         bool isInResultVar;
00216         bool isCoveredVar;
00217         bool isCoveredSetVar;
00218         bool isVisitedVar;
00219 };
00220 
00221 class Node;
00222 class EdgeIntersectionList;
00223 class Edge: public GraphComponent{
00224 public:
00225         static void updateIM(Label *lbl,IntersectionMatrix *im);
00226         CoordinateSequence* pts;
00227         EdgeIntersectionList *eiList;
00228         Edge();
00229         Edge(CoordinateSequence* newPts, Label *newLabel);
00230         Edge(CoordinateSequence* newPts);
00231         virtual ~Edge();
00232         virtual int getNumPoints();
00233         virtual void setName(string newName);
00234         virtual const CoordinateSequence* getCoordinates() const;
00235         virtual const Coordinate& getCoordinate(int i);
00236         virtual const Coordinate& getCoordinate(); 
00237         virtual Depth *getDepth();
00242         virtual int getDepthDelta();
00243         virtual void setDepthDelta(int newDepthDelta);
00244         virtual int getMaximumSegmentIndex();
00245         virtual EdgeIntersectionList* getEdgeIntersectionList();
00246         virtual MonotoneChainEdge* getMonotoneChainEdge();
00247         virtual bool isClosed();
00248         virtual bool isCollapsed();
00249         virtual Edge* getCollapsedEdge();
00250         virtual void setIsolated(bool newIsIsolated);
00251         virtual bool isIsolated();
00252         virtual void addIntersections(LineIntersector *li,int segmentIndex,int geomIndex);
00253         virtual void addIntersection(LineIntersector *li,int segmentIndex,int geomIndex,int intIndex);
00254         virtual void computeIM(IntersectionMatrix *im);
00255         virtual bool isPointwiseEqual(Edge *e);
00256         virtual string print();
00257         virtual string printReverse();
00258         virtual bool equals(Edge* e);
00259         virtual Envelope* getEnvelope();
00260 private:
00261         string name;
00262         MonotoneChainEdge *mce;
00263         Envelope *env;
00264         bool isIsolatedVar;
00265         Depth *depth;
00266         int depthDelta;   // the change in area depth from the R to L side of this edge
00267 };
00268 
00269 class EdgeEnd {
00270 friend class Unload;
00271 public:
00272         EdgeEnd();
00273         virtual ~EdgeEnd();
00274         EdgeEnd(Edge* newEdge, Coordinate& newP0, Coordinate& newP1);
00275         EdgeEnd(Edge* newEdge, Coordinate& newP0, Coordinate& newP1, Label* newLabel);
00276         virtual Edge* getEdge();
00277         virtual Label* getLabel();
00278         virtual Coordinate& getCoordinate();
00279         virtual Coordinate& getDirectedCoordinate();
00280         virtual int getQuadrant();
00281         virtual double getDx();
00282         virtual double getDy();
00283         virtual void setNode(Node* newNode);
00284         virtual Node* getNode();
00285         virtual int compareTo(EdgeEnd *e);
00286         virtual int compareDirection(EdgeEnd *e);
00287         virtual void computeLabel();
00288         virtual string print();
00289 protected:
00290 //      static CGAlgorithms *cga;
00291         Edge* edge;// the parent edge of this edge end
00292         Label* label;
00293         EdgeEnd(Edge* newEdge);
00294         virtual void init(const Coordinate& newP0, const Coordinate& newP1);
00295 private:
00296         Node* node;          // the node this edge end originates at
00297         Coordinate p0,p1;  // points of initial line segment
00298         double dx, dy;      // the direction vector for this edge from its starting point
00299         int quadrant;
00300 };
00301 
00302 struct EdgeEndLT {
00303         bool operator()(EdgeEnd *s1, EdgeEnd *s2) const {
00304                 return s1->compareTo(s2)<0;
00305         }
00306 };
00307 
00308 class GeometryGraph;
00309 class EdgeEndStar {
00310 public:
00311         EdgeEndStar();
00312         virtual ~EdgeEndStar();
00313         virtual void insert(EdgeEnd *e);
00314         virtual Coordinate& getCoordinate();
00315         virtual int getDegree();
00316         virtual vector<EdgeEnd*>::iterator getIterator();
00317         virtual vector<EdgeEnd*>* getEdges();
00318         virtual EdgeEnd* getNextCW(EdgeEnd *ee);
00319         virtual void computeLabelling(vector<GeometryGraph*> *geom); // throw(TopologyException *);
00320         virtual int getLocation(int geomIndex,Coordinate& p,vector<GeometryGraph*> *geom);
00321         virtual bool isAreaLabelsConsistent();
00322         virtual void propagateSideLabels(int geomIndex); // throw(TopologyException *);
00323         virtual int findIndex(EdgeEnd *eSearch);
00324         virtual string print();
00325 protected:
00326         map<EdgeEnd*,void*,EdgeEndLT> *edgeMap;
00327         vector<EdgeEnd*> *edgeList;
00328         virtual void insertEdgeEnd(EdgeEnd *e,void* obj);
00329 private:
00330         int ptInAreaLocation[2];
00331         virtual void computeEdgeEndLabels();
00332         virtual bool checkAreaLabelsConsistent(int geomIndex);
00333 };
00334 
00335 class DirectedEdge;
00336 class EdgeRing;
00337 class DirectedEdgeStar: public EdgeEndStar {
00338 public:
00339         DirectedEdgeStar();
00340         ~DirectedEdgeStar();
00341         void insert(EdgeEnd *ee);
00342         Label *getLabel();
00343         int getOutgoingDegree();
00344         int getOutgoingDegree(EdgeRing *er);
00345         DirectedEdge* getRightmostEdge();
00346         void computeLabelling(vector<GeometryGraph*> *geom); // throw(TopologyException *);
00347         void mergeSymLabels();
00348         void updateLabelling(Label *nodeLabel);
00349         void linkResultDirectedEdges(); // throw(TopologyException *);
00350         void linkMinimalDirectedEdges(EdgeRing *er);
00351         void linkAllDirectedEdges();
00352         void findCoveredLineEdges();
00353         void computeDepths(DirectedEdge *de);
00354         string print();
00355 private:
00359         vector<DirectedEdge*> *resultAreaEdgeList;
00360         Label *label;
00361         vector<DirectedEdge*>* getResultAreaEdges();
00362         enum {
00363                 SCANNING_FOR_INCOMING=1,
00364                 LINKING_TO_OUTGOING
00365         };
00366 //      static const int SCANNING_FOR_INCOMING=1;
00367 //      static const int LINKING_TO_OUTGOING=2;
00368         int computeDepths(int startIndex, int endIndex, int startDepth);
00369 };
00370 
00371 class Node: public GraphComponent {
00372 
00373 public:
00374         Node(Coordinate& newCoord, EdgeEndStar* newEdges);
00375         virtual ~Node();
00376         virtual const Coordinate& getCoordinate() const;
00377         virtual EdgeEndStar* getEdges();
00378         virtual bool isIsolated();
00379         virtual void add(EdgeEnd *e);
00380         virtual void mergeLabel(const Node* n);
00381         virtual void mergeLabel(const Label* label2);
00382         virtual void setLabel(int argIndex, int onLocation);
00383         virtual void setLabelBoundary(int argIndex);
00384         virtual int computeMergedLocation(const Label* label2, int eltIndex);
00385         virtual string print();
00386         virtual const vector<double> &getZ() const;
00387         virtual void addZ(double);
00388 
00389 protected:
00390         Coordinate coord;
00391         EdgeEndStar* edges;
00392         virtual void computeIM(IntersectionMatrix *im) {};
00393 
00394 private:
00395         vector<double>zvals;
00396         double ztot;
00397 
00398 };
00399 
00400 class NodeFactory {
00401 public:
00402         virtual Node* createNode(Coordinate coord);
00403 };
00404 
00405 class EdgeIntersection {
00406 public:
00407         Coordinate coord;
00408         int segmentIndex;
00409         double dist;
00410         EdgeIntersection(const Coordinate& newCoord, int newSegmentIndex, double newDist);
00411         virtual ~EdgeIntersection();
00412         int compare(int newSegmentIndex, double newDist);
00413         bool isEndPoint(int maxSegmentIndex);
00414         string print();
00415         int compareTo(void* obj);
00416 };
00417 
00418 class EdgeIntersectionList{
00419 public:
00420         vector<EdgeIntersection*> *list;
00421         Edge *edge;
00422         EdgeIntersectionList(Edge *edge);
00423         ~EdgeIntersectionList();
00424         EdgeIntersection* add(const Coordinate& coord, int segmentIndex, double dist);
00425         vector<EdgeIntersection*>::iterator iterator();
00426         bool isEmpty();
00427         bool findInsertionPoint(int segmentIndex,double dist,vector<EdgeIntersection*>::iterator *insertIt);
00428         bool isIntersection(const Coordinate& pt);
00429         void addEndpoints();
00430         void addSplitEdges(vector<Edge*> *edgeList);
00431         Edge *createSplitEdge(EdgeIntersection *ei0, EdgeIntersection *ei1);
00432         string print();
00433 };
00434 
00435 class EdgeList {
00436 public:
00437         EdgeList();
00438         virtual ~EdgeList();
00439         void add(Edge *e);
00440         void addAll(vector<Edge*> *edgeColl);
00441         vector<Edge*>* getEdges();
00442         Edge* findEqualEdge(Edge* e);
00443         Edge* get(int i);
00444         int findEdgeIndex(Edge *e);
00445         string print();
00446 private:
00447         vector<Edge*> *edges;
00457         SpatialIndex* index;
00458 };
00459 
00460 struct CoordLT {
00461         bool operator()(Coordinate s1, Coordinate s2) const {
00462                 return s1.compareTo(s2)<0;
00463         }
00464 };
00465 
00466 class NodeMap{
00467 public:
00468         map<Coordinate,Node*,CoordLT>* nodeMap;
00469         NodeFactory *nodeFact;
00470         // newNodeFact will be deleted by ~NodeMap
00471         NodeMap(NodeFactory *newNodeFact);
00472         virtual ~NodeMap();
00473         Node* addNode(const Coordinate& coord);
00474         Node* addNode(Node *n);
00475         void add(EdgeEnd *e);
00476         Node *find(const Coordinate& coord) const;
00477         map<Coordinate,Node*,CoordLT>::iterator iterator() const;
00478         //Collection values(); //Doesn't work yet. Use iterator.
00479         //vector instead of Collection
00480         vector<Node*>* getBoundaryNodes(int geomIndex) const; //returns new obj
00481         string print() const;
00482 };
00483 
00484 class EdgeRing;
00485 
00486 class DirectedEdge: public EdgeEnd{
00487 public:
00488         static int depthFactor(int currLocation, int nextLocation);
00489         DirectedEdge(); 
00490         virtual ~DirectedEdge();        
00491         DirectedEdge(Edge *newEdge, bool newIsForward);
00492         Edge* getEdge();
00493         void setInResult(bool newIsInResult);
00494         bool isInResult();
00495         bool isVisited();
00496         void setVisited(bool newIsVisited);
00497         void setEdgeRing(EdgeRing *newEdgeRing);
00498         EdgeRing* getEdgeRing();
00499         void setMinEdgeRing(EdgeRing *newMinEdgeRing);
00500         EdgeRing* getMinEdgeRing();
00501         int getDepth(int position);
00502         void setDepth(int position, int newDepth);
00503         int getDepthDelta();
00504         void setVisitedEdge(bool newIsVisited);
00505         DirectedEdge* getSym();
00506         bool isForward();
00507         void setSym(DirectedEdge *de);
00508         DirectedEdge* getNext();
00509         void setNext(DirectedEdge *newNext);
00510         DirectedEdge* getNextMin();
00511         void setNextMin(DirectedEdge *newNextMin);
00512         bool isLineEdge();
00513         bool isInteriorAreaEdge();
00514         void setEdgeDepths(int position, int newDepth);
00515         void OLDsetEdgeDepths(int position, int newDepth);
00516         string print();
00517         string printEdge();
00518 protected:
00519         bool isForwardVar;
00520 private:
00521         bool isInResultVar;
00522         bool isVisitedVar;
00523         DirectedEdge *sym; // the symmetric edge
00524         DirectedEdge *next;  // the next edge in the edge ring for the polygon containing this edge
00525         DirectedEdge *nextMin;  // the next edge in the MinimalEdgeRing that contains this edge
00526         EdgeRing *edgeRing;  // the EdgeRing that this edge is part of
00527         EdgeRing *minEdgeRing;  // the MinimalEdgeRing that this edge is part of
00532         int depth[3];
00533         void computeDirectedLabel();
00534 };
00535 
00536 class EdgeRing{
00537 public:
00538         EdgeRing(DirectedEdge *newStart, const GeometryFactory *newGeometryFactory, CGAlgorithms *newCga);
00539         virtual ~EdgeRing();
00540         bool isIsolated();
00541         bool isHole();
00542         const Coordinate& getCoordinate(int i);
00543         LinearRing* getLinearRing();
00544         Label* getLabel();
00545         bool isShell();
00546         EdgeRing *getShell();
00547         void setShell(EdgeRing *newShell);
00548         void addHole(EdgeRing *edgeRing);
00549         Polygon* toPolygon(const GeometryFactory* geometryFactory);
00550         void computeRing();
00551         virtual DirectedEdge* getNext(DirectedEdge *de)=0;
00552         virtual void setEdgeRing(DirectedEdge *de, EdgeRing *er)=0;
00553         vector<DirectedEdge*>* getEdges();
00554         int getMaxNodeDegree();
00555         void setInResult();
00556         bool containsPoint(Coordinate& p);
00557 protected:
00558         DirectedEdge *startDe; // the directed edge which starts the list of edges for this EdgeRing
00559         const GeometryFactory *geometryFactory;
00560         CGAlgorithms *cga;
00561         void computePoints(DirectedEdge *newStart);
00562         void mergeLabel(Label *deLabel);
00563         void mergeLabel(Label *deLabel, int geomIndex);
00564         void addPoints(Edge *edge, bool isForward, bool isFirstEdge);
00565         vector<EdgeRing*>* holes; // a list of EdgeRings which are holes in this EdgeRing
00566 private:
00567         int maxNodeDegree;
00568         vector<DirectedEdge*>* edges; // the DirectedEdges making up this EdgeRing
00569         CoordinateSequence* pts;
00570         Label* label; // label stores the locations of each geometry on the face surrounded by this ring
00571         LinearRing *ring;  // the ring created for this EdgeRing
00572         bool isHoleVar;
00573         EdgeRing *shell;   // if non-null, the ring is a hole and this EdgeRing is its containing shell
00574         void computeMaxNodeDegree();
00575 };
00576 
00577 class PlanarGraph {
00578 public:
00579         static CGAlgorithms *cga;
00580 //      static LineIntersector *li;
00581         static void linkResultDirectedEdges(vector<Node*>* allNodes); // throw(TopologyException *);
00582         // nodeFact will be deleted by ~NodeMap
00583         PlanarGraph(NodeFactory *nodeFact);
00584         PlanarGraph();
00585         virtual ~PlanarGraph();
00586         virtual vector<Edge*>::iterator getEdgeIterator();
00587         virtual vector<EdgeEnd*>* getEdgeEnds();
00588         virtual bool isBoundaryNode(int geomIndex,Coordinate& coord);
00589         virtual void add(EdgeEnd *e);
00590         virtual map<Coordinate,Node*,CoordLT>::iterator getNodeIterator();
00591         virtual vector<Node*>* getNodes();
00592         virtual Node* addNode(Node *node);
00593         virtual Node* addNode(const Coordinate& coord);
00594         virtual Node* find(Coordinate& coord);
00595         virtual void addEdges(vector<Edge*>* edgesToAdd);
00596         virtual void linkResultDirectedEdges();
00597         virtual void linkAllDirectedEdges();
00598         virtual EdgeEnd* findEdgeEnd(Edge *e);
00599         virtual Edge* findEdge(const Coordinate& p0,const Coordinate& p1);
00600         virtual Edge* findEdgeInSameDirection(const Coordinate& p0,const Coordinate& p1);
00601         virtual string printEdges();
00602         virtual NodeMap* getNodeMap();
00603         //Not used 
00604         //string debugPrint();
00605         //string debugPrintln();
00606 protected:
00607         vector<Edge*> *edges;
00608         NodeMap *nodes;
00609         vector<EdgeEnd*> *edgeEndList;
00610         virtual void insertEdge(Edge *e);
00611 private:
00612         bool matchInSameDirection(const Coordinate& p0, const Coordinate& p1, const Coordinate& ep0, const Coordinate& ep1);
00613 };
00614 
00615 struct LineStringLT {
00616         bool operator()(const LineString *ls1, const LineString *ls2) const {
00617                 return ls1->compareTo(ls2)<0;
00618         }
00619 };
00620 
00621 class GeometryGraph: public PlanarGraph {
00622 public:
00623         static bool isInBoundary(int boundaryCount);
00624         static int determineBoundary(int boundaryCount);
00625         GeometryGraph();
00626         virtual ~GeometryGraph();
00627         GeometryGraph(int newArgIndex, const Geometry *newParentGeom);
00628         const Geometry* getGeometry();
00629         vector<Node*>* getBoundaryNodes();
00630         CoordinateSequence* getBoundaryPoints();
00631         Edge* findEdge(const LineString *line);
00632         void computeSplitEdges(vector<Edge*> *edgelist);
00633         void addEdge(Edge *e);
00634         void addPoint(Coordinate& pt);
00635         SegmentIntersector* computeSelfNodes(LineIntersector *li,
00636                 bool computeRingSelfNodes);
00637         SegmentIntersector* computeEdgeIntersections(GeometryGraph *g,
00638                 LineIntersector *li,bool includeProper);
00639         vector<Edge*> *getEdges();
00640         bool hasTooFewPoints();
00641         const Coordinate& getInvalidPoint(); 
00642 
00643 private:
00644 
00645         const Geometry *parentGeom;
00646 
00647         /*
00648          * The lineEdgeMap is a map of the linestring components of the
00649          * parentGeometry to the edges which are derived from them.
00650          * This is used to efficiently perform findEdge queries
00651          */
00652         map<const LineString*,Edge*,LineStringLT>* lineEdgeMap;
00653 
00654         /*
00655          * If this flag is true, the Boundary Determination Rule will
00656          * used when deciding whether nodes are in the boundary or not
00657          */
00658         bool useBoundaryDeterminationRule;
00659 
00660         /*
00661          * the index of this geometry as an argument to a spatial function
00662          * (used for labelling)
00663          */
00664         int argIndex;
00665 
00666         vector<Node*>* boundaryNodes;
00667 
00668         bool hasTooFewPointsVar;
00669 
00670         Coordinate invalidPoint; 
00671 
00672         EdgeSetIntersector* createEdgeSetIntersector();
00673 
00674         void add(const Geometry *g); // throw(UnsupportedOperationException *);
00675         void addCollection(const GeometryCollection *gc);
00676         void addPoint(const Point *p);
00677         void addPolygonRing(const LinearRing *lr,int cwLeft,int cwRight);
00678         void addPolygon(const Polygon *p);
00679         void addLineString(const LineString *line);
00680 
00681         void insertPoint(int argIndex, const Coordinate& coord,int onLocation);
00682         void insertBoundaryPoint(int argIndex, const Coordinate& coord);
00683 
00684         void addSelfIntersectionNodes(int argIndex);
00685         void addSelfIntersectionNode(int argIndex,Coordinate& coord,int loc);
00686 };
00687 
00688 class SegmentString;
00689 class NodingValidator;
00690 
00691 /*
00692  * Validates that a collection of SegmentStrings is correctly noded.
00693  * Throws an appropriate exception if an noding error is found.
00694  *
00695  * @version 1.4
00696  */
00697 class EdgeNodingValidator {
00698 private:
00699         static vector<SegmentString*>* toSegmentStrings(vector<Edge*> *edges);
00700         NodingValidator *nv;
00701 public:
00702         EdgeNodingValidator(vector<Edge*> *edges);
00703         virtual ~EdgeNodingValidator();
00704         void checkValid();
00705 };
00706 
00707 //Operators
00708 bool operator==(Edge a,Edge b);
00709 
00710 } // namespace geos
00711 
00712 #endif // ifndef GEOS_GEOMGRAPH_H
00713 
00714 /**********************************************************************
00715  * $Log: geomgraph.h,v $
00716  * Revision 1.7  2004/11/20 15:46:45  strk
00717  * Added composing Z management functions and elements for class Node
00718  *
00719  * Revision 1.6  2004/11/17 08:13:16  strk
00720  * Indentation changes.
00721  * Some Z_COMPUTATION activated by default.
00722  *
00723  * Revision 1.5  2004/10/21 22:29:54  strk
00724  * Indentation changes and some more COMPUTE_Z rules
00725  *
00726  * Revision 1.4  2004/07/19 13:19:31  strk
00727  * Documentation fixes
00728  *
00729  * Revision 1.3  2004/07/13 08:33:52  strk
00730  * Added missing virtual destructor to virtual classes.
00731  * Fixed implicit unsigned int -> int casts
00732  *
00733  * Revision 1.2  2004/07/08 19:34:49  strk
00734  * Mirrored JTS interface of CoordinateSequence, factory and
00735  * default implementations.
00736  * Added DefaultCoordinateSequenceFactory::instance() function.
00737  *
00738  * Revision 1.1  2004/07/02 13:20:42  strk
00739  * Header files moved under geos/ dir.
00740  *
00741  * Revision 1.6  2004/06/30 20:59:12  strk
00742  * Removed GeoemtryFactory copy from geometry constructors.
00743  * Enforced const-correctness on GeometryFactory arguments.
00744  *
00745  * Revision 1.5  2004/05/26 09:50:05  strk
00746  * Added comments about OverlayNodeFactory() ownership in NodeMap and PlanarGraph constuctors
00747  *
00748  * Revision 1.4  2004/05/03 10:43:42  strk
00749  * Exception specification considered harmful - left as comment.
00750  *
00751  * Revision 1.3  2004/04/10 08:40:01  ybychkov
00752  * "operation/buffer" upgraded to JTS 1.4
00753  *
00754  * Revision 1.2  2004/04/04 06:29:11  ybychkov
00755  * "planargraph" and "geom/utill" upgraded to JTS 1.4
00756  *
00757  * Revision 1.1  2004/03/19 09:48:45  ybychkov
00758  * "geomgraph" and "geomgraph/indexl" upgraded to JTS 1.4
00759  *
00760  * Revision 1.27  2003/11/12 18:02:56  strk
00761  * Added throw specification. Fixed leaks on exceptions.
00762  *
00763  * Revision 1.26  2003/11/12 15:43:38  strk
00764  * Added some more throw specifications
00765  *
00766  * Revision 1.25  2003/11/07 01:23:42  pramsey
00767  * Add standard CVS headers licence notices and copyrights to all cpp and h
00768  * files.
00769  *
00770  * Revision 1.24  2003/11/06 18:45:05  strk
00771  * Added throw specification for DirectEdgeStar::linkResultDirectedEdges()
00772  *
00773  **********************************************************************/
00774 

Generated on Tue Apr 19 07:10:18 2005 for GEOS by  doxygen 1.4.2