opvalid.h

一个很好的vc代码

/**********************************************************************
 * $Id: opValid.h,v 1.7 2004/11/05 11:41:57 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: opValid.h,v $
 * Revision 1.7  2004/11/05 11:41:57  strk
 * Made IsValidOp handle IllegalArgumentException throw from GeometryGraph
 * as a sign of invalidity (just for Polygon geometries).
 * Removed leaks generated by this specific exception.
 *
 * Revision 1.6  2004/09/13 12:39:14  strk
 * Made Point and MultiPoint subject to Validity tests.
 *
 * Revision 1.5  2004/09/13 10:12:49  strk
 * Added invalid coordinates checks in IsValidOp.
 * Cleanups.
 *
 * Revision 1.4  2004/09/13 09:18:10  strk
 * Added IsValidOp::isValid(Coordinate &)
 *
 * 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.15  2004/05/18 00:02:37  ybychkov
 * IsValidOp::checkShellNotNested() bugfix from JTS 1.4.1 (not released yet) has been added.
 *
 * Revision 1.14  2004/03/29 06:59:24  ybychkov
 * "noding/snapround" package ported (JTS 1.4);
 * "operation", "operation/valid", "operation/relate" and "operation/overlay" upgraded to JTS 1.4;
 * "geom" partially upgraded.
 *
 * Revision 1.13  2003/11/07 01:23:42  pramsey
 * Add standard CVS headers licence notices and copyrights to all cpp and h
 * files.
 *
 *
 **********************************************************************/


#ifndef GEOS_OPVALID_H
#define GEOS_OPVALID_H

#include <memory>
#include <string>
#include <vector>
#include <map>
#include <geos/platform.h>
#include <geos/opRelate.h>
#include <geos/indexSweepline.h>
#include <geos/indexQuadtree.h>

namespace geos {

/*
 * Tests whether any of a set of {@link LinearRing}s are
 * nested inside another ring in the set, using a simple O(n^2)
 * comparison.
 *
 */
class SimpleNestedRingTester {
public:
	SimpleNestedRingTester(GeometryGraph *newGraph);
	~SimpleNestedRingTester();
	void add(LinearRing *ring);
	Coordinate& getNestedPoint();
	bool isNonNested();
private:
	CGAlgorithms *cga;
	GeometryGraph *graph;  // used to find non-node vertices
	vector<LinearRing*> *rings;
	Coordinate nestedPt;
};

/*
 * Contains information about the nature and location of a {@link Geometry}
 * validation error
 *
 */
class TopologyValidationError {
public:
	enum {
		ERROR,
		REPEATED_POINT,
		HOLE_OUTSIDE_SHELL,
		NESTED_HOLES,
		DISCONNECTED_INTERIOR,
		SELF_INTERSECTION,
		RING_SELF_INTERSECTION,
		NESTED_SHELLS,
		DUPLICATE_RINGS,
		TOO_FEW_POINTS,
		INVALID_COORDINATE
	};

