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

opValid.h

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

Generated on Fri Nov 26 21:30:45 2004 for GEOS by  doxygen 1.3.9.1