noding.h

一个很好的vc代码

/**********************************************************************
 * $Id: noding.h,v 1.5 2004/11/04 19:08:07 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: noding.h,v $
 * Revision 1.5  2004/11/04 19:08:07  strk
 * Cleanups, initializers list, profiling.
 *
 * Revision 1.4  2004/11/01 16:43:04  strk
 * Added Profiler code.
 * Temporarly patched a bug in DoubleBits (must check drawbacks).
 * Various cleanups and speedups.
 *
 * Revision 1.3  2004/07/19 13:19:31  strk
 * Documentation fixes
 *
 * Revision 1.2  2004/07/08 19:34:49  strk
 * Mirrored JTS interface of CoordinateSequence, factory and
 * default implementations.
 * Added DefaultCoordinateSequenceFactory::instance() function.
 *
 * Revision 1.1  2004/07/02 13:20:42  strk
 * Header files moved under geos/ dir.
 *
 * Revision 1.12  2004/07/01 14:12:44  strk
 *
 * Geometry constructors come now in two flavors:
 * 	- deep-copy args (pass-by-reference)
 * 	- take-ownership of args (pass-by-pointer)
 * Same functionality is available through GeometryFactory,
 * including buildGeometry().
 *
 * Revision 1.11  2004/06/16 13:13:25  strk
 * Changed interface of SegmentString, now copying CoordinateSequence argument.
 * Fixed memory leaks associated with this and MultiGeometry constructors.
 * Other associated fixes.
 *
 * Revision 1.10  2004/05/07 07:57:27  strk
 * Added missing EdgeNodingValidator to build scripts.
 * Changed SegmentString constructor back to its original form
 * (takes const void *), implemented local tracking of "contexts"
 * in caller objects for proper destruction.
 *
 * Revision 1.9  2004/05/06 15:54:15  strk
 * SegmentNodeList keeps track of created splitEdges for later destruction.
 * SegmentString constructor copies given Label.
 * Buffer operation does no more leaks for doc/example.cpp
 *
 * Revision 1.8  2004/05/03 22:56:44  strk
 * leaks fixed, exception specification omitted.
 *
 * Revision 1.7  2004/04/30 09:15:28  strk
 * Enlarged exception specifications to allow for AssertionFailedException.
 * Added missing initializers.
 *
 * Revision 1.6  2004/04/23 00:02:18  strk
 * const-correctness changes
 *
 * Revision 1.5  2004/04/19 16:14:52  strk
 * Some memory leaks plugged in noding algorithms.
 *
 * Revision 1.4  2004/04/19 12:51:01  strk
 * Memory leaks fixes. Throw specifications added.
 *
 * Revision 1.3  2004/04/14 09:30:48  strk
 * Private iterated noding funx now use int* instead of vector to know
 * when it's time to stop.
 *
 * Revision 1.2  2004/03/26 07:48:30  ybychkov
 * "noding" package ported (JTS 1.4)
 *
 *
 **********************************************************************/


#ifndef GEOS_NODING_H
#define GEOS_NODING_H

#include <string>
#include <vector>
#include <set>
#include <geos/platform.h>
#include <geos/geom.h>
#include <geos/geomgraph.h>
#include <geos/geosAlgorithm.h>

using namespace std;

namespace geos {

/*
 * Represents an intersection point between two {@link SegmentString}s.
 *
 */
class SegmentNode {
public:
	Coordinate *coord;   // the point of intersection
	int segmentIndex;   // the index of the containing line segment in the parent edge
	double dist;        // the edge distance of this point along the containing line segment
	SegmentNode(Coordinate *newCoord, int nSegmentIndex, double newDist);
	virtual ~SegmentNode();
	/**
	* @return -1 this EdgeIntersection is located before the argument location
	* @return 0 this EdgeIntersection is at the argument location
	* @return 1 this EdgeIntersection is located after the argument location
	*/
	int compare(int cSegmentIndex,double cDist);
	bool isEndPoint(int maxSegmentIndex);
	int compareTo(void* obj);
	string print();
};

struct SegmentNodeLT {
	bool operator()(SegmentNode *s1, SegmentNode *s2) const {
		return s1->compareTo(s2)<0;
	}
};

class SegmentString;
/*
 * A list of the {@link SegmentNode}s present along a
 * noded {@link SegmentString}.
 *
 */
class SegmentNodeList {
private:
	set<SegmentNode*,SegmentNodeLT> *nodes;
	const SegmentString *edge;  // the parent edge
	vector<SegmentNode*> *sortedNodes;

	// This vector is here to keep track of created splitEdges
	vector<SegmentString*> splitEdges;

	// This vector is here to keep track of created Coordinates
	vector<CoordinateSequence*> splitCoordLists;

	void checkSplitEdgesCorrectness(vector<SegmentString*> *splitEdges);
	/**
	* Create a new "split edge" with the section of points between
	* (and including) the two intersections.
	* The label for the new edge is the same as the label for the parent edge.
	*/
	SegmentString* createSplitEdge(SegmentNode *ei0, SegmentNode *ei1);

public:

