sweeplinenestedringtester.cpp

在Linux下做的QuadTree的程序

/**********************************************************************
 * $Id: SweeplineNestedRingTester.cpp 1820 2006-09-06 16:54:23Z mloskot $
 *
 * GEOS - Geometry Engine Open Source
 * http://geos.refractions.net
 *
 * Copyright (C) 2005-2006 Refractions Research Inc.
 * 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.
 *
 **********************************************************************/

#include <geos/operation/valid/SweeplineNestedRingTester.h>
#include <geos/operation/valid/IsValidOp.h>
#include <geos/index/sweepline/SweepLineInterval.h>
#include <geos/index/sweepline/SweepLineIndex.h>
#include <geos/algorithm/CGAlgorithms.h>
#include <geos/geom/LinearRing.h>

#include <cassert>

using namespace geos::algorithm;
using namespace geos::index::sweepline;
using namespace geos::geom;

namespace geos {
namespace operation { // geos.operation
namespace valid { // geos.operation.valid

SweeplineNestedRingTester::OverlapAction::OverlapAction(SweeplineNestedRingTester *p)
{
	isNonNested=true;
	parent=p;
}

void
SweeplineNestedRingTester::OverlapAction::overlap(SweepLineInterval *s0, SweepLineInterval *s1)
{
	LinearRing *innerRing=(LinearRing*) s0->getItem();
	LinearRing *searchRing=(LinearRing*) s1->getItem();
	if (innerRing==searchRing) return;
	if (parent->isInside(innerRing, searchRing))
		isNonNested=false;
}


bool
SweeplineNestedRingTester::isNonNested()
{
	buildIndex();
	OverlapAction *action=new OverlapAction(this);
	sweepLine->computeOverlaps(action);
	return action->isNonNested;
}

void
SweeplineNestedRingTester::buildIndex()
{
	sweepLine=new SweepLineIndex();
	for(size_t i=0, n=rings.size(); i<n; i++) {
		LinearRing *ring=rings[i];
		const Envelope *env=ring->getEnvelopeInternal();
		SweepLineInterval *sweepInt=new SweepLineInterval(env->getMinX(),env->getMaxX(),ring);
		sweepLine->add(sweepInt);
	}
}

bool
SweeplineNestedRingTester::isInside(LinearRing *innerRing,LinearRing *searchRing)
{
	CoordinateSequence *innerRingPts=innerRing->getCoordinates();
	CoordinateSequence *searchRingPts=searchRing->getCoordinates();

	if (!innerRing->getEnvelopeInternal()->intersects(searchRing->getEnvelopeInternal()))
		return false;
	const Coordinate *innerRingPt=IsValidOp::findPtNotNode(innerRingPts, searchRing, graph);

	// Unable to find a ring point not a node of the search ring
	assert(innerRingPt!=NULL);

	bool isInside=CGAlgorithms::isPointInRing(*innerRingPt,searchRingPts);
	if (isInside) {
		/*
		 * innerRingPt is const just because the input
		 * CoordinateSequence is const. If the input
		 * Polygon survives lifetime of this object
		 * we are safe.
		 */
		nestedPt=const_cast<Coordinate *>(innerRingPt);
		return true;
	}
	return false;
}

} // namespace geos.operation.valid
} // namespace geos.operation
} // namespace geos

/**********************************************************************
 * $Log$
 * Revision 1.18  2006/06/12 11:29:24  strk
 * unsigned int => size_t
 *
 * Revision 1.17  2006/04/09 04:09:43  mloskot
 * Removed redundant semicolon reported by g++ -pedantic.
 *
 * Revision 1.16  2006/03/21 10:01:30  strk
 * indexSweepline.h header split
 *
 **********************************************************************/