Quantum GIS API Documentation
1.8
|
00001 /*************************************************************************** 00002 qgsgeometryvalidator.cpp - geometry validation thread 00003 ------------------------------------------------------------------- 00004 Date : 03.01.2012 00005 Copyright : (C) 2012 by Juergen E. Fischer 00006 email : jef at norbit dot de 00007 *************************************************************************** 00008 * * 00009 * This program is free software; you can redistribute it and/or modify * 00010 * it under the terms of the GNU General Public License as published by * 00011 * the Free Software Foundation; either version 2 of the License, or * 00012 * (at your option) any later version. * 00013 * * 00014 ***************************************************************************/ 00015 00016 #include "qgis.h" 00017 #include "qgsgeometryvalidator.h" 00018 #include "qgsgeometry.h" 00019 #include "qgslogger.h" 00020 00021 #include <QSettings> 00022 00023 QgsGeometryValidator::QgsGeometryValidator( QgsGeometry *g, QList<QgsGeometry::Error> *errors ) 00024 : QThread() 00025 , mErrors( errors ) 00026 , mStop( false ) 00027 , mErrorCount( 0 ) 00028 { 00029 Q_ASSERT( g ); 00030 if ( g ) 00031 mG = *g; 00032 } 00033 00034 QgsGeometryValidator::~QgsGeometryValidator() 00035 { 00036 stop(); 00037 wait(); 00038 } 00039 00040 void QgsGeometryValidator::stop() 00041 { 00042 mStop = true; 00043 } 00044 00045 void QgsGeometryValidator::checkRingIntersections( 00046 int p0, int i0, const QgsPolyline &ring0, 00047 int p1, int i1, const QgsPolyline &ring1 ) 00048 { 00049 for ( int i = 0; !mStop && i < ring0.size() - 1; i++ ) 00050 { 00051 QgsVector v = ring0[i+1] - ring0[i]; 00052 00053 for ( int j = 0; !mStop && j < ring1.size() - 1; j++ ) 00054 { 00055 QgsVector w = ring1[j+1] - ring1[j]; 00056 00057 QgsPoint s; 00058 if ( intersectLines( ring0[i], v, ring1[j], w, s ) ) 00059 { 00060 double d = -distLine2Point( ring0[i], v.perpVector(), s ); 00061 00062 if ( d >= 0 && d <= v.length() ) 00063 { 00064 d = -distLine2Point( ring1[j], w.perpVector(), s ); 00065 if ( d >= 0 && d <= w.length() ) 00066 { 00067 QString msg = QObject::tr( "segment %1 of ring %2 of polygon %3 intersects segment %4 of ring %5 of polygon %6 at %7" ) 00068 .arg( i0 ).arg( i ).arg( p0 ) 00069 .arg( i1 ).arg( j ).arg( p1 ) 00070 .arg( s.toString() ); 00071 QgsDebugMsg( msg ); 00072 emit errorFound( QgsGeometry::Error( msg, s ) ); 00073 mErrorCount++; 00074 } 00075 } 00076 } 00077 } 00078 } 00079 } 00080 00081 void QgsGeometryValidator::validatePolyline( int i, QgsPolyline line, bool ring ) 00082 { 00083 if ( ring ) 00084 { 00085 if ( line.size() < 4 ) 00086 { 00087 QString msg = QObject::tr( "ring %1 with less than four points" ).arg( i ); 00088 QgsDebugMsg( msg ); 00089 emit errorFound( QgsGeometry::Error( msg ) ); 00090 mErrorCount++; 00091 return; 00092 } 00093 00094 if ( line[0] != line[ line.size()-1 ] ) 00095 { 00096 QString msg = QObject::tr( "ring %1 not closed" ).arg( i ); 00097 QgsDebugMsg( msg ); 00098 emit errorFound( QgsGeometry::Error( msg ) ); 00099 mErrorCount++; 00100 return; 00101 } 00102 } 00103 else if ( line.size() < 2 ) 00104 { 00105 QString msg = QObject::tr( "line %1 with less than two points" ).arg( i ); 00106 QgsDebugMsg( msg ); 00107 emit errorFound( QgsGeometry::Error( msg ) ); 00108 mErrorCount++; 00109 return; 00110 } 00111 00112 int j = 0; 00113 while ( j < line.size() - 1 ) 00114 { 00115 int n = 0; 00116 while ( j < line.size() - 1 && line[j] == line[j+1] ) 00117 { 00118 line.remove( j ); 00119 n++; 00120 } 00121 00122 if ( n > 0 ) 00123 { 00124 QString msg = QObject::tr( "line %1 contains %n duplicate node(s) at %2", "number of duplicate nodes", n ).arg( i ).arg( j ); 00125 QgsDebugMsg( msg ); 00126 emit errorFound( QgsGeometry::Error( msg, line[j] ) ); 00127 mErrorCount++; 00128 } 00129 00130 j++; 00131 } 00132 00133 for ( j = 0; !mStop && j < line.size() - 3; j++ ) 00134 { 00135 QgsVector v = line[j+1] - line[j]; 00136 double vl = v.length(); 00137 00138 int n = ( j == 0 && ring ) ? line.size() - 2 : line.size() - 1; 00139 00140 for ( int k = j + 2; !mStop && k < n; k++ ) 00141 { 00142 QgsVector w = line[k+1] - line[k]; 00143 00144 QgsPoint s; 00145 if ( !intersectLines( line[j], v, line[k], w, s ) ) 00146 continue; 00147 00148 double d = -distLine2Point( line[j], v.perpVector(), s ); 00149 if ( d < 0 || d > vl ) 00150 continue; 00151 00152 d = -distLine2Point( line[k], w.perpVector(), s ); 00153 if ( d < 0 || d > w.length() ) 00154 continue; 00155 00156 QString msg = QObject::tr( "segments %1 and %2 of line %3 intersect at %4" ).arg( j ).arg( k ).arg( i ).arg( s.toString() ); 00157 QgsDebugMsg( msg ); 00158 emit errorFound( QgsGeometry::Error( msg, s ) ); 00159 mErrorCount++; 00160 } 00161 } 00162 } 00163 00164 void QgsGeometryValidator::validatePolygon( int idx, const QgsPolygon &polygon ) 00165 { 00166 // check if holes are inside polygon 00167 for ( int i = 1; !mStop && i < polygon.size(); i++ ) 00168 { 00169 if ( !ringInRing( polygon[i], polygon[0] ) ) 00170 { 00171 QString msg = QObject::tr( "ring %1 of polygon %2 not in exterior ring" ).arg( i ).arg( idx ); 00172 QgsDebugMsg( msg ); 00173 emit errorFound( QgsGeometry::Error( msg ) ); 00174 mErrorCount++; 00175 } 00176 } 00177 00178 // check holes for intersections 00179 for ( int i = 1; !mStop && i < polygon.size(); i++ ) 00180 { 00181 for ( int j = i + 1; !mStop && j < polygon.size(); j++ ) 00182 { 00183 checkRingIntersections( idx, i, polygon[i], idx, j, polygon[j] ); 00184 } 00185 } 00186 00187 // check if rings are self-intersecting 00188 for ( int i = 0; !mStop && i < polygon.size(); i++ ) 00189 { 00190 validatePolyline( i, polygon[i], true ); 00191 } 00192 } 00193 00194 void QgsGeometryValidator::run() 00195 { 00196 mErrorCount = 0; 00197 #if defined(GEOS_VERSION_MAJOR) && defined(GEOS_VERSION_MINOR) && \ 00198 ( (GEOS_VERSION_MAJOR==3 && GEOS_VERSION_MINOR>=3) || GEOS_VERSION_MAJOR>3) 00199 QSettings settings; 00200 if ( settings.value( "/qgis/digitizing/validate_geometries", 1 ).toInt() == 2 ) 00201 { 00202 char *r = 0; 00203 GEOSGeometry *g0 = mG.asGeos(); 00204 if ( !g0 ) 00205 { 00206 emit errorFound( QgsGeometry::Error( QObject::tr( "GEOS error:could not produce geometry for GEOS (check log window)" ) ) ); 00207 } 00208 else 00209 { 00210 GEOSGeometry *g1 = 0; 00211 if ( GEOSisValidDetail( g0, GEOSVALID_ALLOW_SELFTOUCHING_RING_FORMING_HOLE, &r, &g1 ) != 1 ) 00212 { 00213 if ( g1 ) 00214 { 00215 const GEOSCoordSequence *cs = GEOSGeom_getCoordSeq( g1 ); 00216 00217 unsigned int n; 00218 if ( GEOSCoordSeq_getSize( cs, &n ) && n == 1 ) 00219 { 00220 double x, y; 00221 GEOSCoordSeq_getX( cs, 0, &x ); 00222 GEOSCoordSeq_getY( cs, 0, &y ); 00223 emit errorFound( QgsGeometry::Error( QObject::tr( "GEOS error:%1" ).arg( r ), QgsPoint( x, y ) ) ); 00224 mErrorCount++; 00225 } 00226 00227 GEOSGeom_destroy( g1 ); 00228 } 00229 else 00230 { 00231 emit errorFound( QgsGeometry::Error( QObject::tr( "GEOS error:%1" ).arg( r ) ) ); 00232 mErrorCount++; 00233 } 00234 00235 GEOSFree( r ); 00236 } 00237 } 00238 00239 return; 00240 } 00241 #endif 00242 00243 QgsDebugMsg( "validation thread started." ); 00244 00245 switch ( mG.wkbType() ) 00246 { 00247 case QGis::WKBPoint: 00248 case QGis::WKBPoint25D: 00249 case QGis::WKBMultiPoint: 00250 case QGis::WKBMultiPoint25D: 00251 break; 00252 00253 case QGis::WKBLineString: 00254 case QGis::WKBLineString25D: 00255 validatePolyline( 0, mG.asPolyline() ); 00256 break; 00257 00258 case QGis::WKBMultiLineString: 00259 case QGis::WKBMultiLineString25D: 00260 { 00261 QgsMultiPolyline mp = mG.asMultiPolyline(); 00262 for ( int i = 0; !mStop && i < mp.size(); i++ ) 00263 validatePolyline( i, mp[i] ); 00264 } 00265 break; 00266 00267 case QGis::WKBPolygon: 00268 case QGis::WKBPolygon25D: 00269 { 00270 validatePolygon( 0, mG.asPolygon() ); 00271 } 00272 break; 00273 00274 case QGis::WKBMultiPolygon: 00275 case QGis::WKBMultiPolygon25D: 00276 { 00277 QgsMultiPolygon mp = mG.asMultiPolygon(); 00278 for ( int i = 0; !mStop && i < mp.size(); i++ ) 00279 { 00280 validatePolygon( i, mp[i] ); 00281 } 00282 00283 for ( int i = 0; !mStop && i < mp.size(); i++ ) 00284 { 00285 for ( int j = i + 1; !mStop && j < mp.size(); j++ ) 00286 { 00287 if ( ringInRing( mp[i][0], mp[j][0] ) ) 00288 { 00289 emit errorFound( QgsGeometry::Error( QObject::tr( "polygon %1 inside polygon %2" ).arg( i ).arg( j ) ) ); 00290 mErrorCount++; 00291 } 00292 else if ( ringInRing( mp[j][0], mp[i][0] ) ) 00293 { 00294 emit errorFound( QgsGeometry::Error( QObject::tr( "polygon %1 inside polygon %2" ).arg( j ).arg( i ) ) ); 00295 mErrorCount++; 00296 } 00297 else 00298 { 00299 checkRingIntersections( i, 0, mp[i][0], j, 0, mp[j][0] ); 00300 } 00301 } 00302 } 00303 } 00304 break; 00305 00306 case QGis::WKBNoGeometry: 00307 case QGis::WKBUnknown: 00308 QgsDebugMsg( QObject::tr( "Unknown geometry type" ) ); 00309 emit errorFound( QgsGeometry::Error( QObject::tr( "Unknown geometry type %1" ).arg( mG.wkbType() ) ) ); 00310 mErrorCount++; 00311 break; 00312 } 00313 00314 QgsDebugMsg( "validation finished." ); 00315 00316 if ( mStop ) 00317 { 00318 emit errorFound( QObject::tr( "Geometry validation was aborted." ) ); 00319 } 00320 else if ( mErrorCount > 0 ) 00321 { 00322 emit errorFound( QObject::tr( "Geometry has %1 errors." ).arg( mErrorCount ) ); 00323 } 00324 #if 0 00325 else 00326 { 00327 emit errorFound( QObject::tr( "Geometry is valid." ) ); 00328 } 00329 #endif 00330 } 00331 00332 void QgsGeometryValidator::addError( QgsGeometry::Error e ) 00333 { 00334 if ( mErrors ) 00335 *mErrors << e; 00336 } 00337 00338 void QgsGeometryValidator::validateGeometry( QgsGeometry *g, QList<QgsGeometry::Error> &errors ) 00339 { 00340 QgsGeometryValidator *gv = new QgsGeometryValidator( g, &errors ); 00341 connect( gv, SIGNAL( errorFound( QgsGeometry::Error ) ), gv, SLOT( addError( QgsGeometry::Error ) ) ); 00342 gv->run(); 00343 gv->wait(); 00344 } 00345 00346 // 00347 // distance of point q from line through p in direction v 00348 // return >0 => q lies left of the line 00349 // <0 => q lies right of the line 00350 // 00351 double QgsGeometryValidator::distLine2Point( QgsPoint p, QgsVector v, QgsPoint q ) 00352 { 00353 if ( v.length() == 0 ) 00354 { 00355 throw QgsException( QObject::tr( "invalid line" ) ); 00356 } 00357 00358 return ( v.x()*( q.y() - p.y() ) - v.y()*( q.x() - p.x() ) ) / v.length(); 00359 } 00360 00361 bool QgsGeometryValidator::intersectLines( QgsPoint p, QgsVector v, QgsPoint q, QgsVector w, QgsPoint &s ) 00362 { 00363 double d = v.y() * w.x() - v.x() * w.y(); 00364 00365 if ( d == 0 ) 00366 return false; 00367 00368 double dx = q.x() - p.x(); 00369 double dy = q.y() - p.y(); 00370 double k = ( dy * w.x() - dx * w.y() ) / d; 00371 00372 s = p + v * k; 00373 00374 return true; 00375 } 00376 00377 bool QgsGeometryValidator::pointInRing( const QgsPolyline &ring, const QgsPoint &p ) 00378 { 00379 bool inside = false; 00380 int j = ring.size() - 1; 00381 00382 for ( int i = 0; !mStop && i < ring.size(); i++ ) 00383 { 00384 if ( ring[i].x() == p.x() && ring[i].y() == p.y() ) 00385 return true; 00386 00387 if (( ring[i].y() < p.y() && ring[j].y() >= p.y() ) || 00388 ( ring[j].y() < p.y() && ring[i].y() >= p.y() ) ) 00389 { 00390 if ( ring[i].x() + ( p.y() - ring[i].y() ) / ( ring[j].y() - ring[i].y() )*( ring[j].x() - ring[i].x() ) <= p.x() ) 00391 inside = !inside; 00392 } 00393 00394 j = i; 00395 } 00396 00397 return inside; 00398 } 00399 00400 bool QgsGeometryValidator::ringInRing( const QgsPolyline &inside, const QgsPolyline &outside ) 00401 { 00402 for ( int i = 0; !mStop && i < inside.size(); i++ ) 00403 { 00404 if ( !pointInRing( outside, inside[i] ) ) 00405 return false; 00406 } 00407 00408 return true; 00409 }