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
00035
00036
00037
00038
00039
00040
00041
00042
00043
00044
00045
00046
00047
00048
00049
00050
00051
00052
00053
00054
00055
00056
00057
00058
00059
00060
00061
00062
00063
00064
00065
00066
00067
00068
00069
00070
00071
00072
00073
00074
00075
00076
00077
00078
00079
00080
00081
00082
00083
00084
00085
00086
00087
00088
00089
00090
00091
00092
00093
00094
00095
00096
00097
00098 #ifndef GEOS_OPBUFFER_H
00099 #define GEOS_OPBUFFER_H
00100
00101 #include <memory>
00102 #include <geos/platform.h>
00103 #include <geos/operation.h>
00104 #include <geos/opOverlay.h>
00105 #include <geos/geomgraph.h>
00106 #include <geos/noding.h>
00107 #include <geos/geom.h>
00108 #include <vector>
00109
00110 namespace geos {
00111
00112
00113
00114
00115
00116
00117
00118
00119
00120 class RightmostEdgeFinder {
00121 private:
00122 CGAlgorithms* cga;
00123 int minIndex;
00124 Coordinate minCoord;
00125 DirectedEdge *minDe;
00126 DirectedEdge *orientedDe;
00127 void findRightmostEdgeAtNode();
00128 void findRightmostEdgeAtVertex();
00129 void checkForRightmostCoordinate(DirectedEdge *de);
00130 int getRightmostSide(DirectedEdge *de, int index);
00131 int getRightmostSideOfSegment(DirectedEdge *de, int i);
00132
00133
00134
00135
00136 public:
00137 RightmostEdgeFinder(CGAlgorithms *newCga);
00138 DirectedEdge* getEdge();
00139 Coordinate& getCoordinate();
00140 void findEdge(vector<DirectedEdge*>* dirEdgeList);
00141 };
00142
00143
00144
00145
00146
00147
00148
00149
00150
00151
00152 class BufferSubgraph {
00153 private:
00154 RightmostEdgeFinder *finder;
00155 vector<DirectedEdge*> *dirEdgeList;
00156 vector<Node*> *nodes;
00157 Coordinate *rightMostCoord;
00158
00159
00160
00161
00162
00163
00164 void addReachable(Node *startNode);
00165
00166
00167
00168
00169
00170 void add(Node *node,vector<Node*> *nodeStack);
00171 void clearVisitedEdges();
00172
00173
00174
00175
00176
00177 void computeDepths(DirectedEdge *startEdge);
00178 void computeNodeDepth(Node *n);
00179 void copySymDepths(DirectedEdge *de);
00180 bool contains(vector<Node*> *nodes,Node *node);
00181 public:
00182 BufferSubgraph(CGAlgorithms *cga);
00183 ~BufferSubgraph();
00184 vector<DirectedEdge*>* getDirectedEdges();
00185 vector<Node*>* getNodes();
00186
00187
00188
00189 Coordinate* getRightmostCoordinate();
00190
00191
00192
00193
00194
00195
00196 void create(Node *node);
00197 void computeDepth(int outsideDepth);
00198
00199
00200
00201
00202
00203
00204
00205
00206 void findResultEdges();
00207
00208
00209
00210
00211
00212
00213
00214
00215
00216
00217
00218 int compareTo(void* o);
00219 };
00220
00221
00222
00223
00224
00225
00226
00227
00228
00229
00230
00231
00232
00233
00234
00235
00236
00237
00238
00239
00240
00241
00242
00243
00244
00245
00246
00247
00248
00249 class BufferOp {
00250
00251 private:
00252
00253 static int MAX_PRECISION_DIGITS;
00254
00255
00256
00257
00258
00259
00260
00261
00262
00263
00264
00265
00266
00267
00268
00269
00270
00271 static double precisionScaleFactor(Geometry *g, double distance,int maxPrecisionDigits);
00272
00273 Geometry *argGeom;
00274
00275 TopologyException *saveException;
00276
00277 double distance;
00278
00279 int quadrantSegments;
00280
00281 int endCapStyle;
00282
00283 Geometry* resultGeometry;
00284
00285 void computeGeometry();
00286
00287 void bufferOriginalPrecision();
00288
00289 void bufferFixedPrecision(int precisionDigits);
00290
00291 public:
00292
00293 enum {
00295 CAP_ROUND,
00297 CAP_BUTT,
00299 CAP_SQUARE
00300 };
00301
00309 static Geometry* bufferOp(Geometry *g, double distance);
00310
00322 static Geometry* bufferOp(Geometry *g, double distance, int quadrantSegments);
00323
00329 BufferOp(Geometry *g);
00330
00338 void setEndCapStyle(int nEndCapStyle);
00339
00347 void setQuadrantSegments(int nQuadrantSegments);
00348
00357 Geometry* getResultGeometry(double nDistance);
00358
00371 Geometry* getResultGeometry(double nDistance, int nQuadrantSegments);
00372 };
00373
00374
00375
00376
00377
00378
00379
00380
00381
00382
00383
00384
00385
00386
00387
00388 class OffsetCurveBuilder {
00389 public:
00397 static const int DEFAULT_QUADRANT_SEGMENTS=8;
00398
00399 OffsetCurveBuilder(const PrecisionModel *newPrecisionModel);
00400 ~OffsetCurveBuilder();
00401 OffsetCurveBuilder(const PrecisionModel *newPrecisionModel,int quadrantSegments);
00402 void setEndCapStyle(int newEndCapStyle);
00403
00411 vector<CoordinateSequence*>* getLineCurve(const CoordinateSequence *inputPts, double distance);
00412
00419 vector<CoordinateSequence*>* getRingCurve(const CoordinateSequence *inputPts, int side, double distance);
00420
00421 private:
00422
00423 static double PI_OVER_2;
00424 static double MAX_CLOSING_SEG_LEN;
00425
00426 CGAlgorithms *cga;
00427 LineIntersector *li;
00432 double filletAngleQuantum;
00436 double maxCurveSegmentError;
00437 CoordinateSequence *ptList;
00438 double distance;
00439 const PrecisionModel *precisionModel;
00440 int endCapStyle;
00441 int joinStyle;
00442 Coordinate s0, s1, s2;
00443 LineSegment *seg0;
00444 LineSegment *seg1;
00445 LineSegment *offset0;
00446 LineSegment *offset1;
00447 int side;
00448
00449 void init(double newDistance);
00450 CoordinateSequence* getCoordinates();
00451 void computeLineBufferCurve(const CoordinateSequence *inputPts);
00452 void computeRingBufferCurve(const CoordinateSequence *inputPts, int side);
00453 void addPt(const Coordinate &pt);
00454 void closePts();
00455 void initSideSegments(const Coordinate &nS1, const Coordinate &nS2, int nSide);
00456 void addNextSegment(const Coordinate &p, bool addStartPoint);
00460 void addLastSegment();
00470 void computeOffsetSegment(LineSegment *seg, int side, double distance, LineSegment *offset);
00474 void addLineEndCap(const Coordinate &p0,const Coordinate &p1);
00480 void addFillet(const Coordinate &p,const Coordinate &p0,const Coordinate &p1, int direction, double distance);
00487 void addFillet(const Coordinate &p, double startAngle, double endAngle, int direction, double distance);
00491 void addCircle(const Coordinate &p, double distance);
00495 void addSquare(const Coordinate &p, double distance);
00496 private:
00497 vector<CoordinateSequence *>ptLists;
00498 };
00499
00500
00501
00502
00503
00504
00505
00506
00507
00508
00509
00510
00511 class OffsetCurveSetBuilder {
00512 public:
00513 OffsetCurveSetBuilder(const Geometry *newInputGeom, double newDistance, OffsetCurveBuilder *newCurveBuilder);
00514 ~OffsetCurveSetBuilder();
00522 vector<SegmentString*>* getCurves();
00523 void addCurves(const vector<CoordinateSequence*> *lineList, int leftLoc, int rightLoc);
00524 private:
00525 vector<Label*> newLabels;
00526 CGAlgorithms *cga;
00527 const Geometry *inputGeom;
00528 double distance;
00529 OffsetCurveBuilder *curveBuilder;
00530 vector<SegmentString*> *curveList;
00540 void addCurve(const CoordinateSequence *coord, int leftLoc, int rightLoc);
00541 void add(const Geometry *g);
00542 void addCollection(const GeometryCollection *gc);
00546 void addPoint(const Point *p);
00547 void addLineString(const LineString *line);
00548 void addPolygon(const Polygon *p);
00562 void addPolygonRing(const CoordinateSequence *coord, double offsetDistance, int side, int cwLeftLoc, int cwRightLoc);
00572 bool isErodedCompletely(CoordinateSequence *ringCoord, double bufferDistance);
00590 bool isTriangleErodedCompletely(CoordinateSequence *triangleCoord,double bufferDistance);
00591 };
00592
00593
00594
00595
00596
00597
00598
00599
00600 class DepthSegment {
00601 private:
00602 LineSegment *upwardSeg;
00614 int compareX(LineSegment *seg0, LineSegment *seg1);
00615 public:
00616 int leftDepth;
00617 DepthSegment(LineSegment *seg, int depth);
00618 ~DepthSegment();
00631 int compareTo(void* obj);
00632 };
00633
00634 bool DepthSegmentLT(DepthSegment *first, DepthSegment *second);
00635
00636
00637
00638
00639
00640
00641
00642
00643
00644
00645
00646 class SubgraphDepthLocater {
00647 public:
00648 SubgraphDepthLocater(vector<BufferSubgraph*> *newSubgraphs);
00649 ~SubgraphDepthLocater();
00650 int getDepth(Coordinate &p);
00651 private:
00652 vector<BufferSubgraph*> *subgraphs;
00653 LineSegment *seg;
00654 CGAlgorithms *cga;
00662 vector<DepthSegment*>* findStabbedSegments(Coordinate &stabbingRayLeftPt);
00671 void findStabbedSegments(Coordinate &stabbingRayLeftPt,vector<DirectedEdge*> *dirEdges,vector<DepthSegment*> *stabbedSegments);
00680 void findStabbedSegments(Coordinate &stabbingRayLeftPt,DirectedEdge *dirEdge,vector<DepthSegment*> *stabbedSegments);
00681 };
00682
00683 bool BufferSubgraphGT(BufferSubgraph *first, BufferSubgraph *second);
00684
00685
00686
00687
00688
00689
00690
00691
00692
00693
00694
00695
00696
00697
00698
00699
00700
00701
00702
00703 class BufferBuilder {
00704 friend class Unload;
00705 public:
00709 BufferBuilder();
00710 ~BufferBuilder();
00716 void setQuadrantSegments(int nQuadrantSegments);
00725 void setWorkingPrecisionModel(PrecisionModel *pm);
00726 void setEndCapStyle(int nEndCapStyle);
00727 Geometry* buffer(Geometry *g, double distance);
00728 private:
00732 static int depthDelta(Label *label);
00733 static CGAlgorithms *cga;
00734 int quadrantSegments;
00735 int endCapStyle;
00736 PrecisionModel *workingPrecisionModel;
00737 const GeometryFactory *geomFact;
00738 EdgeList *edgeList;
00739 vector<Label *>newLabels;
00740 void computeNodedEdges(vector<SegmentString*> *bufferSegStrList, const PrecisionModel *precisionModel);
00746 void insertEdge(Edge *e);
00747 vector<BufferSubgraph*>* createSubgraphs(PlanarGraph *graph);
00756 void buildSubgraphs(vector<BufferSubgraph*> *subgraphList, PolygonBuilder *polyBuilder);
00757 };
00758
00759 }
00760 #endif