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

planargraph.h

00001 /**********************************************************************
00002  * $Id: planargraph.h,v 1.6 2004/12/14 10:35:44 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 #ifndef GEOS_PLANARGRAPH_H
00017 #define GEOS_PLANARGRAPH_H
00018 
00019 #include <geos/platform.h>
00020 #include <geos/geosAlgorithm.h>
00021 #include <vector>
00022 #include <string>
00023 #include <map>
00024 
00025 using namespace std;
00026 
00027 namespace geos {
00028 //namespace planargraph {
00029 
00030 /*
00031  * \class planarGraphComponent planargraph.h geos/planargraph.h
00032  *
00033  * \brief The base class for all graph component classes.
00034  *
00035  * Maintains flags of use in generic graph algorithms.
00036  * Provides two flags:
00037  * 
00038  *  - <b>marked</b> - typically this is used to indicate a state that
00039  *    persists for the course of the graph's lifetime.  For instance,
00040  *    it can be used to indicate that a component has been logically
00041  *    deleted from the graph.
00042  *  - <b>visited</b> - this is used to indicate that a component has been
00043  *    processed or visited by an single graph algorithm.  For instance,
00044  *    a breadth-first traversal of the graph might use this to indicate
00045  *    that a node has already been traversed.
00046  *    The visited flag may be set and cleared many times during the
00047  *    lifetime of a graph.
00048  *
00049  */
00050 class planarGraphComponent {
00051 
00052 protected:
00053 
00054         bool isMarkedVar;
00055 
00056         bool isVisitedVar;
00057 
00058 public:
00059 
00060         planarGraphComponent();
00061         virtual ~planarGraphComponent();
00062 
00063         /*
00064          * \brief Tests if a component has been visited during the course
00065          * of a graph algorithm.
00066          *
00067          * @return <code>true</code> if the component has been visited
00068          */
00069         virtual bool isVisited();
00070 
00071         /*
00072          * \brief Sets the visited flag for this component.
00073          * @param isVisited the desired value of the visited flag
00074          */
00075         virtual void setVisited(bool isVisited);
00076 
00077         /*
00078          * \brief Tests if a component has been marked at some point
00079          * during the processing involving this graph.
00080          * @return <code>true</code> if the component has been marked
00081          */
00082         virtual bool isMarked();
00083 
00084         /*
00085          * \brief Sets the marked flag for this component.
00086          * @param isMarked the desired value of the marked flag
00087          */
00088         virtual void setMarked(bool isMarked);
00089 };
00090 
00091 class planarDirectedEdge;
00092 class planarEdge;
00093 
00094 bool pdeLessThan(planarDirectedEdge *first,planarDirectedEdge * second);
00095 
00096 /*
00097  * \class planarDirectedEdgeStar planargraph.h geos/planargraph.h
00098  *
00099  * \brief
00100  * A sorted collection of DirectedEdge which leave a Node in a PlanarGraph.
00101  */
00102 class planarDirectedEdgeStar {
00103 protected:
00104         /*
00105          * \brief The underlying list of outgoing DirectedEdges
00106          */
00107         vector<planarDirectedEdge*> *outEdges;
00108 
00109 private:
00110         bool sorted;
00111         void sortEdges();
00112 
00113 public:
00114         /*
00115          * \brief Constructs a DirectedEdgeStar with no edges.
00116          */
00117         planarDirectedEdgeStar();
00118 
00119         virtual ~planarDirectedEdgeStar();
00120 
00121         /*
00122          * \brief Adds a new member to this DirectedEdgeStar.
00123          */
00124         void add(planarDirectedEdge *de);
00125 
00126         /*
00127          * \brief Drops a member of this DirectedEdgeStar.
00128          */
00129         void remove(planarDirectedEdge *de);
00130 
00131         /*
00132          * \brief Returns an Iterator over the DirectedEdges,
00133          * in ascending order by angle with the positive x-axis.
00134          */
00135         vector<planarDirectedEdge*>::iterator iterator();
00136 
00137         /*
00138          * \brief Returns the number of edges around the Node associated
00139          * with this DirectedEdgeStar.
00140          */
00141         int getDegree();
00142 
00143         /*
00144          * \brief Returns the coordinate for the node at wich this
00145          * star is based
00146          */
00147         Coordinate& getCoordinate();
00148 
00149         /*
00150          * \brief Returns the DirectedEdges, in ascending order
00151          * by angle with the positive x-axis.
00152          */
00153         vector<planarDirectedEdge*>* getEdges();
00154 
00155         /*
00156          * \brief Returns the zero-based index of the given Edge,
00157          * after sorting in ascending order by angle with the
00158          * positive x-axis.
00159          */
00160         int getIndex(planarEdge *edge);
00161 
00162         /*
00163          * \brief Returns the zero-based index of the given DirectedEdge,
00164          * after sorting in ascending order
00165          * by angle with the positive x-axis.
00166          */  
00167         int getIndex(planarDirectedEdge *dirEdge);
00168 
00169         /*
00170          * \brief Returns the remainder when i is divided by the number of
00171          * edges in this DirectedEdgeStar. 
00172          */
00173         int getIndex(int i);
00174 
00175         /*
00176          * \brief Returns the DirectedEdge on the left-hand side
00177          * of the given DirectedEdge (which must be a member of this
00178          * DirectedEdgeStar). 
00179          */
00180         planarDirectedEdge* getNextEdge(planarDirectedEdge *dirEdge);
00181 };
00182 
00183 /*
00184  * \class planarNode planargraph.h geos/planargraph.h
00185  *
00186  * \brief A node in a PlanarGraph is a location where 0 or more Edge meet.
00187  *
00188  * A node is connected to each of its incident Edges via an outgoing
00189  * DirectedEdge. Some clients using a <code>PlanarGraph</code> may want to
00190  * subclass <code>Node</code> to add their own application-specific
00191  * data and methods.
00192  *
00193  */
00194 class planarNode: public planarGraphComponent {
00195 protected:
00196 
00197         /* \brief The location of this Node */
00198         Coordinate pt;
00199 
00200         /* \brief The collection of DirectedEdges that leave this Node */
00201         planarDirectedEdgeStar *deStar;
00202 
00203 public:
00204 
00205         /*
00206          * \brief Returns all Edges that connect the two nodes (which are
00207          * assumed to be different).
00208          */
00209         static vector<planarEdge*>* getEdgesBetween(planarNode *node0, planarNode *node1);
00210 
00211         /*
00212          * \brief Constructs a Node with the given location.
00213          */
00214         planarNode(const Coordinate& newPt);
00215 
00216         ~planarNode();
00217 
00218         /*
00219          * \brief Constructs a Node with the given location and
00220          * collection of outgoing planarDirectedEdges.
00221          */
00222         planarNode(Coordinate& newPt, planarDirectedEdgeStar *newDeStar);
00223 
00224         /*
00225          * \brief Returns the location of this Node.
00226          */
00227         Coordinate& getCoordinate();
00228 
00229         /*
00230          * \brief Adds an outgoing DirectedEdge to this Node.
00231          */
00232         void addOutEdge(planarDirectedEdge *de);
00233 
00234         /*
00235          * \brief Returns the collection of DirectedEdges that
00236          * leave this Node.
00237          */
00238         planarDirectedEdgeStar* getOutEdges();
00239 
00240         /*
00241          * \brief Returns the number of edges around this Node.
00242          */
00243         int getDegree();
00244 
00245         /*
00246          * \brief Returns the zero-based index of the given Edge,
00247          * after sorting in ascending order by angle with
00248          * the positive x-axis.
00249          */
00250         int getIndex(planarEdge *edge);
00251 };
00252 
00253 /*
00254  * \class planarEdge planargraph.h geos/planargraph.h
00255  *
00256  * \brief Represents an undirected edge of a PlanarGraph.
00257  *
00258  * An undirected edge in fact simply acts as a central point of reference
00259  * for two opposite DirectedEdge.
00260  * 
00261  * Usually a client using a PlanarGraph will subclass Edge
00262  * to add its own application-specific data and methods.
00263  */
00264 class planarEdge: public planarGraphComponent {
00265 
00266 protected:
00267 
00268         /* \brief The two DirectedEdges associated with this Edge */
00269         vector<planarDirectedEdge*> dirEdge;
00270 
00271         /*
00272          * \brief Constructs an Edge whose DirectedEdges are not yet set.
00273          *
00274          * Be sure to call setDirectedEdges(DirectedEdge, DirectedEdge)
00275          */
00276 
00277 public:
00278 
00279         planarEdge();
00280 
00281         /*
00282          * \brief Constructs an Edge initialized with the given DirectedEdges.
00283          *
00284          * For  each DirectedEdge: sets the Edge, sets the symmetric
00285          * DirectedEdge, and adds this Edge to its from-Node.
00286          */
00287         planarEdge(planarDirectedEdge *de0, planarDirectedEdge *de1);
00288 
00289         /*
00290          * \brief Initializes this Edge's two DirectedEdges.
00291          *
00292          * For each DirectedEdge:
00293          *  sets the Edge, sets the symmetric DirectedEdge, and
00294          *  adds this Edge to its from-Node.
00295          */
00296         void setDirectedEdges(planarDirectedEdge *de0, planarDirectedEdge *de1);
00297 
00298         /*
00299          * \brief Returns one of the DirectedEdges associated with this Edge.
00300          * @param i 0 or 1
00301          */
00302         planarDirectedEdge* getDirEdge(int i);
00303 
00304         /*
00305          * \brief Returns the DirectedEdge that starts from the given node,
00306          * or null if the node is not one of the two nodes associated
00307          * with this Edge.
00308          */
00309         planarDirectedEdge* getDirEdge(planarNode *fromNode);
00310 
00311         /*
00312          * \brief If <code>node</code> is one of the two nodes associated
00313          * with this Edge, returns the other node; otherwise returns null.
00314          */
00315         planarNode* getOppositeNode(planarNode *node);
00316 };
00317 
00318 
00319 /*
00320  * \class planarDirectedEdge planargraph.h geos/planargraph.h
00321  *
00322  * \brief Represents a directed edge in a PlanarGraph.
00323  *
00324  * A DirectedEdge may or may not have a reference to a parent Edge
00325  * (some applications of planar graphs may not require explicit Edge
00326  * objects to be created). Usually a client using a PlanarGraph
00327  * will subclass DirectedEdge to add its own application-specific
00328  * data and methods.
00329  */
00330 class planarDirectedEdge: public planarGraphComponent {
00331 //friend class Unload;
00332 
00333 protected:
00334         //static const CGAlgorithms* cga;
00335         static CGAlgorithms cga;
00336         planarEdge* parentEdge;
00337         planarNode* from;
00338         planarNode* to;
00339         Coordinate p0, p1;
00340         planarDirectedEdge* sym;  // optional
00341         bool edgeDirection;
00342         int quadrant;
00343         double angle;
00344 public:
00345         /*
00346          * \brief Returns a List containing the parent Edge (possibly null)
00347          * for each of the given DirectedEdges.
00348          */
00349         static vector<planarEdge*>* toEdges(vector<planarDirectedEdge*> *dirEdges);
00350 
00351         /*
00352          * \brief Constructs a DirectedEdge connecting the <code>from</code>
00353          * node to the <code>to</code> node.
00354          *
00355          * @param directionPt specifies this DirectedEdge's direction
00356          *                    (given by an imaginary line from the
00357          *                    <code>from</code> node to
00358          *                    <code>directionPt</code>)
00359          * @param edgeDirection whether this DirectedEdge's direction
00360          *                     is the same as or opposite to that of the
00361          *                     parent Edge (if any)
00362          */
00363         planarDirectedEdge(planarNode *newFrom,planarNode *newTo, const Coordinate &directionPt,bool newEdgeDirection);
00364 
00365         /*
00366          * \brief Returns this DirectedEdge's parent Edge,
00367          * or null if it has none.
00368          */
00369         planarEdge* getEdge() const;
00370 
00371         /*
00372          * \brief Associates this DirectedEdge with an Edge
00373          * (possibly null, indicating no associated Edge).
00374          */
00375         void setEdge(planarEdge* newParentEdge);
00376 
00377         /*
00378          * \brief Returns 0, 1, 2, or 3, indicating the quadrant in which
00379          * this DirectedEdge's orientation lies.
00380          */
00381         int getQuadrant() const;
00382 
00383         /*
00384          * \brief Returns a point to which an imaginary line is drawn
00385          * from the from-node to specify this DirectedEdge's orientation.
00386          */
00387         const Coordinate& getDirectionPt() const;
00388 
00389         /*
00390          * \brief Returns whether the direction of the parent Edge (if any)
00391          * is the same as that of this Directed Edge.
00392          */
00393         bool getEdgeDirection() const;
00394 
00395         /*
00396          * \brief Returns the node from which this DirectedEdge leaves.
00397          */
00398         planarNode* getFromNode() const;
00399 
00400         /*
00401          * \brief Returns the node to which this DirectedEdge goes.
00402          */
00403         planarNode* getToNode() const;
00404 
00405         /*
00406          * \brief
00407          * Returns the coordinate of the from-node.
00408          */
00409         Coordinate& getCoordinate() const;
00410 
00411         /*
00412          * \brief
00413          * Returns the angle that the start of this DirectedEdge makes
00414          * with the positive x-axis, in radians.
00415          */
00416         double getAngle() const;
00417 
00418         /*
00419          * \brief
00420          * Returns the symmetric DirectedEdge -- the other DirectedEdge
00421          * associated with this DirectedEdge's parent Edge.
00422          */
00423         planarDirectedEdge* getSym() const;
00424 
00425         /*
00426          * \brief
00427          * Sets this DirectedEdge's symmetric DirectedEdge, which runs
00428          * in the opposite direction.
00429          */
00430         void setSym(planarDirectedEdge *newSym);
00431 
00432         /*
00433          * \brief
00434          * Returns 1 if this DirectedEdge has a greater angle with the
00435          * positive x-axis than b", 0 if the DirectedEdges are collinear,
00436          * and -1 otherwise.
00437          *
00438          * Using the obvious algorithm of simply computing the angle is
00439          * not robust, since the angle calculation is susceptible to roundoff.
00440          * A robust algorithm is:
00441          * 
00442          * - first compare the quadrants.
00443          *   If the quadrants are different, it it
00444          *   trivial to determine which vector is "greater".
00445          * - if the vectors lie in the same quadrant, the robust
00446          *   RobustCGAlgorithms::computeOrientation(Coordinate, Coordinate, Coordinate)
00447          *   function can be used to decide the relative orientation of
00448          *   the vectors.
00449          * 
00450          */
00451         int compareTo(const planarDirectedEdge* obj) const;
00452 
00453         /*
00454          * \brief
00455          * Returns 1 if this DirectedEdge has a greater angle with the
00456          * positive x-axis than b", 0 if the DirectedEdges are collinear,
00457          * and -1 otherwise.
00458          *
00459          * Using the obvious algorithm of simply computing the angle is
00460          * not robust, since the angle calculation is susceptible to roundoff.
00461          * A robust algorithm is:
00462          * 
00463          * - first compare the quadrants.
00464          *   If the quadrants are different, it it trivial to determine
00465          *   which vector is "greater".
00466          * - if the vectors lie in the same quadrant, the robust
00467          *   RobustCGAlgorithms::computeOrientation(Coordinate, Coordinate, Coordinate)
00468          *   function can be used to decide the relative orientation of
00469          *   the vectors.
00470          *
00471          */
00472         int compareDirection(const planarDirectedEdge *e) const;
00473 
00474         /*
00475          * \brief
00476          * Prints a detailed string representation of this DirectedEdge
00477          * to the given PrintStream.
00478          */
00479         string print() const;
00480 
00481 };
00482 
00483 struct planarCoordLT {
00484         bool operator()(Coordinate s1, Coordinate s2) const {
00485                 return s1.compareTo(s2)<0;
00486         }
00487 };
00488 
00489 /*
00490  * \class planarNodeMap planargraph.h geos/planargraph.h
00491  * \brief
00492  * A map of Node, indexed by the coordinate of the node.
00493  *
00494  */
00495 class planarNodeMap {
00496 private:
00497         map<Coordinate,planarNode*, planarCoordLT> *nodeMap;
00498 public:  
00499         /*
00500          * \brief Constructs a NodeMap without any Nodes.
00501          */
00502         planarNodeMap();
00503 
00504         map<Coordinate,planarNode*,planarCoordLT>* getNodeMap();
00505 
00506         virtual ~planarNodeMap();
00507 
00508         /*
00509          * \brief
00510          * Adds a node to the map, replacing any that is already
00511          * at that location.
00512          * @return the added node
00513          */
00514         planarNode* add(planarNode *n);
00515 
00516         /*
00517          * \brief
00518          * Removes the Node at the given location, and returns it
00519          * (or null if no Node was there).
00520          */
00521         planarNode* remove(Coordinate& pt);
00522 
00523         /*
00524          * \brief
00525          * Returns the Node at the given location,
00526          * or null if no Node was there.
00527          */
00528         planarNode* find(const Coordinate& coord);
00529 
00530         /*
00531          * \brief
00532          * Returns an Iterator over the Nodes in this NodeMap,
00533          * sorted in ascending order
00534          * by angle with the positive x-axis.
00535          */
00536         map<Coordinate,planarNode*,planarCoordLT>::iterator iterator();
00537 
00538         /*
00539          * \brief
00540          * Returns the Nodes in this NodeMap, sorted in ascending order
00541          * by angle with the positive x-axis.
00542          */
00543         vector<planarNode*>* getNodes();
00544 };
00545 
00546 /*
00547  * \class planarPlanarGraph planargraph.h geos/planargraph.h
00548  * \brief
00549  * Represents a directed graph which is embeddable in a planar surface.
00550  * 
00551  * This class and the other classes in this package serve as a framework for
00552  * building planar graphs for specific algorithms. This class must be
00553  * subclassed to expose appropriate methods to construct the graph. This allows
00554  * controlling the types of graph components (DirectedEdge, Edge and Node)
00555  * which can be added to the graph. An application which uses the graph
00556  * framework will almost always provide subclasses for one or more graph
00557  * components, which hold application-specific data and graph algorithms.
00558  */
00559 class planarPlanarGraph {
00560 
00561 protected:
00562 
00563         vector<planarEdge*> *edges;
00564         vector<planarDirectedEdge*> *dirEdges;
00565         planarNodeMap *nodeMap;
00566 
00567         /*
00568          * \brief
00569          * Adds a node to the map, replacing any that is already at that
00570          * location.
00571          *
00572          * Only subclasses can add Nodes, to ensure Nodes are
00573          * of the right type.
00574          * @return the added node
00575          */
00576         void add(planarNode *node);
00577 
00578         /*
00579          * \brief
00580          * Adds the Edge and its DirectedEdges with this PlanarGraph.
00581          *
00582          * Assumes that the Edge has already been created with its associated
00583          * DirectEdges.
00584          * Only subclasses can add Edges, to ensure the edges added are of
00585          * the right class.
00586          */
00587         void add(planarEdge *edge);
00588 
00589         /*
00590          * \brief
00591          * Adds the Edge to this PlanarGraph.
00592          *
00593          * Only subclasses can add DirectedEdges,
00594          * to ensure the edges added are of the right class.
00595          */
00596         void add(planarDirectedEdge *dirEdge);
00597 
00598 public:
00599 
00600         /*
00601          * \brief
00602          * Constructs a PlanarGraph without any Edges, DirectedEdges, or Nodes.
00603          */
00604         planarPlanarGraph();
00605 
00606         virtual ~planarPlanarGraph();
00607 
00608         /*
00609          * \brief
00610          * Returns the Node at the given location,
00611          * or null if no Node was there.
00612          */
00613         planarNode* findNode(const Coordinate& pt);
00614 
00615         /*
00616          * \brief
00617          * Returns an Iterator over the Nodes in this PlanarGraph.
00618          */
00619         map<Coordinate,planarNode*,planarCoordLT>::iterator nodeIterator();
00620 
00621         /*
00622          * \brief
00623          * Returns the Nodes in this PlanarGraph.
00624          */  
00625         vector<planarNode*>* getNodes();
00626 
00627         /*
00628          * \brief
00629          * Returns an Iterator over the DirectedEdges in this PlanarGraph,
00630          * in the order in which they were added.
00631          *
00632          * @see add(Edge)
00633          * @see add(DirectedEdge)
00634          */
00635         vector<planarDirectedEdge*>::iterator dirEdgeIterator();
00636 
00637         /*
00638          * \brief
00639          * Returns an Iterator over the Edges in this PlanarGraph,
00640          * in the order in which they were added.
00641          *
00642          * @see #add(Edge)
00643          */
00644         vector<planarEdge*>::iterator edgeIterator();
00645 
00646         /*
00647          * \brief
00648          * Returns the Edges that have been added to this PlanarGraph
00649          * @see #add(Edge)
00650          */
00651         vector<planarEdge*>* getEdges();
00652 
00653         /*
00654          * \brief
00655          * Removes an Edge and its associated DirectedEdges from their
00656          * from-Nodes and from this PlanarGraph.
00657          *
00658          * Note: This method does not remove the Nodes associated
00659          * with the Edge, even if the removal of the Edge reduces the
00660          * degree of a Node to zero.
00661          */
00662         void remove(planarEdge *edge);
00663 
00664         /*
00665          * \brief
00666          * Removes DirectedEdge from its from-Node and from this PlanarGraph.
00667          *
00668          * Note:
00669          * This method does not remove the Nodes associated with the
00670          * DirectedEdge, even if the removal of the DirectedEdge reduces
00671          * the degree of a Node to zero.
00672          */
00673         void remove(planarDirectedEdge *de);
00674 
00675         /*
00676          * \brief
00677          * Removes a node from the graph, along with any associated
00678          * DirectedEdges and Edges.
00679          */
00680         void remove(planarNode *node);
00681 
00682         /*
00683          * \brief
00684          * Returns all Nodes with the given number of Edges around it.
00685          */
00686         vector<planarNode*>* findNodesOfDegree(int degree);
00687 };
00688 
00689 //} // namespace planargraph
00690 } // namespace geos
00691 #endif
00692 
00693 /**********************************************************************
00694  * $Log: planargraph.h,v $
00695  * Revision 1.6  2004/12/14 10:35:44  strk
00696  * Comments cleanup. PolygonizeGraph keeps track of generated CoordinateSequence
00697  * for delayed destruction.
00698  *
00699  * Revision 1.5  2004/10/19 19:51:14  strk
00700  * Fixed many leaks and bugs in Polygonizer.
00701  * Output still bogus.
00702  *
00703  * Revision 1.4  2004/10/13 10:03:02  strk
00704  * Added missing linemerge and polygonize operation.
00705  * Bug fixes and leaks removal from the newly added modules and
00706  * planargraph (used by them).
00707  * Some comments and indentation changes.
00708  *
00709  * Revision 1.3  2004/07/19 13:19:31  strk
00710  * Documentation fixes
00711  *
00712  * Revision 1.2  2004/07/13 08:33:52  strk
00713  * Added missing virtual destructor to virtual classes.
00714  * Fixed implicit unsigned int -> int casts
00715  *
00716  * Revision 1.1  2004/07/02 13:20:42  strk
00717  * Header files moved under geos/ dir.
00718  *
00719  * Revision 1.3  2004/04/16 08:52:52  strk
00720  * Unload::Release final delete (static heap allocations should be gone now)
00721  *
00722  * Revision 1.2  2004/04/07 06:55:50  ybychkov
00723  * "operation/linemerge" ported from JTS 1.4
00724  *
00725  * Revision 1.1  2004/04/04 06:29:11  ybychkov
00726  * "planargraph" and "geom/utill" upgraded to JTS 1.4
00727  *
00728  *
00729  **********************************************************************/
00730 

Generated on Tue Dec 13 19:44:50 2005 for GEOS by  doxygen 1.4.4