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

planargraph.h

00001 /**********************************************************************
00002  * $Id: planargraph.h,v 1.3 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: planargraph.h,v $
00016  * Revision 1.3  2004/07/19 13:19:31  strk
00017  * Documentation fixes
00018  *
00019  * Revision 1.2  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.1  2004/07/02 13:20:42  strk
00024  * Header files moved under geos/ dir.
00025  *
00026  * Revision 1.3  2004/04/16 08:52:52  strk
00027  * Unload::Release final delete (static heap allocations should be gone now)
00028  *
00029  * Revision 1.2  2004/04/07 06:55:50  ybychkov
00030  * "operation/linemerge" ported from JTS 1.4
00031  *
00032  * Revision 1.1  2004/04/04 06:29:11  ybychkov
00033  * "planargraph" and "geom/utill" upgraded to JTS 1.4
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  * The base class for all graph component classes.
00054  * Maintains flags of use in generic graph algorithms.
00055  * Provides two flags:
00056  * 
00057  *  - <b>marked</b> - typically this is used to indicate a state that
00058  *    persists for the course of the graph's lifetime.  For instance,
00059  *    it can be used to indicate that a component has been logically
00060  *    deleted from the graph.
00061  *  - <b>visited</b> - this is used to indicate that a component has been
00062  *    processed or visited by an single graph algorithm.  For instance,
00063  *    a breadth-first traversal of the graph might use this to indicate
00064  *    that a node has already been traversed.
00065  *    The visited flag may be set and cleared many times during the
00066  *    lifetime of a graph.
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  * A sorted collection of {@link DirectedEdge}s which leave a {@link Node}
00115  * in a {@link PlanarGraph}.
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  * A node in a {@link PlanarGraph}is a location where 0 or more {@link Edge}s
00181  * meet. A node is connected to each of its incident Edges via an outgoing
00182  * DirectedEdge. Some clients using a <code>PlanarGraph</code> may want to
00183  * subclass <code>Node</code> to add their own application-specific
00184  * data and methods.
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  * Represents an undirected edge of a {@link PlanarGraph}. An undirected edge
00231  * in fact simply acts as a central point of reference for two opposite
00232  * {@link DirectedEdge}s.
00233  * <p>
00234  * Usually a client using a <code>PlanarGraph</code> will subclass <code>Edge</code>
00235  * to add its own application-specific data and methods.
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  * Represents a directed edge in a {@link PlanarGraph}. A DirectedEdge may or
00279  * may not have a reference to a parent {@link Edge} (some applications of
00280  * planar graphs may not require explicit Edge objects to be created). Usually
00281  * a client using a <code>PlanarGraph</code> will subclass <code>DirectedEdge</code>
00282  * to add its own application-specific data and methods.
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;  // optional
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  * A map of Node, indexed by the coordinate of the node.
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  * Represents a directed graph which is embeddable in a planar surface.
00453  * <p>
00454  * This class and the other classes in this package serve as a framework for
00455  * building planar graphs for specific algorithms. This class must be
00456  * subclassed to expose appropriate methods to construct the graph. This allows
00457  * controlling the types of graph components ({@link DirectedEdge}s,
00458  * {@link Edge}s and {@link Node}s) which can be added to the graph. An
00459  * application which uses the graph framework will almost always provide
00460  * subclasses for one or more graph components, which hold application-specific
00461  * data and graph algorithms.
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

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