src/geomgraph/PlanarGraph.cpp

   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 #include <geos/geom/Coordinate.h>
  21 #include <geos/geom/CoordinateSequence.h>
  22 #include <geos/geom/Location.h>
  23
  24 #include <geos/geomgraph/PlanarGraph.h>
  25 #include <geos/geomgraph/Node.h>
  26 #include <geos/geomgraph/NodeFactory.h>
  27 #include <geos/geomgraph/Edge.h>
  28 #include <geos/geomgraph/EdgeEndStar.h>
  29 #include <geos/geomgraph/DirectedEdge.h>
  30 #include <geos/geomgraph/DirectedEdgeStar.h>
  31 #include <geos/geomgraph/NodeMap.h>
  32 #include <geos/geomgraph/Quadrant.h>
  33
  34 #include <geos/algorithm/CGAlgorithms.h>
  35
  36 #include <vector>
  37 #include <sstream>
  38 #include <string>
  39 #include <cassert>
  40
  41
  42 #ifndef GEOS_DEBUG
  43 #define GEOS_DEBUG 0
  44 #endif
  45
  46 using namespace std;
  47 using namespace geos::algorithm;
  48 using namespace geos::geom;
  49
  50 namespace geos {
  51 namespace geomgraph { // geos.geomgraph
  52
  53 /*public*/
  54 PlanarGraph::PlanarGraph(const NodeFactory &nodeFact)
  55         :
  56         edges(new vector<Edge*>()),
  57         nodes(new NodeMap(nodeFact)),
  58         edgeEndList(new vector<EdgeEnd*>())
  59 {
  60 }
  61
  62 /*public*/
  63 PlanarGraph::PlanarGraph()
  64         :
  65         edges(new vector<Edge*>()),
  66         nodes(new NodeMap(NodeFactory::instance())),
  67         edgeEndList(new vector<EdgeEnd*>())
  68 {
  69 }
  70
  71 /*public*/
  72 PlanarGraph::~PlanarGraph()
  73 {
  74         delete nodes;
  75 #if 1 // FIXME: PlanarGraph should *not* own edges!
  76         for(size_t i=0, n=edges->size(); i<n; i++) {
  77                 delete (*edges)[i];
  78         }
  79 #endif
  80         delete edges;
  81
  82         for(size_t i=0, n=edgeEndList->size(); i<n; i++) {
  83                 delete (*edgeEndList)[i];
  84         }
  85         delete edgeEndList;
  86 }
  87
  88 /*public*/
  89 vector<Edge*>::iterator
  90 PlanarGraph::getEdgeIterator()
  91 {
  92         assert(edges);
  93         return edges->begin();
  94 }
  95
  96 /*public*/
  97 vector<EdgeEnd*> *
  98 PlanarGraph::getEdgeEnds()
  99 {
 100         return edgeEndList;
 101 }
 102
 103 /*public*/
 104 bool
 105 PlanarGraph::isBoundaryNode(int geomIndex, const Coordinate& coord)
 106 {
 107         assert(nodes);
 108
 109         Node *node=nodes->find(coord);
 110         if (node==NULL) return false;
 111
 112         const Label& label = node->getLabel();
 113         if (! label.isNull() && label.getLocation(geomIndex)==Location::BOUNDARY)
 114                         return true;
 115
 116         return false;
 117 }
 118
 119 /*protected*/
 120 void
 121 PlanarGraph::insertEdge(Edge *e)
 122 {
 123         assert(e);
 124         assert(edges);
 125         edges->push_back(e);
 126 }
 127
 128 /*public*/
 129 void
 130 PlanarGraph::add(EdgeEnd* e)
 131 {
 132
 133         assert(e);
 134         assert(nodes);
 135         nodes->add(e);
 136
 137         assert(edgeEndList);
 138         edgeEndList->push_back(e);
 139 }
 140
 141 /*public*/
 142 NodeMap::iterator
 143 PlanarGraph::getNodeIterator()
 144 {
 145         assert(nodes);
 146         return nodes->begin();
 147 }
 148
 149 /*public*/
 150 void
 151 PlanarGraph::getNodes(vector<Node*>& values)
 152 {
 153         assert(nodes);
 154         NodeMap::iterator it=nodes->nodeMap.begin();
 155         while(it!=nodes->nodeMap.end()) {
 156                 assert(it->second);
 157                 values.push_back(it->second);
 158                 it++;
 159         }
 160 }
 161
 162 // arg cannot be const, NodeMap::addNode will
 163 // occasionally label-merge first arg.
 164 /*public*/
 165 Node*
 166 PlanarGraph::addNode(Node *node)
 167 {
 168         assert(nodes);
 169 #if GEOS_DEBUG
 170         cerr << "PlanarGraph::addNode(Node * " << *node
 171                 << ")" << endl;
 172 #endif
 173         return nodes->addNode(node);
 174 }
 175
 176 /*public*/
 177 Node*
 178 PlanarGraph::addNode(const Coordinate& coord)
 179 {
 180 #if GEOS_DEBUG
 181         cerr << "PlanarGraph::addNode(Coordinate& "
 182                 << coord << ")" << endl;
 183 #endif
 184         return nodes->addNode(coord);
 185 }
 186
 187 /*public*/
 188 Node*
 189 PlanarGraph::find(Coordinate& coord)
 190 {
 191         assert(nodes);
 192         return nodes->find(coord);
 193 }
 194
 195 /*public*/
 196 void
 197 PlanarGraph::addEdges(const vector<Edge*>& edgesToAdd)
 198 {
 199         // create all the nodes for the edges
 200         for (vector<Edge*>::const_iterator it=edgesToAdd.begin(),
 201                 endIt=edgesToAdd.end(); it!=endIt; ++it)
 202         {
 203                 Edge *e=*it;
 204                 assert(e);
 205                 edges->push_back(e);
 206
 207                 // PlanarGraph destructor will delete all DirectedEdges
 208                 // in edgeEndList, which is where these are added
 209                 // by the ::add(EdgeEnd) call
 210                 DirectedEdge *de1=new DirectedEdge(e, true);
 211                 DirectedEdge *de2=new DirectedEdge(e, false);
 212
 213                 de1->setSym(de2);
 214                 de2->setSym(de1);
 215                 add(de1);
 216                 add(de2);
 217         }
 218 }
 219
 220 /*public static*/
 221 void
 222 PlanarGraph::linkResultDirectedEdges()
 223 {
 224 #if GEOS_DEBUG
 225         cerr<<"PlanarGraph::linkResultDirectedEdges called"<<endl;
 226 #endif
 227         NodeMap::iterator nodeit=nodes->nodeMap.begin();
 228         for (;nodeit!=nodes->nodeMap.end();nodeit++) {
 229                 Node *node=nodeit->second;
 230                 assert(node);
 231
 232                 EdgeEndStar* ees=node->getEdges();
 233                 assert(ees);
 234                 assert(dynamic_cast<DirectedEdgeStar*>(ees));
 235                 DirectedEdgeStar* des = static_cast<DirectedEdgeStar*>(ees);
 236
 237                 // this might throw an exception
 238                 des->linkResultDirectedEdges();
 239         }
 240 }
 241
 242 /*
 243  * Link the DirectedEdges at the nodes of the graph.
 244  * This allows clients to link only a subset of nodes in the graph, for
 245  * efficiency (because they know that only a subset is of interest).
 246  */
 247 void
 248 PlanarGraph::linkAllDirectedEdges()
 249 {
 250 #if GEOS_DEBUG
 251         cerr<<"PlanarGraph::linkAllDirectedEdges called"<<endl;
 252 #endif
 253         NodeMap::iterator nodeit=nodes->nodeMap.begin();
 254         for (;nodeit!=nodes->nodeMap.end();nodeit++)
 255         {
 256                 Node *node=nodeit->second;
 257                 assert(node);
 258
 259                 EdgeEndStar *ees=node->getEdges();
 260                 assert(ees);
 261
 262                 // Unespected non-DirectedEdgeStar in node
 263                 assert(dynamic_cast<DirectedEdgeStar *>(ees));
 264                 DirectedEdgeStar *des=static_cast<DirectedEdgeStar *>(ees);
 265
 266                 des->linkAllDirectedEdges();
 267         }
 268 }
 269
 270 /*public*/
 271 EdgeEnd*
 272 PlanarGraph::findEdgeEnd(Edge *e)
 273 {
 274         vector<EdgeEnd*>* eev=getEdgeEnds();
 275         assert(eev);
 276
 277         for (vector<EdgeEnd*>::iterator i=eev->begin(), iEnd=eev->end();
 278                         i != iEnd;
 279                         ++i)
 280         {
 281                 EdgeEnd *ee=*i;
 282                 assert(ee);
 283
 284                 // should test using values rather then pointers ?
 285                 if (ee->getEdge()==e) return ee;
 286         }
 287         return NULL;
 288 }
 289
 290 /*public*/
 291 Edge*
 292 PlanarGraph::findEdge(const Coordinate& p0, const Coordinate& p1)
 293 {
 294         for (size_t i=0, n=edges->size(); i<n; ++i)
 295         {
 296                 Edge *e=(*edges)[i];
 297                 assert(e);
 298
 299                 const CoordinateSequence* eCoord=e->getCoordinates();
 300                 assert(eCoord);
 301
 302                 if (p0==eCoord->getAt(0) && p1==eCoord->getAt(1))
 303                         return e;
 304         }
 305         return NULL;
 306 }
 307
 308 /*public*/
 309 Edge*
 310 PlanarGraph::findEdgeInSameDirection(const Coordinate& p0,
 311                 const Coordinate& p1)
 312 {
 313         for(size_t i=0, n=edges->size(); i<n; i++)
 314         {
 315                 Edge *e=(*edges)[i];
 316                 assert(e);
 317
 318                 const CoordinateSequence* eCoord=e->getCoordinates();
 319                 assert(eCoord);
 320
 321                 size_t nCoords=eCoord->size();
 322                 assert(nCoords>1);
 323
 324                 if (matchInSameDirection(p0, p1,
 325                                 eCoord->getAt(0),
 326                                 eCoord->getAt(1)))
 327                 {
 328                         return e;
 329                 }
 330
 331                 if (matchInSameDirection(p0, p1,
 332                                 eCoord->getAt(nCoords-1),
 333                                 eCoord->getAt(nCoords-2)))
 334                 {
 335                         return e;
 336                 }
 337         }
 338
 339         return NULL;
 340 }
 341
 342 /*private*/
 343 bool
 344 PlanarGraph::matchInSameDirection(const Coordinate& p0, const Coordinate& p1,
 345                 const Coordinate& ep0, const Coordinate& ep1)
 346 {
 347         if (!(p0==ep0))
 348                 return false;
 349
 350         if (CGAlgorithms::computeOrientation(p0,p1,ep1)==CGAlgorithms::COLLINEAR
 351                 && Quadrant::quadrant(p0,p1)==Quadrant::quadrant(ep0,ep1))
 352                         return true;
 353         return false;
 354 }
 355
 356 string
 357 PlanarGraph::printEdges()
 358 {
 359
 360     std::ostringstream oss;
 361     oss << "Edges: ";
 362         for(size_t i=0, n=edges->size(); i<n; ++i)
 363         {
 364         Edge *e=(*edges)[i];
 365                 oss << "edge " << i << ":\n" << e->print() << e->eiList.print();
 366         }
 367     return oss.str();
 368 }
 369
 370 NodeMap*
 371 PlanarGraph::getNodeMap()
 372 {
 373         return nodes;
 374 }
 375
 376 } // namespace geos.geomgraph
 377 } // namespace geos
 378