planargraph.h

一个很好的vc代码

/**********************************************************************
 * $Id: planargraph.h,v 1.6 2004/12/14 10:35:44 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_PLANARGRAPH_H
#define GEOS_PLANARGRAPH_H

#include <geos/platform.h>
#include <geos/geosAlgorithm.h>
#include <vector>
#include <string>
#include <map>

using namespace std;

namespace geos {
//namespace planargraph {

/*
 * \class planarGraphComponent planargraph.h geos/planargraph.h
 *
 * \brief The base class for all graph component classes.
 *
 * Maintains flags of use in generic graph algorithms.
 * Provides two flags:
 * 
 *  - <b>marked</b> - typically this is used to indicate a state that
 *    persists for the course of the graph's lifetime.  For instance,
 *    it can be used to indicate that a component has been logically
 *    deleted from the graph.
 *  - <b>visited</b> - this is used to indicate that a component has been
 *    processed or visited by an single graph algorithm.  For instance,
 *    a breadth-first traversal of the graph might use this to indicate
 *    that a node has already been traversed.
 *    The visited flag may be set and cleared many times during the
 *    lifetime of a graph.
 *
 */
class planarGraphComponent {

protected:

	bool isMarkedVar;

	bool isVisitedVar;

public:

	planarGraphComponent();
	virtual ~planarGraphComponent();

	/*
	 * \brief Tests if a component has been visited during the course
	 * of a graph algorithm.
	 *
	 * @return <code>true</code> if the component has been visited
	 */
	virtual bool isVisited();

	/*
	 * \brief Sets the visited flag for this component.
	 * @param isVisited the desired value of the visited flag
	 */
	virtual void setVisited(bool isVisited);

	/*
	 * \brief Tests if a component has been marked at some point
	 * during the processing involving this graph.
	 * @return <code>true</code> if the component has been marked
	 */
	virtual bool isMarked();

	/*
	 * \brief Sets the marked flag for this component.
	 * @param isMarked the desired value of the marked flag
	 */
	virtual void setMarked(bool isMarked);
};

class planarDirectedEdge;
class planarEdge;

bool pdeLessThan(planarDirectedEdge *first,planarDirectedEdge * second);

/*
 * \class planarDirectedEdgeStar planargraph.h geos/planargraph.h
 *
 * \brief
 * A sorted collection of DirectedEdge which leave a Node in a PlanarGraph.
 */
class planarDirectedEdgeStar {
protected:
	/*
	 * \brief The underlying list of outgoing DirectedEdges
	 */
	vector<planarDirectedEdge*> *outEdges;

private:
	bool sorted;
	void sortEdges();

public:
	/*
	 * \brief Constructs a DirectedEdgeStar with no edges.
	 */
	planarDirectedEdgeStar();

	virtual ~planarDirectedEdgeStar();

	/*
	 * \brief Adds a new member to this DirectedEdgeStar.
	 */
	void add(planarDirectedEdge *de);

	/*
	 * \brief Drops a member of this DirectedEdgeStar.
	 */
	void remove(planarDirectedEdge *de);

	/*
	 * \brief Returns an Iterator over the DirectedEdges,
	 * in ascending order by angle with the positive x-axis.
	 */
	vector<planarDirectedEdge*>::iterator iterator();

	/*
	 * \brief Returns the number of edges around the Node associated
	 * with this DirectedEdgeStar.
	 */
	int getDegree();

	/*
	 * \brief Returns the coordinate for the node at wich this
	 * star is based
	 */
	Coordinate& getCoordinate();

	/*
	 * \brief Returns the DirectedEdges, in ascending order
	 * by angle with the positive x-axis.
	 */
	vector<planarDirectedEdge*>* getEdges();

	/*
	 * \brief Returns the zero-based index of the given Edge,
	 * after sorting in ascending order by angle with the
	 * positive x-axis.
	 */
	int getIndex(planarEdge *edge);

	/*
	 * \brief Returns the zero-based index of the given DirectedEdge,
	 * after sorting in ascending order
	 * by angle with the positive x-axis.
	 */  
	int getIndex(planarDirectedEdge *dirEdge);

	/*
	 * \brief Returns the remainder when i is divided by the number of
	 * edges in this DirectedEdgeStar. 
	 */
	int getIndex(int i);

	/*
	 * \brief Returns the DirectedEdge on the left-hand side
	 * of the given DirectedEdge (which must be a member of this
	 * DirectedEdgeStar). 
	 */
	planarDirectedEdge* getNextEdge(planarDirectedEdge *dirEdge);
};

/*
 * \class planarNode planargraph.h geos/planargraph.h
 *
 * \brief A node in a PlanarGraph is a location where 0 or more Edge meet.
 *
 * A node is connected to each of its incident Edges via an outgoing
 * DirectedEdge. Some clients using a <code>PlanarGraph</code> may want to
 * subclass <code>Node</code> to add their own application-specific
 * data and methods.
 *
 */
