Main Page | Namespace List | Class Hierarchy | Class List | File List | Namespace Members | Class Members | Related Pages

geomgraph.h

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

Generated on Fri Nov 26 21:30:45 2004 for GEOS by  doxygen 1.3.9.1