Main Page | Namespace List | Class Hierarchy | Class List | Directories | File List | Namespace Members | Class Members

opBuffer.h

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

Generated on Sat May 28 11:24:08 2005 for GEOS by  doxygen 1.4.2