	SegmentNodeList(const SegmentString *newEdge);

	virtual ~SegmentNodeList();

	/**
	* Adds an intersection into the list, if it isn't already there.
	* The input segmentIndex and dist are expected to be normalized.
	* @return the SegmentIntersection found or added
	*/
	SegmentNode* add(Coordinate *intPt, int segmentIndex, double dist);

	/**
	* returns the set of SegmentNodes
	*/
	//replaces iterator()
	set<SegmentNode*,SegmentNodeLT>* getNodes() { return nodes; }

	/**
	* Adds entries for the first and last points of the edge to the list
	*/
	void addEndpoints();

	/**
	* Creates new edges for all the edges that the intersections in this
	* list split the parent edge into.
	* Adds the edges to the input list (this is so a single list
	* can be used to accumulate all split edges for a Geometry).
	*/
	void addSplitEdges(vector<SegmentString*> *edgeList);

	string print();
};



/*
 * Contains a list of consecutive line segments which can be used to node the segments.
 * The line segments are represented by an array of {@link Coordinate}s.
 *
 */
class SegmentString {
private:
	SegmentNodeList *eiList;
	const CoordinateSequence *pts;
	const void* context;
	bool isIsolatedVar;
public:
	/**
	 * This function copies given CoordinateSequence
	 */
	SegmentString(const CoordinateSequence *newPts, const void* newContext);
	virtual ~SegmentString();
	const void* getContext() const;
	SegmentNodeList* getIntersectionList() const;
	int size() const;
	const Coordinate& getCoordinate(int i) const;
	CoordinateSequence* getCoordinates() const;
	const CoordinateSequence* getCoordinatesRO() const;
	void setIsolated(bool isIsolated);
	bool isIsolated() const;
	bool isClosed() const;
	/**
	* Adds EdgeIntersections for one or both
	* intersections found for a segment of an edge to the edge intersection list.
	*/
	void addIntersections(LineIntersector *li,int segmentIndex, int geomIndex);
	/**
	* Add an SegmentNode for intersection intIndex.
	* An intersection that falls exactly on a vertex
	* of the SegmentString is normalized
	* to use the higher of the two possible segmentIndexes
	*/
	void addIntersection(LineIntersector *li, int segmentIndex, int geomIndex, int intIndex);