class planarNode: public planarGraphComponent {
protected:

	/* \brief The location of this Node */
	Coordinate pt;

	/* \brief The collection of DirectedEdges that leave this Node */
	planarDirectedEdgeStar *deStar;

public:

	/*
	 * \brief Returns all Edges that connect the two nodes (which are
	 * assumed to be different).
	 */
	static vector<planarEdge*>* getEdgesBetween(planarNode *node0, planarNode *node1);

	/*
	 * \brief Constructs a Node with the given location.
	 */
	planarNode(const Coordinate& newPt);

	~planarNode();

	/*
	 * \brief Constructs a Node with the given location and
	 * collection of outgoing planarDirectedEdges.
	 */
	planarNode(Coordinate& newPt, planarDirectedEdgeStar *newDeStar);

	/*
	 * \brief Returns the location of this Node.
	 */
	Coordinate& getCoordinate();

	/*
	 * \brief Adds an outgoing DirectedEdge to this Node.
	 */
	void addOutEdge(planarDirectedEdge *de);

	/*
	 * \brief Returns the collection of DirectedEdges that
	 * leave this Node.
	 */
	planarDirectedEdgeStar* getOutEdges();

	/*
	 * \brief Returns the number of edges around this Node.
	 */
	int getDegree();

	/*
	 * \brief Returns the zero-based index of the given Edge,
	 * after sorting in ascending order by angle with
	 * the positive x-axis.
	 */
	int getIndex(planarEdge *edge);
};

/*
 * \class planarEdge planargraph.h geos/planargraph.h
 *
 * \brief Represents an undirected edge of a PlanarGraph.
 *
 * An undirected edge in fact simply acts as a central point of reference
 * for two opposite DirectedEdge.
 * 
 * Usually a client using a PlanarGraph will subclass Edge
 * to add its own application-specific data and methods.
 */
class planarEdge: public planarGraphComponent {

protected:

	/* \brief The two DirectedEdges associated with this Edge */
	vector<planarDirectedEdge*> dirEdge;

	/*
	 * \brief Constructs an Edge whose DirectedEdges are not yet set.
	 *
	 * Be sure to call setDirectedEdges(DirectedEdge, DirectedEdge)
	 */

public:

	planarEdge();

	/*
	 * \brief Constructs an Edge initialized with the given DirectedEdges.
	 *
	 * For  each DirectedEdge: sets the Edge, sets the symmetric
	 * DirectedEdge, and adds this Edge to its from-Node.
	 */
	planarEdge(planarDirectedEdge *de0, planarDirectedEdge *de1);

	/*
	 * \brief Initializes this Edge's two DirectedEdges.
	 *
	 * For each DirectedEdge:
	 *  sets the Edge, sets the symmetric DirectedEdge, and
	 *  adds this Edge to its from-Node.
	 */
	void setDirectedEdges(planarDirectedEdge *de0, planarDirectedEdge *de1);

	/*
	 * \brief Returns one of the DirectedEdges associated with this Edge.
	 * @param i 0 or 1
	 */
	planarDirectedEdge* getDirEdge(int i);

	/*
	 * \brief Returns the DirectedEdge that starts from the given node,
	 * or null if the node is not one of the two nodes associated
	 * with this Edge.
	 */
	planarDirectedEdge* getDirEdge(planarNode *fromNode);

	/*
	 * \brief If <code>node</code> is one of the two nodes associated
	 * with this Edge, returns the other node; otherwise returns null.
	 */
	planarNode* getOppositeNode(planarNode *node);
};


/*
 * \class planarDirectedEdge planargraph.h geos/planargraph.h
 *
 * \brief Represents a directed edge in a PlanarGraph.
 *
 * A DirectedEdge may or may not have a reference to a parent Edge
 * (some applications of planar graphs may not require explicit Edge
 * objects to be created). Usually a client using a PlanarGraph
 * will subclass DirectedEdge to add its own application-specific
 * data and methods.
 */
class planarDirectedEdge: public planarGraphComponent {
//friend class Unload;

protected:
	//static const CGAlgorithms* cga;
	static CGAlgorithms cga;
	planarEdge* parentEdge;
	planarNode* from;
	planarNode* to;
	Coordinate p0, p1;
	planarDirectedEdge* sym;  // optional
	bool edgeDirection;
	int quadrant;
	double angle;
public:
	/*
	 * \brief Returns a List containing the parent Edge (possibly null)
	 * for each of the given DirectedEdges.
	 */
	static vector<planarEdge*>* toEdges(vector<planarDirectedEdge*> *dirEdges);

	/*
	 * \brief Constructs a DirectedEdge 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)
	 */
	planarDirectedEdge(planarNode *newFrom,planarNode *newTo, const Coordinate &directionPt,bool newEdgeDirection);

	/*
	 * \brief Returns this DirectedEdge's parent Edge,