include/geos/geomgraph/PlanarGraph.h

   1 /**********************************************************************
   2  *
   3  * GEOS - Geometry Engine Open Source
   4  * http://geos.osgeo.org
   5  *
   6  * Copyright (C) 2005-2006 Refractions Research Inc.
   7  * Copyright (C) 2001-2002 Vivid Solutions Inc.
   8  *
   9  * This is free software; you can redistribute and/or modify it under
  10  * the terms of the GNU Lesser General Public Licence as published
  11  * by the Free Software Foundation.
  12  * See the COPYING file for more information.
  13  *
  14  **********************************************************************
  15  *
  16  * Last port: geomgraph/PlanarGraph.java r428 (JTS-1.12+)
  17  *
  18  **********************************************************************/
  19
  20
  21 #ifndef GEOS_GEOMGRAPH_PLANARGRAPH_H
  22 #define GEOS_GEOMGRAPH_PLANARGRAPH_H
  23
  24 #include <geos/export.h>
  25 #include <map>
  26 #include <vector>
  27 #include <memory>
  28
  29 #include <geos/geom/Coordinate.h>
  30 #include <geos/geomgraph/PlanarGraph.h>
  31 #include <geos/geomgraph/NodeMap.h> // for typedefs
  32 #include <geos/geomgraph/DirectedEdgeStar.h> // for inlines
  33
  34 #include <geos/inline.h>
  35
  36 // Forward declarations
  37 namespace geos {
  38         namespace geom {
  39                 class Coordinate;
  40         }
  41         namespace geomgraph {
  42                 class Edge;
  43                 class Node;
  44                 class EdgeEnd;
  45                 class NodeFactory;
  46         }
  47 }
  48
  49 namespace geos {
  50 namespace geomgraph { // geos.geomgraph
  51
  52 /**
  53  * \brief
  54  * Represents a directed graph which is embeddable in a planar surface.
  55  *
  56  * The computation of the IntersectionMatrix relies on the use of a structure
  57  * called a "topology graph".  The topology graph contains nodes and edges
  58  * corresponding to the nodes and line segments of a Geometry. Each
  59  * node and edge in the graph is labeled with its topological location
  60  * relative to the source geometry.
  61  *
  62  * Note that there is no requirement that points of self-intersection
  63  * be a vertex.
  64  * Thus to obtain a correct topology graph, Geometry objects must be
  65  * self-noded before constructing their graphs.
  66  *
  67  * Two fundamental operations are supported by topology graphs:
  68  *
  69  *  - Computing the intersections between all the edges and nodes of
  70  *    a single graph
  71  *  - Computing the intersections between the edges and nodes of two
  72  *    different graphs
  73  *
  74  */
  75 class GEOS_DLL PlanarGraph {
  76 public:
  77
  78         /** \brief
  79          * For nodes in the collection (first..last),
  80          * link the DirectedEdges at the node that are in the result.
  81          *
  82          * This allows clients to link only a subset of nodes in the graph,
  83          * for efficiency (because they know that only a subset is of
  84          * interest).
  85          */
  86   template <typename It>
  87   static void linkResultDirectedEdges(It first, It last)
  88     // throw(TopologyException);
  89   {
  90     for ( ; first!=last; ++first )
  91     {
  92       Node *node=*first;
  93       assert(node);
  94
  95       EdgeEndStar* ees = node->getEdges();
  96       assert(ees);
  97       DirectedEdgeStar* des = dynamic_cast<DirectedEdgeStar*>(ees);
  98       assert(des);
  99
 100       // this might throw an exception
 101       des->linkResultDirectedEdges();
 102     }
 103   }
 104
 105         PlanarGraph(const NodeFactory &nodeFact);
 106
 107         PlanarGraph();
 108
 109         virtual ~PlanarGraph();
 110
 111         virtual std::vector<Edge*>::iterator getEdgeIterator();
 112
 113         virtual std::vector<EdgeEnd*>* getEdgeEnds();
 114
 115         virtual bool isBoundaryNode(int geomIndex, const geom::Coordinate& coord);
 116
 117         virtual void add(EdgeEnd *e);
 118
 119         virtual NodeMap::iterator getNodeIterator();
 120
 121         virtual void getNodes(std::vector<Node*>&);
 122
 123         virtual Node* addNode(Node *node);
 124
 125         virtual Node* addNode(const geom::Coordinate& coord);
 126
 127         /** \brief
 128          * @return the node if found; null otherwise
 129          */
 130         virtual Node* find(geom::Coordinate& coord);
 131
 132         /** \brief
 133          * Add a set of edges to the graph.  For each edge two DirectedEdges
 134          * will be created.  DirectedEdges are NOT linked by this method.
 135          */
 136         virtual void addEdges(const std::vector<Edge*> &edgesToAdd);
 137
 138         virtual void linkResultDirectedEdges();
 139
 140         virtual void linkAllDirectedEdges();
 141
 142         /** \brief
 143          * Returns the EdgeEnd which has edge e as its base edge
 144          * (MD 18 Feb 2002 - this should return a pair of edges)
 145          *
 146          * @return the edge, if found
 147          *    <code>null</code> if the edge was not found
 148          */
 149         virtual EdgeEnd* findEdgeEnd(Edge *e);
 150
 151         /** \brief
 152          * Returns the edge whose first two coordinates are p0 and p1
 153          *
 154          * @return the edge, if found
 155          *    <code>null</code> if the edge was not found
 156          */
 157         virtual Edge* findEdge(const geom::Coordinate& p0,
 158                         const geom::Coordinate& p1);
 159
 160         /** \brief
 161          * Returns the edge which starts at p0 and whose first segment is
 162          * parallel to p1
 163          *
 164          * @return the edge, if found
 165          *    <code>null</code> if the edge was not found
 166          */
 167         virtual Edge* findEdgeInSameDirection(const geom::Coordinate& p0,
 168                         const geom::Coordinate& p1);
 169
 170         virtual std::string printEdges();
 171
 172         virtual NodeMap* getNodeMap();
 173
 174 protected:
 175
 176         std::vector<Edge*> *edges;
 177
 178         NodeMap *nodes;
 179
 180         std::vector<EdgeEnd*> *edgeEndList;
 181
 182         virtual void insertEdge(Edge *e);
 183
 184 private:
 185
 186         /** \brief
 187          * The coordinate pairs match if they define line segments
 188          * lying in the same direction.
 189          *
 190          * E.g. the segments are parallel and in the same quadrant
 191          * (as opposed to parallel and opposite!).
 192          */
 193         bool matchInSameDirection(const geom::Coordinate& p0,
 194                         const geom::Coordinate& p1,
 195                         const geom::Coordinate& ep0,
 196                         const geom::Coordinate& ep1);
 197 };
 198
 199
 200
 201 } // namespace geos.geomgraph
 202 } // namespace geos
 203
 204 //#ifdef GEOS_INLINE
 205 //# include "geos/geomgraph/PlanarGraph.inl"
 206 //#endif
 207
 208 #endif // ifndef GEOS_GEOMGRAPH_PLANARGRAPH_H
 209