00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039 #ifndef GEOS_PLANARGRAPH_H
00040 #define GEOS_PLANARGRAPH_H
00041
00042 #include <geos/platform.h>
00043 #include <geos/geosAlgorithm.h>
00044 #include <vector>
00045 #include <string>
00046 #include <map>
00047
00048 using namespace std;
00049
00050 namespace geos {
00051
00052
00053
00054
00055
00056
00057
00058
00059
00060
00061
00062
00063
00064
00065
00066
00067
00068
00069 class planarGraphComponent {
00070
00071 protected:
00072
00073 bool isMarkedVar;
00074
00075 bool isVisitedVar;
00076
00077 public:
00078
00079 planarGraphComponent();
00080 virtual ~planarGraphComponent();
00081
00086 virtual bool isVisited();
00087
00092 virtual void setVisited(bool newIsVisited);
00093
00099 virtual bool isMarked();
00100
00105 virtual void setMarked(bool newIsMarked);
00106 };
00107
00108 class planarDirectedEdge;
00109 class planarEdge;
00110
00111 bool pdeLessThan(planarDirectedEdge *first,planarDirectedEdge * second);
00112
00113
00114
00115
00116
00117
00118 class planarDirectedEdgeStar {
00119 protected:
00123 vector<planarDirectedEdge*> *outEdges;
00124 private:
00125 bool sorted;
00126 void sortEdges();
00127 public:
00131 planarDirectedEdgeStar();
00132 virtual ~planarDirectedEdgeStar();
00136 void add(planarDirectedEdge *de);
00140 void remove(planarDirectedEdge *de);
00144 vector<planarDirectedEdge*>::iterator iterator();
00148 int getDegree();
00152 Coordinate& getCoordinate();
00156 vector<planarDirectedEdge*>* getEdges();
00161 int getIndex(planarEdge *edge);
00166 int getIndex(planarDirectedEdge *dirEdge);
00171 int getIndex(int i);
00176 planarDirectedEdge* getNextEdge(planarDirectedEdge *dirEdge);
00177 };
00178
00179
00180
00181
00182
00183
00184
00185
00186
00187 class planarNode: public planarGraphComponent {
00188 protected:
00190 Coordinate pt;
00192 planarDirectedEdgeStar *deStar;
00193 public:
00197 static vector<planarEdge*>* getEdgesBetween(planarNode *node0, planarNode *node1);
00201 planarNode(Coordinate& newPt);
00205 planarNode(Coordinate& newPt, planarDirectedEdgeStar *newDeStar);
00209 Coordinate& getCoordinate();
00213 void addOutEdge(planarDirectedEdge *de);
00217 planarDirectedEdgeStar* getOutEdges();
00221 int getDegree();
00226 int getIndex(planarEdge *edge);
00227 };
00228
00229
00230
00231
00232
00233
00234
00235
00236
00237
00238 class planarEdge: public planarGraphComponent {
00239 protected:
00241 vector<planarDirectedEdge*> *dirEdge;
00246 public:
00247 planarEdge();
00253 planarEdge(planarDirectedEdge *de0, planarDirectedEdge *de1);
00258 void setDirectedEdges(planarDirectedEdge *de0,planarDirectedEdge *de1);
00263 planarDirectedEdge* getDirEdge(int i);
00268 planarDirectedEdge* getDirEdge(planarNode *fromNode);
00273 planarNode* getOppositeNode(planarNode *node);
00274 };
00275
00276
00277
00278
00279
00280
00281
00282
00283
00284
00285 class planarDirectedEdge: public planarGraphComponent {
00286 friend class Unload;
00287 protected:
00288 static const CGAlgorithms* cga;
00289 planarEdge* parentEdge;
00290 planarNode* from;
00291 planarNode* to;
00292 Coordinate p0, p1;
00293 planarDirectedEdge* sym;
00294 bool edgeDirection;
00295 int quadrant;
00296 double angle;
00297 public:
00302 static vector<planarEdge*>* toEdges(vector<planarDirectedEdge*> *dirEdges);
00314 planarDirectedEdge(planarNode *newFrom,planarNode *newTo,Coordinate &directionPt,bool newEdgeDirection);
00318 planarEdge* getEdge();
00323 void setEdge(planarEdge* newParentEdge);
00328 int getQuadrant();
00333 Coordinate& getDirectionPt();
00338 bool getEdgeDirection();
00342 planarNode* getFromNode();
00346 planarNode* getToNode();
00350 Coordinate& getCoordinate();
00355 double getAngle();
00360 planarDirectedEdge* getSym();
00365 void setSym(planarDirectedEdge *newSym);
00366
00382 int compareTo(void* obj);
00398 int compareDirection(planarDirectedEdge *e);
00402 string print();
00403
00404 };
00405
00406 struct planarCoordLT {
00407 bool operator()(Coordinate s1, Coordinate s2) const {
00408 return s1.compareTo(s2)<0;
00409 }
00410 };
00411
00412
00413
00414
00415
00416 class planarNodeMap {
00417 private:
00418 map<Coordinate,planarNode*,planarCoordLT> *nodeMap;
00419 public:
00423 planarNodeMap();
00424 map<Coordinate,planarNode*,planarCoordLT>* getNodeMap();
00425 virtual ~planarNodeMap();
00430 planarNode* add(planarNode *n);
00434 planarNode* remove(Coordinate& pt);
00438 planarNode* find(Coordinate& coord);
00443 map<Coordinate,planarNode*,planarCoordLT>::iterator iterator();
00448 vector<planarNode*>* getNodes();
00449 };
00450
00451
00452
00453
00454
00455
00456
00457
00458
00459
00460
00461
00462
00463
00464 class planarPlanarGraph {
00465 protected:
00466 vector<planarEdge*> *edges;
00467 vector<planarDirectedEdge*> *dirEdges;
00468 planarNodeMap *nodeMap;
00474 void add(planarNode *node);
00480 void add(planarEdge *edge);
00485 void add(planarDirectedEdge *dirEdge);
00486 public:
00490 planarPlanarGraph();
00491 virtual ~planarPlanarGraph();
00495 planarNode* findNode(Coordinate& pt);
00499 map<Coordinate,planarNode*,planarCoordLT>::iterator nodeIterator();
00503 vector<planarNode*>* getNodes();
00511 vector<planarDirectedEdge*>::iterator dirEdgeIterator();
00518 vector<planarEdge*>::iterator edgeIterator();
00523 vector<planarEdge*>* getEdges();
00530 void remove(planarEdge *edge);
00537 void remove(planarDirectedEdge *de);
00542 void remove(planarNode *node);
00546 vector<planarNode*>* findNodesOfDegree(int degree);
00547 };
00548
00549 }
00550 #endif