opOverlay.h

00001 /**********************************************************************
00002  * $Id: opOverlay.h,v 1.8.2.1 2005/06/28 01:07:11 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 
00017 #ifndef GEOS_OPOVERLAY_H
00018 #define GEOS_OPOVERLAY_H
00019 
00020 #include <memory>
00021 #include <string>
00022 #include <vector>
00023 #include <set>
00024 #include <map>
00025 #include <geos/platform.h>
00026 #include <geos/operation.h>
00027 #include <geos/geomgraph.h>
00028 #include <geos/geosAlgorithm.h>
00029 
00030 using namespace std;
00031 
00032 namespace geos {
00033 
00034 class ElevationMatrixCell {
00035 public:
00036         ElevationMatrixCell();
00037         ~ElevationMatrixCell();
00038         void add(const Coordinate &c);
00039         void add(double z);
00040         double getAvg(void) const;
00041         double getTotal(void) const;
00042         string print() const;
00043 private:
00044         set<double>zvals;
00045         double ztot;
00046 };
00047 
00048 /*
00049  */
00050 class ElevationMatrix {
00051 public:
00052         ElevationMatrix(const Envelope &extent, unsigned int rows,
00053                 unsigned int cols);
00054         ~ElevationMatrix();
00055         void add(const Geometry *geom);
00056         void elevate(Geometry *geom) const;
00057         // set Z value for each cell w/out one
00058         double getAvgElevation() const;
00059         ElevationMatrixCell &getCell(const Coordinate &c);
00060         const ElevationMatrixCell &getCell(const Coordinate &c) const;
00061         string print() const;
00062 private:
00063         void add(const CoordinateSequence *cs);
00064         void add(const Coordinate &c);
00065         Envelope env;
00066         unsigned int cols;
00067         unsigned int rows;
00068         double cellwidth;
00069         double cellheight;
00070         mutable bool avgElevationComputed;
00071         mutable double avgElevation;
00072         vector<ElevationMatrixCell>cells;
00073 };
00074 
00075 class ElevationMatrixFilter: public CoordinateFilter
00076 {
00077 public:
00078         ElevationMatrixFilter(const ElevationMatrix *em);
00079         ~ElevationMatrixFilter();
00080         void filter_rw(Coordinate *c);
00081         void filter_ro(const Coordinate *c) {};
00082 private:
00083         const ElevationMatrix *em;
00084         double avgElevation;
00085 };
00086 
00087 /*
00088  * Computes the overlay of two {@link Geometry}s.  The overlay
00089  * can be used to determine any boolean combination of the geometries.
00090  */
00091 class OverlayOp: public GeometryGraphOperation {
00092 
00093 public:
00094 
00095         /*
00096          * The spatial functions supported by this class.
00097          * These operations implement various boolean combinations of
00098          * the resultants of the overlay.
00099          */
00100         enum {
00101                 INTERSECTION=1,
00102                 UNION,
00103                 DIFFERENCE,
00104                 SYMDIFFERENCE
00105         };
00106 
00107         static Geometry* overlayOp(const Geometry *geom0, const Geometry *geom1,int opCode); //throw(TopologyException *);
00108 
00109         static bool isResultOfOp(Label *label,int opCode);
00110 
00111         /*
00112          * This method will handle arguments of Location.NULL correctly
00113          *
00114          * @return true if the locations correspond to the opCode
00115          */
00116         static bool isResultOfOp(int loc0,int loc1,int opCode);
00117 
00118         OverlayOp(const Geometry *g0, const Geometry *g1);
00119 
00120         virtual ~OverlayOp();
00121 
00122         Geometry* getResultGeometry(int funcCode);
00123                 // throw(TopologyException *);
00124 
00125         PlanarGraph* getGraph();
00126 
00127         /*
00128          * This method is used to decide if a point node should be included
00129          * in the result or not.
00130          *
00131          * @return true if the coord point is covered by a result Line
00132          * or Area geometry
00133          */
00134         bool isCoveredByLA(const Coordinate& coord);
00135 
00136         /*
00137          * This method is used to decide if an L edge should be included
00138          * in the result or not.
00139          *
00140          * @return true if the coord point is covered by a result Area geometry
00141          */
00142         bool isCoveredByA(const Coordinate& coord);
00143 
00144         /*
00145          * @return true if the coord is located in the interior or boundary of
00146          * a geometry in the list.
00147          */
00148 
00149 protected:
00150 
00151         /*
00152          * Insert an edge from one of the noded input graphs.
00153          * Checks edges that are inserted to see if an
00154          * identical edge already exists.
00155          * If so, the edge is not inserted, but its label is merged
00156          * with the existing edge.
00157          */
00158         void insertUniqueEdge(Edge *e);
00159 
00160 private:
00161         PointLocator *ptLocator;
00162         const GeometryFactory *geomFact;
00163         Geometry *resultGeom;
00164         PlanarGraph *graph;
00165         EdgeList *edgeList;
00166         vector<Polygon*> *resultPolyList;
00167         vector<LineString*> *resultLineList;
00168         vector<Point*> *resultPointList;
00169         void computeOverlay(int opCode); // throw(TopologyException *);
00170         void insertUniqueEdges(vector<Edge*> *edges);
00171 
00172         /*
00173          * If either of the GeometryLocations for the existing label is
00174          * exactly opposite to the one in the labelToMerge,
00175          * this indicates a dimensional collapse has happened.
00176          * In this case, convert the label for that Geometry to a Line label
00177          */
00178         //Not needed
00179         //void checkDimensionalCollapse(Label labelToMerge, Label existingLabel);
00180         /*
00181          * Update the labels for edges according to their depths.
00182          * For each edge, the depths are first normalized.
00183          * Then, if the depths for the edge are equal,
00184          * this edge must have collapsed into a line edge.
00185          * If the depths are not equal, update the label
00186          * with the locations corresponding to the depths
00187          * (i.e. a depth of 0 corresponds to a Location of EXTERIOR,
00188          * a depth of 1 corresponds to INTERIOR)
00189          */
00190         void computeLabelsFromDepths();
00191 
00192         /*
00193          * If edges which have undergone dimensional collapse are found,
00194          * replace them with a new edge which is a L edge
00195          */
00196         void replaceCollapsedEdges();
00197 
00198         /*
00199          * Copy all nodes from an arg geometry into this graph.
00200          * The node label in the arg geometry overrides any previously
00201          * computed label for that argIndex.
00202          * (E.g. a node may be an intersection node with
00203          * a previously computed label of BOUNDARY,
00204          * but in the original arg Geometry it is actually
00205          * in the interior due to the Boundary Determination Rule)
00206          */
00207         void copyPoints(int argIndex);
00208 
00209         /*
00210          * Compute initial labelling for all DirectedEdges at each node.
00211          * In this step, DirectedEdges will acquire a complete labelling
00212          * (i.e. one with labels for both Geometries)
00213          * only if they
00214          * are incident on a node which has edges for both Geometries
00215          */
00216         void computeLabelling(); // throw(TopologyException *);
00217 
00218         /*
00219          * For nodes which have edges from only one Geometry incident on them,
00220          * the previous step will have left their dirEdges with no
00221          * labelling for the other Geometry. 
00222          * However, the sym dirEdge may have a labelling for the other
00223          * Geometry, so merge the two labels.
00224          */
00225         void mergeSymLabels();
00226 
00227         void updateNodeLabelling();
00228 
00229         /*
00230          * Incomplete nodes are nodes whose labels are incomplete.
00231          * (e.g. the location for one Geometry is NULL).
00232          * These are either isolated nodes,
00233          * or nodes which have edges from only a single Geometry incident
00234          * on them.
00235          *
00236          * Isolated nodes are found because nodes in one graph which
00237          * don't intersect nodes in the other are not completely
00238          * labelled by the initial process of adding nodes to the nodeList.
00239          * To complete the labelling we need to check for nodes that
00240          * lie in the interior of edges, and in the interior of areas.
00241          * 
00242          * When each node labelling is completed, the labelling of the
00243          * incident edges is updated, to complete their labelling as well.
00244          */
00245         void labelIncompleteNodes();
00246 
00247         /*
00248          * Label an isolated node with its relationship to the target geometry.
00249          */
00250         void labelIncompleteNode(Node *n,int targetIndex);
00251 
00252         /*
00253          * Find all edges whose label indicates that they are in the result
00254          * area(s), according to the operation being performed. 
00255          * Since we want polygon shells to be
00256          * oriented CW, choose dirEdges with the interior of the result
00257          * on the RHS.
00258          * Mark them as being in the result.
00259          * Interior Area edges are the result of dimensional collapses.
00260          * They do not form part of the result area boundary.
00261          */
00262         void findResultAreaEdges(int opCode);
00263 
00264         /*
00265          * If both a dirEdge and its sym are marked as being in the result,
00266          * cancel them out.
00267          */
00268         void cancelDuplicateResultEdges();
00269 
00270         bool isCovered(const Coordinate& coord,vector<Geometry*> *geomList);
00271         bool isCovered(const Coordinate& coord,vector<Polygon*> *geomList);
00272         bool isCovered(const Coordinate& coord,vector<LineString*> *geomList);
00273 
00274         /*
00275          * Build a Geometry containing all Geometries in the given vectors.
00276          * Takes element's ownership, vector control is left to caller. 
00277          */
00278         Geometry* computeGeometry(vector<Point*> *nResultPointList,
00279                               vector<LineString*> *nResultLineList,
00280                               vector<Polygon*> *nResultPolyList);
00281 
00282         /* Caches for memory management */
00283         vector<Edge *>dupEdges;
00284 
00285         /*
00286          * Merge Z values of node with those of the segment or vertex in
00287          * the given Polygon it is on.
00288          */
00289         int OverlayOp::mergeZ(Node *n, const Polygon *poly) const;
00290 
00291         /*
00292          * Merge Z values of node with those of the segment or vertex in
00293          * the given LineString it is on.
00294          * @returns 1 if an intersection is found, 0 otherwise.
00295          */
00296         int OverlayOp::mergeZ(Node *n, const LineString *line) const;
00297 
00298         /*
00299          * Average Z of input geometries
00300          */
00301         double avgz[2];
00302         bool avgzcomputed[2];
00303 
00304         double getAverageZ(int targetIndex);
00305         static double getAverageZ(const Polygon *poly);
00306 
00307         ElevationMatrix *elevationMatrix;
00308 
00309 };
00310 
00311 /*
00312  * A ring of {@link Edge}s with the property that no node
00313  * has degree greater than 2.  These are the form of rings required
00314  * to represent polygons under the OGC SFS spatial data model.
00315  *
00316  * @see com.vividsolutions.jts.operation.overlay.MaximalEdgeRing
00317  */
00318 class MinimalEdgeRing: public EdgeRing {
00319 public:
00320         MinimalEdgeRing(DirectedEdge *start, const GeometryFactory *geometryFactory,CGAlgorithms *cga);
00321         virtual ~MinimalEdgeRing();
00322         DirectedEdge* getNext(DirectedEdge *de);
00323         void setEdgeRing(DirectedEdge *de,EdgeRing *er);
00324 };
00325 
00326 /*
00327  * A ring of {@link edges} which may contain nodes of degree > 2.
00328  * A MaximalEdgeRing may represent two different spatial entities:
00329  * <ul>
00330  * <li>a single polygon possibly containing inversions (if the ring is oriented CW)
00331  * <li>a single hole possibly containing exversions (if the ring is oriented CCW)
00332  * </ul>
00333  * If the MaximalEdgeRing represents a polygon,
00334  * the interior of the polygon is strongly connected.
00335  * <p>
00336  * These are the form of rings used to define polygons under some spatial data models.
00337  * However, under the OGC SFS model, {@link MinimalEdgeRings} are required.
00338  * A MaximalEdgeRing can be converted to a list of MinimalEdgeRings using the
00339  * {@link #buildMinimalRings() } method.
00340  *
00341  * @see com.vividsolutions.jts.operation.overlay.MinimalEdgeRing
00342  */
00343 
00344 class MaximalEdgeRing: public EdgeRing {
00345 public:
00346         MaximalEdgeRing(DirectedEdge *start, const GeometryFactory *geometryFactory, CGAlgorithms *cga);
00347         virtual ~MaximalEdgeRing();
00348         DirectedEdge* getNext(DirectedEdge *de);
00349         void setEdgeRing(DirectedEdge* de,EdgeRing* er);
00350         vector<MinimalEdgeRing*>* buildMinimalRings();
00351         void linkDirectedEdgesForMinimalEdgeRings();
00352 };
00353 
00354 /*
00355  * Constructs {@link Point}s from the nodes of an overlay graph.
00356  */
00357 class PointBuilder {
00358 private:
00359 
00360         OverlayOp *op;
00361         const GeometryFactory *geometryFactory;
00362         void extractNonCoveredResultNodes(int opCode);
00363 
00364         /*
00365          * Converts non-covered nodes to Point objects and adds them to
00366          * the result.
00367          *
00368          * A node is covered if it is contained in another element Geometry
00369          * with higher dimension (e.g. a node point might be contained in
00370          * a polygon, in which case the point can be eliminated from
00371          * the result).
00372          *
00373          * @param n the node to test
00374          */
00375         void filterCoveredNodeToPoint(const Node *);
00376 
00377         vector<Point*> *resultPointList;
00378 
00379 public:
00380 
00381         PointBuilder(OverlayOp *newOp,
00382                 const GeometryFactory *newGeometryFactory,
00383                 PointLocator *newPtLocator=NULL);
00384 
00385         /*
00386          * @return a list of the Points in the result of the specified
00387          * overlay operation
00388          */
00389         vector<Point*>* build(int opCode);
00390 };
00391 
00392 /*
00393  * Forms JTS LineStrings out of a the graph of {@link DirectedEdge}s
00394  * created by an {@link OverlayOp}.
00395  *
00396  */
00397 class LineBuilder {
00398 public:
00399         LineBuilder(OverlayOp *newOp, const GeometryFactory *newGeometryFactory, PointLocator *newPtLocator);
00400         ~LineBuilder();
00404         vector<LineString*>* build(int opCode);
00412         void collectLineEdge(DirectedEdge *de,int opCode,vector<Edge*>* edges);
00423         void collectBoundaryTouchEdge(DirectedEdge *de,int opCode,vector<Edge*>* edges);
00424 private:
00425         OverlayOp *op;
00426         const GeometryFactory *geometryFactory;
00427         PointLocator *ptLocator;
00428         vector<Edge*>* lineEdgesList;
00429         vector<LineString*>* resultLineList;
00430         void findCoveredLineEdges();
00431         void collectLines(int opCode);
00432         void buildLines(int opCode);
00433         void labelIsolatedLines(vector<Edge*> *edgesList);
00437         void labelIsolatedLine(Edge *e,int targetIndex);
00438 
00439         /*
00440          * If the given CoordinateSequence has mixed 3d/2d vertexes
00441          * set Z for all vertexes missing it.
00442          * The Z value is interpolated between 3d vertexes and copied
00443          * from a 3d vertex to the end.
00444          */
00445         void LineBuilder::propagateZ(CoordinateSequence *cs);
00446 };
00447 
00448 /*
00449  * Forms {@link Polygon}s out of a graph of {@link DirectedEdge}s.
00450  * The edges to use are marked as being in the result Area.
00451  * <p>
00452  *
00453  */
00454 class PolygonBuilder {
00455 public:
00456         PolygonBuilder(const GeometryFactory *newGeometryFactory, CGAlgorithms *newCga);
00457         ~PolygonBuilder();
00463         void add(PlanarGraph *graph); // throw(TopologyException *);
00469         void add(vector<DirectedEdge*> *dirEdges,vector<Node*> *nodes); // throw(TopologyException *);
00470         vector<Geometry*>* getPolygons();
00471         bool containsPoint(Coordinate& p);
00472 private:
00473         const GeometryFactory *geometryFactory;
00474         CGAlgorithms *cga;
00475 //      List dirEdgeList; //Doesn't seem to be used at all
00476 //      NodeMap *nodes;
00477         vector<EdgeRing*> *shellList;
00481         vector<MaximalEdgeRing*>* buildMaximalEdgeRings(vector<DirectedEdge*> *dirEdges);
00482         vector<MaximalEdgeRing*>* buildMinimalEdgeRings(vector<MaximalEdgeRing*> *maxEdgeRings,
00483                                                                                                 vector<EdgeRing*> *newShellList,
00484                                                                                                 vector<EdgeRing*> *freeHoleList);
00495         EdgeRing* findShell(vector<MinimalEdgeRing*>* minEdgeRings);
00507         void placePolygonHoles(EdgeRing *shell,vector<MinimalEdgeRing*> *minEdgeRings);
00515         void sortShellsAndHoles(vector<MaximalEdgeRing*> *edgeRings,
00516                                                                                                 vector<EdgeRing*> *newShellList,
00517                                                                                                 vector<EdgeRing*> *freeHoleList);
00529         void placeFreeHoles(vector<EdgeRing*>* newShellList, vector<EdgeRing*> *freeHoleList);
00544         EdgeRing* findEdgeRingContaining(EdgeRing *testEr,vector<EdgeRing*> *newShellList);
00545         vector<Geometry*>* computePolygons(vector<EdgeRing*> *newShellList);
00551 };
00552 
00553 
00554 /*
00555  * Creates nodes for use in the {@link PlanarGraph}s constructed during
00556  * overlay operations.
00557  *
00558  */
00559 class OverlayNodeFactory: public NodeFactory {
00560 public:
00561 //      OverlayNodeFactory() {};
00562         Node* createNode(Coordinate coord);
00563 };
00564 
00565 /*
00566  * Nodes a set of edges.
00567  * Takes one or more sets of edges and constructs a
00568  * new set of edges consisting of all the split edges created by
00569  * noding the input edges together
00570  */
00571 class EdgeSetNoder {
00572 private:
00573         LineIntersector *li;
00574         vector<Edge*>* inputEdges;
00575 public:
00576         EdgeSetNoder(LineIntersector *newLi);
00577         ~EdgeSetNoder();
00578         void addEdges(vector<Edge*> *edges);
00579         vector<Edge*>* getNodedEdges();
00580 };
00581 
00582 
00583 } // namespace geos
00584 
00585 #endif
00586 
00587 /**********************************************************************
00588  * $Log: opOverlay.h,v $
00589  * Revision 1.8.2.1  2005/06/28 01:07:11  strk
00590  * improved extraction of result points in overlay op
00591  *
00592  * Revision 1.8  2004/12/08 13:54:43  strk
00593  * gcc warnings checked and fixed, general cleanups.
00594  *
00595  * Revision 1.7  2004/11/23 16:22:49  strk
00596  * Added ElevationMatrix class and components to do post-processing draping of overlayed geometries.
00597  *
00598  * Revision 1.6  2004/11/22 15:51:52  strk
00599  * Added interpolation of containing geometry's average Z for point_in_poly case.
00600  *
00601  * Revision 1.5  2004/11/20 18:17:26  strk
00602  * Added Z propagation for overlay lines output.
00603  *
00604  * Revision 1.4  2004/11/20 17:16:10  strk
00605  * Handled Z merging for point on polygon boundary case.
00606  *
00607  * Revision 1.3  2004/10/21 22:29:54  strk
00608  * Indentation changes and some more COMPUTE_Z rules
00609  *
00610  * Revision 1.2  2004/07/19 13:19:31  strk
00611  * Documentation fixes
00612  *
00613  * Revision 1.1  2004/07/02 13:20:42  strk
00614  * Header files moved under geos/ dir.
00615  *
00616  * Revision 1.18  2004/07/01 14:12:44  strk
00617  *
00618  * Geometry constructors come now in two flavors:
00619  *      - deep-copy args (pass-by-reference)
00620  *      - take-ownership of args (pass-by-pointer)
00621  * Same functionality is available through GeometryFactory,
00622  * including buildGeometry().
00623  *
00624  * Revision 1.17  2004/06/30 20:59:13  strk
00625  * Removed GeoemtryFactory copy from geometry constructors.
00626  * Enforced const-correctness on GeometryFactory arguments.
00627  *
00628  * Revision 1.16  2004/05/03 10:43:42  strk
00629  * Exception specification considered harmful - left as comment.
00630  *
00631  * Revision 1.15  2004/04/10 08:40:01  ybychkov
00632  * "operation/buffer" upgraded to JTS 1.4
00633  *
00634  * Revision 1.14  2004/03/29 06:59:24  ybychkov
00635  * "noding/snapround" package ported (JTS 1.4);
00636  * "operation", "operation/valid", "operation/relate" and "operation/overlay" upgraded to JTS 1.4;
00637  * "geom" partially upgraded.
00638  *
00639  * Revision 1.13  2004/03/19 09:48:45  ybychkov
00640  * "geomgraph" and "geomgraph/indexl" upgraded to JTS 1.4
00641  *
00642  * Revision 1.12  2003/11/12 18:02:56  strk
00643  * Added throw specification. Fixed leaks on exceptions.
00644  *
00645  * Revision 1.11  2003/11/12 16:14:56  strk
00646  * Added some more throw specifications and cleanup on exception (leaks removed).
00647  *
00648  * Revision 1.10  2003/11/07 01:23:42  pramsey
00649  * Add standard CVS headers licence notices and copyrights to all cpp and h
00650  * files.
00651  *
00652  *
00653  **********************************************************************/

Generated on Sun Dec 11 18:28:29 2005 for GEOS by  doxygen 1.4.5