src/noding/NodingValidator.cpp

   1 /**********************************************************************
   2  *
   3  * GEOS - Geometry Engine Open Source
   4  * http://geos.osgeo.org
   5  *
   6  * Copyright (C) 2006 Refractions Research Inc.
   7  * Copyright (C) 2001-2002 Vivid Solutions Inc.
   8  *
   9  * This is free software; you can redistribute and/or modify it under
  10  * the terms of the GNU Lesser General Licence as published
  11  * by the Free Software Foundation.
  12  * See the COPYING file for more information.
  13  *
  14  **********************************************************************
  15  *
  16  * Last port: noding/NodingValidator.java rev. 1.6 (JTS-1.7)
  17  *
  18  **********************************************************************/
  19
  20 #include <sstream>
  21 #include <vector>
  22
  23 #include <geos/util/TopologyException.h>
  24 #include <geos/algorithm/LineIntersector.h>
  25 #include <geos/noding/NodingValidator.h>
  26 #include <geos/noding/SegmentString.h>
  27 #include <geos/geom/Coordinate.h>
  28 #include <geos/geom/CoordinateSequence.h>
  29
  30 using namespace std;
  31 using namespace geos::algorithm;
  32 using namespace geos::geom;
  33
  34 namespace geos {
  35 namespace noding { // geos.noding
  36
  37 /*public*/
  38 void
  39 NodingValidator::checkValid()
  40 {
  41         checkEndPtVertexIntersections();
  42         checkInteriorIntersections();
  43         checkCollapses();
  44 }
  45
  46 /*private*/
  47 void
  48 NodingValidator::checkCollapses() const
  49 {
  50         for (SegmentString::NonConstVect::const_iterator
  51                 it = segStrings.begin(), itEnd = segStrings.end();
  52                 it != itEnd;
  53                 ++it)
  54         {
  55                 const SegmentString* ss = *it;
  56                 checkCollapses(*ss);
  57         }
  58 }
  59
  60 /* private */
  61 void
  62 NodingValidator::checkCollapses(const SegmentString& ss) const
  63 {
  64         const CoordinateSequence& pts = *(ss.getCoordinates());
  65         for (unsigned int i=0, n=pts.getSize()-2; i<n; ++i)
  66         {
  67                 checkCollapse(pts[i], pts[i + 1], pts[i + 2]);
  68         }
  69 }
  70
  71 /* private */
  72 void
  73 NodingValidator::checkCollapse(const Coordinate& p0,
  74                 const Coordinate& p1, const Coordinate& p2) const
  75 {
  76         if (p0.equals2D(p2))
  77                 throw util::TopologyException("found non-noded collapse at " +
  78                         p0.toString() + ", " +
  79                         p1.toString() + ", " +
  80                         p2.toString());
  81 }
  82
  83 /*private*/
  84 void
  85 NodingValidator::checkInteriorIntersections()
  86 {
  87         for (SegmentString::NonConstVect::const_iterator
  88                 it = segStrings.begin(), itEnd = segStrings.end();
  89                 it != itEnd;
  90                 ++it)
  91         {
  92                 SegmentString* ss0 = *it;
  93                 for (SegmentString::NonConstVect::const_iterator
  94                         j = segStrings.begin(), jEnd = segStrings.end();
  95                         j != jEnd; ++j)
  96                 {
  97                         const SegmentString* ss1 = *j;
  98                         checkInteriorIntersections(*ss0, *ss1);
  99                 }
 100         }
 101
 102 }
 103
 104 /* private */
 105 void
 106 NodingValidator::checkInteriorIntersections(const SegmentString& ss0,
 107                 const SegmentString& ss1)
 108 {
 109         const CoordinateSequence& pts0 = *(ss0.getCoordinates());
 110         const CoordinateSequence& pts1 = *(ss1.getCoordinates());
 111         for (unsigned int i0=0, n0=pts0.size(); i0<n0-1; i0++) {
 112                 for (unsigned int i1=0, n1=pts1.size(); i1<n1-1; i1++) {
 113                         checkInteriorIntersections(ss0, i0, ss1, i1);
 114                 }
 115         }
 116 }
 117
 118
 119 /* private */
 120 void
 121 NodingValidator::checkInteriorIntersections(
 122                 const SegmentString& e0, unsigned int segIndex0,
 123                 const SegmentString& e1, unsigned int segIndex1)
 124 {
 125         if (&e0 == &e1 && segIndex0 == segIndex1) return;
 126         const Coordinate& p00 = e0.getCoordinates()->getAt(segIndex0);
 127         const Coordinate& p01 = e0.getCoordinates()->getAt(segIndex0 + 1);
 128         const Coordinate& p10 = e1.getCoordinates()->getAt(segIndex1);
 129         const Coordinate& p11 = e1.getCoordinates()->getAt(segIndex1 + 1);
 130
 131         li.computeIntersection(p00, p01, p10, p11);
 132         if (li.hasIntersection()) {
 133                 if (li.isProper()
 134                         || hasInteriorIntersection(li, p00, p01)
 135                         || hasInteriorIntersection(li, p10, p11))
 136                 {
 137                         throw util::TopologyException(
 138                                 "found non-noded intersection at "
 139                                 + p00.toString() + "-" + p01.toString()
 140                                 + " and "
 141                                 + p10.toString() + "-" + p11.toString());
 142                 }
 143         }
 144 }
 145
 146 /* private */
 147 void
 148 NodingValidator::checkEndPtVertexIntersections() const
 149 {
 150         for (SegmentString::NonConstVect::const_iterator
 151                 it = segStrings.begin(), itEnd = segStrings.end();
 152                 it != itEnd;
 153                 ++it)
 154         {
 155                 const SegmentString* ss = *it;
 156                 const CoordinateSequence& pts = *(ss->getCoordinates());
 157                 checkEndPtVertexIntersections(pts[0], segStrings);
 158                 checkEndPtVertexIntersections(pts[pts.size() - 1], segStrings);
 159         }
 160 }
 161
 162 /* private */
 163 void
 164 NodingValidator::checkEndPtVertexIntersections(const Coordinate& testPt,
 165                 const SegmentString::NonConstVect& segStrings) const
 166 {
 167         for (SegmentString::NonConstVect::const_iterator
 168                 it = segStrings.begin(), itEnd = segStrings.end();
 169                 it != itEnd;
 170                 ++it)
 171         {
 172                 const SegmentString* ss0 = *it;
 173                 const CoordinateSequence& pts = *(ss0->getCoordinates());
 174                 for (unsigned int j=1, n=pts.size()-1; j<n; ++j)
 175                 {
 176                         if (pts[j].equals(testPt))
 177                         {
 178                                 stringstream s;
 179                                 s<<"found endpt/interior pt intersection ";
 180                                 s<<"at index "<<j<<" :pt "<<testPt;
 181                                 throw util::TopologyException(s.str());
 182                         }
 183                 }
 184         }
 185 }
 186
 187
 188
 189
 190
 191 /* private */
 192 bool
 193 NodingValidator::hasInteriorIntersection(const LineIntersector& aLi,
 194                 const Coordinate& p0, const Coordinate& p1) const
 195 {
 196         for (int i=0, n=aLi.getIntersectionNum(); i<n; i++)
 197         {
 198                 const Coordinate &intPt=aLi.getIntersection(i);
 199                 if (!(intPt==p0 || intPt==p1))
 200                         return true;
 201         }
 202         return false;
 203 }
 204
 205
 206 } // namespace geos.noding
 207 } // namespace geos
 208
 209 /**********************************************************************
 210  * $Log$
 211  * Revision 1.16  2006/03/15 09:51:12  strk
 212  * streamlined headers usage
 213  *
 214  * Revision 1.15  2006/03/06 19:40:47  strk
 215  * geos::util namespace. New GeometryCollection::iterator interface, many cleanups.
 216  *
 217  * Revision 1.14  2006/03/03 10:46:21  strk
 218  * Removed 'using namespace' from headers, added missing headers in .cpp files, removed useless includes in headers (bug#46)
 219  *
 220  * Revision 1.13  2006/02/19 19:46:49  strk
 221  * Packages <-> namespaces mapping for most GEOS internal code (uncomplete, but working). Dir-level libs for index/ subdirs.
 222  *
 223  * Revision 1.12  2006/02/18 21:08:09  strk
 224  * - new CoordinateSequence::applyCoordinateFilter method (slow but useful)
 225  * - SegmentString::getCoordinates() doesn't return a clone anymore.
 226  * - SegmentString::getCoordinatesRO() obsoleted.
 227  * - SegmentString constructor does not promises constness of passed
 228  *   CoordinateSequence anymore.
 229  * - NEW ScaledNoder class
 230  * - Stubs for MCIndexPointSnapper and  MCIndexSnapRounder
 231  * - Simplified internal interaces of OffsetCurveBuilder and OffsetCurveSetBuilder
 232  *
 233  * Revision 1.11  2006/02/16 08:41:40  strk
 234  * Fixed include: "util.h" => "geos/util.h"
 235  *
 236  * Revision 1.10  2006/02/15 17:19:18  strk
 237  * NodingValidator synced with JTS-1.7, added CoordinateSequence::operator[]
 238  * and size() to easy port maintainance.
 239  *
 240  * Revision 1.9  2006/02/14 13:28:26  strk
 241  * New SnapRounding code ported from JTS-1.7 (not complete yet).
 242  * Buffer op optimized by using new snaprounding code.
 243  * Leaks fixed in XMLTester.
 244  *
 245  * Revision 1.8  2006/02/09 15:52:47  strk
 246  * GEOSException derived from std::exception; always thrown and cought by const ref.
 247  *
 248  * Revision 1.7  2006/01/31 19:07:34  strk
 249  * - Renamed DefaultCoordinateSequence to CoordinateArraySequence.
 250  * - Moved GetNumGeometries() and GetGeometryN() interfaces
 251  *   from GeometryCollection to Geometry class.
 252  * - Added getAt(int pos, Coordinate &to) funtion to CoordinateSequence class.
 253  * - Reworked automake scripts to produce a static lib for each subdir and
 254  *   then link all subsystem's libs togheter
 255  * - Moved C-API in it's own top-level dir capi/
 256  * - Moved source/bigtest and source/test to tests/bigtest and test/xmltester
 257  * - Fixed PointLocator handling of LinearRings
 258  * - Changed CoordinateArrayFilter to reduce memory copies
 259  * - Changed UniqueCoordinateArrayFilter to reduce memory copies
 260  * - Added CGAlgorithms::isPointInRing() version working with
 261  *   Coordinate::ConstVect type (faster!)
 262  * - Ported JTS-1.7 version of ConvexHull with big attention to
 263  *   memory usage optimizations.
 264  * - Improved XMLTester output and user interface
 265  * - geos::geom::util namespace used for geom/util stuff
 266  * - Improved memory use in geos::geom::util::PolygonExtractor
 267  * - New ShortCircuitedGeometryVisitor class
 268  * - New operation/predicate package
 269  *
 270  * Revision 1.6  2005/11/25 11:31:21  strk
 271  * Removed all CoordinateSequence::getSize() calls embedded in for loops.
 272  *
 273  * Revision 1.5  2005/06/24 11:09:43  strk
 274  * Dropped RobustLineIntersector, made LineIntersector a concrete class.
 275  * Added LineIntersector::hasIntersection(Coordinate&,Coordinate&,Coordinate&)
 276  * to avoid computing intersection point (Z) when it's not necessary.
 277  *
 278  * Revision 1.4  2004/11/01 16:43:04  strk
 279  * Added Profiler code.
 280  * Temporarly patched a bug in DoubleBits (must check drawbacks).
 281  * Various cleanups and speedups.
 282  *
 283  * Revision 1.3  2004/07/08 19:34:49  strk
 284  * Mirrored JTS interface of CoordinateSequence, factory and
 285  * default implementations.
 286  * Added CoordinateArraySequenceFactory::instance() function.
 287  *
 288  * Revision 1.2  2004/07/02 13:28:27  strk
 289  * Fixed all #include lines to reflect headers layout change.
 290  * Added client application build tips in README.
 291  *
 292  * Revision 1.1  2004/03/26 07:48:30  ybychkov
 293  * "noding" package ported (JTS 1.4)
 294  *
 295  *
 296  **********************************************************************/
 297