isvalidop.cpp

在Linux下做的QuadTree的程序

/**********************************************************************
 * $Id: IsValidOp.cpp 1820 2006-09-06 16:54:23Z mloskot $
 *
 * 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/valid/IsValidOp.java rev. 1.39 (JTS-1.7)
 *
 **********************************************************************/

#include <geos/operation/valid/IsValidOp.h>
#include <geos/operation/valid/ConsistentAreaTester.h>
#include <geos/operation/valid/QuadtreeNestedRingTester.h>
#include <geos/operation/valid/ConnectedInteriorTester.h>
#include <geos/util/UnsupportedOperationException.h>
#include <geos/geomgraph/index/SegmentIntersector.h> 
#include <geos/geomgraph/GeometryGraph.h> 
#include <geos/geomgraph/Edge.h> 
#include <geos/algorithm/MCPointInRing.h> 
#include <geos/algorithm/CGAlgorithms.h> 
#include <geos/algorithm/LineIntersector.h> 
#include <geos/geom/CoordinateSequence.h>
#include <geos/geom/LineString.h>
#include <geos/geom/LinearRing.h>
#include <geos/geom/Point.h>
#include <geos/geom/Polygon.h>
#include <geos/geom/MultiPolygon.h>
#include <geos/geom/GeometryCollection.h>

#include <typeinfo>
#include <set>
#include <cassert>

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

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

/**
 * Find a point from the list of testCoords
 * that is NOT a node in the edge for the list of searchCoords
 *
 * @return the point found, or <code>null</code> if none found
 */
const Coordinate *
IsValidOp::findPtNotNode(const CoordinateSequence *testCoords,
	const LinearRing *searchRing, GeometryGraph *graph)
{
	// find edge corresponding to searchRing.
	Edge *searchEdge=graph->findEdge(searchRing);
	// find a point in the testCoords which is not a node of the searchRing
	EdgeIntersectionList &eiList=searchEdge->getEdgeIntersectionList();
	// somewhat inefficient - is there a better way? (Use a node map, for instance?)
	unsigned int npts=testCoords->getSize();
	for(unsigned int i=0; i<npts; ++i)
	{
		const Coordinate& pt=testCoords->getAt(i);
		if (!eiList.isIntersection(pt)) {
			return &pt;
		}
	}
	return NULL;
}


bool
IsValidOp::isValid()
{
	checkValid(parentGeometry);
	return validErr==NULL;
}

/*
 * Checks whether a coordinate is valid for processing.
 * Coordinates are valid iff their x and y coordinates are in the
 * range of the floating point representation.
 *
 * @param coord the coordinate to validate
 * @return <code>true</code> if the coordinate is valid
 */
bool
IsValidOp::isValid(const Coordinate &coord)
{
	if (! FINITE(coord.x) ) return false;
	if (! FINITE(coord.y) ) return false;
	return true;
}

TopologyValidationError *
IsValidOp::getValidationError()
{
	checkValid(parentGeometry);
	return validErr;
}

void
IsValidOp::checkValid(const Geometry *g)
{
	if (isChecked) return;
	validErr=NULL;

	// empty geometries are always valid!
	if (g->isEmpty()) return;

	const GeometryCollection *gc;

	if (typeid(*g)==typeid(Point)) checkValid((Point *)g);
	else if (typeid(*g)==typeid(LinearRing)) checkValid((LinearRing*)g);
	else if (typeid(*g)==typeid(LineString)) checkValid((LineString*)g);
	else if (typeid(*g)==typeid(Polygon)) checkValid((Polygon*)g);
	else if (typeid(*g)==typeid(MultiPolygon)) checkValid((MultiPolygon*)g);
	else if ((gc=dynamic_cast<const GeometryCollection *>(g)))
		checkValid(gc);
	else throw util::UnsupportedOperationException();
}

/*
 * Checks validity of a Point.
 */
void
IsValidOp::checkValid(const Point *g)
{
	checkInvalidCoordinates(g->getCoordinatesRO());
}

/*
 * Checks validity of a LineString.  Almost anything goes for linestrings!
 */
void
IsValidOp::checkValid(const LineString *g)
{
	checkInvalidCoordinates(g->getCoordinatesRO());
	if (validErr != NULL) return;

	GeometryGraph graph(0,g);
	checkTooFewPoints(&graph);
}

/**
 * Checks validity of a LinearRing.
 */
void
IsValidOp::checkValid(const LinearRing *g){
	checkInvalidCoordinates(g->getCoordinatesRO());
	if (validErr != NULL) return;

	checkClosedRing(g);
	if (validErr != NULL) return;

	GeometryGraph graph(0, g);
	checkTooFewPoints(&graph);
	if (validErr!=NULL) return;

	LineIntersector li;
	delete graph.computeSelfNodes(&li, true);
	checkNoSelfIntersectingRings(&graph);
}

/**
 * Checks the validity of a polygon.
 * Sets the validErr flag.
 */
void
IsValidOp::checkValid(const Polygon *g)
{
	checkInvalidCoordinates(g);
	if (validErr != NULL) return;

	checkClosedRings(g);
	if (validErr != NULL) return;

	GeometryGraph graph(0,g);

	checkTooFewPoints(&graph);
	if (validErr!=NULL) return;

	checkConsistentArea(&graph);
	if (validErr!=NULL) return;

	if (!isSelfTouchingRingFormingHoleValid) {
		checkNoSelfIntersectingRings(&graph);
		if (validErr!=NULL) return;
	}

	checkHolesInShell(g,&graph);
	if (validErr!=NULL) return;

	checkHolesNotNested(g,&graph);
	if (validErr!=NULL) return;

	checkConnectedInteriors(graph);
}

