Main Page | Namespace List | Class Hierarchy | Class List | Directories | File List | Namespace Members | Class Members | Related Pages

opValid.h

00001 /**********************************************************************
00002  * $Id: opValid.h,v 1.7 2004/11/05 11:41:57 strk Exp $
00003  *
00004  * GEOS - Geometry Engine Open Source
00005  * http://geos.refractions.net
00006  *
00007  * Copyright (C) 2001-2002 Vivid Solutions Inc.
00008  *
00009  * This is free software; you can redistribute and/or modify it under
00010  * the terms of the GNU Lesser General Public Licence as published
00011  * by the Free Software Foundation. 
00012  * See the COPYING file for more information.
00013  *
00014  **********************************************************************
00015  * $Log: opValid.h,v $
00016  * Revision 1.7  2004/11/05 11:41:57  strk
00017  * Made IsValidOp handle IllegalArgumentException throw from GeometryGraph
00018  * as a sign of invalidity (just for Polygon geometries).
00019  * Removed leaks generated by this specific exception.
00020  *
00021  * Revision 1.6  2004/09/13 12:39:14  strk
00022  * Made Point and MultiPoint subject to Validity tests.
00023  *
00024  * Revision 1.5  2004/09/13 10:12:49  strk
00025  * Added invalid coordinates checks in IsValidOp.
00026  * Cleanups.
00027  *
00028  * Revision 1.4  2004/09/13 09:18:10  strk
00029  * Added IsValidOp::isValid(Coordinate &)
00030  *
00031  * Revision 1.3  2004/07/19 13:19:31  strk
00032  * Documentation fixes
00033  *
00034  * Revision 1.2  2004/07/08 19:34:49  strk
00035  * Mirrored JTS interface of CoordinateSequence, factory and
00036  * default implementations.
00037  * Added DefaultCoordinateSequenceFactory::instance() function.
00038  *
00039  * Revision 1.1  2004/07/02 13:20:42  strk
00040  * Header files moved under geos/ dir.
00041  *
00042  * Revision 1.15  2004/05/18 00:02:37  ybychkov
00043  * IsValidOp::checkShellNotNested() bugfix from JTS 1.4.1 (not released yet) has been added.
00044  *
00045  * Revision 1.14  2004/03/29 06:59:24  ybychkov
00046  * "noding/snapround" package ported (JTS 1.4);
00047  * "operation", "operation/valid", "operation/relate" and "operation/overlay" upgraded to JTS 1.4;
00048  * "geom" partially upgraded.
00049  *
00050  * Revision 1.13  2003/11/07 01:23:42  pramsey
00051  * Add standard CVS headers licence notices and copyrights to all cpp and h
00052  * files.
00053  *
00054  *
00055  **********************************************************************/
00056 
00057 
00058 #ifndef GEOS_OPVALID_H
00059 #define GEOS_OPVALID_H
00060 
00061 #include <memory>
00062 #include <string>
00063 #include <vector>
00064 #include <map>
00065 #include <geos/platform.h>
00066 #include <geos/opRelate.h>
00067 #include <geos/indexSweepline.h>
00068 #include <geos/indexQuadtree.h>
00069 
00070 namespace geos {
00071 
00072 /*
00073  * Tests whether any of a set of {@link LinearRing}s are
00074  * nested inside another ring in the set, using a simple O(n^2)
00075  * comparison.
00076  *
00077  */
00078 class SimpleNestedRingTester {
00079 public:
00080         SimpleNestedRingTester(GeometryGraph *newGraph);
00081         ~SimpleNestedRingTester();
00082         void add(LinearRing *ring);
00083         Coordinate& getNestedPoint();
00084         bool isNonNested();
00085 private:
00086         CGAlgorithms *cga;
00087         GeometryGraph *graph;  // used to find non-node vertices
00088         vector<LinearRing*> *rings;
00089         Coordinate nestedPt;
00090 };
00091 
00092 /*
00093  * Contains information about the nature and location of a {@link Geometry}
00094  * validation error
00095  *
00096  */
00097 class TopologyValidationError {
00098 public:
00099         enum {
00100                 ERROR,
00101                 REPEATED_POINT,
00102                 HOLE_OUTSIDE_SHELL,
00103                 NESTED_HOLES,
00104                 DISCONNECTED_INTERIOR,
00105                 SELF_INTERSECTION,
00106                 RING_SELF_INTERSECTION,
00107                 NESTED_SHELLS,
00108                 DUPLICATE_RINGS,
00109                 TOO_FEW_POINTS,
00110                 INVALID_COORDINATE
00111         };
00112 
00113         TopologyValidationError(int newErrorType,Coordinate newPt);
00114         TopologyValidationError(int newErrorType);
00115         Coordinate& getCoordinate();
00116         string getMessage();
00117         int getErrorType();
00118         string toString();
00119 private:
00120         static string errMsg[];
00121         int errorType;
00122         Coordinate pt;
00123 };
00124 
00125 /*
00126  * Implements the appropriate checks for repeated points
00127  * (consecutive identical coordinates) as defined in the
00128  * JTS spec.
00129  */
00130 class RepeatedPointTester {
00131 public:
00132         RepeatedPointTester() {};
00133         Coordinate& getCoordinate();
00134         bool hasRepeatedPoint(const Geometry *g);
00135         bool hasRepeatedPoint(const CoordinateSequence *coord);
00136 private:
00137         Coordinate repeatedCoord;
00138         bool hasRepeatedPoint(const Polygon *p);
00139         bool hasRepeatedPoint(const GeometryCollection *gc);
00140         bool hasRepeatedPoint(const MultiPolygon *gc);
00141         bool hasRepeatedPoint(const MultiLineString *gc);
00142 };
00143 
00144 /*
00145  * Checks that a {@link GeometryGraph} representing an area
00146  * (a {@link Polygon} or {@link MultiPolygon} )
00147  * is consistent with the SFS semantics for area geometries.
00148  * Checks include:
00149  * <ul>
00150  * <li>testing for rings which self-intersect (both properly
00151  * and at nodes)
00152  * <li>testing for duplicate rings
00153  * </ul>
00154  * If an inconsistency if found the location of the problem
00155  * is recorded.
00156  */
00157 class ConsistentAreaTester {
00158 private:
00159         LineIntersector *li;
00160         GeometryGraph *geomGraph;
00161         RelateNodeGraph *nodeGraph;
00162         // the intersection point found (if any)
00163         Coordinate invalidPoint;
00168         bool isNodeEdgeAreaLabelsConsistent();
00169 public:
00170         ConsistentAreaTester(GeometryGraph *newGeomGraph);
00171         ~ConsistentAreaTester();
00175         Coordinate& getInvalidPoint();
00176         bool isNodeConsistentArea();
00192         bool hasDuplicateRings();
00193 };
00194 
00195 
00196 /*
00197  * Tests whether any of a set of {@link LinearRing}s are
00198  * nested inside another ring in the set, using a {@link SweepLineIndex}
00199  * index to speed up the comparisons.
00200  *
00201  */
00202 class SweeplineNestedRingTester {
00203 public:
00204         SweeplineNestedRingTester(GeometryGraph *newGraph);
00205         ~SweeplineNestedRingTester();
00206         Coordinate& getNestedPoint();
00207         void add(LinearRing* ring);
00208         bool isNonNested();
00209         bool isInside(LinearRing *innerRing,LinearRing *searchRing);
00210         class OverlapAction: public SweepLineOverlapAction {
00211         public:
00212                 bool isNonNested;
00213                 OverlapAction(SweeplineNestedRingTester *p);
00214                 void overlap(SweepLineInterval *s0, SweepLineInterval *s1);
00215         private:
00216                 SweeplineNestedRingTester *parent;
00217         };
00218 private:
00219         CGAlgorithms *cga;
00220         GeometryGraph *graph;  // used to find non-node vertices
00221         vector<LinearRing*> *rings;
00222         Envelope *totalEnv;
00223         SweepLineIndex *sweepLine;
00224         Coordinate nestedPt;
00225         void buildIndex();
00226 };
00227 
00228 /*
00229  * Tests whether any of a set of {@link LinearRing}s are
00230  * nested inside another ring in the set, using a {@link Quadtree}
00231  * index to speed up the comparisons.
00232  *
00233  */
00234 class QuadtreeNestedRingTester {
00235 public:
00236         QuadtreeNestedRingTester(GeometryGraph *newGraph);
00237         virtual ~QuadtreeNestedRingTester();
00238         Coordinate& getNestedPoint();
00239         void add(LinearRing *ring);
00240         bool isNonNested();
00241 private:
00242         GeometryGraph *graph;  // used to find non-node vertices
00243         vector<LinearRing*> *rings;
00244         Envelope *totalEnv;
00245         Quadtree *qt;
00246         Coordinate nestedPt;
00247         void buildQuadtree();
00248 };
00249 
00250 /*
00251  * This class tests that the interior of an area {@link Geometry}
00252  *  ({@link Polygon}  or {@link MultiPolygon} )
00253  * is connected.  An area Geometry is invalid if the interior is disconnected.
00254  * This can happen if:
00255  * <ul>
00256  * <li>one or more holes either form a chain touching the shell at two places
00257  * <li>one or more holes form a ring around a portion of the interior
00258  * </ul>
00259  * If an inconsistency if found the location of the problem
00260  * is recorded.
00261  */
00262 class ConnectedInteriorTester {
00263 public:
00264         ConnectedInteriorTester(GeometryGraph *newGeomGraph);
00265         ~ConnectedInteriorTester();
00266         Coordinate& getCoordinate();
00267         bool isInteriorsConnected();
00268         static const Coordinate& findDifferentPoint(const CoordinateSequence *coord, const Coordinate& pt);
00269 private:
00270         GeometryFactory *geometryFactory;
00271         CGAlgorithms *cga;
00272         GeometryGraph *geomGraph;
00273         // save a coordinate for any disconnected interior found
00274         // the coordinate will be somewhere on the ring surrounding the disconnected interior
00275         Coordinate disconnectedRingcoord;
00276         void setAllEdgesInResult(PlanarGraph *graph);
00277         vector<EdgeRing*>* buildEdgeRings(vector<EdgeEnd*> *dirEdges);
00282         void visitShellInteriors(const Geometry *g, PlanarGraph *graph);
00283         void visitInteriorRing(const LineString *ring, PlanarGraph *graph);
00294         bool hasUnvisitedShellEdge(vector<EdgeRing*> *edgeRings);
00295 protected:
00296         void visitLinkedDirectedEdges(DirectedEdge *start);
00297 };
00298 
00299 /*
00300  * Implements the algorithsm required to compute the <code>isValid()</code> method
00301  * for {@link Geometry}s.
00302  *
00303  */
00304 class IsValidOp {
00305 friend class Unload;
00306 public:
00313         static const Coordinate& findPtNotNode(const CoordinateSequence *testCoords,const LinearRing *searchRing, GeometryGraph *graph);
00314 
00323         static bool isValid(const Coordinate &coord);
00324 
00325         IsValidOp(const Geometry *geom);
00326         virtual ~IsValidOp();
00327         bool isValid();
00328         TopologyValidationError* getValidationError();
00329 private:
00330         const Geometry *parentGeometry;  // the base Geometry to be validated
00331         bool isChecked;
00332         TopologyValidationError* validErr;
00333         void checkValid(const Geometry *g);
00334         void checkValid(const Point *g);
00335         void checkValid(const LinearRing *g);
00336         void checkValid(const LineString *g);
00337         void checkValid(const Polygon *g);
00338         void checkValid(const MultiPolygon *g);
00339         void checkValid(const GeometryCollection *gc);
00340         void checkConsistentArea(GeometryGraph *graph);
00341         void checkNoSelfIntersectingRings(GeometryGraph *graph);
00347         void checkSelfIntersectingRing(EdgeIntersectionList *eiList);
00348         void checkTooFewPoints(GeometryGraph *graph);
00357         void checkHolesInShell(const Polygon *p,GeometryGraph *graph);
00358 //      void OLDcheckHolesInShell(Polygon *p);
00371         void checkHolesNotNested(const Polygon *p,GeometryGraph *graph);
00372 //      void SLOWcheckHolesNotNested(Polygon *p);
00386         void checkShellsNotNested(const MultiPolygon *mp,GeometryGraph *graph);
00396         void checkShellNotNested(const LinearRing *shell,const Polygon *p,GeometryGraph *graph);
00400         const Coordinate& checkShellInsideHole(const LinearRing *shell,const LinearRing *hole,GeometryGraph *graph);
00401         void checkConnectedInteriors(GeometryGraph *graph);
00402         void checkInvalidCoordinates(const CoordinateSequence *cs);
00403         void checkInvalidCoordinates(const Polygon *poly);
00404 };
00405 
00406 }
00407 #endif

Generated on Tue Dec 13 19:44:49 2005 for GEOS by  doxygen 1.4.4