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(GeometryFactory::create()),
  73         geomGraph(newGeomGraph),
  74         disconnectedRingcoord()
  75 {
  76 }
  77
  78 ConnectedInteriorTester::~ConnectedInteriorTester()
  79 {
  80 }
  81
  82 Coordinate&
  83 ConnectedInteriorTester::getCoordinate()
  84 {
  85         return disconnectedRingcoord;
  86 }
  87
  88 const Coordinate&
  89 ConnectedInteriorTester::findDifferentPoint(const CoordinateSequence *coord,
  90                 const Coordinate& pt)
  91 {
  92         assert(coord);
  93         size_t npts=coord->getSize();
  94         for(size_t i=0; i<npts; ++i)
  95         {
  96                 if(!(coord->getAt(i)==pt))
  97                         return coord->getAt(i);
  98         }
  99         return Coordinate::getNull();
 100 }
 101
 102 /*public*/
 103 bool
 104 ConnectedInteriorTester::isInteriorsConnected()
 105 {
 106
 107         // node the edges, in case holes touch the shell
 108         std::vector<Edge*> splitEdges;
 109         geomGraph.computeSplitEdges(&splitEdges);
 110
 111         // form the edges into rings
 112         PlanarGraph graph(operation::overlay::OverlayNodeFactory::instance());
 113
 114         graph.addEdges(splitEdges);
 115         setInteriorEdgesInResult(graph);
 116         graph.linkResultDirectedEdges();
 117
 118         std::vector<EdgeRing*> edgeRings;
 119         buildEdgeRings(graph.getEdgeEnds(), edgeRings);
 120
 121 #if GEOS_DEBUG
 122         cerr << "buildEdgeRings constructed " << edgeRings.size() << " edgeRings." << endl;
 123 #endif
 124
 125         /*
 126          * Mark all the edges for the edgeRings corresponding to the shells
 127          * of the input polygons.
 128          *
 129          * Only ONE ring gets marked for each shell - if there are others
 130          * which remain unmarked this indicates a disconnected interior.
 131          */
 132         visitShellInteriors(geomGraph.getGeometry(), graph);
 133
 134 #if GEOS_DEBUG
 135         cerr << "after visitShellInteriors edgeRings are " << edgeRings.size() << " edgeRings." << endl;
 136 #endif
 137
 138         /*
 139          * If there are any unvisited shell edges
 140          * (i.e. a ring which is not a hole and which has the interior
 141          * of the parent area on the RHS)
 142          * this means that one or more holes must have split the interior of the
 143          * polygon into at least two pieces.  The polygon is thus invalid.
 144          */
 145         bool res=!hasUnvisitedShellEdge(&edgeRings);
 146
 147 #if GEOS_DEBUG
 148         cerr << "releasing " << edgeRings.size() << " edgeRings." << endl;
 149 #endif
 150         // Release memory allocated by buildEdgeRings
 151         for(size_t i=0, n=edgeRings.size(); i<n; ++i)
 152         {
 153                 EdgeRing* er = edgeRings[i];
 154 #if GEOS_DEBUG
 155                 cerr<<*er<<endl;
 156 #endif
 157                 assert(er);
 158                 delete er;
 159 #if GEOS_DEBUG
 160         cerr << "releasing edgeRing at " << er << endl;
 161 #endif
 162         }
 163         edgeRings.clear();
 164
 165         // Release memory allocated by MaximalEdgeRings
 166         // There should be no more references to this object
 167         // how to check this ? boost::shared_ptr<> comes to mind.
 168         //
 169         for (size_t i=0, n=maximalEdgeRings.size(); i<n; i++)
 170         {
 171                 delete maximalEdgeRings[i];
 172         }
 173         maximalEdgeRings.clear();
 174
 175         return res;
 176 }
 177
 178 void
 179 ConnectedInteriorTester::setInteriorEdgesInResult(PlanarGraph &graph)
 180 {
 181         std::vector<EdgeEnd*> *ee=graph.getEdgeEnds();
 182         for(size_t i=0, n=ee->size(); i<n; ++i)
 183         {
 184                 // Unexpected non DirectedEdge in graphEdgeEnds
 185                 assert(dynamic_cast<DirectedEdge*>((*ee)[i]));
 186                 DirectedEdge *de=static_cast<DirectedEdge*>((*ee)[i]);
 187                 if ( de->getLabel().getLocation(0, Position::RIGHT) == Location::INTERIOR)
 188                 {
 189                         de->setInResult(true);
 190                 }
 191         }
 192 }
 193
 194 /*private*/
 195 void
 196 ConnectedInteriorTester::buildEdgeRings(std::vector<EdgeEnd*> *dirEdges,
 197                                         std::vector<EdgeRing*>& minEdgeRings)
 198 {
 199 #if GEOS_DEBUG
 200         cerr << __FUNCTION__ << " got " << dirEdges->size() << " EdgeEnd vector" << endl;
 201 #endif
 202
 203         typedef std::vector<EdgeEnd*> EdgeEnds;
 204
 205         //std::vector<MinimalEdgeRing*> minEdgeRings;
 206         for(EdgeEnds::size_type i=0, n=dirEdges->size(); i<n; ++i)
 207         {
 208 #ifdef GEOS_CAST_PARANOIA
 209                 assert(dynamic_cast<DirectedEdge*>((*dirEdges)[i]));
 210 #endif
 211                 DirectedEdge *de=static_cast<DirectedEdge*>((*dirEdges)[i]);
 212
 213 #if GEOS_DEBUG
 214                 cerr << "DirectedEdge " << i << ": " << de->print() << endl;
 215 #endif
 216
 217                 // if this edge has not yet been processed
 218                 if(de->isInResult() && de->getEdgeRing()==NULL)
 219                 {
 220                         MaximalEdgeRing* er = new MaximalEdgeRing(de,
 221                                                            geometryFactory.get());
 222                         // We track MaximalEdgeRings allocations
 223                         // using the private maximalEdgeRings vector
 224                         maximalEdgeRings.push_back(er);
 225
 226                         er->linkDirectedEdgesForMinimalEdgeRings();
 227                         er->buildMinimalRings(minEdgeRings);
 228                 }
 229         }
 230 /*
 231         std::vector<EdgeRing*> *edgeRings=new std::vector<EdgeRing*>();
 232         edgeRings->assign(minEdgeRings.begin(), minEdgeRings.end());
 233         return edgeRings;
 234 */
 235 }
 236
 237 /**
 238  * Mark all the edges for the edgeRings corresponding to the shells
 239  * of the input polygons.  Note only ONE ring gets marked for each shell.
 240  */
 241 void
 242 ConnectedInteriorTester::visitShellInteriors(const Geometry *g, PlanarGraph &graph)
 243 {
 244         if (const Polygon* p=dynamic_cast<const Polygon*>(g))
 245         {
 246                 visitInteriorRing(p->getExteriorRing(), graph);
 247         }
 248
 249         if (const MultiPolygon* mp=dynamic_cast<const MultiPolygon*>(g))
 250         {
 251                 for (size_t i=0, n=mp->getNumGeometries(); i<n; i++) {
 252                         const Polygon *p=dynamic_cast<const Polygon*>(mp->getGeometryN(i));
 253                         visitInteriorRing(p->getExteriorRing(), graph);
 254                 }
 255         }
 256 }
 257
 258 void
 259 ConnectedInteriorTester::visitInteriorRing(const LineString *ring, PlanarGraph &graph)
 260 {
 261         // can't visit an empty ring
 262         if(ring->isEmpty()) return;
 263
 264         const CoordinateSequence *pts=ring->getCoordinatesRO();
 265         const Coordinate& pt0=pts->getAt(0);
 266
 267         /**
 268          * Find first point in coord list different to initial point.
 269          * Need special check since the first point may be repeated.
 270          */
 271         const Coordinate& pt1=findDifferentPoint(pts, pt0);
 272         Edge *e=graph.findEdgeInSameDirection(pt0, pt1);
 273         DirectedEdge *de=static_cast<DirectedEdge*>(graph.findEdgeEnd(e));
 274         DirectedEdge *intDe=NULL;
 275         if (de->getLabel().getLocation(0,Position::RIGHT)==Location::INTERIOR) {
 276                 intDe=de;
 277         } else if (de->getSym()->getLabel().getLocation(0,Position::RIGHT)==Location::INTERIOR) {
 278                 intDe=de->getSym();
 279         }
 280         assert(intDe!=NULL); // unable to find dirEdge with Interior on RHS
 281         visitLinkedDirectedEdges(intDe);
 282 }
 283
 284
 285 void
 286 ConnectedInteriorTester::visitLinkedDirectedEdges(DirectedEdge *start)
 287 {
 288         DirectedEdge *startDe=start;
 289         DirectedEdge *de=start;
 290         //Debug.println(de);
 291         do {
 292                 // found null Directed Edge
 293                 assert(de!=NULL);
 294
 295                 de->setVisited(true);
 296                 de=de->getNext();
 297                 //Debug.println(de);
 298         } while (de!=startDe);
 299 }
 300
 301 /*private*/
 302 bool
 303 ConnectedInteriorTester::hasUnvisitedShellEdge(std::vector<EdgeRing*> *edgeRings)
 304 {
 305
 306 #if GEOS_DEBUG
 307         cerr << "hasUnvisitedShellEdge called with " << edgeRings->size() << " edgeRings." << endl;
 308 #endif
 309
 310         for(std::vector<EdgeRing*>::iterator
 311                 it=edgeRings->begin(), itEnd=edgeRings->end();
 312                 it != itEnd;
 313                 ++it)
 314         {
 315                 EdgeRing *er=*it;
 316                 assert(er);
 317
 318                 // don't check hole rings
 319                 if (er->isHole()) continue;
 320
 321                 std::vector<DirectedEdge*>& edges=er->getEdges();
 322                 DirectedEdge *de=edges[0];
 323                 assert(de);
 324
 325                 // don't check CW rings which are holes
 326                 // (MD - this check may now be irrelevant - 2006-03-09)
 327                 if (de->getLabel().getLocation(0, Position::RIGHT) != Location::INTERIOR) continue;
 328
 329                 /*
 330                  * the edgeRing is CW ring which surrounds the INT
 331                  * of the area, so check all edges have been visited.
 332                  * If any are unvisited, this is a disconnected part
 333                  * of the interior
 334                  */
 335                 for(std::vector<DirectedEdge*>::iterator
 336                         jt=edges.begin(), jtEnd=edges.end();
 337                         jt != jtEnd;
 338                         ++jt)
 339                 {
 340                         de=*jt;
 341                         assert(de);
 342                         //Debug.print("visted? "); Debug.println(de);
 343                         if (!de->isVisited()) {
 344                                 //Debug.print("not visited "); Debug.println(de);
 345                                 disconnectedRingcoord=de->getCoordinate();
 346                                 return true;
 347                         }
 348                 }
 349         }
 350         return false;
 351 }
 352
 353 } // namespace geos.operation.valid
 354 } // namespace geos.operation
 355 } // namespace geos