	/**
	* Add an EdgeIntersection for intersection intIndex.
	* An intersection that falls exactly on a vertex of the edge is normalized
	* to use the higher of the two possible segmentIndexes
	*/
	void addIntersection(Coordinate& intPt, int segmentIndex);
	void addIntersection(Coordinate& intPt, int segmentIndex, double dist);
};

/*
 * Computes the intersections between two line segments in {@link SegmentString}s
 * and adds them to each string.
 * The {@link nodingSegmentIntersector} is passed to a {@link Noder}.
 * The {@link addIntersections} method is called whenever the {@link Noder}
 * detects that two SegmentStrings <i>might</i> intersect.
 * This class is an example of the <i>Strategy</i> pattern.
 *
 */
class nodingSegmentIntersector {
private:
	/**
	* These variables keep track of what types of intersections were
	* found during ALL edges that have been intersected.
	*/
	bool hasIntersectionVar;
	bool hasProperVar;
	bool hasProperInteriorVar;
	bool hasInteriorVar;
	// the proper intersection point found
	Coordinate *properIntersectionPoint;
	LineIntersector *li;
	bool recordIsolated;
	bool isSelfIntersectionVar;
	/**
	* A trivial intersection is an apparent self-intersection which in fact
	* is simply the point shared by adjacent line segments.
	* Note that closed edges require a special check for the point shared by the beginning
	* and end segments.
	*/
	bool isTrivialIntersection(SegmentString *e0, int segIndex0, SegmentString *e1, int segIndex1);
public:
	static bool isAdjacentSegments(int i1, int i2);
	int numIntersections;
	int numInteriorIntersections;
	int numProperIntersections;
	// testing only
	int numTests;
	nodingSegmentIntersector(LineIntersector *newLi);
	LineIntersector* getLineIntersector();
	/**
	* @return the proper intersection point, or <code>null</code> if none was found
	*/
	Coordinate* getProperIntersectionPoint();
	bool hasIntersection();
	/**
	* A proper intersection is an intersection which is interior to at least two
	* line segments.  Note that a proper intersection is not necessarily
	* in the interior of the entire Geometry, since another edge may have
	* an endpoint equal to the intersection, which according to SFS semantics
	* can result in the point being on the Boundary of the Geometry.
	*/
	bool hasProperIntersection();
	/**
	* A proper interior intersection is a proper intersection which is <b>not</b>
	* contained in the set of boundary nodes set for this nodingSegmentIntersector.
	*/
	bool hasProperInteriorIntersection();
	/**
	* An interior intersection is an intersection which is
	* in the interior of some segment.
	*/
	bool hasInteriorIntersection();
	/**
	* This method is called by clients
	* of the {@link nodingSegmentIntersector} class to process
	* intersections for two segments of the {@link SegmentStrings} being intersected.
	* Note that some clients (such as {@link MonotoneChain}s) may optimize away
	* this call for segment pairs which they have determined do not intersect
	* (e.g. by an disjoint envelope test).
	*/
	void processIntersections(SegmentString *e0, int segIndex0,SegmentString *e1, int segIndex1);
};

/*
 * Computes all intersections between segments in a set of {@link SegmentString}s.
 * Intersections found are represented as {@link SegmentNode}s and add to the
 * {@link SegmentString}s in which they occur.
 *
 */
class Noder {
public:
	static vector<SegmentString*>* getNodedEdges(vector<SegmentString*>* segStrings);
	static void getNodedEdges(vector<SegmentString*>* segStrings,vector<SegmentString*>* resultEdgelist);
	nodingSegmentIntersector *segInt;
public:
	Noder(){};
	virtual void setSegmentIntersector(nodingSegmentIntersector *newSegInt);
	virtual vector<SegmentString*>* node(vector<SegmentString*>* segStrings)=0;
};

/*
 * Nodes a set of {@link SegmentString}s by
 * performing a brute-force comparison of every segment to every other one.
 * This has n^2 performance, so is too slow for use on large numbers
 * of segments.
 *
 */
class SimpleNoder: public Noder {
public:
	SimpleNoder(){};
	virtual vector<SegmentString*>* node(vector<SegmentString*> *inputSegStrings);
private:
	virtual void computeIntersects(SegmentString *e0, SegmentString *e1);
};

/*
 * Validates that a collection of {@link SegmentString}s is correctly noded.
 * Throws an appropriate exception if an noding error is found.
 *
 */
class NodingValidator {
public:
	NodingValidator(vector<SegmentString*> *newSegStrings);
	virtual ~NodingValidator();
	void checkValid();
private:
	LineIntersector *li;
	vector<SegmentString*> *segStrings;
	void checkProperIntersections();
	void checkProperIntersections(SegmentString *ss0, SegmentString *ss1);
	void checkProperIntersections(SegmentString *e0, int segIndex0, SegmentString *e1, int segIndex1);
	/**
	*@return true if there is an intersection point which is not an endpoint of the segment p0-p1
	*/
	bool hasInteriorIntersection(LineIntersector *aLi, Coordinate& p0, Coordinate& p1);
	void checkNoInteriorPointsSame();
	void checkNoInteriorPointsSame(const Coordinate& testPt,vector<SegmentString*> *segStrings);
};


/*
 * Nodes a set of SegmentStrings using a index based
 * on indexMonotoneChain and a SpatialIndex.
 * The SpatialIndex used should be something that supports
 * envelope (range) queries efficiently (such as a Quadtree
 * or STRtree.
 *
 */
class MCQuadtreeNoder: public Noder {
public:
	MCQuadtreeNoder();
	virtual ~MCQuadtreeNoder();
	vector<SegmentString*>* node(vector<SegmentString*> *inputSegStrings);
	class SegmentOverlapAction: public MonotoneChainOverlapAction {
		private:
			nodingSegmentIntersector *si;
		public:
			SegmentOverlapAction(nodingSegmentIntersector *newSi);
			void overlap(indexMonotoneChain *mc1, int start1, indexMonotoneChain *mc2, int start2);
	};

private:
	vector<indexMonotoneChain*> *chains;
	SpatialIndex *index;
	int idCounter;
	// statistics
	int nOverlaps;
	void intersectChains();
	void add(SegmentString *segStr);
};

/*
 * Nodes a set of SegmentStrings completely.
 * The set of segmentStrings is fully noded;
 * i.e. noding is repeated until no further
 * intersections are detected.
 * <p>
 * Iterated noding using a FLOATING precision model is not guaranteed to converge,
 * due to roundoff error.   This problem is detected and an exception is thrown.
 * Clients can choose to rerun the noding using a lower precision model.
 *
 */
class IteratedNoder {
private:
	/**
	* Node the input segment strings once
	* and create the split edges between the nodes
	*/
	vector<SegmentString*>* node(vector<SegmentString*> *segStrings, int *numInteriorIntersections);
	const PrecisionModel *pm;
	LineIntersector *li;
public:
	IteratedNoder(const PrecisionModel *newPm);
	virtual ~IteratedNoder();
	/**
	* Fully nodes a list of {@link SegmentStrings}, i.e. peforms noding iteratively
	* until no intersections are found between segments.
	* Maintains labelling of edges correctly through
	* the noding.
	*
	* @param segStrings a collection of SegmentStrings to be noded
	* @return a collection of the noded SegmentStrings
	* @throws TopologyException if the iterated noding fails to converge.
	*/
	vector<SegmentString*>* node(vector<SegmentString*> *segStrings); // throw(GEOSException *);
};

}
#endif