offsetcurvebuilder.cpp

在Linux下做的QuadTree的程序

/**********************************************************************
 * $Id: OffsetCurveBuilder.cpp 1959 2007-01-09 17:34:00Z strk $
 *
 * GEOS-Geometry Engine Open Source
 * http://geos.refractions.net
 *
 * Copyright (C) 2001-2002 Vivid Solutions Inc.
 * Copyright (C) 2005 Refractions Research 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.
 *
 **********************************************************************
 *
 * Last port: operation/buffer/OffsetCurveBuilder.java rev. 1.9
 *
 **********************************************************************/

#include <cassert>
#include <cmath>
#include <vector>

#include <geos/algorithm/CGAlgorithms.h>
#include <geos/operation/buffer/OffsetCurveBuilder.h>
#include <geos/operation/buffer/BufferOp.h>
#include <geos/geomgraph/Position.h>
#include <geos/geom/CoordinateArraySequence.h>
#include <geos/geom/CoordinateSequence.h>
#include <geos/geom/Coordinate.h>
#include <geos/geom/PrecisionModel.h>

#include "OffsetCurveVertexList.h"

#ifndef GEOS_DEBUG
#define GEOS_DEBUG 0
#endif

using namespace std;
using namespace geos::geomgraph;
using namespace geos::algorithm;
using namespace geos::geom;

