opRelate.h

00001 /**********************************************************************
00002  * $Id: opRelate.h,v 1.3 2004/07/27 16:35:46 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: opRelate.h,v $
00016  * Revision 1.3  2004/07/27 16:35:46  strk
00017  * Geometry::getEnvelopeInternal() changed to return a const Envelope *.
00018  * This should reduce object copies as once computed the envelope of a
00019  * geometry remains the same.
00020  *
00021  * Revision 1.2  2004/07/19 13:19:31  strk
00022  * Documentation fixes
00023  *
00024  * Revision 1.1  2004/07/02 13:20:42  strk
00025  * Header files moved under geos/ dir.
00026  *
00027  * Revision 1.15  2004/03/29 06:59:24  ybychkov
00028  * "noding/snapround" package ported (JTS 1.4);
00029  * "operation", "operation/valid", "operation/relate" and "operation/overlay" upgraded to JTS 1.4;
00030  * "geom" partially upgraded.
00031  *
00032  * Revision 1.14  2004/03/19 09:48:46  ybychkov
00033  * "geomgraph" and "geomgraph/indexl" upgraded to JTS 1.4
00034  *
00035  * Revision 1.13  2004/03/01 22:04:59  strk
00036  * applied const correctness changes by Manuel Prieto Villegas <ManuelPrietoVillegas@telefonica.net>
00037  *
00038  * Revision 1.12  2003/11/07 01:23:42  pramsey
00039  * Add standard CVS headers licence notices and copyrights to all cpp and h
00040  * files.
00041  *
00042  *
00043  **********************************************************************/
00044 
00045 
00046 #ifndef GEOS_OPRELATE_H
00047 #define GEOS_OPRELATE_H
00048 
00049 #include <memory>
00050 #include <string>
00051 #include <vector>
00052 #include <geos/platform.h>
00053 #include <geos/operation.h>
00054 #include <geos/geomgraph.h>
00055 #include <geos/geosAlgorithm.h>
00056 
00057 namespace geos {
00058 
00059 /*
00060  * Represents a node in the topological graph used to compute spatial
00061  * relationships.
00062  */
00063 class RelateNode: public Node {
00064 public:
00065         RelateNode(Coordinate& coord,EdgeEndStar *edges);
00066         virtual ~RelateNode();
00067         void updateIMFromEdges(IntersectionMatrix *im);
00068 protected:
00069         void computeIM(IntersectionMatrix *im);
00070 };
00071 
00072 /*
00073  * Computes the EdgeEnd objects which arise from a noded Edge.
00074  */
00075 class EdgeEndBuilder {
00076 public:
00077         EdgeEndBuilder();
00078         vector<EdgeEnd*> *computeEdgeEnds(vector<Edge*> *edges);
00079         void computeEdgeEnds(Edge *edge,vector<EdgeEnd*> *l);
00080 protected:
00081         void createEdgeEndForPrev(Edge *edge,vector<EdgeEnd*> *l,EdgeIntersection *eiCurr,EdgeIntersection *eiPrev);
00082         void createEdgeEndForNext(Edge *edge,vector<EdgeEnd*> *l,EdgeIntersection *eiCurr,EdgeIntersection *eiNext);
00083 };
00084 
00085 /*
00086  * Contains all EdgeEnd objectss which start at the same point
00087  * and are parallel.
00088  */
00089 class EdgeEndBundle: public EdgeEnd {
00090 public:
00091         EdgeEndBundle(EdgeEnd *e);
00092         virtual ~EdgeEndBundle();
00093         Label *getLabel();
00094 //Iterator iterator() //Not needed
00095         vector<EdgeEnd*>* getEdgeEnds();
00096         void insert(EdgeEnd *e);
00097         void computeLabel() ; 
00098         void updateIM(IntersectionMatrix *im);
00099         string print();
00100 protected:
00101         vector<EdgeEnd*> *edgeEnds;
00102         void computeLabelOn(int geomIndex);
00103         void computeLabelSides(int geomIndex);
00104         void computeLabelSide(int geomIndex,int side);
00105 };
00106 
00107 /*
00108  * An ordered list of EdgeEndBundle objects around a RelateNode.
00109  * They are maintained in CCW order (starting with the positive x-axis)
00110  * around the node
00111  * for efficient lookup and topology building.
00112  */
00113 class EdgeEndBundleStar: public EdgeEndStar {
00114 public:
00115         EdgeEndBundleStar();
00116         virtual ~EdgeEndBundleStar();
00117         void insert(EdgeEnd *e);
00118         void updateIM(IntersectionMatrix *im);
00119 };
00120 
00121 /*
00122  * Used by the NodeMap in a RelateNodeGraph to create RelateNode objects.
00123  */
00124 class RelateNodeFactory: public NodeFactory {
00125 public:
00126         Node* createNode(Coordinate coord);
00127 };
00128 
00129 /*
00130  * Implements the simple graph of Nodes and EdgeEnd which is all that is
00131  * required to determine topological relationships between Geometries.
00132  * Also supports building a topological graph of a single Geometry, to
00133  * allow verification of valid topology.
00134  * 
00135  * It is <b>not</b> necessary to create a fully linked
00136  * PlanarGraph to determine relationships, since it is sufficient
00137  * to know how the Geometries interact locally around the nodes.
00138  * In fact, this is not even feasible, since it is not possible to compute
00139  * exact intersection points, and hence the topology around those nodes
00140  * cannot be computed robustly.
00141  * The only Nodes that are created are for improper intersections;
00142  * that is, nodes which occur at existing vertices of the Geometries.
00143  * Proper intersections (e.g. ones which occur between the interior of
00144  * line segments)
00145  * have their topology determined implicitly, without creating a Node object
00146  * to represent them.
00147  *
00148  */
00149 class RelateNodeGraph {
00150 public:
00151         RelateNodeGraph();
00152         virtual ~RelateNodeGraph();
00153 //      Iterator getNodeIterator();
00154         map<Coordinate,Node*,CoordLT>* getNodeMap();
00155         void build(GeometryGraph *geomGraph);
00156         void computeIntersectionNodes(GeometryGraph *geomGraph,int argIndex);
00157         void copyNodesAndLabels(GeometryGraph *geomGraph,int argIndex);
00158         void insertEdgeEnds(vector<EdgeEnd*> *ee);
00159 private:
00160         NodeMap *nodes;
00161 };
00162 
00163 /*
00164  * Computes the topological relationship between two Geometries.
00165  *
00166  * RelateComputer does not need to build a complete graph structure to compute
00167  * the IntersectionMatrix.  The relationship between the geometries can
00168  * be computed by simply examining the labelling of edges incident on each node.
00169  * 
00170  * RelateComputer does not currently support arbitrary GeometryCollections.
00171  * This is because GeometryCollections can contain overlapping Polygons.
00172  * In order to correct compute relate on overlapping Polygons, they
00173  * would first need to be noded and merged (if not explicitly, at least
00174  * implicitly).
00175  *
00176  */
00177 class RelateComputer {
00178 friend class Unload;
00179 public:
00180         RelateComputer();
00181         virtual ~RelateComputer();
00182         RelateComputer(vector<GeometryGraph*> *newArg);
00183         IntersectionMatrix* computeIM();
00184 private:
00185         static const LineIntersector* li;
00186         static const PointLocator* ptLocator;
00187         vector<GeometryGraph*> *arg;  // the arg(s) of the operation
00188         NodeMap *nodes;
00189         // this intersection matrix will hold the results compute for the relate
00190         IntersectionMatrix *im;
00191         vector<Edge*> *isolatedEdges;
00192         // the intersection point found (if any)
00193         Coordinate invalidPoint;
00194         void insertEdgeEnds(vector<EdgeEnd*> *ee);
00195         void computeProperIntersectionIM(SegmentIntersector *intersector,IntersectionMatrix *imX);
00196         void copyNodesAndLabels(int argIndex);
00197         void computeIntersectionNodes(int argIndex);
00198         void labelIntersectionNodes(int argIndex);
00199         void computeDisjointIM(IntersectionMatrix *imX);
00200         void labelNodeEdges();
00201         void updateIM(IntersectionMatrix *imX);
00202         void labelIsolatedEdges(int thisIndex,int targetIndex);
00203         void labelIsolatedEdge(Edge *e,int targetIndex, const Geometry *target);
00204         void labelIsolatedNodes();
00205         void labelIsolatedNode(Node *n,int targetIndex);
00206 };
00207 
00208 /*
00209  * Implements the relate() operation on Geometry.
00210  * 
00211  * WARNING: The current implementation of this class will compute a result for
00212  * GeometryCollections.  However, the semantics of this operation are
00213  * not well-defined and the value returned may not represent
00214  * an appropriate notion of relate.
00215  */
00216 class RelateOp: public GeometryGraphOperation {
00217 public:
00218         static IntersectionMatrix* relate(const Geometry *a,const Geometry *b);
00219         RelateOp(const Geometry *g0, const Geometry *g1);
00220         virtual ~RelateOp();
00221         IntersectionMatrix* getIntersectionMatrix();
00222 private:
00223         RelateComputer relateComp;
00224 };
00225 }
00226 
00227 #endif
00228 

Generated on Mon Jan 8 23:49:01 2007 for GEOS by  doxygen 1.5.1