src/operation/polygonize/Polygonizer.cpp

   1 /**********************************************************************
   2  *
   3  * GEOS - Geometry Engine Open Source
   4  * http://geos.osgeo.org
   5  *
   6  * Copyright (C) 2010 Sandro Santilli <strk@keybit.net>
   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/polygonize/Polygonizer.java rev. 1.6 (JTS-1.10)
  18  *
  19  **********************************************************************/
  20
  21 #include <geos/operation/polygonize/Polygonizer.h>
  22 #include <geos/operation/polygonize/PolygonizeGraph.h>
  23 #include <geos/operation/polygonize/EdgeRing.h>
  24 #include <geos/geom/LineString.h>
  25 #include <geos/geom/Geometry.h>
  26 #include <geos/geom/Polygon.h>
  27 // std
  28 #include <vector>
  29
  30 #ifdef _MSC_VER
  31 #pragma warning(disable:4355)
  32 #endif
  33
  34 #ifndef GEOS_DEBUG
  35 #define GEOS_DEBUG 0
  36 #endif
  37
  38 using namespace std;
  39 using namespace geos::geom;
  40
  41 namespace geos {
  42 namespace operation { // geos.operation
  43 namespace polygonize { // geos.operation.polygonize
  44
  45 Polygonizer::LineStringAdder::LineStringAdder(Polygonizer *p):
  46         pol(p)
  47 {
  48 }
  49
  50 void
  51 Polygonizer::LineStringAdder::filter_ro(const Geometry *g)
  52 {
  53         const LineString *ls = dynamic_cast<const LineString *>(g);
  54         if ( ls ) pol->add(ls);
  55 }
  56
  57
  58 /*
  59  * Create a polygonizer with the same GeometryFactory
  60  * as the input Geometry
  61  */
  62 Polygonizer::Polygonizer():
  63         lineStringAdder(this),
  64         graph(NULL),
  65         dangles(),
  66         cutEdges(),
  67         invalidRingLines(),
  68         holeList(),
  69         shellList(),
  70         polyList(NULL)
  71 {
  72 }
  73
  74 Polygonizer::~Polygonizer()
  75 {
  76         delete graph;
  77
  78         for (unsigned int i=0, n=invalidRingLines.size(); i<n; ++i)
  79                 delete invalidRingLines[i];
  80
  81         if ( polyList )
  82         {
  83                 for (unsigned int i=0, n=polyList->size(); i<n; ++i)
  84                         delete (*polyList)[i];
  85                 delete polyList;
  86         }
  87 }
  88
  89 /*
  90  * Add a collection of geometries to be polygonized.
  91  * May be called multiple times.
  92  * Any dimension of Geometry may be added;
  93  * the constituent linework will be extracted and used
  94  *
  95  * @param geomList a list of {@link Geometry}s with linework to be polygonized
  96  */
  97 void
  98 Polygonizer::add(vector<Geometry*> *geomList)
  99 {
 100         for(unsigned int i=0, n=geomList->size(); i<n; ++i)
 101         {
 102                 const Geometry *geometry=(*geomList)[i];
 103                 add(geometry);
 104         }
 105 }
 106
 107 /*
 108  * Add a collection of geometries to be polygonized.
 109  * May be called multiple times.
 110  * Any dimension of Geometry may be added;
 111  * the constituent linework will be extracted and used
 112  *
 113  * @param geomList a list of {@link Geometry}s with linework to be polygonized
 114  */
 115 void
 116 Polygonizer::add(vector<const Geometry*> *geomList)
 117 {
 118         for(unsigned int i=0, n=geomList->size(); i<n; ++i)
 119         {
 120                 const Geometry *geometry=(*geomList)[i];
 121                 add(geometry);
 122         }
 123 }
 124
 125 /*
 126  * Add a geometry to the linework to be polygonized.
 127  * May be called multiple times.
 128  * Any dimension of Geometry may be added;
 129  * the constituent linework will be extracted and used
 130  *
 131  * @param g a Geometry with linework to be polygonized
 132  */
 133 void
 134 Polygonizer::add(Geometry *g)
 135 {
 136         g->apply_ro(&lineStringAdder);
 137 }
 138
 139 /*
 140  * Add a geometry to the linework to be polygonized.
 141  * May be called multiple times.
 142  * Any dimension of Geometry may be added;
 143  * the constituent linework will be extracted and used
 144  *
 145  * @param g a Geometry with linework to be polygonized
 146  */
 147 void
 148 Polygonizer::add(const Geometry *g)
 149 {
 150         g->apply_ro(&lineStringAdder);
 151 }
 152
 153 /*
 154  * Add a linestring to the graph of polygon edges.
 155  *
 156  * @param line the LineString to add
 157  */
 158 void
 159 Polygonizer::add(const LineString *line)
 160 {
 161         // create a new graph using the factory from the input Geometry
 162         if (graph==NULL)
 163                 graph=new PolygonizeGraph(line->getFactory());
 164         graph->addEdge(line);
 165 }
 166
 167 /*
 168  * Gets the list of polygons formed by the polygonization.
 169  * @return a collection of Polygons
 170  */
 171 vector<Polygon*>*
 172 Polygonizer::getPolygons()
 173 {
 174         polygonize();
 175         vector<Polygon *> *ret = polyList;
 176         polyList = NULL;
 177         return ret;
 178 }
 179
 180 /* public */
 181 const vector<const LineString*>&
 182 Polygonizer::getDangles()
 183 {
 184         polygonize();
 185         return dangles;
 186 }
 187
 188 /* public */
 189 const vector<const LineString*>&
 190 Polygonizer::getCutEdges()
 191 {
 192         polygonize();
 193         return cutEdges;
 194 }
 195
 196 /* public */
 197 const vector<LineString*>&
 198 Polygonizer::getInvalidRingLines()
 199 {
 200         polygonize();
 201         return invalidRingLines;
 202 }
 203
 204 /* public */
 205 void
 206 Polygonizer::polygonize()
 207 {
 208         // check if already computed
 209         if (polyList!=NULL) return;
 210
 211         polyList=new vector<Polygon*>();
 212
 213         // if no geometries were supplied it's possible graph could be null
 214         if (graph==NULL) return;
 215
 216         graph->deleteDangles(dangles);
 217
 218         graph->deleteCutEdges(cutEdges);
 219
 220         vector<EdgeRing*> edgeRingList;
 221         graph->getEdgeRings(edgeRingList);
 222 #if GEOS_DEBUG
 223         cerr<<"Polygonizer::polygonize(): "<<edgeRingList.size()<<" edgeRings in graph"<<endl;
 224 #endif
 225         vector<EdgeRing*> validEdgeRingList;
 226         invalidRingLines.clear(); /* what if it was populated already ? we should clean ! */
 227         findValidRings(edgeRingList, validEdgeRingList, invalidRingLines);
 228 #if GEOS_DEBUG
 229         cerr<<"                           "<<validEdgeRingList.size()<<" valid"<<endl;
 230         cerr<<"                           "<<invalidRingLines.size()<<" invalid"<<endl;
 231 #endif
 232
 233         findShellsAndHoles(validEdgeRingList);
 234 #if GEOS_DEBUG
 235         cerr<<"                           "<<holeList.size()<<" holes"<<endl;
 236         cerr<<"                           "<<shellList.size()<<" shells"<<endl;
 237 #endif
 238
 239         assignHolesToShells(holeList, shellList);
 240
 241         for (unsigned int i=0, n=shellList.size(); i<n; ++i)
 242         {
 243                 EdgeRing *er=shellList[i];
 244                 polyList->push_back(er->getPolygon());
 245         }
 246 }
 247
 248 /* private */
 249 void
 250 Polygonizer::findValidRings(const vector<EdgeRing*>& edgeRingList,
 251         vector<EdgeRing*>& validEdgeRingList,
 252         vector<LineString*>& invalidRingList)
 253 {
 254         typedef vector<EdgeRing*> EdgeRingList;
 255
 256         for (EdgeRingList::size_type i=0, n=edgeRingList.size(); i<n; ++i)
 257         {
 258                 EdgeRing *er = edgeRingList[i];
 259                 if (er->isValid())
 260                 {
 261                         validEdgeRingList.push_back(er);
 262                 }
 263                 else
 264                 {
 265                         // NOTE: polygonize::EdgeRing::getLineString
 266                         // returned LineString ownership is transferred.
 267                         invalidRingList.push_back(er->getLineString());
 268                 }
 269         }
 270 }
 271
 272 /* private */
 273 void
 274 Polygonizer::findShellsAndHoles(const vector<EdgeRing*>& edgeRingList)
 275 {
 276         holeList.clear();
 277         shellList.clear();
 278         for (unsigned int i=0, n=edgeRingList.size(); i<n; ++i)
 279         {
 280                 EdgeRing *er=edgeRingList[i];
 281                 if (er->isHole())
 282                         holeList.push_back(er);
 283                 else
 284                         shellList.push_back(er);
 285         }
 286 }
 287
 288 /* private */
 289 void
 290 Polygonizer::assignHolesToShells(const vector<EdgeRing*>& holeList, vector<EdgeRing*>& shellList)
 291 {
 292         for (unsigned int i=0, n=holeList.size(); i<n; ++i)
 293         {
 294                 EdgeRing *holeER=holeList[i];
 295                 assignHoleToShell(holeER, shellList);
 296         }
 297 }
 298
 299 /* private */
 300 void
 301 Polygonizer::assignHoleToShell(EdgeRing *holeER,
 302                 vector<EdgeRing*>& shellList)
 303 {
 304         EdgeRing *shell = EdgeRing::findEdgeRingContaining(holeER, &shellList);
 305
 306         if (shell!=NULL)
 307                 shell->addHole(holeER->getRingOwnership());
 308 }
 309
 310
 311 } // namespace geos.operation.polygonize
 312 } // namespace geos.operation
 313 } // namespace geos
 314
 315 /**********************************************************************
 316  * $Log$
 317  * Revision 1.13  2006/03/22 11:19:06  strk
 318  * opPolygonize.h headers split.
 319  *
 320  * Revision 1.12  2006/03/03 10:46:22  strk
 321  * Removed 'using namespace' from headers, added missing headers in .cpp files, removed useless includes in headers (bug#46)
 322  *
 323  * Revision 1.11  2006/03/02 12:12:01  strk
 324  * Renamed DEBUG macros to GEOS_DEBUG, all wrapped in #ifndef block to allow global override (bug#43)
 325  *
 326  * Revision 1.10  2006/02/19 19:46:49  strk
 327  * Packages <-> namespaces mapping for most GEOS internal code (uncomplete, but working). Dir-level libs for index/ subdirs.
 328  *
 329  * Revision 1.9  2005/12/09 10:32:28  strk
 330  * Cleaned up debugging line left over from previous commit
 331  *
 332  * Revision 1.8  2005/12/09 10:03:46  strk
 333  * Fixed a bug making PolygonizeGraph choking on invalid LineStrings.
 334  * Minor optimizations in Polygonizer loops.
 335  *
 336  * Revision 1.7  2005/06/17 15:08:06  strk
 337  * Polygonizer segfault fix
 338  *
 339  * Revision 1.6  2004/12/08 13:54:44  strk
 340  * gcc warnings checked and fixed, general cleanups.
 341  *
 342  * Revision 1.5  2004/10/27 13:57:07  strk
 343  * Added some debugging lines (disabled by default)
 344  *
 345  * Revision 1.4  2004/10/26 16:09:21  strk
 346  * Some more intentation and envelope equality check fix.
 347  *
 348  * Revision 1.3  2004/10/19 19:51:14  strk
 349  * Fixed many leaks and bugs in Polygonizer.
 350  * Output still bogus.
 351  *
 352  * Revision 1.2  2004/07/02 13:28:29  strk
 353  * Fixed all #include lines to reflect headers layout change.
 354  * Added client application build tips in README.
 355  *
 356  * Revision 1.1  2004/04/08 04:53:56  ybychkov
 357  * "operation/polygonize" ported from JTS 1.4
 358  *
 359  *
 360  **********************************************************************/