/********************************************************************** * $Id: opPolygonize.h,v 1.7.2.1 2005/05/23 17:23:15 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. * **********************************************************************/#ifndef GEOS_OPPOLYGONIZE_H#define GEOS_OPPOLYGONIZE_H#include <geos/platform.h>#include <geos/planargraph.h>#include <geos/geosAlgorithm.h>#include <geos/geom.h>#include <vector>namespace geos {//using namespace planargraph;/* * An edge of a polygonization graph. * * @version 1.4 */class PolygonizeEdge: public planarEdge {private:	const LineString *line;public:	PolygonizeEdge(const LineString *newLine);	const LineString* getLine();};/* * Represents a ring of PolygonizeDirectedEdge which form * a ring of a polygon.  The ring may be either an outer shell or a hole. */class polygonizeEdgeRing {private:	const GeometryFactory *factory;	static CGAlgorithms cga;	vector<const planarDirectedEdge*> *deList;	// cache the following data for efficiency	LinearRing *ring;	CoordinateSequence *ringPts;	vector<Geometry*> *holes;	/*	 * Computes the list of coordinates which are contained in this ring.	 * The coordinatea are computed once only and cached.	 *	 * @return an array of the Coordinate in this ring	 */	CoordinateSequence* getCoordinates();	static void addEdge(const CoordinateSequence *coords, bool isForward, CoordinateSequence *coordList);public:	/**	 * Find the innermost enclosing shell polygonizeEdgeRing	 * containing the argument polygonizeEdgeRing, if any.	 * The innermost enclosing ring is the <i>smallest</i> enclosing ring.	 * The algorithm used depends on the fact that:	 * 	 * ring A contains ring B iff envelope(ring A) contains envelope(ring B)	 *	 * This routine is only safe to use if the chosen point of the hole	 * is known to be properly contained in a shell	 * (which is guaranteed to be the case if the hole does not touch	 * its shell)	 *	 * @return containing polygonizeEdgeRing, if there is one	 * @return null if no containing polygonizeEdgeRing is found	 */	static polygonizeEdgeRing* findEdgeRingContaining(polygonizeEdgeRing *testEr, vector<polygonizeEdgeRing*> *shellList);	/*	 * \brief	 * Finds a point in a list of points which is not contained in	 * another list of points.	 *	 * @param testPts the CoordinateSequence to test	 * @param pts the CoordinateSequence to test the input points against	 * @return a Coordinate reference from <code>testPts</code> which is	 * not in <code>pts</code>, or <code>Coordinate::nullCoord</code>	 */	static const Coordinate& ptNotInList(const CoordinateSequence *testPts, const CoordinateSequence *pts);	/*	 * Tests whether a given point is in an array of points.	 * Uses a value-based test.	 *	 * @param pt a Coordinate for the test point	 * @param pts an array of Coordinate to test	 * @return <code>true</code> if the point is in the array	 */	static bool isInList(const Coordinate &pt, const CoordinateSequence *pts);	polygonizeEdgeRing(const GeometryFactory *newFactory);	~polygonizeEdgeRing();	/*	 * Adds a DirectedEdge which is known to form part of this ring.	 * @param de the DirectedEdge to add. Ownership to the caller.	 */	void add(const planarDirectedEdge *de);	/*	 * Tests whether this ring is a hole.	 * Due to the way the edges in the polyongization graph are linked,	 * a ring is a hole if it is oriented counter-clockwise.	 * @return <code>true</code> if this ring is a hole	 */	bool isHole();	/*	 * Adds a hole to the polygon formed by this ring.	 * @param hole the LinearRing forming the hole.	 */	void addHole(LinearRing *hole);	/*	 * Computes the Polygon formed by this ring and any contained holes.	 *	 * @return the Polygon formed by this ring and its holes.	 */	Polygon* getPolygon();	/*	 * Tests if the LinearRing ring formed by this edge ring	 * is topologically valid.	 */	bool isValid();	/*	 * Gets the coordinates for this ring as a LineString.	 * Used to return the coordinates in this ring	 * as a valid geometry, when it has been detected that the ring	 * is topologically invalid.	 * @return a LineString containing the coordinates in this ring	 */	LineString* getLineString();	/*	 * Returns this ring as a LinearRing, or null if an Exception	 * occurs while creating it (such as a topology problem).	 * Ownership of ring is retained by the object.	 * Details of problems are written to standard output.	 */	LinearRing* getRingInternal();	/*	 * Returns this ring as a LinearRing taking ownership	 * of it. 	 */	LinearRing* getRingOwnership();};/* * A DirectedEdge of a PolygonizeGraph, which represents * an edge of a polygon formed by the graph. * May be logically deleted from the graph by setting the * <code>marked</code> flag. */class PolygonizeDirectedEdge: public planarDirectedEdge {private:	polygonizeEdgeRing *edgeRing;	PolygonizeDirectedEdge *next;	long label;public:	/*	 * \brief	 * Constructs a directed edge connecting the <code>from</code> node	 * to the <code>to</code> node.	 *	 * @param directionPt	 *    specifies this DirectedEdge's direction (given by an imaginary	 *    line from the <code>from</code> node to <code>directionPt</code>)	 *	 * @param edgeDirection	 *    whether this DirectedEdge's direction is the same as or	 *    opposite to that of the parent Edge (if any)	 */	PolygonizeDirectedEdge(planarNode *newFrom,planarNode *newTo, const Coordinate& newDirectionPt,bool nEdgeDirection);	/*	 * Returns the identifier attached to this directed edge.	 */	long getLabel() const;	/*	 * Attaches an identifier to this directed edge.	 */	void setLabel(long newLabel);	/*	 * Returns the next directed edge in the EdgeRing that this	 * directed edge is a member of.	 */	PolygonizeDirectedEdge* getNext() const;	/*	 * Sets the next directed edge in the EdgeRing that this	 * directed edge is a member of.	 */	void setNext(PolygonizeDirectedEdge *newNext);	/*	 * Returns the ring of directed edges that this directed edge is	 * a member of, or null if the ring has not been set.	 * @see #setRing(EdgeRing)	 */	bool isInRing() const;	/*	 * Sets the ring of directed edges that this directed edge is	 * a member of.	 */	void setRing(polygonizeEdgeRing *newEdgeRing);};/* * Represents a planar graph of edges that can be used to compute a * polygonization, and implements the algorithms to compute the * EdgeRings formed by the graph. *  * The marked flag on DirectedEdge is used to indicate that a directed edge * has be logically deleted from the graph. * */class PolygonizeGraph: public planarPlanarGraph {public:	/*	 * \brief	 * Deletes all edges at a node	 */	static void deleteAllEdges(planarNode *node);	/*	 * \brief	 * Create a new polygonization graph.	 */	PolygonizeGraph(const GeometryFactory *newFactory);	/*	 * \brief	 * Destroy a polygonization graph.	 */	~PolygonizeGraph();	/*	 * \brief	 * Add a LineString forming an edge of the polygon graph.	 * @param line the line to add	 */	void addEdge(const LineString *line);