00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016 #ifndef GEOS_OPBUFFER_H
00017 #define GEOS_OPBUFFER_H
00018
00019 #include <memory>
00020 #include <geos/platform.h>
00021 #include <geos/operation.h>
00022 #include <geos/opOverlay.h>
00023 #include <geos/geomgraph.h>
00024 #include <geos/noding.h>
00025 #include <geos/geom.h>
00026 #include <vector>
00027
00028 namespace geos {
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038 class RightmostEdgeFinder {
00039 private:
00040 CGAlgorithms* cga;
00041 int minIndex;
00042 Coordinate minCoord;
00043 DirectedEdge *minDe;
00044 DirectedEdge *orientedDe;
00045 void findRightmostEdgeAtNode();
00046 void findRightmostEdgeAtVertex();
00047 void checkForRightmostCoordinate(DirectedEdge *de);
00048 int getRightmostSide(DirectedEdge *de, int index);
00049 int getRightmostSideOfSegment(DirectedEdge *de, int i);
00050
00051 public:
00052
00053
00054
00055
00056
00057
00058 RightmostEdgeFinder(CGAlgorithms *newCga);
00059 DirectedEdge* getEdge();
00060 Coordinate& getCoordinate();
00061 void findEdge(vector<DirectedEdge*>* dirEdgeList);
00062 };
00063
00064
00065
00066
00067
00068
00069
00070
00071
00072
00073 class BufferSubgraph {
00074 private:
00075 RightmostEdgeFinder *finder;
00076
00077 vector<DirectedEdge*> *dirEdgeList;
00078
00079 vector<Node*> *nodes;
00080
00081 Coordinate *rightMostCoord;
00082
00083 Envelope *env;
00084
00085
00086
00087
00088
00089
00090
00091 void addReachable(Node *startNode);
00092
00093
00094
00095
00096
00097
00098 void add(Node *node,vector<Node*> *nodeStack);
00099
00100 void clearVisitedEdges();
00101
00102
00103
00104
00105
00106
00107
00108 void computeDepths(DirectedEdge *startEdge);
00109
00110 void computeNodeDepth(Node *n);
00111 void copySymDepths(DirectedEdge *de);
00112 bool contains(vector<Node*> *nodes,Node *node);
00113
00114 public:
00115 BufferSubgraph(CGAlgorithms *cga);
00116 ~BufferSubgraph();
00117 vector<DirectedEdge*>* getDirectedEdges();
00118 vector<Node*>* getNodes();
00119
00120
00121
00122
00123 Coordinate* getRightmostCoordinate();
00124
00125
00126
00127
00128
00129
00130
00131
00132 void create(Node *node);
00133
00134 void computeDepth(int outsideDepth);
00135
00136
00137
00138
00139
00140
00141
00142
00143
00144
00145 void findResultEdges();
00146
00147
00148
00149
00150
00151
00152
00153
00154
00155
00156
00157
00158
00159
00160 int compareTo(void* o);
00161
00168 Envelope *getEnvelope();
00169 };
00170
00171
00172
00173
00174
00175
00176
00177
00178
00179
00180
00181
00182
00183
00184
00185
00186
00187
00188
00189
00190
00191
00192
00193
00194
00195
00196
00197
00198
00199 class BufferOp {
00200
00201 private:
00202
00203 static int MAX_PRECISION_DIGITS;
00204
00205
00206
00207
00208
00209
00210
00211
00212
00213
00214
00215
00216
00217
00218
00219
00220
00221 static double precisionScaleFactor(Geometry *g, double distance,int maxPrecisionDigits);
00222
00223 Geometry *argGeom;
00224
00225 TopologyException *saveException;
00226
00227 double distance;
00228
00229 int quadrantSegments;
00230
00231 int endCapStyle;
00232
00233 Geometry* resultGeometry;
00234
00235 void computeGeometry();
00236
00237 void bufferOriginalPrecision();
00238
00239 void bufferFixedPrecision(int precisionDigits);
00240
00241 public:
00242
00243 enum {
00245 CAP_ROUND,
00247 CAP_BUTT,
00249 CAP_SQUARE
00250 };
00251
00259 static Geometry* bufferOp(Geometry *g, double distance);
00260
00272 static Geometry* bufferOp(Geometry *g, double distance, int quadrantSegments);
00273
00279 BufferOp(Geometry *g);
00280
00288 void setEndCapStyle(int nEndCapStyle);
00289
00297 void setQuadrantSegments(int nQuadrantSegments);
00298
00307 Geometry* getResultGeometry(double nDistance);
00308
00321 Geometry* getResultGeometry(double nDistance, int nQuadrantSegments);
00322 };
00323
00324
00325
00326
00327
00328
00329
00330
00331
00332
00333
00334
00335
00336
00337
00338 class OffsetCurveBuilder {
00339 public:
00347 static const int DEFAULT_QUADRANT_SEGMENTS=8;
00348
00349 OffsetCurveBuilder(const PrecisionModel *newPrecisionModel);
00350 ~OffsetCurveBuilder();
00351 OffsetCurveBuilder(const PrecisionModel *newPrecisionModel,int quadrantSegments);
00352 void setEndCapStyle(int newEndCapStyle);
00353
00361 vector<CoordinateSequence*>* getLineCurve(const CoordinateSequence *inputPts, double distance);
00362
00369 vector<CoordinateSequence*>* getRingCurve(const CoordinateSequence *inputPts, int side, double distance);
00370
00371 private:
00372
00373 static double PI_OVER_2;
00374 static double MAX_CLOSING_SEG_LEN;
00375
00376 CGAlgorithms *cga;
00377 LineIntersector *li;
00378
00383 double filletAngleQuantum;
00384
00389 double maxCurveSegmentError;
00390
00391 CoordinateSequence *ptList;
00392
00393 double distance;
00394 const PrecisionModel *precisionModel;
00395 int endCapStyle;
00396 int joinStyle;
00397 Coordinate s0, s1, s2;
00398 LineSegment *seg0;
00399 LineSegment *seg1;
00400 LineSegment *offset0;
00401 LineSegment *offset1;
00402 int side;
00403
00404 void init(double newDistance);
00405 CoordinateSequence* getCoordinates();
00406 void computeLineBufferCurve(const CoordinateSequence *inputPts);
00407 void computeRingBufferCurve(const CoordinateSequence *inputPts, int side);
00408 void addPt(const Coordinate &pt);
00409 void closePts();
00410 void initSideSegments(const Coordinate &nS1, const Coordinate &nS2, int nSide);
00411 void addNextSegment(const Coordinate &p, bool addStartPoint);
00415 void addLastSegment();
00425 void computeOffsetSegment(LineSegment *seg, int side, double distance, LineSegment *offset);
00429 void addLineEndCap(const Coordinate &p0,const Coordinate &p1);
00435 void addFillet(const Coordinate &p,const Coordinate &p0,const Coordinate &p1, int direction, double distance);
00442 void addFillet(const Coordinate &p, double startAngle, double endAngle, int direction, double distance);
00446 void addCircle(const Coordinate &p, double distance);
00450 void addSquare(const Coordinate &p, double distance);
00451 private:
00452 vector<CoordinateSequence *>ptLists;
00453 };
00454
00455
00456
00457
00458
00459
00460
00461
00462
00463
00464
00465
00466 class OffsetCurveSetBuilder {
00467 public:
00468 OffsetCurveSetBuilder(const Geometry *newInputGeom, double newDistance, OffsetCurveBuilder *newCurveBuilder);
00469 ~OffsetCurveSetBuilder();
00477 vector<SegmentString*>* getCurves();
00478 void addCurves(const vector<CoordinateSequence*> *lineList, int leftLoc, int rightLoc);
00479 private:
00480 vector<Label*> newLabels;
00481 CGAlgorithms *cga;
00482 const Geometry *inputGeom;
00483 double distance;
00484 OffsetCurveBuilder *curveBuilder;
00485 vector<SegmentString*> *curveList;
00495 void addCurve(const CoordinateSequence *coord, int leftLoc, int rightLoc);
00496 void add(const Geometry *g);
00497 void addCollection(const GeometryCollection *gc);
00501 void addPoint(const Point *p);
00502 void addLineString(const LineString *line);
00503 void addPolygon(const Polygon *p);
00517 void addPolygonRing(const CoordinateSequence *coord, double offsetDistance, int side, int cwLeftLoc, int cwRightLoc);
00527 bool isErodedCompletely(CoordinateSequence *ringCoord, double bufferDistance);
00528
00529
00547 bool isTriangleErodedCompletely(CoordinateSequence *triangleCoord, double bufferDistance);
00548 };
00549
00550
00551
00552
00553
00554
00555
00556
00557 class DepthSegment {
00558 private:
00559 LineSegment *upwardSeg;
00571 int compareX(LineSegment *seg0, LineSegment *seg1);
00572 public:
00573 int leftDepth;
00574 DepthSegment(LineSegment *seg, int depth);
00575 ~DepthSegment();
00588 int compareTo(void* obj);
00589 };
00590
00591 bool DepthSegmentLT(DepthSegment *first, DepthSegment *second);
00592
00593
00594
00595
00596
00597
00598
00599
00600
00601
00602
00603 class SubgraphDepthLocater {
00604 public:
00605 SubgraphDepthLocater(vector<BufferSubgraph*> *newSubgraphs);
00606 ~SubgraphDepthLocater();
00607 int getDepth(Coordinate &p);
00608 private:
00609 vector<BufferSubgraph*> *subgraphs;
00610 LineSegment *seg;
00611 CGAlgorithms *cga;
00619 vector<DepthSegment*>* findStabbedSegments(Coordinate &stabbingRayLeftPt);
00628 void findStabbedSegments(Coordinate &stabbingRayLeftPt,vector<DirectedEdge*> *dirEdges,vector<DepthSegment*> *stabbedSegments);
00637 void findStabbedSegments(Coordinate &stabbingRayLeftPt,DirectedEdge *dirEdge,vector<DepthSegment*> *stabbedSegments);
00638 };
00639
00640 bool BufferSubgraphGT(BufferSubgraph *first, BufferSubgraph *second);
00641
00642
00643
00644
00645
00646
00647
00648
00649
00650
00651
00652
00653
00654
00655
00656
00657
00658
00659
00660 class BufferBuilder {
00661 friend class Unload;
00662 public:
00666 BufferBuilder();
00667 ~BufferBuilder();
00668
00675 void setQuadrantSegments(int nQuadrantSegments);
00676
00687 void setWorkingPrecisionModel(PrecisionModel *pm);
00688
00689 void setEndCapStyle(int nEndCapStyle);
00690
00691 Geometry* buffer(Geometry *g, double distance);
00692
00693
00694 private:
00698 static int depthDelta(Label *label);
00699 static CGAlgorithms *cga;
00700 int quadrantSegments;
00701 int endCapStyle;
00702 PrecisionModel *workingPrecisionModel;
00703 const GeometryFactory *geomFact;
00704 EdgeList *edgeList;
00705 vector<Label *>newLabels;
00706 void computeNodedEdges(vector<SegmentString*> *bufferSegStrList, const PrecisionModel *precisionModel);
00707
00714 void insertEdge(Edge *e);
00715 vector<BufferSubgraph*>* createSubgraphs(PlanarGraph *graph);
00716
00727 void buildSubgraphs(vector<BufferSubgraph*> *subgraphList, PolygonBuilder *polyBuilder);
00728 };
00729
00730 }
00731
00732 #endif // ndef GEOS_OPBUFFER_H
00733
00734
00735
00736
00737
00738
00739
00740
00741
00742
00743
00744
00745
00746
00747
00748
00749
00750
00751
00752
00753
00754
00755
00756
00757
00758
00759
00760
00761
00762
00763
00764
00765
00766
00767
00768
00769
00770
00771
00772
00773
00774
00775
00776
00777
00778
00779
00780
00781
00782
00783
00784
00785
00786
00787
00788
00789
00790
00791
00792
00793
00794
00795
00796
00797
00798
00799
00800
00801
00802
00803
00804
00805
00806
00807
00808
00809
00810
00811
00812
00813
00814
00815
00816
00817
00818
00819
00820
00821
00822
00823
00824
00825
00826
00827
00828
00829
00830