namespace geos {
namespace operation { // geos.operation
namespace buffer { // geos.operation.buffer

/*private data*/
const double OffsetCurveBuilder::MIN_CURVE_VERTEX_FACTOR = 1.0E-6;
const double OffsetCurveBuilder::PI = 3.14159265358979;
const double OffsetCurveBuilder::MAX_CLOSING_SEG_LEN = 3.0;

/*public*/
OffsetCurveBuilder::OffsetCurveBuilder(const PrecisionModel *newPrecisionModel,
		int quadrantSegments)
		:
		li(),
		maxCurveSegmentError(0.0),
		vertexList(new OffsetCurveVertexList()),
		distance(0.0),
		precisionModel(newPrecisionModel),
		endCapStyle(BufferOp::CAP_ROUND),
		s0(),
		s1(),
		s2(),
		seg0(),
		seg1(),
		offset0(),
		offset1(),
		side(0),
		vertexLists()
{
	int limitedQuadSegs=quadrantSegments<1 ? 1 : quadrantSegments;
	filletAngleQuantum=PI / 2.0 / limitedQuadSegs;
}

/*public*/
OffsetCurveBuilder::~OffsetCurveBuilder()
{
	delete vertexList;
	for (unsigned int i=0; i<vertexLists.size(); i++) delete vertexLists[i];
}


/*public*/
void
OffsetCurveBuilder::getLineCurve(const CoordinateSequence *inputPts,
		double distance, vector<CoordinateSequence*>& lineList)
{
	// a zero or negative width buffer of a line/point is empty
	if (distance<= 0.0) return;

	init(distance);

	if (inputPts->getSize() < 2) {
		switch (endCapStyle) {
			case BufferOp::CAP_ROUND:
				addCircle(inputPts->getAt(0), distance);
				break;
			case BufferOp::CAP_SQUARE:
				addSquare(inputPts->getAt(0), distance);
				break;
			// default is for buffer to be empty (e.g. for a butt line cap);
		}
	} else {
		computeLineBufferCurve(*inputPts);
	}
	CoordinateSequence *lineCoord=vertexList->getCoordinates();
	lineList.push_back(lineCoord);
}

/*public*/
void
OffsetCurveBuilder::getRingCurve(const CoordinateSequence *inputPts,
		int side, double distance,
		vector<CoordinateSequence*>& lineList)
{
	init(distance);
	if (inputPts->getSize()<= 2)
	{
		getLineCurve(inputPts, distance, lineList);
		return;
	}
	// optimize creating ring for for zero distance
	if (distance==0.0) {
		vertexLists.push_back(vertexList);
		vertexList = new OffsetCurveVertexList(); // is this needed ?
		lineList.push_back(inputPts->clone());
		return;
	}
	computeRingBufferCurve(*inputPts, side);
	lineList.push_back(vertexList->getCoordinates()); // this will be vertexList
}

/*private*/
void
OffsetCurveBuilder::init(double newDistance)
{
	distance=newDistance;
	maxCurveSegmentError=distance*(1-cos(filletAngleQuantum/2.0));
	// Point list needs to be reset
	// but if a previous point list exists
	// we'd better back it up for final deletion
	vertexLists.push_back(vertexList);
	vertexList=new OffsetCurveVertexList();
	vertexList->setPrecisionModel(precisionModel);
	/**
	 * Choose the min vertex separation as a small fraction of the offset distance.
	 */
	vertexList->setMinimumVertexDistance(distance * MIN_CURVE_VERTEX_FACTOR);
}

/*private*/
void
OffsetCurveBuilder::computeLineBufferCurve(const CoordinateSequence& inputPts)
{
	int n=inputPts.size()-1;
	// compute points for left side of line
	initSideSegments(inputPts[0], inputPts[1], Position::LEFT);
	for (int i=2;i<= n;i++) {
		addNextSegment(inputPts[i], true);
	}
	addLastSegment();
	// add line cap for end of line
	addLineEndCap(inputPts[n-1], inputPts[n]);
	// compute points for right side of line
	initSideSegments(inputPts[n], inputPts[n-1], Position::LEFT);
	for (int i=n-2; i>=0; i--) {
		addNextSegment(inputPts[i], true);
	}
	addLastSegment();
	// add line cap for start of line
	addLineEndCap(inputPts[1], inputPts[0]);
	vertexList->closeRing();
}

/*private*/
void
OffsetCurveBuilder::computeRingBufferCurve(const CoordinateSequence& inputPts,
	int side)
{
	int n=inputPts.size()-1;
	initSideSegments(inputPts[n-1], inputPts[0], side);
	for (int i=1; i<=n; i++) {
		bool addStartPoint=i != 1;
		addNextSegment(inputPts[i], addStartPoint);
	}
	vertexList->closeRing();
}

/*private*/
void
OffsetCurveBuilder::initSideSegments(const Coordinate &nS1, const Coordinate &nS2, int nSide)
{
	s1=nS1;
	s2=nS2;
	side=nSide;
	seg1.setCoordinates(s1, s2);
	computeOffsetSegment(seg1, side, distance, offset1);
}

/*private*/
void
OffsetCurveBuilder::addNextSegment(const Coordinate &p, bool addStartPoint)
{
	// s0-s1-s2 are the coordinates of the previous segment and the current one
	s0=s1;
	s1=s2;
	s2=p;
	seg0.setCoordinates(s0, s1);
	computeOffsetSegment(seg0, side, distance, offset0);
	seg1.setCoordinates(s1, s2);
	computeOffsetSegment(seg1, side, distance, offset1);

	// do nothing if points are equal
	if (s1==s2) return;
	int orientation=CGAlgorithms::computeOrientation(s0, s1, s2);
	bool outsideTurn =(orientation==CGAlgorithms::CLOCKWISE
						&& side==Position::LEFT)
						||(orientation==CGAlgorithms::COUNTERCLOCKWISE 
						&& side==Position::RIGHT);
	if (orientation==0)
	{ // lines are collinear
		li.computeIntersection(s0,s1,s1,s2);
		int numInt=li.getIntersectionNum();

		/**
		 * if numInt is<2, the lines are parallel and in the same direction.
		 * In this case the point can be ignored, since the offset lines will also be
		 * parallel.
		 */
		if (numInt>= 2) {
			/**
			 * segments are collinear but reversing.  Have to add an "end-cap" fillet
			 * all the way around to other direction
			 * This case should ONLY happen for LineStrings, so the orientation is always CW.
			 * Polygons can never have two consecutive segments which are parallel but
			 * reversed, because that would be a self intersection.
			 */
			addFillet(s1, offset0.p1, offset1.p0, CGAlgorithms::CLOCKWISE, distance);
		}
	}
	else if (outsideTurn)
	{
		// add a fillet to connect the endpoints of the offset segments
		if (addStartPoint) vertexList->addPt(offset0.p1);
		// TESTING-comment out to produce beveled joins
		addFillet(s1, offset0.p1, offset1.p0, orientation, distance);
		vertexList->addPt(offset1.p0);
	}
	else
	{ // inside turn

		// add intersection point of offset segments (if any)
		li.computeIntersection( offset0.p0, offset0.p1, offset1.p0, offset1.p1);
		if (li.hasIntersection()) {
			vertexList->addPt(li.getIntersection(0));
		} else {
			/**
			 * If no intersection, it means the angle is so small and/or the offset so large
			 * that the offsets segments don't intersect.
			 * In this case we must add a offset joining curve to make sure the buffer line
			 * is continuous and tracks the buffer correctly around the corner.
			 * Note that the joining curve won't appear in the final buffer.
			 *
			 * The intersection test above is vulnerable to robustness errors;
			 * i.e. it may be that the offsets should intersect very close to their
			 * endpoints, but don't due to rounding.  To handle this situation
			 * appropriately, we use the following test:
			 * If the offset points are very close, don't add a joining curve
			 * but simply use one of the offset points
			 */
			if (offset0.p1.distance(offset1.p0)<distance / 1000.0) {
				vertexList->addPt(offset0.p1);
			} else {
				// add endpoint of this segment offset
				vertexList->addPt(offset0.p1);
				// <FIX> MD-add in centre point of corner, to make sure offset closer lines have correct topology
				vertexList->addPt(s1);
				vertexList->addPt(offset1.p0);
			}
		}
	}
}