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.3 2004/07/19 13:19:31 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  * $Log: opPolygonize.h,v $
00016  * Revision 1.3  2004/07/19 13:19:31  strk
00017  * Documentation fixes
00018  *
00019  * Revision 1.2  2004/07/08 19:34:49  strk
00020  * Mirrored JTS interface of CoordinateSequence, factory and
00021  * default implementations.
00022  * Added DefaultCoordinateSequenceFactory::instance() function.
00023  *
00024  * Revision 1.1  2004/07/02 13:20:42  strk
00025  * Header files moved under geos/ dir.
00026  *
00027  * Revision 1.1  2004/04/08 04:53:56  ybychkov
00028  * "operation/polygonize" ported from JTS 1.4
00029  *
00030  *
00031  **********************************************************************/
00032 
00033 
00034 #ifndef GEOS_OPPOLYGONIZE_H
00035 #define GEOS_OPPOLYGONIZE_H
00036 
00037 #include <geos/platform.h>
00038 #include <geos/planargraph.h>
00039 #include <geos/geosAlgorithm.h>
00040 #include <geos/geom.h>
00041 #include <vector>
00042 
00043 namespace geos {
00044 
00045 /*
00046 * An edge of a polygonization graph.
00047 *
00048 * @version 1.4
00049 */
00050 class PolygonizeEdge: public planarEdge {
00051 private:
00052         LineString *line;
00053 public:
00054         PolygonizeEdge(LineString *newLine);
00055         LineString* getLine();
00056 };
00057 
00058 
00059 /*
00060  * Represents a ring of {@link PolygonizeDirectedEdge}s which form
00061  * a ring of a polygon.  The ring may be either an outer shell or a hole.
00062  *
00063  */
00064 class polygonizeEdgeRing {
00065 private:
00066         GeometryFactory *factory;
00067         static CGAlgorithms *cga;
00068         vector<planarDirectedEdge*> *deList;
00069         // cache the following data for efficiency
00070         LinearRing *ring;
00071         CoordinateSequence *ringPts;
00072         vector<LinearRing*> *holes;
00079         CoordinateSequence* getCoordinates();
00080         static void addEdge(CoordinateSequence *coords, bool isForward, CoordinateSequence *coordList);
00081 
00082 public:
00097         static polygonizeEdgeRing* findEdgeRingContaining(polygonizeEdgeRing *testEr, vector<polygonizeEdgeRing*> *shellList);
00098 
00106         static Coordinate& ptNotInList(CoordinateSequence *testPts, CoordinateSequence *pts);
00115         static bool isInList(Coordinate &pt, CoordinateSequence *pts);
00116         polygonizeEdgeRing(GeometryFactory *newFactory);
00117         ~polygonizeEdgeRing();
00122         void add(planarDirectedEdge *de);
00129         bool isHole();
00134         void addHole(LinearRing *hole);
00140         Polygon* getPolygon();
00145         bool isValid();
00153         LineString* getLineString();
00159         LinearRing* getRing();
00160 };
00161 
00162 
00163 /*
00164  * A {@link DirectedEdge} of a {@link PolygonizeGraph}, which represents
00165  * an edge of a polygon formed by the graph.
00166  * May be logically deleted from the graph by setting the <code>marked</code> flag.
00167  *
00168  */
00169 class PolygonizeDirectedEdge: public planarDirectedEdge {
00170 private:
00171         polygonizeEdgeRing *edgeRing;
00172         PolygonizeDirectedEdge *next;
00173         long label;
00174 public:
00186         PolygonizeDirectedEdge(planarNode *newFrom,planarNode *newTo,Coordinate& newDirectionPt,bool nEdgeDirection);
00190         long getLabel();
00194         void setLabel(long newLabel);
00199         PolygonizeDirectedEdge* getNext();
00204         void setNext(PolygonizeDirectedEdge *newNext);
00210         bool isInRing();
00215         void setRing(polygonizeEdgeRing *newEdgeRing);
00216 };
00217 
00218 
00219 /*
00220  * Represents a planar graph of edges that can be used to compute a
00221  * polygonization, and implements the algorithms to compute the
00222  * {@link EdgeRings} formed by the graph.
00223  * <p>
00224  * The marked flag on {@link DirectedEdge}s is used to indicate that a directed edge
00225  * has be logically deleted from the graph.
00226  *
00227  */
00228 class PolygonizeGraph: public planarPlanarGraph {
00229 public:
00233         static void deleteAllEdges(planarNode *node);
00237         PolygonizeGraph(GeometryFactory *newFactory);
00242         void addEdge(LineString *line);
00247         vector<polygonizeEdgeRing*>* getEdgeRings();
00252         vector<LineString*>* deleteCutEdges();
00263         vector<LineString*>* deleteDangles();
00264 private:
00265         static int getDegreeNonDeleted(planarNode *node);
00266         static int getDegree(planarNode *node, long label);
00267         GeometryFactory *factory;
00268         planarNode* getNode(Coordinate& pt);
00269         void computeNextCWEdges();
00276         void convertMaximalToMinimalEdgeRings(vector<PolygonizeDirectedEdge*> *ringEdges);
00284         static vector<planarNode*>* findIntersectionNodes(PolygonizeDirectedEdge *startDE, long label);
00290         static vector<PolygonizeDirectedEdge*>* findLabeledEdgeRings(vector<planarDirectedEdge*> *dirEdges);
00291         static void label(vector<planarDirectedEdge*> *dirEdges, long label);
00292         static void computeNextCWEdges(planarNode *node);
00298         static void computeNextCCWEdges(planarNode *node, long label);
00307         static vector<planarDirectedEdge*>* findDirEdgesInRing(PolygonizeDirectedEdge *startDE);
00308         polygonizeEdgeRing* findEdgeRing(PolygonizeDirectedEdge *startDE);
00309 };
00310 
00311 /*
00312  * Polygonizes a set of Geometrys which contain linework that
00313  * represents the edges of a planar graph.
00314  * Any dimension of Geometry is handled - the constituent linework is extracted
00315  * to form the edges.
00316  * The edges must be correctly noded; that is, they must only meet
00317  * at their endpoints.  The Polygonizer will still run on incorrectly noded input
00318  * but will not form polygons from incorrected noded edges.
00319  * <p>
00320  * The Polygonizer reports the follow kinds of errors:
00321  * <ul>
00322  * <li><b>Dangles</b> - edges which have one or both ends which are not incident on another edge endpoint
00323  * <li><b>Cut Edges</b> - edges which are connected at both ends but which do not form part of polygon
00324  * <li><b>Invalid Ring Lines</b> - edges which form rings which are invalid
00325  * (e.g. the component lines contain a self-intersection)
00326  * </ul>
00327  *
00328  */
00329 class Polygonizer {
00330 private:
00334         class LineStringAdder: public GeometryComponentFilter {
00335         public:
00336                 Polygonizer *pol;
00337                 LineStringAdder(Polygonizer *p);
00338                 void filter_rw(Geometry *g);
00339                 void filter_ro(const Geometry *g){};
00340         };
00341 
00342         // default factory
00343         LineStringAdder *lineStringAdder;
00349         void add(LineString *line);
00353         void polygonize();
00354         void findValidRings(vector<polygonizeEdgeRing*> *edgeRingList, vector<polygonizeEdgeRing*> *validEdgeRingList,vector<LineString*> *invalidRingList);
00355         void findShellsAndHoles(vector<polygonizeEdgeRing*> *edgeRingList);
00356         static void assignHolesToShells(vector<polygonizeEdgeRing*> *holeList,vector<polygonizeEdgeRing*> *shellList);
00357         static void assignHoleToShell(polygonizeEdgeRing *holeER,vector<polygonizeEdgeRing*> *shellList);
00358 protected:
00359         PolygonizeGraph *graph;
00360         // initialize with empty collections, in case nothing is computed
00361         vector<LineString*> *dangles;
00362         vector<LineString*> *cutEdges;
00363         vector<LineString*> *invalidRingLines;
00364 
00365         vector<polygonizeEdgeRing*> *holeList;
00366         vector<polygonizeEdgeRing*> *shellList;
00367         vector<Polygon*> *polyList;
00368 public:
00373         Polygonizer();
00374         ~Polygonizer();
00383         void add(vector<Geometry*> *geomList);
00392         void add(Geometry *g);
00397         vector<Polygon*>* getPolygons();
00402         vector<LineString*>* getDangles();
00407         vector<LineString*>* getCutEdges();
00412         vector<LineString*>* getInvalidRingLines();
00413 };
00414 }
00415 #endif

Generated on Fri Nov 26 21:30:45 2004 for GEOS by  doxygen 1.3.9.1