Quantum GIS API Documentation  1.8
src/core/qgsgeometryvalidator.cpp
Go to the documentation of this file.
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 }
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines