opbuffer.h

一个很好的vc代码

/**********************************************************************
 * $Id: opBuffer.h,v 1.6.2.1 2005/06/30 18:31:21 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_OPBUFFER_H
#define GEOS_OPBUFFER_H

#include <memory>
#include <geos/platform.h>
#include <geos/operation.h>
#include <geos/opOverlay.h>
#include <geos/geomgraph.h>
#include <geos/noding.h>
#include <geos/geom.h>
#include <vector>

namespace geos {

/*
 * \class RightmostEdgeFinder opBuffer.h geos/opBuffer.h
 *
 * \brief
 * A RightmostEdgeFinder find the DirectedEdge in a list which has
 * the highest coordinate, and which is oriented L to R at that point.
 * (I.e. the right side is on the RHS of the edge.)
 */
class RightmostEdgeFinder {
private:
	CGAlgorithms* cga;
	int minIndex;
	Coordinate minCoord;
	DirectedEdge *minDe;
	DirectedEdge *orientedDe;
	void findRightmostEdgeAtNode();
	void findRightmostEdgeAtVertex();
	void checkForRightmostCoordinate(DirectedEdge *de);
	int getRightmostSide(DirectedEdge *de, int index);
	int getRightmostSideOfSegment(DirectedEdge *de, int i);

public:
	/*
	 * A RightmostEdgeFinder finds the DirectedEdge with the
	 * rightmost coordinate.
	 * The DirectedEdge returned is guranteed to have the R of
	 * the world on its RHS.
	 */
	RightmostEdgeFinder(CGAlgorithms *newCga);
	DirectedEdge* getEdge();
	Coordinate& getCoordinate();
	void findEdge(vector<DirectedEdge*>* dirEdgeList);
};

/*
 * \class BufferSubgraph opBuffer.h geos/opBuffer.h
 *
 * \brief A connected subset of the graph of DirectedEdges and Node.
 * 
 * Its edges will generate either
 * - a single polygon in the complete buffer, with zero or more holes, or
 * -  ne or more connected holes
 */
class BufferSubgraph {
private:
	RightmostEdgeFinder *finder;

	vector<DirectedEdge*> *dirEdgeList;

	vector<Node*> *nodes;

	Coordinate *rightMostCoord;

	Envelope *env;

	/*
	 * Adds all nodes and edges reachable from this node to the subgraph.
	 * Uses an explicit stack to avoid a large depth of recursion.
	 *
	 * @param node a node known to be in the subgraph
	 */
	void addReachable(Node *startNode);

	/*
	 * Adds the argument node and all its out edges to the subgraph
	 * @param node the node to add
	 * @param nodeStack the current set of nodes being traversed
	 */
	void add(Node *node,vector<Node*> *nodeStack);

	void clearVisitedEdges();

	/*
	 * Compute depths for all dirEdges via breadth-first traversal
	 * of nodes in graph
	 * @param startEdge edge to start processing with
	 */
	// <FIX> MD - use iteration & queue rather than recursion, for speed and robustness
	void computeDepths(DirectedEdge *startEdge);

	void computeNodeDepth(Node *n);
	void copySymDepths(DirectedEdge *de);
	bool contains(vector<Node*> *nodes,Node *node);

public:
	BufferSubgraph(CGAlgorithms *cga);
	~BufferSubgraph();
	vector<DirectedEdge*>* getDirectedEdges();
	vector<Node*>* getNodes();

	/*
	 * Gets the rightmost coordinate in the edges of the subgraph
	 */
	Coordinate* getRightmostCoordinate();

	/*
	 * Creates the subgraph consisting of all edges reachable from
	 * this node.
	 * Finds the edges in the graph and the rightmost coordinate.
	 *
	 * @param node a node to start the graph traversal from
	 */
	void create(Node *node);

	void computeDepth(int outsideDepth);
	/*
	 * Find all edges whose depths indicates that they are in the
	 * result area(s).
	 * Since we want polygon shells to be
	 * oriented CW, choose dirEdges with the interior of the result
	 * on the RHS.
	 * Mark them as being in the result.
	 * Interior Area edges are the result of dimensional collapses.
	 * They do not form part of the result area boundary.
	 */
	void findResultEdges();