void
IsValidOp::checkValid(const MultiPolygon *g)
{
	unsigned int ngeoms = g->getNumGeometries();
	vector<const Polygon *>polys(ngeoms);

	for (unsigned int i=0; i<ngeoms; ++i)
	{
		const Polygon *p = (const Polygon *)g->getGeometryN(i);

		checkInvalidCoordinates(p);
		if (validErr != NULL) return;

		checkClosedRings(p);
		if (validErr != NULL) return;

		polys[i]=p;
	}

	GeometryGraph graph(0,g);

	checkTooFewPoints(&graph);
	if (validErr!=NULL) return;

	checkConsistentArea(&graph);
	if (validErr!=NULL) return;

	if (!isSelfTouchingRingFormingHoleValid)
	{
		checkNoSelfIntersectingRings(&graph);
		if (validErr!=NULL) return;
	}

	for(unsigned int i=0; i<ngeoms; ++i)
	{
		const Polygon *p=polys[i]; 
		checkHolesInShell(p, &graph);
		if (validErr!=NULL) return;
	}

	for(unsigned int i=0; i<ngeoms; ++i)
	{
		const Polygon *p=polys[i];
		checkHolesNotNested(p, &graph);
		if (validErr!=NULL) return;
	}

	checkShellsNotNested(g,&graph);
	if (validErr!=NULL) return;

	checkConnectedInteriors(graph);
}

void
IsValidOp::checkValid(const GeometryCollection *gc)
{
	for(unsigned int i=0, ngeoms=gc->getNumGeometries(); i<ngeoms; ++i)
	{
		const Geometry *g=gc->getGeometryN(i);
		checkValid(g);
		if (validErr!=NULL) return;
	}
}

void
IsValidOp::checkTooFewPoints(GeometryGraph *graph)
{
	if (graph->hasTooFewPoints()) {
		validErr=new TopologyValidationError(
			TopologyValidationError::eTooFewPoints,
			graph->getInvalidPoint());
		return;
	}
}

/**
 * Checks that the arrangement of edges in a polygonal geometry graph
 * forms a consistent area.
 *
 * @param graph
 *
 * @see ConsistentAreaTester
 */
void
IsValidOp::checkConsistentArea(GeometryGraph *graph)
{
	ConsistentAreaTester cat(graph);
	bool isValidArea=cat.isNodeConsistentArea();

	if (!isValidArea)
	{
		validErr=new TopologyValidationError(
			TopologyValidationError::eSelfIntersection,
			cat.getInvalidPoint());
		return;
	}

	if (cat.hasDuplicateRings())
	{
		validErr=new TopologyValidationError(
			TopologyValidationError::eDuplicatedRings,
			cat.getInvalidPoint());
	}
}


/*private*/
void
IsValidOp::checkNoSelfIntersectingRings(GeometryGraph *graph)
{
	vector<Edge*> *edges=graph->getEdges();
	for(unsigned int i=0; i<edges->size(); ++i)
	{
		Edge *e=(*edges)[i];
		checkNoSelfIntersectingRing(e->getEdgeIntersectionList());
		if(validErr!=NULL) return;
	}
}

/*private*/
void
IsValidOp::checkNoSelfIntersectingRing(EdgeIntersectionList &eiList)
{
	set<const Coordinate*,CoordinateLessThen>nodeSet;
	bool isFirst=true;
	EdgeIntersectionList::iterator it=eiList.begin();
	EdgeIntersectionList::iterator end=eiList.end();
	for(; it!=end; ++it)
	{
		EdgeIntersection *ei=*it;
		if (isFirst) {
			isFirst=false;
			continue;
		}
		if (nodeSet.find(&ei->coord)!=nodeSet.end()) {
			validErr=new TopologyValidationError(
				TopologyValidationError::eRingSelfIntersection,
				ei->coord);
			return;
		} else {
			nodeSet.insert(&ei->coord);
		}
	}
}

/*private*/
void
IsValidOp::checkHolesInShell(const Polygon *p, GeometryGraph *graph)
{
	assert(dynamic_cast<const LinearRing*>(p->getExteriorRing()));

	const LinearRing *shell=static_cast<const LinearRing*>(
			p->getExteriorRing());

	//SimplePointInRing pir(shell);
	//SIRtreePointInRing pir(shell);
	MCPointInRing pir(shell);

	int nholes = p->getNumInteriorRing();
	for(int i=0; i<nholes; ++i)
	{
		assert(dynamic_cast<const LinearRing*>(
				p->getInteriorRingN(i)));

		const LinearRing *hole=static_cast<const LinearRing*>(
				p->getInteriorRingN(i));

		const Coordinate *holePt=findPtNotNode(
				hole->getCoordinatesRO(), shell, graph);

		/**
		 * If no non-node hole vertex can be found, the hole must
		 * split the polygon into disconnected interiors.
		 * This will be caught by a subsequent check.
		 */
		if (holePt==NULL) return;

		bool outside = !pir.isInside(*holePt);
		if (outside) {
			validErr=new TopologyValidationError(
				TopologyValidationError::eHoleOutsideShell,
				*holePt);
			return;
		}
	}
}

/*private*/
void
IsValidOp::checkHolesNotNested(const Polygon *p, GeometryGraph *graph)
{
	//SimpleNestedRingTester nestedTester(graph);
	//SweeplineNestedRingTester nestedTester(graph);
	QuadtreeNestedRingTester nestedTester(graph);

	int nholes=p->getNumInteriorRing();
	for(int i=0; i<nholes; ++i)
	{
		assert(dynamic_cast<const LinearRing*>(
				p->getInteriorRingN(i)));

		const LinearRing *innerHole=static_cast<const LinearRing*>(
				p->getInteriorRingN(i));

		nestedTester.add(innerHole);
	}

	bool isNonNested=nestedTester.isNonNested();
	if (!isNonNested)