00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
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
00047
00048
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
00061
00062
00063
00064 class polygonizeEdgeRing {
00065 private:
00066 GeometryFactory *factory;
00067 static CGAlgorithms *cga;
00068 vector<planarDirectedEdge*> *deList;
00069
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
00165
00166
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
00221
00222
00223
00224
00225
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
00313
00314
00315
00316
00317
00318
00319
00320
00321
00322
00323
00324
00325
00326
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
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
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