	/*
	 * BufferSubgraphs are compared on the x-value of their rightmost
	 * Coordinate.
	 * This defines a partial ordering on the graphs such that:
	 * 
	 * g1 >= g2 <==> Ring(g2) does not contain Ring(g1)
	 *
	 * where Polygon(g) is the buffer polygon that is built from g.
	 *
	 * This relationship is used to sort the BufferSubgraphs so
	 * that shells are guaranteed to
	 * be built before holes.
	 */
	int compareTo(void* o);

	/**
	 * Computes the envelope of the edges in the subgraph.
	 * The envelope is cached after being computed.
	 *
	 * @return the envelope of the graph.
	 */
	Envelope *getEnvelope();
};

/*
 * \class BufferOp opBuffer.h geos/opBuffer.h
 *
 * \brief
 * Computes the buffer of a geometry, for both positive and negative
 * buffer distances.
 *
 * In GIS, the buffer of a geometry is defined as
 * the Minkowski sum or difference of the geometry
 * with a circle with radius equal to the absolute value of the buffer
 * distance.
 * In the CAD/CAM world buffers are known as </b>offset curves</b>.
 * 
 * Since true buffer curves may contain circular arcs,
 * computed buffer polygons can only be approximations to the true geometry.
 * The user can control the accuracy of the curve approximation by specifying
 * the number of linear segments with which to approximate a curve.
 * 
 * The end cap style of a linear buffer may be specified.
 * The following end cap styles are supported:
 * - CAP_ROUND - the usual round end caps
 * - CAP_BUTT - end caps are truncated flat at the line ends
 * - CAP_SQUARE - end caps are squared off at the buffer distance
 *   beyond the line ends
 * 
 * The computation uses an algorithm involving iterated noding and
 * precision reduction to provide a high degree of robustness.
 */
class BufferOp {

private:

	static int MAX_PRECISION_DIGITS;

	/*
	 * Compute a reasonable scale factor to limit the precision of
	 * a given combination of Geometry and buffer distance.
	 * The scale factor is based on a heuristic.
	 *
	 * @param g the Geometry being buffered
	 *
	 * @param distance the buffer distance
	 *
	 * @param maxPrecisionDigits the mzx # of digits that should be
	 *        allowed by the precision determined by the
	 *        computed scale factor
	 *
	 * @return a scale factor that allows a reasonable amount of
	 *         precision for the buffer computation
	 */
	static double precisionScaleFactor(Geometry *g,	double distance,int maxPrecisionDigits);

	Geometry *argGeom;

	TopologyException *saveException;

	double distance;

	int quadrantSegments;

	int endCapStyle;

	Geometry* resultGeometry;

	void computeGeometry();

	void bufferOriginalPrecision();

	void bufferFixedPrecision(int precisionDigits);

public:

	enum {
		/// Specifies a round line buffer end cap style.
		CAP_ROUND,
		/// Specifies a butt (or flat) line buffer end cap style.
		CAP_BUTT,
		/// Specifies a square line buffer end cap style.
		CAP_SQUARE
	};

	/**
	 * Computes the buffer of a geometry for a given buffer distance.
	 *
	 * @param g the geometry to buffer
	 * @param distance the buffer distance
	 * @return the buffer of the input geometry
	 */
	static Geometry* bufferOp(Geometry *g, double distance);

	/**
	 * Comutes the buffer for a geometry for a given buffer distance
	 * and accuracy of approximation.
	 *
	 * @param g the geometry to buffer
	 * @param distance the buffer distance
	 * @param quadrantSegments the number of segments used to
	 *        approximate a quarter circle
	 * @return the buffer of the input geometry
	 *
	 */
	static Geometry* bufferOp(Geometry *g, double distance, int quadrantSegments);

	/**
	 * Initializes a buffer computation for the given geometry
	 *
	 * @param g the geometry to buffer
	 */
	BufferOp(Geometry *g);

	/**
	 * Specifies the end cap style of the generated buffer.
	 * The styles supported are CAP_ROUND, CAP_BUTT, and CAP_SQUARE.
	 * The default is CAP_ROUND.
	 *
	 * @param endCapStyle the end cap style to specify
	 */
	void setEndCapStyle(int nEndCapStyle);

	/**
	 * Specifies the end cap style of the generated buffer.
	 * The styles supported are CAP_ROUND, CAP_BUTT, and CAP_SQUARE.
	 * The default is CAP_ROUND.
	 *
	 * @param endCapStyle the end cap style to specify
	 */
	void setQuadrantSegments(int nQuadrantSegments);

	/**
	 * Returns the buffer computed for a geometry for a given buffer
	 * distance.
	 *
	 * @param g the geometry to buffer
	 * @param distance the buffer distance
	 * @return the buffer of the input geometry
	 */
	Geometry* getResultGeometry(double nDistance);

	/**
	 * Comutes the buffer for a geometry for a given buffer distance
	 * and accuracy of approximation.
	 *
	 * @param g the geometry to buffer
	 * @param distance the buffer distance
	 * @param quadrantSegments the number of segments used to
	 * approximate a quarter circle
	 * @return the buffer of the input geometry
	 *
	 * @deprecated use setQuadrantSegments instead
	 */
	Geometry* getResultGeometry(double nDistance, int nQuadrantSegments);
};

/*
 * \class OffsetCurveBuilder opBuffer.h geos/opBuffer.h
 *
 * \brief
 * Computes the raw offset curve for a
 * single Geometry component (ring, line or point).
 *
 * A raw offset curve line is not noded -
 * it may contain self-intersections (and usually will).
 * The final buffer polygon is computed by forming a topological graph
 * of all the noded raw curves and tracing outside contours.
 * The points in the raw curve are rounded to the required precision model.
 *
 */
class OffsetCurveBuilder {
public:
	/** \brief
	 * The default number of facets into which to divide a fillet
	 * of 90 degrees.
	 *
	 * A value of 8 gives less than 2% max error in the buffer distance.
	 * For a max error of < 1%, use QS = 12
	 */
	static const int DEFAULT_QUADRANT_SEGMENTS=8;

	OffsetCurveBuilder(const PrecisionModel *newPrecisionModel);
	~OffsetCurveBuilder();
	OffsetCurveBuilder(const PrecisionModel *newPrecisionModel,int quadrantSegments);
	void setEndCapStyle(int newEndCapStyle);

	/**
	 * This method handles single points as well as lines.
	 * Lines are assumed to <b>not</b> be closed (the function will not
	 * fail for closed lines, but will generate superfluous line caps).
	 *
	 * @return a List of Coordinate[]
	 */
	vector<CoordinateSequence*>* getLineCurve(const CoordinateSequence *inputPts, double distance);

	/**
	 * This method handles the degenerate cases of single points and lines,
	 * as well as rings.
	 *
	 * @return a List of Coordinate[]
	 */
	vector<CoordinateSequence*>* getRingCurve(const CoordinateSequence *inputPts, int side, double distance);

private:

	static double PI_OVER_2;
	static double MAX_CLOSING_SEG_LEN;
//	static final Coordinate[] arrayTypeCoordinate = new Coordinate[0];
	CGAlgorithms *cga;
	LineIntersector *li;

	/**
	 * The angle quantum with which to approximate a fillet curve
	 * (based on the input # of quadrant segments)
	 */
	double filletAngleQuantum;

	/**
	 * the max error of approximation between a quad segment and
	 * the true fillet curve
	 */
	double maxCurveSegmentError;

	CoordinateSequence *ptList;

	double distance;
	const PrecisionModel *precisionModel;
	int endCapStyle;
	int joinStyle;
	Coordinate s0, s1, s2;
	LineSegment *seg0;
	LineSegment *seg1;
	LineSegment *offset0;
	LineSegment *offset1;
	int side;
//	static CoordinateSequence* copyCoordinates(CoordinateSequence *pts);
	void init(double newDistance);
	CoordinateSequence* getCoordinates();
	void computeLineBufferCurve(const CoordinateSequence *inputPts);
	void computeRingBufferCurve(const CoordinateSequence *inputPts, int side);
	void addPt(const Coordinate &pt);
	void closePts();
	void initSideSegments(const Coordinate &nS1, const Coordinate &nS2, int nSide);
	void addNextSegment(const Coordinate &p, bool addStartPoint);
	/**
	* Add last offset point
	*/
	void addLastSegment();
	/**