Main Page | Namespace List | Class Hierarchy | Class List | File List | Namespace Members | Class Members | Related Pages

opPolygonize.h

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  **********************************************************************/

Generated on Sun Aug 5 23:04:38 2007 for GEOS by  doxygen 1.3.9.1