opOverlay.h

00001 /**********************************************************************
00002  * $Id: opOverlay.h,v 1.8.2.1.2.1 2005/11/30 11:18:07 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 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 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 DirectedEdge
00394  * created by an OverlayOp.
00395  *
00396  */
00397 class LineBuilder {
00398 public:
00399         LineBuilder(OverlayOp *newOp,
00400                 const GeometryFactory *newGeometryFactory,
00401                 PointLocator *newPtLocator);
00402 
00403         ~LineBuilder();
00404 
00405         /*
00406          * @return a list of the LineStrings in the result of the
00407          * specified overlay operation
00408          */
00409         vector<LineString*>* build(int opCode);
00410 
00411         /*
00412          * Find and mark L edges which are "covered" by the result area
00413          * (if any).
00414          * L edges at nodes which also have A edges can be checked by
00415          * checking their depth at that node.
00416          * L edges at nodes which do not have A edges can be checked by
00417          * doing a point-in-polygon test with the previously computed
00418          * result areas.
00419          */
00420         void collectLineEdge(DirectedEdge *de,int opCode,vector<Edge*>* edges);
00421 
00422         /*
00423          * Collect edges from Area inputs which should be in the result but
00424          * which have not been included in a result area.
00425          * This happens ONLY:
00426          * <ul>
00427          * <li>during an intersection when the boundaries of two
00428          * areas touch in a line segment
00429          * <li> OR as a result of a dimensional collapse.
00430          * </ul>
00431          */
00432         void collectBoundaryTouchEdge(DirectedEdge *de,int opCode,vector<Edge*>* edges);
00433 
00434 private:
00435         OverlayOp *op;
00436         const GeometryFactory *geometryFactory;
00437         PointLocator *ptLocator;
00438         vector<Edge*>* lineEdgesList;
00439         vector<LineString*>* resultLineList;
00440         void findCoveredLineEdges();
00441         void collectLines(int opCode);
00442         void buildLines(int opCode);
00443         void labelIsolatedLines(vector<Edge*> *edgesList);
00444 
00445         /*
00446          * Label an isolated node with its relationship to the target geometry.
00447          */
00448         void labelIsolatedLine(Edge *e,int targetIndex);
00449 
00450         /*
00451          * If the given CoordinateSequence has mixed 3d/2d vertexes
00452          * set Z for all vertexes missing it.
00453          * The Z value is interpolated between 3d vertexes and copied
00454          * from a 3d vertex to the end.
00455          */
00456         void propagateZ(CoordinateSequence *cs);
00457 };
00458 
00459 /*
00460  * Forms {@link Polygon}s out of a graph of {@link DirectedEdge}s.
00461  * The edges to use are marked as being in the result Area.
00462  * <p>
00463  *
00464  */
00465 class PolygonBuilder {
00466 public:
00467         PolygonBuilder(const GeometryFactory *newGeometryFactory, CGAlgorithms *newCga);
00468         ~PolygonBuilder();
00474         void add(PlanarGraph *graph); // throw(TopologyException *);
00480         void add(vector<DirectedEdge*> *dirEdges,vector<Node*> *nodes); // throw(TopologyException *);
00481         vector<Geometry*>* getPolygons();
00482         bool containsPoint(Coordinate& p);
00483 private:
00484         const GeometryFactory *geometryFactory;
00485         CGAlgorithms *cga;
00486 //      List dirEdgeList; //Doesn't seem to be used at all
00487 //      NodeMap *nodes;
00488         vector<EdgeRing*> *shellList;
00492         vector<MaximalEdgeRing*>* buildMaximalEdgeRings(vector<DirectedEdge*> *dirEdges);
00493         vector<MaximalEdgeRing*>* buildMinimalEdgeRings(vector<MaximalEdgeRing*> *maxEdgeRings,
00494                                                                                                 vector<EdgeRing*> *newShellList,
00495                                                                                                 vector<EdgeRing*> *freeHoleList);
00506         EdgeRing* findShell(vector<MinimalEdgeRing*>* minEdgeRings);
00518         void placePolygonHoles(EdgeRing *shell,vector<MinimalEdgeRing*> *minEdgeRings);
00526         void sortShellsAndHoles(vector<MaximalEdgeRing*> *edgeRings,
00527                                                                                                 vector<EdgeRing*> *newShellList,
00528                                                                                                 vector<EdgeRing*> *freeHoleList);
00540         void placeFreeHoles(vector<EdgeRing*>* newShellList, vector<EdgeRing*> *freeHoleList);
00555         EdgeRing* findEdgeRingContaining(EdgeRing *testEr,vector<EdgeRing*> *newShellList);
00556         vector<Geometry*>* computePolygons(vector<EdgeRing*> *newShellList);
00562 };
00563 
00564 
00565 /*
00566  * Creates nodes for use in the {@link PlanarGraph}s constructed during
00567  * overlay operations.
00568  *
00569  */
00570 class OverlayNodeFactory: public NodeFactory {
00571 public:
00572 //      OverlayNodeFactory() {};
00573         Node* createNode(Coordinate coord);
00574 };
00575 
00576 /*
00577  * Nodes a set of edges.
00578  * Takes one or more sets of edges and constructs a
00579  * new set of edges consisting of all the split edges created by
00580  * noding the input edges together
00581  */
00582 class EdgeSetNoder {
00583 private:
00584         LineIntersector *li;
00585         vector<Edge*>* inputEdges;
00586 public:
00587         EdgeSetNoder(LineIntersector *newLi);
00588         ~EdgeSetNoder();
00589         void addEdges(vector<Edge*> *edges);
00590         vector<Edge*>* getNodedEdges();
00591 };
00592 
00593 
00594 } // namespace geos
00595 
00596 #endif
00597 
00598 /**********************************************************************
00599  * $Log: opOverlay.h,v $
00600  * Revision 1.8.2.1.2.1  2005/11/30 11:18:07  strk
00601  * Fixed doxygen warnings
00602  *
00603  * Revision 1.8.2.1  2005/06/28 01:07:11  strk
00604  * improved extraction of result points in overlay op
00605  *
00606  * Revision 1.8  2004/12/08 13:54:43  strk
00607  * gcc warnings checked and fixed, general cleanups.
00608  *
00609  * Revision 1.7  2004/11/23 16:22:49  strk
00610  * Added ElevationMatrix class and components to do post-processing draping of overlayed geometries.
00611  *
00612  * Revision 1.6  2004/11/22 15:51:52  strk
00613  * Added interpolation of containing geometry's average Z for point_in_poly case.
00614  *
00615  * Revision 1.5  2004/11/20 18:17:26  strk
00616  * Added Z propagation for overlay lines output.
00617  *
00618  * Revision 1.4  2004/11/20 17:16:10  strk
00619  * Handled Z merging for point on polygon boundary case.
00620  *
00621  * Revision 1.3  2004/10/21 22:29:54  strk
00622  * Indentation changes and some more COMPUTE_Z rules
00623  *
00624  * Revision 1.2  2004/07/19 13:19:31  strk
00625  * Documentation fixes
00626  *
00627  * Revision 1.1  2004/07/02 13:20:42  strk
00628  * Header files moved under geos/ dir.
00629  *
00630  * Revision 1.18  2004/07/01 14:12:44  strk
00631  *
00632  * Geometry constructors come now in two flavors:
00633  *      - deep-copy args (pass-by-reference)
00634  *      - take-ownership of args (pass-by-pointer)
00635  * Same functionality is available through GeometryFactory,
00636  * including buildGeometry().
00637  *
00638  * Revision 1.17  2004/06/30 20:59:13  strk
00639  * Removed GeoemtryFactory copy from geometry constructors.
00640  * Enforced const-correctness on GeometryFactory arguments.
00641  *
00642  * Revision 1.16  2004/05/03 10:43:42  strk
00643  * Exception specification considered harmful - left as comment.
00644  *
00645  * Revision 1.15  2004/04/10 08:40:01  ybychkov
00646  * "operation/buffer" upgraded to JTS 1.4
00647  *
00648  * Revision 1.14  2004/03/29 06:59:24  ybychkov
00649  * "noding/snapround" package ported (JTS 1.4);
00650  * "operation", "operation/valid", "operation/relate" and "operation/overlay" upgraded to JTS 1.4;
00651  * "geom" partially upgraded.
00652  *
00653  * Revision 1.13  2004/03/19 09:48:45  ybychkov
00654  * "geomgraph" and "geomgraph/indexl" upgraded to JTS 1.4
00655  *
00656  * Revision 1.12  2003/11/12 18:02:56  strk
00657  * Added throw specification. Fixed leaks on exceptions.
00658  *
00659  * Revision 1.11  2003/11/12 16:14:56  strk
00660  * Added some more throw specifications and cleanup on exception (leaks removed).
00661  *
00662  * Revision 1.10  2003/11/07 01:23:42  pramsey
00663  * Add standard CVS headers licence notices and copyrights to all cpp and h
00664  * files.
00665  *
00666  *
00667  **********************************************************************/

Generated on Tue Jan 9 00:13:00 2007 for GEOS by  doxygen 1.5.1