	TopologyValidationError(int newErrorType,Coordinate newPt);
	TopologyValidationError(int newErrorType);
	Coordinate& getCoordinate();
	string getMessage();
	int getErrorType();
	string toString();
private:
	static string errMsg[];
	int errorType;
	Coordinate pt;
};

/*
 * Implements the appropriate checks for repeated points
 * (consecutive identical coordinates) as defined in the
 * JTS spec.
 */
class RepeatedPointTester {
public:
	RepeatedPointTester() {};
	Coordinate& getCoordinate();
	bool hasRepeatedPoint(const Geometry *g);
	bool hasRepeatedPoint(const CoordinateSequence *coord);
private:
	Coordinate repeatedCoord;
	bool hasRepeatedPoint(const Polygon *p);
	bool hasRepeatedPoint(const GeometryCollection *gc);
	bool hasRepeatedPoint(const MultiPolygon *gc);
	bool hasRepeatedPoint(const MultiLineString *gc);
};

/*
 * Checks that a {@link GeometryGraph} representing an area
 * (a {@link Polygon} or {@link MultiPolygon} )
 * is consistent with the SFS semantics for area geometries.
 * Checks include:
 * <ul>
 * <li>testing for rings which self-intersect (both properly
 * and at nodes)
 * <li>testing for duplicate rings
 * </ul>
 * If an inconsistency if found the location of the problem
 * is recorded.
 */
class ConsistentAreaTester {
private:
	LineIntersector *li;
	GeometryGraph *geomGraph;
	RelateNodeGraph *nodeGraph;
	// the intersection point found (if any)
	Coordinate invalidPoint;
	/**
	* Check all nodes to see if their labels are consistent.
	* If any are not, return false
	*/
	bool isNodeEdgeAreaLabelsConsistent();
public:
	ConsistentAreaTester(GeometryGraph *newGeomGraph);
	~ConsistentAreaTester();
	/**
	* @return the intersection point, or <code>null</code> if none was found
	*/
	Coordinate& getInvalidPoint();
	bool isNodeConsistentArea();
	/**
	* Checks for two duplicate rings in an area.
	* Duplicate rings are rings that are topologically equal
	* (that is, which have the same sequence of points up to point order).
	* If the area is topologically consistent (determined by calling the
	* <code>isNodeConsistentArea</code>,
	* duplicate rings can be found by checking for EdgeBundles which contain
	* more than one EdgeEnd.
	* (This is because topologically consistent areas cannot have two rings sharing
	* the same line segment, unless the rings are equal).
	* The start point of one of the equal rings will be placed in
	* invalidPoint.
	*
	* @return true if this area Geometry is topologically consistent but has two duplicate rings
	*/
	bool hasDuplicateRings();
};


/*
 * Tests whether any of a set of {@link LinearRing}s are
 * nested inside another ring in the set, using a {@link SweepLineIndex}
 * index to speed up the comparisons.
 *
 */
class SweeplineNestedRingTester {
public:
	SweeplineNestedRingTester(GeometryGraph *newGraph);
	~SweeplineNestedRingTester();
	Coordinate& getNestedPoint();
	void add(LinearRing* ring);
	bool isNonNested();
	bool isInside(LinearRing *innerRing,LinearRing *searchRing);
	class OverlapAction: public SweepLineOverlapAction {
	public:
		bool isNonNested;
		OverlapAction(SweeplineNestedRingTester *p);
		void overlap(SweepLineInterval *s0, SweepLineInterval *s1);
	private:
		SweeplineNestedRingTester *parent;
	};
private:
	CGAlgorithms *cga;
	GeometryGraph *graph;  // used to find non-node vertices
	vector<LinearRing*> *rings;
	Envelope *totalEnv;
	SweepLineIndex *sweepLine;
	Coordinate nestedPt;
	void buildIndex();
};

/*
 * Tests whether any of a set of {@link LinearRing}s are
 * nested inside another ring in the set, using a {@link Quadtree}
 * index to speed up the comparisons.
 *
 */
class QuadtreeNestedRingTester {
public:
	QuadtreeNestedRingTester(GeometryGraph *newGraph);
	virtual ~QuadtreeNestedRingTester();
	Coordinate& getNestedPoint();
	void add(LinearRing *ring);
	bool isNonNested();
private:
	GeometryGraph *graph;  // used to find non-node vertices
	vector<LinearRing*> *rings;
	Envelope *totalEnv;
	Quadtree *qt;
	Coordinate nestedPt;
	void buildQuadtree();
};

/*
 * This class tests that the interior of an area {@link Geometry}
 *  ({@link Polygon}  or {@link MultiPolygon} )
 * is connected.  An area Geometry is invalid if the interior is disconnected.
 * This can happen if:
 * <ul>
 * <li>one or more holes either form a chain touching the shell at two places
 * <li>one or more holes form a ring around a portion of the interior
 * </ul>
 * If an inconsistency if found the location of the problem
 * is recorded.
 */
class ConnectedInteriorTester {
public:
	ConnectedInteriorTester(GeometryGraph *newGeomGraph);
	~ConnectedInteriorTester();
	Coordinate& getCoordinate();
	bool isInteriorsConnected();
	static const Coordinate& findDifferentPoint(const CoordinateSequence *coord, const Coordinate& pt);
private:
	GeometryFactory *geometryFactory;
	CGAlgorithms *cga;
	GeometryGraph *geomGraph;
	// save a coordinate for any disconnected interior found
	// the coordinate will be somewhere on the ring surrounding the disconnected interior
	Coordinate disconnectedRingcoord;
	void setAllEdgesInResult(PlanarGraph *graph);
	vector<EdgeRing*>* buildEdgeRings(vector<EdgeEnd*> *dirEdges);
	/**
	* Mark all the edges for the edgeRings corresponding to the shells
	* of the input polygons.  Note only ONE ring gets marked for each shell.
	*/
	void visitShellInteriors(const Geometry *g, PlanarGraph *graph);
	void visitInteriorRing(const LineString *ring, PlanarGraph *graph);
	/**
	* Check if any shell ring has an unvisited edge.
	* A shell ring is a ring which is not a hole and which has the interior
	* of the parent area on the RHS.
	* (Note that there may be non-hole rings with the interior on the LHS,
	* since the interior of holes will also be polygonized into CW rings
	* by the linkAllDirectedEdges() step)
	*
	* @return true if there is an unvisited edge in a non-hole ring
	*/
	bool hasUnvisitedShellEdge(vector<EdgeRing*> *edgeRings);
protected:
	void visitLinkedDirectedEdges(DirectedEdge *start);
};

/*
 * Implements the algorithsm required to compute the <code>isValid()</code> method
 * for {@link Geometry}s.
 *
 */
class IsValidOp {
friend class Unload;
public:
	/**
	* 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
	*/
	static const Coordinate& findPtNotNode(const CoordinateSequence *testCoords,const LinearRing *searchRing, GeometryGraph *graph);

