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

opOverlay.h

00001 /**********************************************************************
00002  * $Id: opOverlay.h,v 1.2 2004/07/19 13:19:31 strk Exp $
00003  *
00004  * GEOS - Geometry Engine Open Source
00005  * http://geos.refractions.net
00006  *
00007  * Copyright (C) 2001-2002 Vivid Solutions Inc.
00008  *
00009  * This is free software; you can redistribute and/or modify it under
00010  * the terms of the GNU Lesser General Public Licence as published
00011  * by the Free Software Foundation. 
00012  * See the COPYING file for more information.
00013  *
00014  **********************************************************************
00015  * $Log: opOverlay.h,v $
00016  * Revision 1.2  2004/07/19 13:19:31  strk
00017  * Documentation fixes
00018  *
00019  * Revision 1.1  2004/07/02 13:20:42  strk
00020  * Header files moved under geos/ dir.
00021  *
00022  * Revision 1.18  2004/07/01 14:12:44  strk
00023  *
00024  * Geometry constructors come now in two flavors:
00025  *      - deep-copy args (pass-by-reference)
00026  *      - take-ownership of args (pass-by-pointer)
00027  * Same functionality is available through GeometryFactory,
00028  * including buildGeometry().
00029  *
00030  * Revision 1.17  2004/06/30 20:59:13  strk
00031  * Removed GeoemtryFactory copy from geometry constructors.
00032  * Enforced const-correctness on GeometryFactory arguments.
00033  *
00034  * Revision 1.16  2004/05/03 10:43:42  strk
00035  * Exception specification considered harmful - left as comment.
00036  *
00037  * Revision 1.15  2004/04/10 08:40:01  ybychkov
00038  * "operation/buffer" upgraded to JTS 1.4
00039  *
00040  * Revision 1.14  2004/03/29 06:59:24  ybychkov
00041  * "noding/snapround" package ported (JTS 1.4);
00042  * "operation", "operation/valid", "operation/relate" and "operation/overlay" upgraded to JTS 1.4;
00043  * "geom" partially upgraded.
00044  *
00045  * Revision 1.13  2004/03/19 09:48:45  ybychkov
00046  * "geomgraph" and "geomgraph/indexl" upgraded to JTS 1.4
00047  *
00048  * Revision 1.12  2003/11/12 18:02:56  strk
00049  * Added throw specification. Fixed leaks on exceptions.
00050  *
00051  * Revision 1.11  2003/11/12 16:14:56  strk
00052  * Added some more throw specifications and cleanup on exception (leaks removed).
00053  *
00054  * Revision 1.10  2003/11/07 01:23:42  pramsey
00055  * Add standard CVS headers licence notices and copyrights to all cpp and h
00056  * files.
00057  *
00058  *
00059  **********************************************************************/
00060 
00061 
00062 #ifndef GEOS_OPOVERLAY_H
00063 #define GEOS_OPOVERLAY_H
00064 
00065 #include <memory>
00066 #include <string>
00067 #include <vector>
00068 #include <map>
00069 #include <geos/platform.h>
00070 #include <geos/operation.h>
00071 #include <geos/geomgraph.h>
00072 #include <geos/geosAlgorithm.h>
00073 
00074 using namespace std;
00075 
00076 namespace geos {
00077 
00078 /*
00079  * Computes the overlay of two {@link Geometry}s.  The overlay
00080  * can be used to determine any boolean combination of the geometries.
00081  */
00082 class OverlayOp: public GeometryGraphOperation {
00083 public:
00088         enum {
00089                 INTERSECTION=1,
00090                 UNION,
00091                 DIFFERENCE,
00092                 SYMDIFFERENCE
00093         };
00094         static Geometry* overlayOp(const Geometry *geom0, const Geometry *geom1,int opCode); //throw(TopologyException *);
00095         static bool isResultOfOp(Label *label,int opCode);
00101         static bool isResultOfOp(int loc0,int loc1,int opCode);
00102         OverlayOp(const Geometry *g0, const Geometry *g1);
00103         virtual ~OverlayOp();
00104         Geometry* getResultGeometry(int funcCode); // throw(TopologyException *);
00105         PlanarGraph* getGraph();
00111         bool isCoveredByLA(const Coordinate& coord);
00117         bool isCoveredByA(const Coordinate& coord);
00122 protected:
00130         void insertUniqueEdge(Edge *e);
00131 private:
00132         PointLocator *ptLocator;
00133         const GeometryFactory *geomFact;
00134         Geometry *resultGeom;
00135         PlanarGraph *graph;
00136         EdgeList *edgeList;
00137         vector<Polygon*> *resultPolyList;
00138         vector<LineString*> *resultLineList;
00139         vector<Point*> *resultPointList;
00140         void computeOverlay(int opCode); // throw(TopologyException *);
00141         void insertUniqueEdges(vector<Edge*> *edges);
00148         //Not needed
00149         //void checkDimensionalCollapse(Label labelToMerge, Label existingLabel);
00160         void computeLabelsFromDepths();
00165         void replaceCollapsedEdges();
00175         void copyPoints(int argIndex);
00183         void computeLabelling(); // throw(TopologyException *);
00190         void mergeSymLabels();
00191         void updateNodeLabelling();
00207         void labelIncompleteNodes();
00211         void labelIncompleteNode(Node *n,int targetIndex);
00220         void findResultAreaEdges(int opCode);
00225         void cancelDuplicateResultEdges();
00226         bool isCovered(const Coordinate& coord,vector<Geometry*> *geomList);
00227         bool isCovered(const Coordinate& coord,vector<Polygon*> *geomList);
00228         bool isCovered(const Coordinate& coord,vector<LineString*> *geomList);
00229 
00234         Geometry* computeGeometry(vector<Point*> *nResultPointList,
00235                               vector<LineString*> *nResultLineList,
00236                               vector<Polygon*> *nResultPolyList);
00237 };
00238 
00239 /*
00240  * A ring of {@link Edge}s with the property that no node
00241  * has degree greater than 2.  These are the form of rings required
00242  * to represent polygons under the OGC SFS spatial data model.
00243  *
00244  * @see com.vividsolutions.jts.operation.overlay.MaximalEdgeRing
00245  */
00246 class MinimalEdgeRing: public EdgeRing {
00247 public:
00248         MinimalEdgeRing(DirectedEdge *start, const GeometryFactory *geometryFactory,CGAlgorithms *cga);
00249         virtual ~MinimalEdgeRing();
00250         DirectedEdge* getNext(DirectedEdge *de);
00251         void setEdgeRing(DirectedEdge *de,EdgeRing *er);
00252 };
00253 
00254 /*
00255  * A ring of {@link edges} which may contain nodes of degree > 2.
00256  * A MaximalEdgeRing may represent two different spatial entities:
00257  * <ul>
00258  * <li>a single polygon possibly containing inversions (if the ring is oriented CW)
00259  * <li>a single hole possibly containing exversions (if the ring is oriented CCW)
00260  * </ul>
00261  * If the MaximalEdgeRing represents a polygon,
00262  * the interior of the polygon is strongly connected.
00263  * <p>
00264  * These are the form of rings used to define polygons under some spatial data models.
00265  * However, under the OGC SFS model, {@link MinimalEdgeRings} are required.
00266  * A MaximalEdgeRing can be converted to a list of MinimalEdgeRings using the
00267  * {@link #buildMinimalRings() } method.
00268  *
00269  * @see com.vividsolutions.jts.operation.overlay.MinimalEdgeRing
00270  */
00271 
00272 class MaximalEdgeRing: public EdgeRing {
00273 public:
00274         MaximalEdgeRing(DirectedEdge *start, const GeometryFactory *geometryFactory, CGAlgorithms *cga);
00275         virtual ~MaximalEdgeRing();
00276         DirectedEdge* getNext(DirectedEdge *de);
00277         void setEdgeRing(DirectedEdge* de,EdgeRing* er);
00278         vector<MinimalEdgeRing*>* buildMinimalRings();
00279         void linkDirectedEdgesForMinimalEdgeRings();
00280 };
00281 
00282 /*
00283  * Constructs {@link Point}s from the nodes of an overlay graph.
00284  */
00285 class PointBuilder {
00286 private:
00287         OverlayOp *op;
00288         const GeometryFactory *geometryFactory;
00289         PointLocator *ptLocator;
00290         vector<Node*>* collectNodes(int opCode);
00298         vector<Point*>* simplifyPoints(vector<Node*>* resultNodeList);
00299 public:
00300         PointBuilder(OverlayOp *newOp, const GeometryFactory *newGeometryFactory, PointLocator *newPtLocator);
00304         vector<Point*>* build(int opCode);
00305 };
00306 
00307 /*
00308  * Forms JTS LineStrings out of a the graph of {@link DirectedEdge}s
00309  * created by an {@link OverlayOp}.
00310  *
00311  */
00312 class LineBuilder {
00313 public:
00314         LineBuilder(OverlayOp *newOp, const GeometryFactory *newGeometryFactory, PointLocator *newPtLocator);
00315         ~LineBuilder();
00319         vector<LineString*>* build(int opCode);
00327         void collectLineEdge(DirectedEdge *de,int opCode,vector<Edge*>* edges);
00338         void collectBoundaryTouchEdge(DirectedEdge *de,int opCode,vector<Edge*>* edges);
00339 private:
00340         OverlayOp *op;
00341         const GeometryFactory *geometryFactory;
00342         PointLocator *ptLocator;
00343         vector<Edge*>* lineEdgesList;
00344         vector<LineString*>* resultLineList;
00345         void findCoveredLineEdges();
00346         void collectLines(int opCode);
00347         void buildLines(int opCode);
00348         void labelIsolatedLines(vector<Edge*> *edgesList);
00352         void labelIsolatedLine(Edge *e,int targetIndex);
00353 };
00354 
00355 /*
00356  * Forms {@link Polygon}s out of a graph of {@link DirectedEdge}s.
00357  * The edges to use are marked as being in the result Area.
00358  * <p>
00359  *
00360  */
00361 class PolygonBuilder {
00362 public:
00363         PolygonBuilder(const GeometryFactory *newGeometryFactory, CGAlgorithms *newCga);
00364         ~PolygonBuilder();
00370         void add(PlanarGraph *graph); // throw(TopologyException *);
00376         void add(vector<DirectedEdge*> *dirEdges,vector<Node*> *nodes); // throw(TopologyException *);
00377         vector<Geometry*>* getPolygons();
00378         bool containsPoint(Coordinate& p);
00379 private:
00380         const GeometryFactory *geometryFactory;
00381         CGAlgorithms *cga;
00382 //      List dirEdgeList; //Doesn't seem to be used at all
00383 //      NodeMap *nodes;
00384         vector<EdgeRing*> *shellList;
00388         vector<MaximalEdgeRing*>* buildMaximalEdgeRings(vector<DirectedEdge*> *dirEdges);
00389         vector<MaximalEdgeRing*>* buildMinimalEdgeRings(vector<MaximalEdgeRing*> *maxEdgeRings,
00390                                                                                                 vector<EdgeRing*> *newShellList,
00391                                                                                                 vector<EdgeRing*> *freeHoleList);
00402         EdgeRing* findShell(vector<MinimalEdgeRing*>* minEdgeRings);
00414         void placePolygonHoles(EdgeRing *shell,vector<MinimalEdgeRing*> *minEdgeRings);
00422         void sortShellsAndHoles(vector<MaximalEdgeRing*> *edgeRings,
00423                                                                                                 vector<EdgeRing*> *newShellList,
00424                                                                                                 vector<EdgeRing*> *freeHoleList);
00436         void placeFreeHoles(vector<EdgeRing*>* newShellList, vector<EdgeRing*> *freeHoleList);
00451         EdgeRing* findEdgeRingContaining(EdgeRing *testEr,vector<EdgeRing*> *newShellList);
00452         vector<Geometry*>* computePolygons(vector<EdgeRing*> *newShellList);
00458 };
00459 
00460 
00461 /*
00462  * Creates nodes for use in the {@link PlanarGraph}s constructed during
00463  * overlay operations.
00464  *
00465  */
00466 class OverlayNodeFactory: public NodeFactory {
00467 public:
00468 //      OverlayNodeFactory() {};
00469         Node* createNode(Coordinate coord);
00470 };
00471 
00472 /*
00473  * Nodes a set of edges.
00474  * Takes one or more sets of edges and constructs a
00475  * new set of edges consisting of all the split edges created by
00476  * noding the input edges together
00477  */
00478 class EdgeSetNoder {
00479 private:
00480         LineIntersector *li;
00481         vector<Edge*>* inputEdges;
00482 public:
00483         EdgeSetNoder(LineIntersector *newLi);
00484         ~EdgeSetNoder();
00485         void addEdges(vector<Edge*> *edges);
00486         vector<Edge*>* getNodedEdges();
00487 };
00488 }
00489 #endif

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