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
00084
00085
00086
00087
00088
00089 void addReachable(Node *startNode);
00090
00091
00092
00093
00094
00095
00096 void add(Node *node,vector<Node*> *nodeStack);
00097
00098 void clearVisitedEdges();
00099
00100
00101
00102
00103
00104
00105
00106 void computeDepths(DirectedEdge *startEdge);
00107
00108 void computeNodeDepth(Node *n);
00109 void copySymDepths(DirectedEdge *de);
00110 bool contains(vector<Node*> *nodes,Node *node);
00111
00112 public:
00113 BufferSubgraph(CGAlgorithms *cga);
00114 ~BufferSubgraph();
00115 vector<DirectedEdge*>* getDirectedEdges();
00116 vector<Node*>* getNodes();
00117
00118
00119
00120
00121 Coordinate* getRightmostCoordinate();
00122
00123
00124
00125
00126
00127
00128
00129
00130 void create(Node *node);
00131
00132 void computeDepth(int outsideDepth);
00133
00134
00135
00136
00137
00138
00139
00140
00141
00142
00143 void findResultEdges();
00144
00145
00146
00147
00148
00149
00150
00151
00152
00153
00154
00155
00156
00157
00158 int compareTo(void* o);
00159 };
00160
00161
00162
00163
00164
00165
00166
00167
00168
00169
00170
00171
00172
00173
00174
00175
00176
00177
00178
00179
00180
00181
00182
00183
00184
00185
00186
00187
00188
00189 class BufferOp {
00190
00191 private:
00192
00193 static int MAX_PRECISION_DIGITS;
00194
00195
00196
00197
00198
00199
00200
00201
00202
00203
00204
00205
00206
00207
00208
00209
00210
00211 static double precisionScaleFactor(Geometry *g, double distance,int maxPrecisionDigits);
00212
00213 Geometry *argGeom;
00214
00215 TopologyException *saveException;
00216
00217 double distance;
00218
00219 int quadrantSegments;
00220
00221 int endCapStyle;
00222
00223 Geometry* resultGeometry;
00224
00225 void computeGeometry();
00226
00227 void bufferOriginalPrecision();
00228
00229 void bufferFixedPrecision(int precisionDigits);
00230
00231 public:
00232
00233 enum {
00235 CAP_ROUND,
00237 CAP_BUTT,
00239 CAP_SQUARE
00240 };
00241
00249 static Geometry* bufferOp(Geometry *g, double distance);
00250
00262 static Geometry* bufferOp(Geometry *g, double distance, int quadrantSegments);
00263
00269 BufferOp(Geometry *g);
00270
00278 void setEndCapStyle(int nEndCapStyle);
00279
00287 void setQuadrantSegments(int nQuadrantSegments);
00288
00297 Geometry* getResultGeometry(double nDistance);
00298
00311 Geometry* getResultGeometry(double nDistance, int nQuadrantSegments);
00312 };
00313
00314
00315
00316
00317
00318
00319
00320
00321
00322
00323
00324
00325
00326
00327
00328 class OffsetCurveBuilder {
00329 public:
00337 static const int DEFAULT_QUADRANT_SEGMENTS=8;
00338
00339 OffsetCurveBuilder(const PrecisionModel *newPrecisionModel);
00340 ~OffsetCurveBuilder();
00341 OffsetCurveBuilder(const PrecisionModel *newPrecisionModel,int quadrantSegments);
00342 void setEndCapStyle(int newEndCapStyle);
00343
00351 vector<CoordinateSequence*>* getLineCurve(const CoordinateSequence *inputPts, double distance);
00352
00359 vector<CoordinateSequence*>* getRingCurve(const CoordinateSequence *inputPts, int side, double distance);
00360
00361 private:
00362
00363 static double PI_OVER_2;
00364 static double MAX_CLOSING_SEG_LEN;
00365
00366 CGAlgorithms *cga;
00367 LineIntersector *li;
00368
00373 double filletAngleQuantum;
00374
00379 double maxCurveSegmentError;
00380
00381 CoordinateSequence *ptList;
00382
00383 double distance;
00384 const PrecisionModel *precisionModel;
00385 int endCapStyle;
00386 int joinStyle;
00387 Coordinate s0, s1, s2;
00388 LineSegment *seg0;
00389 LineSegment *seg1;
00390 LineSegment *offset0;
00391 LineSegment *offset1;
00392 int side;
00393
00394 void init(double newDistance);
00395 CoordinateSequence* getCoordinates();
00396 void computeLineBufferCurve(const CoordinateSequence *inputPts);
00397 void computeRingBufferCurve(const CoordinateSequence *inputPts, int side);
00398 void addPt(const Coordinate &pt);
00399 void closePts();
00400 void initSideSegments(const Coordinate &nS1, const Coordinate &nS2, int nSide);
00401 void addNextSegment(const Coordinate &p, bool addStartPoint);
00405 void addLastSegment();
00415 void computeOffsetSegment(LineSegment *seg, int side, double distance, LineSegment *offset);
00419 void addLineEndCap(const Coordinate &p0,const Coordinate &p1);
00425 void addFillet(const Coordinate &p,const Coordinate &p0,const Coordinate &p1, int direction, double distance);
00432 void addFillet(const Coordinate &p, double startAngle, double endAngle, int direction, double distance);
00436 void addCircle(const Coordinate &p, double distance);
00440 void addSquare(const Coordinate &p, double distance);
00441 private:
00442 vector<CoordinateSequence *>ptLists;
00443 };
00444
00445
00446
00447
00448
00449
00450
00451
00452
00453
00454
00455
00456 class OffsetCurveSetBuilder {
00457 public:
00458 OffsetCurveSetBuilder(const Geometry *newInputGeom, double newDistance, OffsetCurveBuilder *newCurveBuilder);
00459 ~OffsetCurveSetBuilder();
00467 vector<SegmentString*>* getCurves();
00468 void addCurves(const vector<CoordinateSequence*> *lineList, int leftLoc, int rightLoc);
00469 private:
00470 vector<Label*> newLabels;
00471 CGAlgorithms *cga;
00472 const Geometry *inputGeom;
00473 double distance;
00474 OffsetCurveBuilder *curveBuilder;
00475 vector<SegmentString*> *curveList;
00485 void addCurve(const CoordinateSequence *coord, int leftLoc, int rightLoc);
00486 void add(const Geometry *g);
00487 void addCollection(const GeometryCollection *gc);
00491 void addPoint(const Point *p);
00492 void addLineString(const LineString *line);
00493 void addPolygon(const Polygon *p);
00507 void addPolygonRing(const CoordinateSequence *coord, double offsetDistance, int side, int cwLeftLoc, int cwRightLoc);
00517 bool isErodedCompletely(CoordinateSequence *ringCoord, double bufferDistance);
00518
00519
00537 bool isTriangleErodedCompletely(CoordinateSequence *triangleCoord, double bufferDistance);
00538 };
00539
00540
00541
00542
00543
00544
00545
00546
00547 class DepthSegment {
00548 private:
00549 LineSegment *upwardSeg;
00561 int compareX(LineSegment *seg0, LineSegment *seg1);
00562 public:
00563 int leftDepth;
00564 DepthSegment(LineSegment *seg, int depth);
00565 ~DepthSegment();
00578 int compareTo(void* obj);
00579 };
00580
00581 bool DepthSegmentLT(DepthSegment *first, DepthSegment *second);
00582
00583
00584
00585
00586
00587
00588
00589
00590
00591
00592
00593 class SubgraphDepthLocater {
00594 public:
00595 SubgraphDepthLocater(vector<BufferSubgraph*> *newSubgraphs);
00596 ~SubgraphDepthLocater();
00597 int getDepth(Coordinate &p);
00598 private:
00599 vector<BufferSubgraph*> *subgraphs;
00600 LineSegment *seg;
00601 CGAlgorithms *cga;
00609 vector<DepthSegment*>* findStabbedSegments(Coordinate &stabbingRayLeftPt);
00618 void findStabbedSegments(Coordinate &stabbingRayLeftPt,vector<DirectedEdge*> *dirEdges,vector<DepthSegment*> *stabbedSegments);
00627 void findStabbedSegments(Coordinate &stabbingRayLeftPt,DirectedEdge *dirEdge,vector<DepthSegment*> *stabbedSegments);
00628 };
00629
00630 bool BufferSubgraphGT(BufferSubgraph *first, BufferSubgraph *second);
00631
00632
00633
00634
00635
00636
00637
00638
00639
00640
00641
00642
00643
00644
00645
00646
00647
00648
00649
00650 class BufferBuilder {
00651 friend class Unload;
00652 public:
00656 BufferBuilder();
00657 ~BufferBuilder();
00658
00665 void setQuadrantSegments(int nQuadrantSegments);
00666
00677 void setWorkingPrecisionModel(PrecisionModel *pm);
00678
00679 void setEndCapStyle(int nEndCapStyle);
00680
00681 Geometry* buffer(Geometry *g, double distance);
00682
00683
00684 private:
00688 static int depthDelta(Label *label);
00689 static CGAlgorithms *cga;
00690 int quadrantSegments;
00691 int endCapStyle;
00692 PrecisionModel *workingPrecisionModel;
00693 const GeometryFactory *geomFact;
00694 EdgeList *edgeList;
00695 vector<Label *>newLabels;
00696 void computeNodedEdges(vector<SegmentString*> *bufferSegStrList, const PrecisionModel *precisionModel);
00697
00704 void insertEdge(Edge *e);
00705 vector<BufferSubgraph*>* createSubgraphs(PlanarGraph *graph);
00706
00717 void buildSubgraphs(vector<BufferSubgraph*> *subgraphList, PolygonBuilder *polyBuilder);
00718 };
00719
00720 }
00721
00722 #endif // ndef GEOS_OPBUFFER_H
00723
00724
00725
00726
00727
00728
00729
00730
00731
00732
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