opBuffer.h

00001 /**********************************************************************
00002  * $Id: opBuffer.h,v 1.6.2.1 2005/06/30 18:31:21 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 
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  * \class RightmostEdgeFinder opBuffer.h geos/opBuffer.h
00032  *
00033  * \brief
00034  * A RightmostEdgeFinder find the DirectedEdge in a list which has
00035  * the highest coordinate, and which is oriented L to R at that point.
00036  * (I.e. the right side is on the RHS of the edge.)
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          * A RightmostEdgeFinder finds the DirectedEdge with the
00054          * rightmost coordinate.
00055          * The DirectedEdge returned is guranteed to have the R of
00056          * the world on its RHS.
00057          */
00058         RightmostEdgeFinder(CGAlgorithms *newCga);
00059         DirectedEdge* getEdge();
00060         Coordinate& getCoordinate();
00061         void findEdge(vector<DirectedEdge*>* dirEdgeList);
00062 };
00063 
00064 /*
00065  * \class BufferSubgraph opBuffer.h geos/opBuffer.h
00066  *
00067  * \brief A connected subset of the graph of DirectedEdges and Node.
00068  * 
00069  * Its edges will generate either
00070  * - a single polygon in the complete buffer, with zero or more holes, or
00071  * -  ne or more connected holes
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          * Adds all nodes and edges reachable from this node to the subgraph.
00087          * Uses an explicit stack to avoid a large depth of recursion.
00088          *
00089          * @param node a node known to be in the subgraph
00090          */
00091         void addReachable(Node *startNode);
00092 
00093         /*
00094          * Adds the argument node and all its out edges to the subgraph
00095          * @param node the node to add
00096          * @param nodeStack the current set of nodes being traversed
00097          */
00098         void add(Node *node,vector<Node*> *nodeStack);
00099 
00100         void clearVisitedEdges();
00101 
00102         /*
00103          * Compute depths for all dirEdges via breadth-first traversal
00104          * of nodes in graph
00105          * @param startEdge edge to start processing with
00106          */
00107         // <FIX> MD - use iteration & queue rather than recursion, for speed and robustness
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          * Gets the rightmost coordinate in the edges of the subgraph
00122          */
00123         Coordinate* getRightmostCoordinate();
00124 
00125         /*
00126          * Creates the subgraph consisting of all edges reachable from
00127          * this node.
00128          * Finds the edges in the graph and the rightmost coordinate.
00129          *
00130          * @param node a node to start the graph traversal from
00131          */
00132         void create(Node *node);
00133 
00134         void computeDepth(int outsideDepth);
00135         /*
00136          * Find all edges whose depths indicates that they are in the
00137          * result area(s).
00138          * Since we want polygon shells to be
00139          * oriented CW, choose dirEdges with the interior of the result
00140          * on the RHS.
00141          * Mark them as being in the result.
00142          * Interior Area edges are the result of dimensional collapses.
00143          * They do not form part of the result area boundary.
00144          */
00145         void findResultEdges();
00146 
00147         /*
00148          * BufferSubgraphs are compared on the x-value of their rightmost
00149          * Coordinate.
00150          * This defines a partial ordering on the graphs such that:
00151          * 
00152          * g1 >= g2 <==> Ring(g2) does not contain Ring(g1)
00153          *
00154          * where Polygon(g) is the buffer polygon that is built from g.
00155          *
00156          * This relationship is used to sort the BufferSubgraphs so
00157          * that shells are guaranteed to
00158          * be built before holes.
00159          */
00160         int compareTo(void* o);
00161 
00168         Envelope *getEnvelope();
00169 };
00170 
00171 /*
00172  * \class BufferOp opBuffer.h geos/opBuffer.h
00173  *
00174  * \brief
00175  * Computes the buffer of a geometry, for both positive and negative
00176  * buffer distances.
00177  *
00178  * In GIS, the buffer of a geometry is defined as
00179  * the Minkowski sum or difference of the geometry
00180  * with a circle with radius equal to the absolute value of the buffer
00181  * distance.
00182  * In the CAD/CAM world buffers are known as </b>offset curves</b>.
00183  * 
00184  * Since true buffer curves may contain circular arcs,
00185  * computed buffer polygons can only be approximations to the true geometry.
00186  * The user can control the accuracy of the curve approximation by specifying
00187  * the number of linear segments with which to approximate a curve.
00188  * 
00189  * The end cap style of a linear buffer may be specified.
00190  * The following end cap styles are supported:
00191  * - CAP_ROUND - the usual round end caps
00192  * - CAP_BUTT - end caps are truncated flat at the line ends
00193  * - CAP_SQUARE - end caps are squared off at the buffer distance
00194  *   beyond the line ends
00195  * 
00196  * The computation uses an algorithm involving iterated noding and
00197  * precision reduction to provide a high degree of robustness.
00198  */
00199 class BufferOp {
00200 
00201 private:
00202 
00203         static int MAX_PRECISION_DIGITS;
00204 
00205         /*
00206          * Compute a reasonable scale factor to limit the precision of
00207          * a given combination of Geometry and buffer distance.
00208          * The scale factor is based on a heuristic.
00209          *
00210          * @param g the Geometry being buffered
00211          *
00212          * @param distance the buffer distance
00213          *
00214          * @param maxPrecisionDigits the mzx # of digits that should be
00215          *        allowed by the precision determined by the
00216          *        computed scale factor
00217          *
00218          * @return a scale factor that allows a reasonable amount of
00219          *         precision for the buffer computation
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  * \class OffsetCurveBuilder opBuffer.h geos/opBuffer.h
00326  *
00327  * \brief
00328  * Computes the raw offset curve for a
00329  * single Geometry component (ring, line or point).
00330  *
00331  * A raw offset curve line is not noded -
00332  * it may contain self-intersections (and usually will).
00333  * The final buffer polygon is computed by forming a topological graph
00334  * of all the noded raw curves and tracing outside contours.
00335  * The points in the raw curve are rounded to the required precision model.
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 //      static final Coordinate[] arrayTypeCoordinate = new Coordinate[0];
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 //      static CoordinateSequence* copyCoordinates(CoordinateSequence *pts);
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  * \class OffsetCurveSetBuilder opBuffer.h geos/opBuffer.h
00458  *
00459  * \brief
00460  * Creates all the raw offset curves for a buffer of a Geometry.
00461  *
00462  * Raw curves need to be noded together and polygonized to form the
00463  * final buffer area.
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         //bool isErodedCompletely(CoordinateSequence *ringCoord, double bufferDistance) { return isErodedCompletely((const CoordinateSequence)ringCoord, bufferDistance) }
00529 
00547         bool isTriangleErodedCompletely(CoordinateSequence *triangleCoord, double bufferDistance);
00548 };
00549 
00550 /*
00551  * \class DepthSegment opBuffer.h geos/opBuffer.h
00552  *
00553  * \brief
00554  * A segment from a directed edge which has been assigned a depth value
00555  * for its sides.
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  * \class SubgraphDepthLocater opBuffer.h geos/opBuffer.h
00595  *
00596  * \brief Locates a subgraph inside a set of subgraphs,
00597  *
00598  * in order to determine the outside depth of the subgraph.
00599  * The input subgraphs are assumed to have had depths
00600  * already calculated for their edges.
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  * \class BufferBuilder opBuffer.h geos/opBuffer.h
00644  *
00645  * \brief
00646  * Builds the buffer geometry for a given input geometry and precision model.
00647  *
00648  * Allows setting the level of approximation for circular arcs,
00649  * and the precision model in which to carry out the computation.
00650  * 
00651  * When computing buffers in floating point double-precision
00652  * it can happen that the process of iterated noding can fail to converge
00653  * (terminate).
00654  *
00655  * In this case a TopologyException will be thrown.
00656  * Retrying the computation in a fixed precision
00657  * can produce more robust results.
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                 // throw (GEOSException *);
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); // throw(GEOSException *);
00707 
00714         void insertEdge(Edge *e);
00715         vector<BufferSubgraph*>* createSubgraphs(PlanarGraph *graph);
00716 
00727         void buildSubgraphs(vector<BufferSubgraph*> *subgraphList, PolygonBuilder *polyBuilder);
00728 };
00729 
00730 } // namespace geos
00731 
00732 #endif // ndef GEOS_OPBUFFER_H
00733 
00734 /**********************************************************************
00735  * $Log: opBuffer.h,v $
00736  * Revision 1.6.2.1  2005/06/30 18:31:21  strk
00737  * Ported SubgraphDepthLocator optimizations from JTS code
00738  *
00739  * Revision 1.6  2004/12/08 13:54:43  strk
00740  * gcc warnings checked and fixed, general cleanups.
00741  *
00742  * Revision 1.5  2004/11/04 19:08:07  strk
00743  * Cleanups, initializers list, profiling.
00744  *
00745  * Revision 1.4  2004/11/01 16:43:04  strk
00746  * Added Profiler code.
00747  * Temporarly patched a bug in DoubleBits (must check drawbacks).
00748  * Various cleanups and speedups.
00749  *
00750  * Revision 1.3  2004/07/19 13:19:31  strk
00751  * Documentation fixes
00752  *
00753  * Revision 1.2  2004/07/08 19:34:49  strk
00754  * Mirrored JTS interface of CoordinateSequence, factory and
00755  * default implementations.
00756  * Added DefaultCoordinateSequenceFactory::instance() function.
00757  *
00758  * Revision 1.1  2004/07/02 13:20:42  strk
00759  * Header files moved under geos/ dir.
00760  *
00761  * Revision 1.22  2004/07/01 14:12:44  strk
00762  *
00763  * Geometry constructors come now in two flavors:
00764  *      - deep-copy args (pass-by-reference)
00765  *      - take-ownership of args (pass-by-pointer)
00766  * Same functionality is available through GeometryFactory,
00767  * including buildGeometry().
00768  *
00769  * Revision 1.21  2004/06/30 20:59:13  strk
00770  * Removed GeoemtryFactory copy from geometry constructors.
00771  * Enforced const-correctness on GeometryFactory arguments.
00772  *
00773  * Revision 1.20  2004/05/27 08:37:16  strk
00774  * Fixed a bug preventing OffsetCurveBuilder point list from being reset.
00775  *
00776  * Revision 1.19  2004/05/26 09:49:03  strk
00777  * PlanarGraph made local to ::buffer instead of Class private.
00778  *
00779  * Revision 1.18  2004/05/07 07:57:27  strk
00780  * Added missing EdgeNodingValidator to build scripts.
00781  * Changed SegmentString constructor back to its original form
00782  * (takes const void *), implemented local tracking of "contexts"
00783  * in caller objects for proper destruction.
00784  *
00785  * Revision 1.17  2004/05/05 16:57:48  strk
00786  * Rewritten static cga allocation to avoid copy constructor calls.
00787  *
00788  * Revision 1.16  2004/05/05 10:54:48  strk
00789  * Removed some private static heap explicit allocation, less cleanup done by
00790  * the unloader.
00791  *
00792  * Revision 1.15  2004/05/03 10:43:42  strk
00793  * Exception specification considered harmful - left as comment.
00794  *
00795  * Revision 1.14  2004/04/30 09:15:28  strk
00796  * Enlarged exception specifications to allow for AssertionFailedException.
00797  * Added missing initializers.
00798  *
00799  * Revision 1.13  2004/04/23 00:02:18  strk
00800  * const-correctness changes
00801  *
00802  * Revision 1.12  2004/04/20 10:58:04  strk
00803  * More memory leaks removed.
00804  *
00805  * Revision 1.11  2004/04/19 15:14:45  strk
00806  * Added missing virtual destructor in SpatialIndex class.
00807  * Memory leaks fixes. Const and throw specifications added.
00808  *
00809  * Revision 1.10  2004/04/19 12:51:01  strk
00810  * Memory leaks fixes. Throw specifications added.
00811  *
00812  * Revision 1.9  2004/04/15 14:00:30  strk
00813  * Added new cleanup to Unload::Release
00814  *
00815  * Revision 1.8  2004/04/10 08:40:01  ybychkov
00816  * "operation/buffer" upgraded to JTS 1.4
00817  *
00818  * Revision 1.7  2004/03/01 22:04:59  strk
00819  * applied const correctness changes by Manuel Prieto Villegas <ManuelPrietoVillegas@telefonica.net>
00820  *
00821  * Revision 1.6  2003/11/07 01:23:42  pramsey
00822  * Add standard CVS headers licence notices and copyrights to all cpp and h
00823  * files.
00824  *
00825  * Revision 1.5  2003/11/06 18:46:34  strk
00826  * Added throw specification for BufferOp's ::buildSubgraphs() 
00827  * and ::computeBuffer()
00828  *
00829  **********************************************************************/
00830 

Generated on Mon Aug 6 22:08:23 2007 for GEOS by  doxygen 1.4.7