00001 /********************************************************************** 00002 * $Id: opPolygonize.h,v 1.7.2.1 2005/05/23 17:23:15 strk Exp $ 00003 * 00004 * GEOS - Geometry Engine Open Source 00005 * http://geos.refractions.net 00006 * 00007 * Copyright (C) 2001-2002 Vivid Solutions Inc. 00008 * 00009 * This is free software; you can redistribute and/or modify it under 00010 * the terms of the GNU Lesser General Public Licence as published 00011 * by the Free Software Foundation. 00012 * See the COPYING file for more information. 00013 * 00014 **********************************************************************/ 00015 00016 00017 #ifndef GEOS_OPPOLYGONIZE_H 00018 #define GEOS_OPPOLYGONIZE_H 00019 00020 #include <geos/platform.h> 00021 #include <geos/planargraph.h> 00022 #include <geos/geosAlgorithm.h> 00023 #include <geos/geom.h> 00024 #include <vector> 00025 00026 namespace geos { 00027 00028 //using namespace planargraph; 00029 00030 /* 00031 * An edge of a polygonization graph. 00032 * 00033 * @version 1.4 00034 */ 00035 class PolygonizeEdge: public planarEdge { 00036 private: 00037 const LineString *line; 00038 public: 00039 PolygonizeEdge(const LineString *newLine); 00040 const LineString* getLine(); 00041 }; 00042 00043 00044 /* 00045 * Represents a ring of PolygonizeDirectedEdge which form 00046 * a ring of a polygon. The ring may be either an outer shell or a hole. 00047 */ 00048 class polygonizeEdgeRing { 00049 private: 00050 const GeometryFactory *factory; 00051 static CGAlgorithms cga; 00052 vector<const planarDirectedEdge*> *deList; 00053 00054 // cache the following data for efficiency 00055 LinearRing *ring; 00056 CoordinateSequence *ringPts; 00057 vector<Geometry*> *holes; 00058 00059 /* 00060 * Computes the list of coordinates which are contained in this ring. 00061 * The coordinatea are computed once only and cached. 00062 * 00063 * @return an array of the Coordinate in this ring 00064 */ 00065 CoordinateSequence* getCoordinates(); 00066 00067 static void addEdge(const CoordinateSequence *coords, bool isForward, CoordinateSequence *coordList); 00068 00069 public: 00086 static polygonizeEdgeRing* findEdgeRingContaining(polygonizeEdgeRing *testEr, vector<polygonizeEdgeRing*> *shellList); 00087 00088 /* 00089 * \brief 00090 * Finds a point in a list of points which is not contained in 00091 * another list of points. 00092 * 00093 * @param testPts the CoordinateSequence to test 00094 * @param pts the CoordinateSequence to test the input points against 00095 * @return a Coordinate reference from <code>testPts</code> which is 00096 * not in <code>pts</code>, or <code>Coordinate::nullCoord</code> 00097 */ 00098 static const Coordinate& ptNotInList(const CoordinateSequence *testPts, const CoordinateSequence *pts); 00099 00100 /* 00101 * Tests whether a given point is in an array of points. 00102 * Uses a value-based test. 00103 * 00104 * @param pt a Coordinate for the test point 00105 * @param pts an array of Coordinate to test 00106 * @return <code>true</code> if the point is in the array 00107 */ 00108 static bool isInList(const Coordinate &pt, const CoordinateSequence *pts); 00109 polygonizeEdgeRing(const GeometryFactory *newFactory); 00110 ~polygonizeEdgeRing(); 00111 00112 /* 00113 * Adds a DirectedEdge which is known to form part of this ring. 00114 * @param de the DirectedEdge to add. Ownership to the caller. 00115 */ 00116 void add(const planarDirectedEdge *de); 00117 00118 /* 00119 * Tests whether this ring is a hole. 00120 * Due to the way the edges in the polyongization graph are linked, 00121 * a ring is a hole if it is oriented counter-clockwise. 00122 * @return <code>true</code> if this ring is a hole 00123 */ 00124 bool isHole(); 00125 00126 /* 00127 * Adds a hole to the polygon formed by this ring. 00128 * @param hole the LinearRing forming the hole. 00129 */ 00130 void addHole(LinearRing *hole); 00131 00132 /* 00133 * Computes the Polygon formed by this ring and any contained holes. 00134 * 00135 * @return the Polygon formed by this ring and its holes. 00136 */ 00137 Polygon* getPolygon(); 00138 00139 /* 00140 * Tests if the LinearRing ring formed by this edge ring 00141 * is topologically valid. 00142 */ 00143 bool isValid(); 00144 00145 /* 00146 * Gets the coordinates for this ring as a LineString. 00147 * Used to return the coordinates in this ring 00148 * as a valid geometry, when it has been detected that the ring 00149 * is topologically invalid. 00150 * @return a LineString containing the coordinates in this ring 00151 */ 00152 LineString* getLineString(); 00153 00154 /* 00155 * Returns this ring as a LinearRing, or null if an Exception 00156 * occurs while creating it (such as a topology problem). 00157 * Ownership of ring is retained by the object. 00158 * Details of problems are written to standard output. 00159 */ 00160 LinearRing* getRingInternal(); 00161 00162 /* 00163 * Returns this ring as a LinearRing taking ownership 00164 * of it. 00165 */ 00166 LinearRing* getRingOwnership(); 00167 }; 00168 00169 00170 /* 00171 * A DirectedEdge of a PolygonizeGraph, which represents 00172 * an edge of a polygon formed by the graph. 00173 * May be logically deleted from the graph by setting the 00174 * <code>marked</code> flag. 00175 */ 00176 class PolygonizeDirectedEdge: public planarDirectedEdge { 00177 private: 00178 polygonizeEdgeRing *edgeRing; 00179 PolygonizeDirectedEdge *next; 00180 long label; 00181 public: 00182 /* 00183 * \brief 00184 * Constructs a directed edge connecting the <code>from</code> node 00185 * to the <code>to</code> node. 00186 * 00187 * @param directionPt 00188 * specifies this DirectedEdge's direction (given by an imaginary 00189 * line from the <code>from</code> node to <code>directionPt</code>) 00190 * 00191 * @param edgeDirection 00192 * whether this DirectedEdge's direction is the same as or 00193 * opposite to that of the parent Edge (if any) 00194 */ 00195 PolygonizeDirectedEdge(planarNode *newFrom,planarNode *newTo, const Coordinate& newDirectionPt,bool nEdgeDirection); 00196 00197 /* 00198 * Returns the identifier attached to this directed edge. 00199 */ 00200 long getLabel() const; 00201 00202 /* 00203 * Attaches an identifier to this directed edge. 00204 */ 00205 void setLabel(long newLabel); 00206 00207 /* 00208 * Returns the next directed edge in the EdgeRing that this 00209 * directed edge is a member of. 00210 */ 00211 PolygonizeDirectedEdge* getNext() const; 00212 00213 /* 00214 * Sets the next directed edge in the EdgeRing that this 00215 * directed edge is a member of. 00216 */ 00217 void setNext(PolygonizeDirectedEdge *newNext); 00218 00219 /* 00220 * Returns the ring of directed edges that this directed edge is 00221 * a member of, or null if the ring has not been set. 00222 * @see #setRing(EdgeRing) 00223 */ 00224 bool isInRing() const; 00225 00226 /* 00227 * Sets the ring of directed edges that this directed edge is 00228 * a member of. 00229 */ 00230 void setRing(polygonizeEdgeRing *newEdgeRing); 00231 }; 00232 00233 00234 /* 00235 * Represents a planar graph of edges that can be used to compute a 00236 * polygonization, and implements the algorithms to compute the 00237 * EdgeRings formed by the graph. 00238 * 00239 * The marked flag on DirectedEdge is used to indicate that a directed edge 00240 * has be logically deleted from the graph. 00241 * 00242 */ 00243 class PolygonizeGraph: public planarPlanarGraph { 00244 public: 00245 /* 00246 * \brief 00247 * Deletes all edges at a node 00248 */ 00249 static void deleteAllEdges(planarNode *node); 00250 00251 /* 00252 * \brief 00253 * Create a new polygonization graph. 00254 */ 00255 PolygonizeGraph(const GeometryFactory *newFactory); 00256 00257 /* 00258 * \brief 00259 * Destroy a polygonization graph. 00260 */ 00261 ~PolygonizeGraph(); 00262 00263 /* 00264 * \brief 00265 * Add a LineString forming an edge of the polygon graph. 00266 * @param line the line to add 00267 */ 00268 void addEdge(const LineString *line); 00269 00270 /* 00271 * \brief 00272 * Computes the EdgeRings formed by the edges in this graph. 00273 * 00274 * @return a list of the EdgeRing found by the 00275 * polygonization process. 00276 */ 00277 vector<polygonizeEdgeRing*>* getEdgeRings(); 00278 00279 /* 00280 * \brief 00281 * Finds and removes all cut edges from the graph. 00282 * 00283 * @return a list of the LineString forming the removed cut edges 00284 */ 00285 vector<const LineString*>* deleteCutEdges(); 00286 00287 /* 00288 * Marks all edges from the graph which are "dangles". 00289 * Dangles are which are incident on a node with degree 1. 00290 * This process is recursive, since removing a dangling edge 00291 * may result in another edge becoming a dangle. 00292 * In order to handle large recursion depths efficiently, 00293 * an explicit recursion stack is used 00294 * 00295 * @return a List containing the LineStrings that formed dangles 00296 */ 00297 vector<const LineString*>* deleteDangles(); 00298 00299 private: 00300 static int getDegreeNonDeleted(planarNode *node); 00301 static int getDegree(planarNode *node, long label); 00302 const GeometryFactory *factory; 00303 planarNode* getNode(const Coordinate& pt); 00304 void computeNextCWEdges(); 00305 00306 /* 00307 * \brief 00308 * Convert the maximal edge rings found by the initial graph traversal 00309 * into the minimal edge rings required by JTS polygon topology rules. 00310 * 00311 * @param ringEdges 00312 * the list of start edges for the edgeRings to convert. 00313 */ 00314 void convertMaximalToMinimalEdgeRings(vector<PolygonizeDirectedEdge*> *ringEdges); 00315 00316 /* 00317 * \brief 00318 * Finds all nodes in a maximal edgering which are self-intersection 00319 * nodes 00320 * 00321 * @param startDE 00322 * @param label 00323 * @return the list of intersection nodes found, 00324 * or <code>null</code> if no intersection nodes were found. 00325 * Ownership of returned vector goes to caller. 00326 */ 00327 static vector<planarNode*>* findIntersectionNodes(PolygonizeDirectedEdge *startDE, long label); 00328 00329 /* 00330 * @param dirEdges a List of the DirectedEdges in the graph 00331 * @return a List of DirectedEdges, one for each edge ring found 00332 */ 00333 static vector<PolygonizeDirectedEdge*>* findLabeledEdgeRings(vector<planarDirectedEdge*> *dirEdges); 00334 00335 static void label(vector<planarDirectedEdge*> *dirEdges, long label); 00336 00337 static void computeNextCWEdges(planarNode *node); 00338 00346 static void computeNextCCWEdges(planarNode *node, long label); 00347 00357 static vector<planarDirectedEdge*>* findDirEdgesInRing(PolygonizeDirectedEdge *startDE); 00358 00359 polygonizeEdgeRing* findEdgeRing(PolygonizeDirectedEdge *startDE); 00360 00361 /* Tese are for memory management */ 00362 vector<planarEdge *>newEdges; 00363 vector<planarDirectedEdge *>newDirEdges; 00364 vector<planarNode *>newNodes; 00365 vector<polygonizeEdgeRing *>newEdgeRings; 00366 vector<CoordinateSequence *>newCoords; 00367 }; 00368 00369 /* 00370 * Polygonizes a set of Geometrys which contain linework that 00371 * represents the edges of a planar graph. 00372 * Any dimension of Geometry is handled - the constituent linework is extracted 00373 * to form the edges. 00374 * The edges must be correctly noded; that is, they must only meet 00375 * at their endpoints. The Polygonizer will still run on incorrectly noded input 00376 * but will not form polygons from incorrected noded edges. 00377 * <p> 00378 * The Polygonizer reports the follow kinds of errors: 00379 * <ul> 00380 * <li><b>Dangles</b> - edges which have one or both ends which are not incident on another edge endpoint 00381 * <li><b>Cut Edges</b> - edges which are connected at both ends but which do not form part of polygon 00382 * <li><b>Invalid Ring Lines</b> - edges which form rings which are invalid 00383 * (e.g. the component lines contain a self-intersection) 00384 * </ul> 00385 * 00386 */ 00387 class Polygonizer { 00388 private: 00392 class LineStringAdder: public GeometryComponentFilter { 00393 public: 00394 Polygonizer *pol; 00395 LineStringAdder(Polygonizer *p); 00396 void filter_rw(Geometry *g); 00397 void filter_ro(const Geometry *g){}; 00398 }; 00399 00400 // default factory 00401 LineStringAdder *lineStringAdder; 00402 00408 void add(LineString *line); 00412 void polygonize(); 00413 void findValidRings(vector<polygonizeEdgeRing*> *edgeRingList, vector<polygonizeEdgeRing*> *validEdgeRingList, vector<LineString*> *invalidRingList); 00414 void findShellsAndHoles(vector<polygonizeEdgeRing*> *edgeRingList); 00415 static void assignHolesToShells(vector<polygonizeEdgeRing*> *holeList,vector<polygonizeEdgeRing*> *shellList); 00416 static void assignHoleToShell(polygonizeEdgeRing *holeER,vector<polygonizeEdgeRing*> *shellList); 00417 protected: 00418 PolygonizeGraph *graph; 00419 00420 // initialize with empty collections, in case nothing is computed 00421 vector<const LineString*> *dangles; 00422 vector<const LineString*> *cutEdges; 00423 vector<LineString*> *invalidRingLines; 00424 00425 vector<polygonizeEdgeRing*> *holeList; 00426 vector<polygonizeEdgeRing*> *shellList; 00427 vector<Polygon*> *polyList; 00428 00429 public: 00430 00431 /* 00432 * Create a polygonizer with the same GeometryFactory 00433 * as the input Geometry 00434 */ 00435 Polygonizer(); 00436 00437 ~Polygonizer(); 00438 00439 /* 00440 * Add a collection of geometries to be polygonized. 00441 * May be called multiple times. 00442 * Any dimension of Geometry may be added; 00443 * the constituent linework will be extracted and used 00444 * 00445 * @param geomList a list of Geometry with linework to be polygonized 00446 */ 00447 void add(vector<Geometry*> *geomList); 00448 00457 void add(Geometry *g); 00458 00465 vector<Polygon*>* getPolygons(); 00466 00471 vector<const LineString*>* getDangles(); 00472 00473 00478 vector<const LineString*>* getCutEdges(); 00479 00480 /* 00481 * Get the list of lines forming invalid rings found during 00482 * polygonization. 00483 * Ownership is tranferred to caller, second call will return 00484 * NULL (unless polygonize is called again). 00485 * @return a collection of LineStrings which form 00486 * invalid rings 00487 */ 00488 vector<LineString*>* getInvalidRingLines(); 00489 00490 // This seems to be needed by GCC 2.95.4 00491 friend class Polygonizer::LineStringAdder; 00492 }; 00493 00494 } // namespace geos 00495 #endif 00496 00497 /********************************************************************** 00498 * $Log: opPolygonize.h,v $ 00499 * Revision 1.7.2.1 2005/05/23 17:23:15 strk 00500 * Commented out Polygonizer::LineStringAdder friendship 00501 * 00502 * Revision 1.7 2004/12/14 10:35:44 strk 00503 * Comments cleanup. PolygonizeGraph keeps track of generated CoordinateSequence 00504 * for delayed destruction. 00505 * 00506 * Revision 1.6 2004/12/13 13:54:42 strk 00507 * Added a not about gcc 2.95.4 required friendship 00508 * 00509 * Revision 1.5 2004/10/19 19:51:14 strk 00510 * Fixed many leaks and bugs in Polygonizer. 00511 * Output still bogus. 00512 * 00513 * Revision 1.4 2004/10/13 10:03:02 strk 00514 * Added missing linemerge and polygonize operation. 00515 * Bug fixes and leaks removal from the newly added modules and 00516 * planargraph (used by them). 00517 * Some comments and indentation changes. 00518 * 00519 * Revision 1.3 2004/07/19 13:19:31 strk 00520 * Documentation fixes 00521 * 00522 * Revision 1.2 2004/07/08 19:34:49 strk 00523 * Mirrored JTS interface of CoordinateSequence, factory and 00524 * default implementations. 00525 * Added DefaultCoordinateSequenceFactory::instance() function. 00526 * 00527 * Revision 1.1 2004/07/02 13:20:42 strk 00528 * Header files moved under geos/ dir. 00529 * 00530 * Revision 1.1 2004/04/08 04:53:56 ybychkov 00531 * "operation/polygonize" ported from JTS 1.4 00532 * 00533 * 00534 **********************************************************************/