src/operation/valid/ConnectedInteriorTester.cpp

   1 /**********************************************************************
   2  *
   3  * GEOS - Geometry Engine Open Source
   4  * http://geos.osgeo.org
   5  *
   6  * Copyright (C) 2007-2010 Safe Software Inc.
   7  * Copyright (C) 2005-2006 Refractions Research Inc.
   8  * Copyright (C) 2001-2002 Vivid Solutions 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: operation/valid/ConnectedInteriorTester.java rev. 1.15 (JTS-1.10)
  18  *
  19  **********************************************************************
  20  *
  21  * TODO:
  22  *
  23  *  - Remove heap allocation of GeometryFactory (might use a singleton)
  24  *  - Track MaximalEdgeRing references: we might be deleting them
  25  *    leaving dangling refs around.
  26  *
  27  **********************************************************************/
  28
  29 #include <geos/operation/valid/ConnectedInteriorTester.h>
  30 #include <geos/operation/overlay/MaximalEdgeRing.h>
  31 #include <geos/operation/overlay/MinimalEdgeRing.h>
  32 #include <geos/operation/overlay/OverlayNodeFactory.h>
  33 #include <geos/geom/GeometryFactory.h>
  34 #include <geos/geom/CoordinateSequence.h>
  35 #include <geos/geom/Coordinate.h>
  36 #include <geos/geom/Location.h>
  37 #include <geos/geom/Polygon.h>
  38 #include <geos/geom/MultiPolygon.h>
  39 #include <geos/geom/MultiPolygon.h>
  40 #include <geos/geom/LineString.h>
  41 #include <geos/geomgraph/GeometryGraph.h>
  42 #include <geos/geomgraph/PlanarGraph.h>
  43 #include <geos/geomgraph/EdgeRing.h>
  44 #include <geos/geomgraph/DirectedEdge.h>
  45 #include <geos/geomgraph/Position.h>
  46 #include <geos/geomgraph/Label.h>
  47
  48 #include <vector>
  49 #include <cassert>
  50 #include <typeinfo>
  51
  52 #ifndef GEOS_DEBUG
  53 #define GEOS_DEBUG 0
  54 #endif
  55
  56 //#define GEOS_CAST_PARANOIA 1
  57
  58 #if GEOS_DEBUG
  59 #include <iostream>
  60 #endif
  61
  62 using namespace std;
  63 using namespace geos::geom;
  64 using namespace geos::geomgraph;
  65 using namespace geos::operation::overlay;
  66
  67 namespace geos {
  68 namespace operation { // geos.operation
  69 namespace valid { // geos.operation.valid
  70
  71 ConnectedInteriorTester::ConnectedInteriorTester(GeometryGraph &newGeomGraph):
  72         geometryFactory(new GeometryFactory()),
  73         geomGraph(newGeomGraph),
  74         disconnectedRingcoord()
  75 {
  76 }
  77
  78 ConnectedInteriorTester::~ConnectedInteriorTester()
  79 {
  80         delete geometryFactory;
  81 }
  82
  83 Coordinate&
  84 ConnectedInteriorTester::getCoordinate()
  85 {
  86         return disconnectedRingcoord;
  87 }
  88
  89 const Coordinate&
  90 ConnectedInteriorTester::findDifferentPoint(const CoordinateSequence *coord,
  91                 const Coordinate& pt)
  92 {
  93         assert(coord);
  94         size_t npts=coord->getSize();
  95         for(size_t i=0; i<npts; ++i)
  96         {
  97                 if(!(coord->getAt(i)==pt))
  98                         return coord->getAt(i);
  99         }
 100         return Coordinate::getNull();
 101 }
 102
 103 /*public*/
 104 bool
 105 ConnectedInteriorTester::isInteriorsConnected()
 106 {
 107
 108         // node the edges, in case holes touch the shell
 109         std::vector<Edge*> splitEdges;
 110         geomGraph.computeSplitEdges(&splitEdges);
 111
 112         // form the edges into rings
 113         PlanarGraph graph(operation::overlay::OverlayNodeFactory::instance());
 114
 115         graph.addEdges(splitEdges);
 116         setInteriorEdgesInResult(graph);
 117         graph.linkResultDirectedEdges();
 118
 119         std::vector<EdgeRing*> edgeRings;
 120         buildEdgeRings(graph.getEdgeEnds(), edgeRings);
 121
 122 #if GEOS_DEBUG
 123         cerr << "buildEdgeRings constructed " << edgeRings.size() << " edgeRings." << endl;
 124 #endif
 125
 126         /*
 127          * Mark all the edges for the edgeRings corresponding to the shells
 128          * of the input polygons.
 129          *
 130          * Only ONE ring gets marked for each shell - if there are others
 131          * which remain unmarked this indicates a disconnected interior.
 132          */
 133         visitShellInteriors(geomGraph.getGeometry(), graph);
 134
 135 #if GEOS_DEBUG
 136         cerr << "after visitShellInteriors edgeRings are " << edgeRings.size() << " edgeRings." << endl;
 137 #endif
 138
 139         /*
 140          * If there are any unvisited shell edges
 141          * (i.e. a ring which is not a hole and which has the interior
 142          * of the parent area on the RHS)
 143          * this means that one or more holes must have split the interior of the
 144          * polygon into at least two pieces.  The polygon is thus invalid.
 145          */
 146         bool res=!hasUnvisitedShellEdge(&edgeRings);
 147
 148 #if GEOS_DEBUG
 149         cerr << "releasing " << edgeRings.size() << " edgeRings." << endl;
 150 #endif
 151         // Release memory allocated by buildEdgeRings
 152         for(size_t i=0, n=edgeRings.size(); i<n; ++i)
 153         {
 154                 EdgeRing* er = edgeRings[i];
 155 #if GEOS_DEBUG
 156                 cerr<<*er<<endl;
 157 #endif
 158                 assert(er);
 159                 delete er;
 160 #if GEOS_DEBUG
 161         cerr << "releasing edgeRing at " << er << endl;
 162 #endif
 163         }
 164         edgeRings.clear();
 165
 166         // Release memory allocated by MaximalEdgeRings
 167         // There should be no more references to this object
 168         // how to check this ? boost::shared_ptr<> comes to mind.
 169         //
 170         for (size_t i=0, n=maximalEdgeRings.size(); i<n; i++)
 171         {
 172                 delete maximalEdgeRings[i];
 173         }
 174         maximalEdgeRings.clear();
 175
 176         return res;
 177 }
 178
 179 void
 180 ConnectedInteriorTester::setInteriorEdgesInResult(PlanarGraph &graph)
 181 {
 182         std::vector<EdgeEnd*> *ee=graph.getEdgeEnds();
 183         for(size_t i=0, n=ee->size(); i<n; ++i)
 184         {
 185                 // Unexpected non DirectedEdge in graphEdgeEnds
 186                 assert(dynamic_cast<DirectedEdge*>((*ee)[i]));
 187                 DirectedEdge *de=static_cast<DirectedEdge*>((*ee)[i]);
 188                 if ( de->getLabel().getLocation(0, Position::RIGHT) == Location::INTERIOR)
 189                 {
 190                         de->setInResult(true);
 191                 }
 192         }
 193 }
 194
 195 /*private*/
 196 void
 197 ConnectedInteriorTester::buildEdgeRings(std::vector<EdgeEnd*> *dirEdges,
 198                                         std::vector<EdgeRing*>& minEdgeRings)
 199 {
 200 #if GEOS_DEBUG
 201         cerr << __FUNCTION__ << " got " << dirEdges->size() << " EdgeEnd vector" << endl;
 202 #endif
 203
 204         typedef std::vector<EdgeEnd*> EdgeEnds;
 205
 206         //std::vector<MinimalEdgeRing*> minEdgeRings;
 207         for(EdgeEnds::size_type i=0, n=dirEdges->size(); i<n; ++i)
 208         {
 209 #ifdef GEOS_CAST_PARANOIA
 210                 assert(dynamic_cast<DirectedEdge*>((*dirEdges)[i]));
 211 #endif
 212                 DirectedEdge *de=static_cast<DirectedEdge*>((*dirEdges)[i]);
 213
 214 #if GEOS_DEBUG
 215                 cerr << "DirectedEdge " << i << ": " << de->print() << endl;
 216 #endif
 217
 218                 // if this edge has not yet been processed
 219                 if(de->isInResult() && de->getEdgeRing()==NULL)
 220                 {
 221                         MaximalEdgeRing* er = new MaximalEdgeRing(de,
 222                                                            geometryFactory);
 223                         // We track MaximalEdgeRings allocations
 224                         // using the private maximalEdgeRings vector
 225                         maximalEdgeRings.push_back(er);
 226
 227                         er->linkDirectedEdgesForMinimalEdgeRings();
 228                         er->buildMinimalRings(minEdgeRings);
 229                 }
 230         }
 231 /*
 232         std::vector<EdgeRing*> *edgeRings=new std::vector<EdgeRing*>();
 233         edgeRings->assign(minEdgeRings.begin(), minEdgeRings.end());
 234         return edgeRings;
 235 */
 236 }
 237
 238 /**
 239  * Mark all the edges for the edgeRings corresponding to the shells
 240  * of the input polygons.  Note only ONE ring gets marked for each shell.
 241  */
 242 void
 243 ConnectedInteriorTester::visitShellInteriors(const Geometry *g, PlanarGraph &graph)
 244 {
 245         if (const Polygon* p=dynamic_cast<const Polygon*>(g))
 246         {
 247                 visitInteriorRing(p->getExteriorRing(), graph);
 248         }
 249
 250         if (const MultiPolygon* mp=dynamic_cast<const MultiPolygon*>(g))
 251         {
 252                 for (size_t i=0, n=mp->getNumGeometries(); i<n; i++) {
 253                         const Polygon *p=dynamic_cast<const Polygon*>(mp->getGeometryN(i));
 254                         visitInteriorRing(p->getExteriorRing(), graph);
 255                 }
 256         }
 257 }
 258
 259 void
 260 ConnectedInteriorTester::visitInteriorRing(const LineString *ring, PlanarGraph &graph)
 261 {
 262         // can't visit an empty ring
 263         if(ring->isEmpty()) return;
 264
 265         const CoordinateSequence *pts=ring->getCoordinatesRO();
 266         const Coordinate& pt0=pts->getAt(0);
 267
 268         /**
 269          * Find first point in coord list different to initial point.
 270          * Need special check since the first point may be repeated.
 271          */
 272         const Coordinate& pt1=findDifferentPoint(pts, pt0);
 273         Edge *e=graph.findEdgeInSameDirection(pt0, pt1);
 274         DirectedEdge *de=static_cast<DirectedEdge*>(graph.findEdgeEnd(e));
 275         DirectedEdge *intDe=NULL;
 276         if (de->getLabel().getLocation(0,Position::RIGHT)==Location::INTERIOR) {
 277                 intDe=de;
 278         } else if (de->getSym()->getLabel().getLocation(0,Position::RIGHT)==Location::INTERIOR) {
 279                 intDe=de->getSym();
 280         }
 281         assert(intDe!=NULL); // unable to find dirEdge with Interior on RHS
 282         visitLinkedDirectedEdges(intDe);
 283 }
 284
 285
 286 void
 287 ConnectedInteriorTester::visitLinkedDirectedEdges(DirectedEdge *start)
 288 {
 289         DirectedEdge *startDe=start;
 290         DirectedEdge *de=start;
 291         //Debug.println(de);
 292         do {
 293                 // found null Directed Edge
 294                 assert(de!=NULL);
 295
 296                 de->setVisited(true);
 297                 de=de->getNext();
 298                 //Debug.println(de);
 299         } while (de!=startDe);
 300 }
 301
 302 /*private*/
 303 bool
 304 ConnectedInteriorTester::hasUnvisitedShellEdge(std::vector<EdgeRing*> *edgeRings)
 305 {
 306
 307 #if GEOS_DEBUG
 308         cerr << "hasUnvisitedShellEdge called with " << edgeRings->size() << " edgeRings." << endl;
 309 #endif
 310
 311         for(std::vector<EdgeRing*>::iterator
 312                 it=edgeRings->begin(), itEnd=edgeRings->end();
 313                 it != itEnd;
 314                 ++it)
 315         {
 316                 EdgeRing *er=*it;
 317                 assert(er);
 318
 319                 // don't check hole rings
 320                 if (er->isHole()) continue;
 321
 322                 std::vector<DirectedEdge*>& edges=er->getEdges();
 323                 DirectedEdge *de=edges[0];
 324                 assert(de);
 325
 326                 // don't check CW rings which are holes
 327                 // (MD - this check may now be irrelevant - 2006-03-09)
 328                 if (de->getLabel().getLocation(0, Position::RIGHT) != Location::INTERIOR) continue;
 329
 330                 /*
 331                  * the edgeRing is CW ring which surrounds the INT
 332                  * of the area, so check all edges have been visited.
 333                  * If any are unvisited, this is a disconnected part
 334                  * of the interior
 335                  */
 336                 for(std::vector<DirectedEdge*>::iterator
 337                         jt=edges.begin(), jtEnd=edges.end();
 338                         jt != jtEnd;
 339                         ++jt)
 340                 {
 341                         de=*jt;
 342                         assert(de);
 343                         //Debug.print("visted? "); Debug.println(de);
 344                         if (!de->isVisited()) {
 345                                 //Debug.print("not visited "); Debug.println(de);
 346                                 disconnectedRingcoord=de->getCoordinate();
 347                                 return true;
 348                         }
 349                 }
 350         }
 351         return false;
 352 }
 353
 354 } // namespace geos.operation.valid
 355 } // namespace geos.operation
 356 } // namespace geos
 357
 358 /**********************************************************************
 359  * $Log$
 360  * Revision 1.29  2006/06/12 11:29:24  strk
 361  * unsigned int => size_t
 362  *
 363  * Revision 1.28  2006/04/06 12:45:28  strk
 364  * Delayed deletion of newly allocated MaximalEdgeRings.
 365  * Existing 'valid' operation tests don't should instability with
 366  * this patch.
 367  *
 368  * Revision 1.27  2006/03/29 13:53:59  strk
 369  * EdgeRing equipped with Invariant testing function and lots of exceptional assertions. Removed useless heap allocations, and pointers usages.
 370  *
 371  * Revision 1.26  2006/03/27 16:02:34  strk
 372  * Added INL file for MinimalEdgeRing, added many debugging blocks,
 373  * fixed memory leak in ConnectedInteriorTester (bug #59)
 374  *
 375  * Revision 1.25  2006/03/27 14:20:46  strk
 376  * Added paranoid assertion checking and a note in header about responsibility of return from buildMaximalEdgeRings()
 377  *
 378  * Revision 1.24  2006/03/20 16:57:44  strk
 379  * spatialindex.h and opValid.h headers split
 380  *
 381  * Revision 1.23  2006/03/17 16:48:55  strk
 382  * LineIntersector and PointLocator made complete components of RelateComputer
 383  * (were statics const pointers before). Reduced inclusions from opRelate.h
 384  * and opValid.h, updated .cpp files to allow build.
 385  *
 386  **********************************************************************/