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