	/**
	 * 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
	 */
	static bool isValid(const Coordinate &coord);

	IsValidOp(const Geometry *geom);
	virtual ~IsValidOp();
	bool isValid();
	TopologyValidationError* getValidationError();
private:
	const Geometry *parentGeometry;  // the base Geometry to be validated
	bool isChecked;
	TopologyValidationError* validErr;
	void checkValid(const Geometry *g);
	void checkValid(const Point *g);
	void checkValid(const LinearRing *g);
	void checkValid(const LineString *g);
	void checkValid(const Polygon *g);
	void checkValid(const MultiPolygon *g);
	void checkValid(const GeometryCollection *gc);
	void checkConsistentArea(GeometryGraph *graph);
	void checkNoSelfIntersectingRings(GeometryGraph *graph);
	/**
	* check that a ring does not self-intersect, except at its endpoints.
	* Algorithm is to count the number of times each node along edge occurs.
	* If any occur more than once, that must be a self-intersection.
	*/
	void checkSelfIntersectingRing(EdgeIntersectionList *eiList);
	void checkTooFewPoints(GeometryGraph *graph);
	/**
	* Test that each hole is inside the polygon shell.
	* This routine assumes that the holes have previously been tested
	* to ensure that all vertices lie on the shell or inside it.
	* A simple test of a single point in the hole can be used,
	* provide the point is chosen such that it does not lie on the
	* boundary of the shell.
	*/
	void checkHolesInShell(const Polygon *p,GeometryGraph *graph);
//	void OLDcheckHolesInShell(Polygon *p);
	/**
	* Tests that no hole is nested inside another hole.
	* This routine assumes that the holes are disjoint.
	* To ensure this, holes have previously been tested
	* to ensure that:
	* <ul>
	* <li>they do not partially overlap
	* (checked by <code>checkRelateConsistency</code>)
	* <li>they are not identical
	* (checked by <code>checkRelateConsistency</code>)
	* </ul>
	*/
	void checkHolesNotNested(const Polygon *p,GeometryGraph *graph);
//	void SLOWcheckHolesNotNested(Polygon *p);
	/**
	* Test that no element polygon is wholly in the interior of another element polygon.
	* TODO: It handles the case that one polygon is nested inside a hole of another.
	* <p>
	* Preconditions:
	* <ul>
	* <li>shells do not partially overlap
	* <li>shells do not touch along an edge
	* <li>no duplicate rings exist
	* </ul>
	* This routine relies on the fact that while polygon shells may touch at one or
	* more vertices, they cannot touch at ALL vertices.
	*/
	void checkShellsNotNested(const MultiPolygon *mp,GeometryGraph *graph);
	/**
	* Check if a shell is incorrectly nested within a polygon.  This is the case
	* if the shell is inside the polygon shell, but not inside a polygon hole.
	* (If the shell is inside a polygon hole, the nesting is valid.)
	* <p>
	* The algorithm used relies on the fact that the rings must be properly contained.
	* E.g. they cannot partially overlap (this has been previously checked by
	* <code>checkRelateConsistency</code>
	*/
	void checkShellNotNested(const LinearRing *shell,const Polygon *p,GeometryGraph *graph);
	/**
	* This routine checks to see if a shell is properly contained in a hole.
	*/
	const Coordinate& checkShellInsideHole(const LinearRing *shell,const LinearRing *hole,GeometryGraph *graph);
	void checkConnectedInteriors(GeometryGraph *graph);
	void checkInvalidCoordinates(const CoordinateSequence *cs);
	void checkInvalidCoordinates(const Polygon *poly);
};

}
#endif