src/geomgraph/GeometryGraph.cpp

   1 /**********************************************************************
   2  * $Id$
   3  *
   4  * GEOS - Geometry Engine Open Source
   5  * http://geos.refractions.net
   6  *
   7  * Copyright (C) 2001-2002 Vivid Solutions Inc.
   8  * Copyright (C) 2005 Refractions Research Inc.
   9  *
  10  * This is free software; you can redistribute and/or modify it under
  11  * the terms of the GNU Lesser General Public Licence as published
  12  * by the Free Software Foundation.
  13  * See the COPYING file for more information.
  14  *
  15  **********************************************************************
  16  *
  17  * Last port: geomgraph/GeometryGraph.java rev. 1.9 (JTS-1.10)
  18  *
  19  **********************************************************************/
  20
  21 #include <geos/algorithm/CGAlgorithms.h>
  22 #include <geos/algorithm/BoundaryNodeRule.h>
  23
  24 #include <geos/util/UnsupportedOperationException.h>
  25
  26 #include <geos/geomgraph/GeometryGraph.h>
  27 #include <geos/geomgraph/Node.h>
  28 #include <geos/geomgraph/Edge.h>
  29 #include <geos/geomgraph/Label.h>
  30 #include <geos/geomgraph/Position.h>
  31
  32 #include <geos/geomgraph/index/SimpleMCSweepLineIntersector.h>
  33 #include <geos/geomgraph/index/SegmentIntersector.h>
  34 #include <geos/geomgraph/index/EdgeSetIntersector.h>
  35
  36 #include <geos/geom/CoordinateArraySequence.h>
  37 #include <geos/geom/CoordinateSequence.h>
  38 #include <geos/geom/Location.h>
  39 #include <geos/geom/Point.h>
  40 #include <geos/geom/LinearRing.h>
  41 #include <geos/geom/LineString.h>
  42 #include <geos/geom/Polygon.h>
  43 #include <geos/geom/MultiPoint.h>
  44 #include <geos/geom/MultiLineString.h>
  45 #include <geos/geom/MultiPolygon.h>
  46 #include <geos/geom/GeometryCollection.h>
  47
  48 #include <geos/inline.h>
  49
  50 #include <vector>
  51 #include <memory> // auto_ptr
  52 #include <cassert>
  53 #include <typeinfo>
  54
  55 #ifndef GEOS_DEBUG
  56 #define GEOS_DEBUG 0
  57 #endif
  58
  59 #ifndef GEOS_INLINE
  60 # include "geos/geomgraph/GeometryGraph.inl"
  61 #endif
  62
  63 using namespace std;
  64 using namespace geos::geomgraph::index;
  65 using namespace geos::algorithm;
  66 using namespace geos::geom;
  67
  68 namespace geos {
  69 namespace geomgraph { // geos.geomgraph
  70
  71 /*
  72  * This method implements the Boundary Determination Rule
  73  * for determining whether
  74  * a component (node or edge) that appears multiple times in elements
  75  * of a MultiGeometry is in the boundary or the interior of the Geometry
  76  *
  77  * The SFS uses the "Mod-2 Rule", which this function implements
  78  *
  79  * An alternative (and possibly more intuitive) rule would be
  80  * the "At Most One Rule":
  81  *    isInBoundary = (componentCount == 1)
  82  */
  83 bool
  84 GeometryGraph::isInBoundary(int boundaryCount)
  85 {
  86         // the "Mod-2 Rule"
  87         return boundaryCount%2==1;
  88 }
  89
  90 int
  91 GeometryGraph::determineBoundary(int boundaryCount)
  92 {
  93         return isInBoundary(boundaryCount)?Location::BOUNDARY : Location::INTERIOR;
  94 }
  95
  96
  97 EdgeSetIntersector*
  98 GeometryGraph::createEdgeSetIntersector()
  99 {
 100         // various options for computing intersections, from slowest to fastest
 101
 102         //private EdgeSetIntersector esi = new SimpleEdgeSetIntersector();
 103         //private EdgeSetIntersector esi = new MonotoneChainIntersector();
 104         //private EdgeSetIntersector esi = new NonReversingChainIntersector();
 105         //private EdgeSetIntersector esi = new SimpleSweepLineIntersector();
 106         //private EdgeSetIntersector esi = new MCSweepLineIntersector();
 107
 108         //return new SimpleEdgeSetIntersector();
 109         return new SimpleMCSweepLineIntersector();
 110 }
 111
 112 /*public*/
 113 vector<Node*>*
 114 GeometryGraph::getBoundaryNodes()
 115 {
 116         if ( ! boundaryNodes.get() )
 117         {
 118                 boundaryNodes.reset(new vector<Node*>());
 119                 getBoundaryNodes(*(boundaryNodes.get()));
 120         }
 121         return boundaryNodes.get();
 122 }
 123
 124 /*public*/
 125 CoordinateSequence*
 126 GeometryGraph::getBoundaryPoints()
 127 {
 128
 129         if ( ! boundaryPoints.get() )
 130         {
 131                 // Collection will be destroied by GeometryGraph dtor
 132                 vector<Node*>* coll = getBoundaryNodes();
 133                 boundaryPoints.reset(new CoordinateArraySequence(coll->size()));
 134                 size_t i=0;
 135                 for (vector<Node*>::iterator it=coll->begin(), endIt=coll->end();
 136                         it!=endIt; ++it)
 137                 {
 138                         Node *node=*it;
 139                         boundaryPoints->setAt(node->getCoordinate(), i++);
 140                 }
 141         }
 142
 143         // We keep ownership of this, will be destroyed by destructor
 144         return boundaryPoints.get();
 145 }
 146
 147 Edge*
 148 GeometryGraph::findEdge(const LineString *line)
 149 {
 150         return lineEdgeMap.find(line)->second;
 151 }
 152
 153 void
 154 GeometryGraph::computeSplitEdges(vector<Edge*> *edgelist)
 155 {
 156 #if GEOS_DEBUG
 157         cerr<<"["<<this<<"] GeometryGraph::computeSplitEdges() scanning "<<edges->size()<<" local and "<<edgelist->size()<<" provided edges"<<endl;
 158 #endif
 159         for (vector<Edge*>::iterator i=edges->begin(), endIt=edges->end();
 160                 i!=endIt; ++i)
 161         {
 162                 Edge *e=*i;
 163 #if GEOS_DEBUG
 164                 cerr<<"   "<<e->print()<<" adding split edges from arg"<<endl;
 165 #endif
 166                 e->eiList.addSplitEdges(edgelist);
 167         }
 168 }
 169
 170 void
 171 GeometryGraph::add(const Geometry *g)
 172         //throw (UnsupportedOperationException *)
 173 {
 174         if (g->isEmpty()) return;
 175
 176         // check if this Geometry should obey the Boundary Determination Rule
 177         // all collections except MultiPolygons obey the rule
 178         if ( dynamic_cast<const MultiPolygon*>(g) )
 179                 useBoundaryDeterminationRule = false;
 180
 181
 182         if ( const Polygon* x = dynamic_cast<const Polygon*>(g) )
 183                 addPolygon(x);
 184
 185         // LineString also handles LinearRings
 186         else if ( const LineString* x = dynamic_cast<const LineString*>(g) )
 187                 addLineString(x);
 188
 189         else if ( const Point* x = dynamic_cast<const Point*>(g) )
 190                 addPoint(x);
 191
 192         else if ( const GeometryCollection* x =
 193             dynamic_cast<const GeometryCollection*>(g) )
 194   {
 195                 addCollection(x);
 196   }
 197
 198         else {
 199                 string out=typeid(*g).name();
 200                 throw util::UnsupportedOperationException("GeometryGraph::add(Geometry *): unknown geometry type: "+out);
 201         }
 202 }
 203
 204 void
 205 GeometryGraph::addCollection(const GeometryCollection *gc)
 206 {
 207         for (size_t i=0, n=gc->getNumGeometries(); i<n; ++i)
 208         {
 209                 const Geometry *g=gc->getGeometryN(i);
 210                 add(g);
 211         }
 212 }
 213
 214 /*
 215  * Add a Point to the graph.
 216  */
 217 void
 218 GeometryGraph::addPoint(const Point *p)
 219 {
 220         const Coordinate& coord=*(p->getCoordinate());
 221         insertPoint(argIndex, coord, Location::INTERIOR);
 222 }
 223
 224 /*
 225  * The left and right topological location arguments assume that the ring
 226  * is oriented CW.
 227  * If the ring is in the opposite orientation,
 228  * the left and right locations must be interchanged.
 229  */
 230 void
 231 GeometryGraph::addPolygonRing(const LinearRing *lr, int cwLeft, int cwRight)
 232         // throw IllegalArgumentException (see below)
 233 {
 234         // skip empty component (see bug #234)
 235         if ( lr->isEmpty() ) return;
 236
 237         const CoordinateSequence *lrcl = lr->getCoordinatesRO();
 238
 239         CoordinateSequence* coord=CoordinateSequence::removeRepeatedPoints(lrcl);
 240         if (coord->getSize()<4) {
 241                 hasTooFewPointsVar=true;
 242                 invalidPoint=coord->getAt(0); // its now a Coordinate
 243                 delete coord;
 244                 return;
 245         }
 246         int left=cwLeft;
 247         int right=cwRight;
 248
 249         /*
 250          * the isCCW call might throw an
 251          * IllegalArgumentException if degenerate ring does
 252          * not contain 3 distinct points.
 253          */
 254         try
 255         {
 256                 if (CGAlgorithms::isCCW(coord)) {
 257                         left=cwRight;
 258                         right=cwLeft;
 259                 }
 260         }
 261         catch(...)
 262         {
 263                 delete coord;
 264                 throw;
 265         }
 266
 267         Edge *e=new Edge(coord,new Label(argIndex,Location::BOUNDARY,left,right));
 268         lineEdgeMap[lr]=e;
 269         insertEdge(e);
 270         insertPoint(argIndex,coord->getAt(0), Location::BOUNDARY);
 271 }
 272
 273 void
 274 GeometryGraph::addPolygon(const Polygon *p)
 275 {
 276         const LineString* ls;
 277         const LinearRing* lr;
 278
 279         ls = p->getExteriorRing();
 280         assert(dynamic_cast<const LinearRing*>(ls));
 281         lr = static_cast<const LinearRing*>(ls);
 282         addPolygonRing(lr, Location::EXTERIOR, Location::INTERIOR);
 283         for (size_t i=0, n=p->getNumInteriorRing(); i<n; ++i)
 284         {
 285                 // Holes are topologically labelled opposite to the shell, since
 286                 // the interior of the polygon lies on their opposite side
 287                 // (on the left, if the hole is oriented CW)
 288                 ls = p->getInteriorRingN(i);
 289                 assert(dynamic_cast<const LinearRing*>(ls));
 290                 lr = static_cast<const LinearRing*>(ls);
 291                 addPolygonRing(lr, Location::INTERIOR, Location::EXTERIOR);
 292         }
 293 }
 294
 295 void
 296 GeometryGraph::addLineString(const LineString *line)
 297 {
 298         CoordinateSequence* coord=CoordinateSequence::removeRepeatedPoints(line->getCoordinatesRO());
 299         if(coord->getSize()<2) {
 300                 hasTooFewPointsVar=true;
 301                 invalidPoint=coord->getAt(0);
 302                 delete coord;
 303                 return;
 304         }
 305
 306         Edge *e=new Edge(coord,new Label(argIndex,Location::INTERIOR));
 307         lineEdgeMap[line]=e;
 308         insertEdge(e);
 309
 310         /*
 311          * Add the boundary points of the LineString, if any.
 312          * Even if the LineString is closed, add both points as if they
 313          * were endpoints.
 314          * This allows for the case that the node already exists and is
 315          * a boundary point.
 316          */
 317         assert(coord->size() >= 2); // found LineString with single point
 318         insertBoundaryPoint(argIndex, coord->getAt(0));
 319         insertBoundaryPoint(argIndex, coord->getAt(coord->getSize()-1));
 320 }
 321
 322 /*
 323  * Add an Edge computed externally.  The label on the Edge is assumed
 324  * to be correct.
 325  */
 326 void
 327 GeometryGraph::addEdge(Edge *e)
 328 {
 329         insertEdge(e);
 330         const CoordinateSequence* coord=e->getCoordinates();
 331         // insert the endpoint as a node, to mark that it is on the boundary
 332         insertPoint(argIndex,coord->getAt(0),Location::BOUNDARY);
 333         insertPoint(argIndex,coord->getAt(coord->getSize()-1),Location::BOUNDARY);
 334 }
 335
 336 /*
 337  * Add a point computed externally.  The point is assumed to be a
 338  * Point Geometry part, which has a location of INTERIOR.
 339  */
 340 void
 341 GeometryGraph::addPoint(Coordinate& pt)
 342 {
 343         insertPoint(argIndex,pt,Location::INTERIOR);
 344 }
 345
 346 /*public*/
 347 SegmentIntersector*
 348 GeometryGraph::computeSelfNodes(LineIntersector *li, bool computeRingSelfNodes)
 349 {
 350         SegmentIntersector *si=new SegmentIntersector(li,true,false);
 351         auto_ptr<EdgeSetIntersector> esi(createEdgeSetIntersector());
 352
 353         // optimized test for Polygons and Rings
 354         if (! computeRingSelfNodes
 355             && ( dynamic_cast<const LinearRing*>(parentGeom)
 356             || dynamic_cast<const Polygon*>(parentGeom)
 357             || dynamic_cast<const MultiPolygon*>(parentGeom) ))
 358         {
 359                 esi->computeIntersections(edges, si, false);
 360         }
 361         else
 362         {
 363                 esi->computeIntersections(edges, si, true);
 364         }
 365
 366 #if GEOS_DEBUG
 367         cerr << "SegmentIntersector # tests = " << si->numTests << endl;
 368 #endif // GEOS_DEBUG
 369
 370         addSelfIntersectionNodes(argIndex);
 371         return si;
 372 }
 373
 374 SegmentIntersector*
 375 GeometryGraph::computeEdgeIntersections(GeometryGraph *g,
 376         LineIntersector *li, bool includeProper)
 377 {
 378 #if GEOS_DEBUG
 379         cerr<<"GeometryGraph::computeEdgeIntersections call"<<endl;
 380 #endif
 381         SegmentIntersector *si=new SegmentIntersector(li, includeProper, true);
 382
 383         si->setBoundaryNodes(getBoundaryNodes(), g->getBoundaryNodes());
 384         auto_ptr<EdgeSetIntersector> esi(createEdgeSetIntersector());
 385         esi->computeIntersections(edges, g->edges, si);
 386 #if GEOS_DEBUG
 387         cerr<<"GeometryGraph::computeEdgeIntersections returns"<<endl;
 388 #endif
 389         return si;
 390 }
 391
 392 void
 393 GeometryGraph::insertPoint(int argIndex, const Coordinate& coord,
 394         int onLocation)
 395 {
 396 #if GEOS_DEBUG
 397         cerr<<"GeometryGraph::insertPoint("<<coord.toString()<<" called"<<endl;
 398 #endif
 399         Node *n=nodes->addNode(coord);
 400         Label *lbl=n->getLabel();
 401         if (lbl==NULL)
 402         {
 403                 n->setLabel(argIndex, onLocation);
 404         }
 405         else
 406         {
 407                 lbl->setLocation(argIndex, onLocation);
 408         }
 409 }
 410
 411 /*
 412  * Adds points using the mod-2 rule of SFS.  This is used to add the boundary
 413  * points of dim-1 geometries (Curves/MultiCurves).  According to the SFS,
 414  * an endpoint of a Curve is on the boundary
 415  * iff if it is in the boundaries of an odd number of Geometries
 416  */
 417 void
 418 GeometryGraph::insertBoundaryPoint(int argIndex,const Coordinate& coord)
 419 {
 420         Node *n=nodes->addNode(coord);
 421         Label *lbl=n->getLabel();
 422
 423         // the new point to insert is on a boundary
 424         int boundaryCount=1;
 425
 426         // determine the current location for the point (if any)
 427   if ( NULL == lbl ) return;
 428
 429         int loc = lbl->getLocation(argIndex,Position::ON);
 430         if (loc==Location::BOUNDARY) boundaryCount++;
 431
 432         // determine the boundary status of the point according to the
 433         // Boundary Determination Rule
 434         int newLoc = determineBoundary(boundaryNodeRule, boundaryCount);
 435         lbl->setLocation(argIndex,newLoc);
 436 }
 437
 438 /*private*/
 439 void
 440 GeometryGraph::addSelfIntersectionNodes(int argIndex)
 441 {
 442         for (vector<Edge*>::iterator i=edges->begin(), endIt=edges->end();
 443                 i!=endIt; ++i)
 444         {
 445                 Edge *e=*i;
 446                 int eLoc=e->getLabel()->getLocation(argIndex);
 447                 EdgeIntersectionList &eiL=e->eiList;
 448                 for (EdgeIntersectionList::iterator
 449                         eiIt=eiL.begin(), eiEnd=eiL.end();
 450                         eiIt!=eiEnd; ++eiIt)
 451                 {
 452                         EdgeIntersection *ei=*eiIt;
 453                         addSelfIntersectionNode(argIndex, ei->coord, eLoc);
 454                 }
 455         }
 456 }
 457
 458 /*private*/
 459 void
 460 GeometryGraph::addSelfIntersectionNode(int argIndex,
 461         const Coordinate& coord, int loc)
 462 {
 463         // if this node is already a boundary node, don't change it
 464         if (isBoundaryNode(argIndex,coord)) return;
 465         if (loc==Location::BOUNDARY && useBoundaryDeterminationRule)
 466         {
 467                 insertBoundaryPoint(argIndex,coord);
 468         }
 469         else
 470         {
 471                 insertPoint(argIndex,coord,loc);
 472         }
 473 }
 474
 475 vector<Edge*> *
 476 GeometryGraph::getEdges()
 477 {
 478         return edges;
 479 }
 480
 481 bool
 482 GeometryGraph::hasTooFewPoints()
 483 {
 484         return hasTooFewPointsVar;
 485 }
 486
 487 const Coordinate&
 488 GeometryGraph::getInvalidPoint()
 489 {
 490         return invalidPoint;
 491 }
 492
 493 GeometryGraph::GeometryGraph(int newArgIndex,
 494                 const geom::Geometry *newParentGeom)
 495         :
 496         PlanarGraph(),
 497         parentGeom(newParentGeom),
 498         useBoundaryDeterminationRule(true),
 499         boundaryNodeRule(algorithm::BoundaryNodeRule::OGC_SFS_BOUNDARY_RULE),
 500         argIndex(newArgIndex),
 501         hasTooFewPointsVar(false)
 502 {
 503         if (parentGeom!=NULL) add(parentGeom);
 504 }
 505
 506 GeometryGraph::GeometryGraph(int newArgIndex,
 507                 const geom::Geometry *newParentGeom,
 508                 const algorithm::BoundaryNodeRule& bnr)
 509         :
 510         PlanarGraph(),
 511         parentGeom(newParentGeom),
 512         useBoundaryDeterminationRule(true),
 513         boundaryNodeRule(bnr),
 514         argIndex(newArgIndex),
 515         hasTooFewPointsVar(false)
 516 {
 517         if (parentGeom!=NULL) add(parentGeom);
 518 }
 519
 520 GeometryGraph::GeometryGraph()
 521         :
 522         PlanarGraph(),
 523         parentGeom(NULL),
 524         useBoundaryDeterminationRule(true),
 525         boundaryNodeRule(algorithm::BoundaryNodeRule::OGC_SFS_BOUNDARY_RULE),
 526         argIndex(-1),
 527         hasTooFewPointsVar(false)
 528 {
 529 }
 530
 531
 532 /* public static */
 533 int
 534 GeometryGraph::determineBoundary(
 535                      const algorithm::BoundaryNodeRule& boundaryNodeRule,
 536                                                     int boundaryCount)
 537 {
 538         return boundaryNodeRule.isInBoundary(boundaryCount)
 539                 ? Location::BOUNDARY : Location::INTERIOR;
 540 }
 541
 542 } // namespace geos.geomgraph
 543 } // namespace geos
 544
 545 /**********************************************************************
 546  * $Log$
 547  * Revision 1.30  2006/06/13 21:40:06  strk
 548  * Cleanups and some more debugging lines
 549  *
 550  * Revision 1.29  2006/06/12 11:29:23  strk
 551  * unsigned int => size_t
 552  *
 553  * Revision 1.28  2006/06/09 07:42:13  strk
 554  * * source/geomgraph/GeometryGraph.cpp, source/operation/buffer/OffsetCurveSetBuilder.cpp, source/operation/overlay/OverlayOp.cpp, source/operation/valid/RepeatedPointTester.cpp: Fixed warning after Polygon ring accessor methods changed to work with size_t. Small optimizations in loops.
 555  *
 556  * Revision 1.27  2006/04/07 09:54:30  strk
 557  * Geometry::getNumGeometries() changed to return 'unsigned int'
 558  * rather then 'int'
 559  *
 560  * Revision 1.26  2006/03/29 15:23:49  strk
 561  * Moved GeometryGraph inlines from .h to .inl file
 562  *
 563  * Revision 1.25  2006/03/15 17:16:29  strk
 564  * streamlined headers inclusion
 565  *
 566  **********************************************************************/
 567
 568