Main Page | Namespace List | Class Hierarchy | Class List | File List | Namespace Members | Class Members | Related Pages

opBuffer.h

00001 /**********************************************************************
00002  * $Id: opBuffer.h,v 1.3 2004/07/19 13:19:31 strk Exp $
00003  *
00004  * GEOS - Geometry Engine Open Source
00005  * http://geos.refractions.net
00006  *
00007  * Copyright (C) 2001-2002 Vivid Solutions Inc.
00008  *
00009  * This is free software; you can redistribute and/or modify it under
00010  * the terms of the GNU Lesser General Public Licence as published
00011  * by the Free Software Foundation. 
00012  * See the COPYING file for more information.
00013  *
00014  **********************************************************************
00015  * $Log: opBuffer.h,v $
00016  * Revision 1.3  2004/07/19 13:19:31  strk
00017  * Documentation fixes
00018  *
00019  * Revision 1.2  2004/07/08 19:34:49  strk
00020  * Mirrored JTS interface of CoordinateSequence, factory and
00021  * default implementations.
00022  * Added DefaultCoordinateSequenceFactory::instance() function.
00023  *
00024  * Revision 1.1  2004/07/02 13:20:42  strk
00025  * Header files moved under geos/ dir.
00026  *
00027  * Revision 1.22  2004/07/01 14:12:44  strk
00028  *
00029  * Geometry constructors come now in two flavors:
00030  *      - deep-copy args (pass-by-reference)
00031  *      - take-ownership of args (pass-by-pointer)
00032  * Same functionality is available through GeometryFactory,
00033  * including buildGeometry().
00034  *
00035  * Revision 1.21  2004/06/30 20:59:13  strk
00036  * Removed GeoemtryFactory copy from geometry constructors.
00037  * Enforced const-correctness on GeometryFactory arguments.
00038  *
00039  * Revision 1.20  2004/05/27 08:37:16  strk
00040  * Fixed a bug preventing OffsetCurveBuilder point list from being reset.
00041  *
00042  * Revision 1.19  2004/05/26 09:49:03  strk
00043  * PlanarGraph made local to ::buffer instead of Class private.
00044  *
00045  * Revision 1.18  2004/05/07 07:57:27  strk
00046  * Added missing EdgeNodingValidator to build scripts.
00047  * Changed SegmentString constructor back to its original form
00048  * (takes const void *), implemented local tracking of "contexts"
00049  * in caller objects for proper destruction.
00050  *
00051  * Revision 1.17  2004/05/05 16:57:48  strk
00052  * Rewritten static cga allocation to avoid copy constructor calls.
00053  *
00054  * Revision 1.16  2004/05/05 10:54:48  strk
00055  * Removed some private static heap explicit allocation, less cleanup done by
00056  * the unloader.
00057  *
00058  * Revision 1.15  2004/05/03 10:43:42  strk
00059  * Exception specification considered harmful - left as comment.
00060  *
00061  * Revision 1.14  2004/04/30 09:15:28  strk
00062  * Enlarged exception specifications to allow for AssertionFailedException.
00063  * Added missing initializers.
00064  *
00065  * Revision 1.13  2004/04/23 00:02:18  strk
00066  * const-correctness changes
00067  *
00068  * Revision 1.12  2004/04/20 10:58:04  strk
00069  * More memory leaks removed.
00070  *
00071  * Revision 1.11  2004/04/19 15:14:45  strk
00072  * Added missing virtual destructor in SpatialIndex class.
00073  * Memory leaks fixes. Const and throw specifications added.
00074  *
00075  * Revision 1.10  2004/04/19 12:51:01  strk
00076  * Memory leaks fixes. Throw specifications added.
00077  *
00078  * Revision 1.9  2004/04/15 14:00:30  strk
00079  * Added new cleanup to Unload::Release
00080  *
00081  * Revision 1.8  2004/04/10 08:40:01  ybychkov
00082  * "operation/buffer" upgraded to JTS 1.4
00083  *
00084  * Revision 1.7  2004/03/01 22:04:59  strk
00085  * applied const correctness changes by Manuel Prieto Villegas <ManuelPrietoVillegas@telefonica.net>
00086  *
00087  * Revision 1.6  2003/11/07 01:23:42  pramsey
00088  * Add standard CVS headers licence notices and copyrights to all cpp and h
00089  * files.
00090  *
00091  * Revision 1.5  2003/11/06 18:46:34  strk
00092  * Added throw specification for BufferOp's ::buildSubgraphs() 
00093  * and ::computeBuffer()
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  * \class RightmostEdgeFinder opBuffer.h geos/opBuffer.h
00114  *
00115  * \brief
00116  * A RightmostEdgeFinder find the DirectedEdge in a list which has
00117  * the highest coordinate, and which is oriented L to R at that point.
00118  * (I.e. the right side is on the RHS of the edge.)
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         * A RightmostEdgeFinder finds the DirectedEdge with the rightmost coordinate.
00134         * The DirectedEdge returned is guranteed to have the R of the world on its RHS.
00135         */
00136 public:
00137         RightmostEdgeFinder(CGAlgorithms *newCga);
00138         DirectedEdge* getEdge();
00139         Coordinate& getCoordinate();
00140         void findEdge(vector<DirectedEdge*>* dirEdgeList);
00141 };
00142 
00143 /*
00144  * \class BufferSubgraph opBuffer.h geos/opBuffer.h
00145  *
00146  * \brief A connected subset of the graph of DirectedEdges and Node.
00147  * 
00148  * Its edges will generate either
00149  * - a single polygon in the complete buffer, with zero or more holes, or
00150  * -  ne or more connected holes
00151  */
00152 class BufferSubgraph {
00153 private:
00154         RightmostEdgeFinder *finder;
00155         vector<DirectedEdge*> *dirEdgeList;
00156         vector<Node*> *nodes;
00157         Coordinate *rightMostCoord;
00158         /*
00159         * Adds all nodes and edges reachable from this node to the subgraph.
00160         * Uses an explicit stack to avoid a large depth of recursion.
00161         *
00162         * @param node a node known to be in the subgraph
00163         */
00164         void addReachable(Node *startNode);
00165         /*
00166         * Adds the argument node and all its out edges to the subgraph
00167         * @param node the node to add
00168         * @param nodeStack the current set of nodes being traversed
00169         */
00170         void add(Node *node,vector<Node*> *nodeStack);
00171         void clearVisitedEdges();
00172         /*
00173         * Compute depths for all dirEdges via breadth-first traversal of nodes in graph
00174         * @param startEdge edge to start processing with
00175         */
00176         // <FIX> MD - use iteration & queue rather than recursion, for speed and robustness
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         * Gets the rightmost coordinate in the edges of the subgraph
00188         */
00189         Coordinate* getRightmostCoordinate();
00190         /*
00191         * Creates the subgraph consisting of all edges reachable from this node.
00192         * Finds the edges in the graph and the rightmost coordinate.
00193         *
00194         * @param node a node to start the graph traversal from
00195         */
00196         void create(Node *node);
00197         void computeDepth(int outsideDepth);
00198         /*
00199         * Find all edges whose depths indicates that they are in the result area(s).
00200         * Since we want polygon shells to be
00201         * oriented CW, choose dirEdges with the interior of the result on the RHS.
00202         * Mark them as being in the result.
00203         * Interior Area edges are the result of dimensional collapses.
00204         * They do not form part of the result area boundary.
00205         */
00206         void findResultEdges();
00207         /*
00208         * BufferSubgraphs are compared on the x-value of their rightmost Coordinate.
00209         * This defines a partial ordering on the graphs such that:
00210         * <p>
00211         * g1 >= g2 <==> Ring(g2) does not contain Ring(g1)
00212         * <p>
00213         * where Polygon(g) is the buffer polygon that is built from g.
00214         * <p>
00215         * This relationship is used to sort the BufferSubgraphs so that shells are guaranteed to
00216         * be built before holes.
00217         */
00218         int compareTo(void* o);
00219 };
00220 
00221 /*
00222  * \class BufferOp opBuffer.h geos/opBuffer.h
00223  *
00224  * \brief
00225  * Computes the buffer of a geometry, for both positive and negative
00226  * buffer distances.
00227  *
00228  * In GIS, the buffer of a geometry is defined as
00229  * the Minkowski sum or difference of the geometry
00230  * with a circle with radius equal to the absolute value of the buffer
00231  * distance.
00232  * In the CAD/CAM world buffers are known as </b>offset curves</b>.
00233  * 
00234  * Since true buffer curves may contain circular arcs,
00235  * computed buffer polygons can only be approximations to the true geometry.
00236  * The user can control the accuracy of the curve approximation by specifying
00237  * the number of linear segments with which to approximate a curve.
00238  * 
00239  * The end cap style of a linear buffer may be specified.
00240  * The following end cap styles are supported:
00241  * - CAP_ROUND - the usual round end caps
00242  * - CAP_BUTT - end caps are truncated flat at the line ends
00243  * - CAP_SQUARE - end caps are squared off at the buffer distance
00244  *   beyond the line ends
00245  * 
00246  * The computation uses an algorithm involving iterated noding and
00247  * precision reduction to provide a high degree of robustness.
00248  */
00249 class BufferOp {
00250 
00251 private:
00252 
00253         static int MAX_PRECISION_DIGITS;
00254 
00255         /*
00256          * Compute a reasonable scale factor to limit the precision of
00257          * a given combination of Geometry and buffer distance.
00258          * The scale factor is based on a heuristic.
00259          *
00260          * @param g the Geometry being buffered
00261          *
00262          * @param distance the buffer distance
00263          *
00264          * @param maxPrecisionDigits the mzx # of digits that should be
00265          *        allowed by the precision determined by the
00266          *        computed scale factor
00267          *
00268          * @return a scale factor that allows a reasonable amount of
00269          *         precision for the buffer computation
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  * \class OffsetCurveBuilder opBuffer.h geos/opBuffer.h
00376  *
00377  * \brief
00378  * Computes the raw offset curve for a
00379  * single Geometry component (ring, line or point).
00380  *
00381  * A raw offset curve line is not noded -
00382  * it may contain self-intersections (and usually will).
00383  * The final buffer polygon is computed by forming a topological graph
00384  * of all the noded raw curves and tracing outside contours.
00385  * The points in the raw curve are rounded to the required precision model.
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 //      static final Coordinate[] arrayTypeCoordinate = new Coordinate[0];
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 //      static CoordinateSequence* copyCoordinates(CoordinateSequence *pts);
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  * \class OffsetCurveSetBuilder opBuffer.h geos/opBuffer.h
00503  *
00504  * \brief
00505  * Creates all the raw offset curves for a buffer of a Geometry.
00506  *
00507  * Raw curves need to be noded together and polygonized to form the
00508  * final buffer area.
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  * \class DepthSegment opBuffer.h geos/opBuffer.h
00595  *
00596  * \brief
00597  * A segment from a directed edge which has been assigned a depth value
00598  * for its sides.
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  * \class SubgraphDepthLocater opBuffer.h geos/opBuffer.h
00638  *
00639  * \brief Locates a subgraph inside a set of subgraphs,
00640  *
00641  * in order to determine the outside depth of the subgraph.
00642  * The input subgraphs are assumed to have had depths
00643  * already calculated for their edges.
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  * \class BufferBuilder opBuffer.h geos/opBuffer.h
00687  *
00688  * \brief
00689  * Builds the buffer geometry for a given input geometry and precision model.
00690  *
00691  * Allows setting the level of approximation for circular arcs,
00692  * and the precision model in which to carry out the computation.
00693  * 
00694  * When computing buffers in floating point double-precision
00695  * it can happen that the process of iterated noding can fail to converge
00696  * (terminate).
00697  *
00698  * In this case a TopologyException will be thrown.
00699  * Retrying the computation in a fixed precision
00700  * can produce more robust results.
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); // throw (GEOSException *);
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); // throw(GEOSException *);
00746         void insertEdge(Edge *e);
00747         vector<BufferSubgraph*>* createSubgraphs(PlanarGraph *graph);
00756         void buildSubgraphs(vector<BufferSubgraph*> *subgraphList, PolygonBuilder *polyBuilder);
00757 };
00758 
00759 }
00760 #endif

Generated on Fri Nov 26 21:30:45 2004 for GEOS by  doxygen 1.3.9.1