00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017 #ifndef GEOS_OPOVERLAY_H
00018 #define GEOS_OPOVERLAY_H
00019
00020 #include <memory>
00021 #include <string>
00022 #include <vector>
00023 #include <set>
00024 #include <map>
00025 #include <geos/platform.h>
00026 #include <geos/operation.h>
00027 #include <geos/geomgraph.h>
00028 #include <geos/geosAlgorithm.h>
00029
00030 using namespace std;
00031
00032 namespace geos {
00033
00034 class ElevationMatrixCell {
00035 public:
00036 ElevationMatrixCell();
00037 ~ElevationMatrixCell();
00038 void add(const Coordinate &c);
00039 void add(double z);
00040 double getAvg(void) const;
00041 double getTotal(void) const;
00042 string print() const;
00043 private:
00044 set<double>zvals;
00045 double ztot;
00046 };
00047
00048
00049
00050 class ElevationMatrix {
00051 public:
00052 ElevationMatrix(const Envelope &extent, unsigned int rows,
00053 unsigned int cols);
00054 ~ElevationMatrix();
00055 void add(const Geometry *geom);
00056 void elevate(Geometry *geom) const;
00057
00058 double getAvgElevation() const;
00059 ElevationMatrixCell &getCell(const Coordinate &c);
00060 const ElevationMatrixCell &getCell(const Coordinate &c) const;
00061 string print() const;
00062 private:
00063 void add(const CoordinateSequence *cs);
00064 void add(const Coordinate &c);
00065 Envelope env;
00066 unsigned int cols;
00067 unsigned int rows;
00068 double cellwidth;
00069 double cellheight;
00070 mutable bool avgElevationComputed;
00071 mutable double avgElevation;
00072 vector<ElevationMatrixCell>cells;
00073 };
00074
00075 class ElevationMatrixFilter: public CoordinateFilter
00076 {
00077 public:
00078 ElevationMatrixFilter(const ElevationMatrix *em);
00079 ~ElevationMatrixFilter();
00080 void filter_rw(Coordinate *c);
00081 void filter_ro(const Coordinate *c) {};
00082 private:
00083 const ElevationMatrix *em;
00084 double avgElevation;
00085 };
00086
00087
00088
00089
00090
00091 class OverlayOp: public GeometryGraphOperation {
00092
00093 public:
00094
00095
00096
00097
00098
00099
00100 enum {
00101 INTERSECTION=1,
00102 UNION,
00103 DIFFERENCE,
00104 SYMDIFFERENCE
00105 };
00106
00107 static Geometry* overlayOp(const Geometry *geom0, const Geometry *geom1,int opCode);
00108
00109 static bool isResultOfOp(Label *label,int opCode);
00110
00111
00112
00113
00114
00115
00116 static bool isResultOfOp(int loc0,int loc1,int opCode);
00117
00118 OverlayOp(const Geometry *g0, const Geometry *g1);
00119
00120 virtual ~OverlayOp();
00121
00122 Geometry* getResultGeometry(int funcCode);
00123
00124
00125 PlanarGraph* getGraph();
00126
00127
00128
00129
00130
00131
00132
00133
00134 bool isCoveredByLA(const Coordinate& coord);
00135
00136
00137
00138
00139
00140
00141
00142 bool isCoveredByA(const Coordinate& coord);
00143
00144
00145
00146
00147
00148
00149 protected:
00150
00151
00152
00153
00154
00155
00156
00157
00158 void insertUniqueEdge(Edge *e);
00159
00160 private:
00161 PointLocator *ptLocator;
00162 const GeometryFactory *geomFact;
00163 Geometry *resultGeom;
00164 PlanarGraph *graph;
00165 EdgeList *edgeList;
00166 vector<Polygon*> *resultPolyList;
00167 vector<LineString*> *resultLineList;
00168 vector<Point*> *resultPointList;
00169 void computeOverlay(int opCode);
00170 void insertUniqueEdges(vector<Edge*> *edges);
00171
00172
00173
00174
00175
00176
00177
00178
00179
00180
00181
00182
00183
00184
00185
00186
00187
00188
00189
00190 void computeLabelsFromDepths();
00191
00192
00193
00194
00195
00196 void replaceCollapsedEdges();
00197
00198
00199
00200
00201
00202
00203
00204
00205
00206
00207 void copyPoints(int argIndex);
00208
00209
00210
00211
00212
00213
00214
00215
00216 void computeLabelling();
00217
00218
00219
00220
00221
00222
00223
00224
00225 void mergeSymLabels();
00226
00227 void updateNodeLabelling();
00228
00229
00230
00231
00232
00233
00234
00235
00236
00237
00238
00239
00240
00241
00242
00243
00244
00245 void labelIncompleteNodes();
00246
00247
00248
00249
00250 void labelIncompleteNode(Node *n,int targetIndex);
00251
00252
00253
00254
00255
00256
00257
00258
00259
00260
00261
00262 void findResultAreaEdges(int opCode);
00263
00264
00265
00266
00267
00268 void cancelDuplicateResultEdges();
00269
00270 bool isCovered(const Coordinate& coord,vector<Geometry*> *geomList);
00271 bool isCovered(const Coordinate& coord,vector<Polygon*> *geomList);
00272 bool isCovered(const Coordinate& coord,vector<LineString*> *geomList);
00273
00274
00275
00276
00277
00278 Geometry* computeGeometry(vector<Point*> *nResultPointList,
00279 vector<LineString*> *nResultLineList,
00280 vector<Polygon*> *nResultPolyList);
00281
00282
00283 vector<Edge *>dupEdges;
00284
00285
00286
00287
00288
00289 int OverlayOp::mergeZ(Node *n, const Polygon *poly) const;
00290
00291
00292
00293
00294
00295
00296 int OverlayOp::mergeZ(Node *n, const LineString *line) const;
00297
00298
00299
00300
00301 double avgz[2];
00302 bool avgzcomputed[2];
00303
00304 double getAverageZ(int targetIndex);
00305 static double getAverageZ(const Polygon *poly);
00306
00307 ElevationMatrix *elevationMatrix;
00308
00309 };
00310
00311
00312
00313
00314
00315
00316
00317
00318 class MinimalEdgeRing: public EdgeRing {
00319 public:
00320 MinimalEdgeRing(DirectedEdge *start, const GeometryFactory *geometryFactory,CGAlgorithms *cga);
00321 virtual ~MinimalEdgeRing();
00322 DirectedEdge* getNext(DirectedEdge *de);
00323 void setEdgeRing(DirectedEdge *de,EdgeRing *er);
00324 };
00325
00326
00327
00328
00329
00330
00331
00332
00333
00334
00335
00336
00337
00338
00339
00340
00341
00342
00343
00344 class MaximalEdgeRing: public EdgeRing {
00345 public:
00346 MaximalEdgeRing(DirectedEdge *start, const GeometryFactory *geometryFactory, CGAlgorithms *cga);
00347 virtual ~MaximalEdgeRing();
00348 DirectedEdge* getNext(DirectedEdge *de);
00349 void setEdgeRing(DirectedEdge* de,EdgeRing* er);
00350 vector<MinimalEdgeRing*>* buildMinimalRings();
00351 void linkDirectedEdgesForMinimalEdgeRings();
00352 };
00353
00354
00355
00356
00357 class PointBuilder {
00358 private:
00359 OverlayOp *op;
00360 const GeometryFactory *geometryFactory;
00361 PointLocator *ptLocator;
00362 vector<Node*>* collectNodes(int opCode);
00370 vector<Point*>* simplifyPoints(vector<Node*>* resultNodeList);
00371 public:
00372 PointBuilder(OverlayOp *newOp, const GeometryFactory *newGeometryFactory, PointLocator *newPtLocator);
00376 vector<Point*>* build(int opCode);
00377 };
00378
00379
00380
00381
00382
00383
00384 class LineBuilder {
00385 public:
00386 LineBuilder(OverlayOp *newOp, const GeometryFactory *newGeometryFactory, PointLocator *newPtLocator);
00387 ~LineBuilder();
00391 vector<LineString*>* build(int opCode);
00399 void collectLineEdge(DirectedEdge *de,int opCode,vector<Edge*>* edges);
00410 void collectBoundaryTouchEdge(DirectedEdge *de,int opCode,vector<Edge*>* edges);
00411 private:
00412 OverlayOp *op;
00413 const GeometryFactory *geometryFactory;
00414 PointLocator *ptLocator;
00415 vector<Edge*>* lineEdgesList;
00416 vector<LineString*>* resultLineList;
00417 void findCoveredLineEdges();
00418 void collectLines(int opCode);
00419 void buildLines(int opCode);
00420 void labelIsolatedLines(vector<Edge*> *edgesList);
00424 void labelIsolatedLine(Edge *e,int targetIndex);
00425
00426
00427
00428
00429
00430
00431
00432 void LineBuilder::propagateZ(CoordinateSequence *cs);
00433 };
00434
00435
00436
00437
00438
00439
00440
00441 class PolygonBuilder {
00442 public:
00443 PolygonBuilder(const GeometryFactory *newGeometryFactory, CGAlgorithms *newCga);
00444 ~PolygonBuilder();
00450 void add(PlanarGraph *graph);
00456 void add(vector<DirectedEdge*> *dirEdges,vector<Node*> *nodes);
00457 vector<Geometry*>* getPolygons();
00458 bool containsPoint(Coordinate& p);
00459 private:
00460 const GeometryFactory *geometryFactory;
00461 CGAlgorithms *cga;
00462
00463
00464 vector<EdgeRing*> *shellList;
00468 vector<MaximalEdgeRing*>* buildMaximalEdgeRings(vector<DirectedEdge*> *dirEdges);
00469 vector<MaximalEdgeRing*>* buildMinimalEdgeRings(vector<MaximalEdgeRing*> *maxEdgeRings,
00470 vector<EdgeRing*> *newShellList,
00471 vector<EdgeRing*> *freeHoleList);
00482 EdgeRing* findShell(vector<MinimalEdgeRing*>* minEdgeRings);
00494 void placePolygonHoles(EdgeRing *shell,vector<MinimalEdgeRing*> *minEdgeRings);
00502 void sortShellsAndHoles(vector<MaximalEdgeRing*> *edgeRings,
00503 vector<EdgeRing*> *newShellList,
00504 vector<EdgeRing*> *freeHoleList);
00516 void placeFreeHoles(vector<EdgeRing*>* newShellList, vector<EdgeRing*> *freeHoleList);
00531 EdgeRing* findEdgeRingContaining(EdgeRing *testEr,vector<EdgeRing*> *newShellList);
00532 vector<Geometry*>* computePolygons(vector<EdgeRing*> *newShellList);
00538 };
00539
00540
00541
00542
00543
00544
00545
00546 class OverlayNodeFactory: public NodeFactory {
00547 public:
00548
00549 Node* createNode(Coordinate coord);
00550 };
00551
00552
00553
00554
00555
00556
00557
00558 class EdgeSetNoder {
00559 private:
00560 LineIntersector *li;
00561 vector<Edge*>* inputEdges;
00562 public:
00563 EdgeSetNoder(LineIntersector *newLi);
00564 ~EdgeSetNoder();
00565 void addEdges(vector<Edge*> *edges);
00566 vector<Edge*>* getNodedEdges();
00567 };
00568
00569
00570 }
00571
00572 #endif
00573
00574
00575
00576
00577
00578
00579
00580
00581
00582
00583
00584
00585
00586
00587
00588
00589
00590
00591
00592
00593
00594
00595
00596
00597
00598
00599
00600
00601
00602
00603
00604
00605
00606
00607
00608
00609
00610
00611
00612
00613
00614
00615
00616
00617
00618
00619
00620
00621
00622
00623
00624
00625
00626
00627
00628
00629
00630
00631
00632
00633
00634
00635
00636
00637