/********************************************************************** * $Id: opRelate.h,v 1.3 2004/07/27 16:35:46 strk Exp $ * * GEOS - Geometry Engine Open Source * http://geos.refractions.net * * Copyright (C) 2001-2002 Vivid Solutions Inc. * * This is free software; you can redistribute and/or modify it under * the terms of the GNU Lesser General Public Licence as published * by the Free Software Foundation.  * See the COPYING file for more information. * ********************************************************************** * $Log: opRelate.h,v $ * Revision 1.3  2004/07/27 16:35:46  strk * Geometry::getEnvelopeInternal() changed to return a const Envelope *. * This should reduce object copies as once computed the envelope of a * geometry remains the same. * * Revision 1.2  2004/07/19 13:19:31  strk * Documentation fixes * * Revision 1.1  2004/07/02 13:20:42  strk * Header files moved under geos/ dir. * * Revision 1.15  2004/03/29 06:59:24  ybychkov * "noding/snapround" package ported (JTS 1.4); * "operation", "operation/valid", "operation/relate" and "operation/overlay" upgraded to JTS 1.4; * "geom" partially upgraded. * * Revision 1.14  2004/03/19 09:48:46  ybychkov * "geomgraph" and "geomgraph/indexl" upgraded to JTS 1.4 * * Revision 1.13  2004/03/01 22:04:59  strk * applied const correctness changes by Manuel Prieto Villegas <ManuelPrietoVillegas@telefonica.net> * * Revision 1.12  2003/11/07 01:23:42  pramsey * Add standard CVS headers licence notices and copyrights to all cpp and h * files. * * **********************************************************************/#ifndef GEOS_OPRELATE_H#define GEOS_OPRELATE_H#include <memory>#include <string>#include <vector>#include <geos/platform.h>#include <geos/operation.h>#include <geos/geomgraph.h>#include <geos/geosAlgorithm.h>namespace geos {/* * Represents a node in the topological graph used to compute spatial * relationships. */class RelateNode: public Node {public:	RelateNode(Coordinate& coord,EdgeEndStar *edges);	virtual ~RelateNode();	void updateIMFromEdges(IntersectionMatrix *im);protected:	void computeIM(IntersectionMatrix *im);};/* * Computes the EdgeEnd objects which arise from a noded Edge. */class EdgeEndBuilder {public:	EdgeEndBuilder();	vector<EdgeEnd*> *computeEdgeEnds(vector<Edge*> *edges);	void computeEdgeEnds(Edge *edge,vector<EdgeEnd*> *l);protected:	void createEdgeEndForPrev(Edge *edge,vector<EdgeEnd*> *l,EdgeIntersection *eiCurr,EdgeIntersection *eiPrev);	void createEdgeEndForNext(Edge *edge,vector<EdgeEnd*> *l,EdgeIntersection *eiCurr,EdgeIntersection *eiNext);};/* * Contains all EdgeEnd objectss which start at the same point * and are parallel. */class EdgeEndBundle: public EdgeEnd {public:	EdgeEndBundle(EdgeEnd *e);	virtual ~EdgeEndBundle();	Label *getLabel();//Iterator iterator() //Not needed	vector<EdgeEnd*>* getEdgeEnds();	void insert(EdgeEnd *e);	void computeLabel() ; 	void updateIM(IntersectionMatrix *im);	string print();protected:	vector<EdgeEnd*> *edgeEnds;	void computeLabelOn(int geomIndex);	void computeLabelSides(int geomIndex);	void computeLabelSide(int geomIndex,int side);};/* * An ordered list of EdgeEndBundle objects around a RelateNode. * They are maintained in CCW order (starting with the positive x-axis) * around the node * for efficient lookup and topology building. */class EdgeEndBundleStar: public EdgeEndStar {public:	EdgeEndBundleStar();	virtual ~EdgeEndBundleStar();	void insert(EdgeEnd *e);	void updateIM(IntersectionMatrix *im);};/* * Used by the NodeMap in a RelateNodeGraph to create RelateNode objects. */class RelateNodeFactory: public NodeFactory {public:	Node* createNode(Coordinate coord);};/* * Implements the simple graph of Nodes and EdgeEnd which is all that is * required to determine topological relationships between Geometries. * Also supports building a topological graph of a single Geometry, to * allow verification of valid topology. *  * It is <b>not</b> necessary to create a fully linked * PlanarGraph to determine relationships, since it is sufficient * to know how the Geometries interact locally around the nodes. * In fact, this is not even feasible, since it is not possible to compute * exact intersection points, and hence the topology around those nodes * cannot be computed robustly. * The only Nodes that are created are for improper intersections; * that is, nodes which occur at existing vertices of the Geometries. * Proper intersections (e.g. ones which occur between the interior of * line segments) * have their topology determined implicitly, without creating a Node object * to represent them. * */class RelateNodeGraph {public:	RelateNodeGraph();	virtual ~RelateNodeGraph();//	Iterator getNodeIterator();	map<Coordinate,Node*,CoordLT>* getNodeMap();	void build(GeometryGraph *geomGraph);	void computeIntersectionNodes(GeometryGraph *geomGraph,int argIndex);	void copyNodesAndLabels(GeometryGraph *geomGraph,int argIndex);	void insertEdgeEnds(vector<EdgeEnd*> *ee);private:	NodeMap *nodes;};/* * Computes the topological relationship between two Geometries. * * RelateComputer does not need to build a complete graph structure to compute * the IntersectionMatrix.  The relationship between the geometries can * be computed by simply examining the labelling of edges incident on each node. *  * RelateComputer does not currently support arbitrary GeometryCollections. * This is because GeometryCollections can contain overlapping Polygons. * In order to correct compute relate on overlapping Polygons, they * would first need to be noded and merged (if not explicitly, at least * implicitly). * */class RelateComputer {friend class Unload;public:	RelateComputer();	virtual ~RelateComputer();	RelateComputer(vector<GeometryGraph*> *newArg);	IntersectionMatrix* computeIM();private:	static const LineIntersector* li;	static const PointLocator* ptLocator;	vector<GeometryGraph*> *arg;  // the arg(s) of the operation	NodeMap *nodes;	// this intersection matrix will hold the results compute for the relate	IntersectionMatrix *im;	vector<Edge*> *isolatedEdges;	// the intersection point found (if any)	Coordinate invalidPoint;	void insertEdgeEnds(vector<EdgeEnd*> *ee);	void computeProperIntersectionIM(SegmentIntersector *intersector,IntersectionMatrix *imX);	void copyNodesAndLabels(int argIndex);	void computeIntersectionNodes(int argIndex);	void labelIntersectionNodes(int argIndex);	void computeDisjointIM(IntersectionMatrix *imX);	void labelNodeEdges();	void updateIM(IntersectionMatrix *imX);	void labelIsolatedEdges(int thisIndex,int targetIndex);	void labelIsolatedEdge(Edge *e,int targetIndex, const Geometry *target);	void labelIsolatedNodes();	void labelIsolatedNode(Node *n,int targetIndex);};/* * Implements the relate() operation on Geometry. *  * WARNING: The current implementation of this class will compute a result for * GeometryCollections.  However, the semantics of this operation are * not well-defined and the value returned may not represent * an appropriate notion of relate. */class RelateOp: public GeometryGraphOperation {public:	static IntersectionMatrix* relate(const Geometry *a,const Geometry *b);	RelateOp(const Geometry *g0, const Geometry *g1);	virtual ~RelateOp();	IntersectionMatrix* getIntersectionMatrix();private:	RelateComputer relateComp;};}#endif