QGIS API Documentation  2.11.0-Master
qgsgeometryvalidator.cpp
Go to the documentation of this file.
1 /***************************************************************************
2  qgsgeometryvalidator.cpp - geometry validation thread
3  -------------------------------------------------------------------
4 Date : 03.01.2012
5 Copyright : (C) 2012 by Juergen E. Fischer
6 email : jef at norbit dot de
7  ***************************************************************************
8  * *
9  * This program is free software; you can redistribute it and/or modify *
10  * it under the terms of the GNU General Public License as published by *
11  * the Free Software Foundation; either version 2 of the License, or *
12  * (at your option) any later version. *
13  * *
14  ***************************************************************************/
15 
16 #include "qgis.h"
17 #include "qgsgeometryvalidator.h"
18 #include "qgsgeometry.h"
19 #include "qgslogger.h"
20 
21 #include <QSettings>
22 
24  : QThread()
25  , mErrors( errors )
26  , mStop( false )
27  , mErrorCount( 0 )
28 {
29  Q_ASSERT( g );
30  if ( g )
31  mG = *g;
32 }
33 
35 {
36  stop();
37  wait();
38 }
39 
41 {
42  mStop = true;
43 }
44 
45 void QgsGeometryValidator::checkRingIntersections(
46  int p0, int i0, const QgsPolyline &ring0,
47  int p1, int i1, const QgsPolyline &ring1 )
48 {
49  for ( int i = 0; !mStop && i < ring0.size() - 1; i++ )
50  {
51  QgsVector v = ring0[i+1] - ring0[i];
52 
53  for ( int j = 0; !mStop && j < ring1.size() - 1; j++ )
54  {
55  QgsVector w = ring1[j+1] - ring1[j];
56 
57  QgsPoint s;
58  if ( intersectLines( ring0[i], v, ring1[j], w, s ) )
59  {
60  double d = -distLine2Point( ring0[i], v.perpVector(), s );
61 
62  if ( d >= 0 && d <= v.length() )
63  {
64  d = -distLine2Point( ring1[j], w.perpVector(), s );
65  if ( d > 0 && d < w.length() &&
66  ring0[i+1] != ring1[j+1] && ring0[i+1] != ring1[j] &&
67  ring0[i+0] != ring1[j+1] && ring0[i+0] != ring1[j] )
68  {
69  QString msg = QObject::tr( "segment %1 of ring %2 of polygon %3 intersects segment %4 of ring %5 of polygon %6 at %7" )
70  .arg( i0 ).arg( i ).arg( p0 )
71  .arg( i1 ).arg( j ).arg( p1 )
72  .arg( s.toString() );
73  QgsDebugMsg( msg );
74  emit errorFound( QgsGeometry::Error( msg, s ) );
75  mErrorCount++;
76  }
77  }
78  }
79  }
80  }
81 }
82 
83 void QgsGeometryValidator::validatePolyline( int i, QgsPolyline line, bool ring )
84 {
85  if ( ring )
86  {
87  if ( line.size() < 4 )
88  {
89  QString msg = QObject::tr( "ring %1 with less than four points" ).arg( i );
90  QgsDebugMsg( msg );
91  emit errorFound( QgsGeometry::Error( msg ) );
92  mErrorCount++;
93  return;
94  }
95 
96  if ( line[0] != line[ line.size()-1 ] )
97  {
98  QString msg = QObject::tr( "ring %1 not closed" ).arg( i );
99  QgsDebugMsg( msg );
100  emit errorFound( QgsGeometry::Error( msg ) );
101  mErrorCount++;
102  return;
103  }
104  }
105  else if ( line.size() < 2 )
106  {
107  QString msg = QObject::tr( "line %1 with less than two points" ).arg( i );
108  QgsDebugMsg( msg );
109  emit errorFound( QgsGeometry::Error( msg ) );
110  mErrorCount++;
111  return;
112  }
113 
114  int j = 0;
115  while ( j < line.size() - 1 )
116  {
117  int n = 0;
118  while ( j < line.size() - 1 && line[j] == line[j+1] )
119  {
120  line.remove( j );
121  n++;
122  }
123 
124  if ( n > 0 )
125  {
126  QString msg = QObject::tr( "line %1 contains %n duplicate node(s) at %2", "number of duplicate nodes", n ).arg( i ).arg( j );
127  QgsDebugMsg( msg );
128  emit errorFound( QgsGeometry::Error( msg, line[j] ) );
129  mErrorCount++;
130  }
131 
132  j++;
133  }
134 
135  for ( j = 0; !mStop && j < line.size() - 3; j++ )
136  {
137  QgsVector v = line[j+1] - line[j];
138  double vl = v.length();
139 
140  int n = ( j == 0 && ring ) ? line.size() - 2 : line.size() - 1;
141 
142  for ( int k = j + 2; !mStop && k < n; k++ )
143  {
144  QgsVector w = line[k+1] - line[k];
145 
146  QgsPoint s;
147  if ( !intersectLines( line[j], v, line[k], w, s ) )
148  continue;
149 
150  double d = -distLine2Point( line[j], v.perpVector(), s );
151  if ( d < 0 || d > vl )
152  continue;
153 
154  d = -distLine2Point( line[k], w.perpVector(), s );
155  if ( d <= 0 || d >= w.length() )
156  continue;
157 
158  QString msg = QObject::tr( "segments %1 and %2 of line %3 intersect at %4" ).arg( j ).arg( k ).arg( i ).arg( s.toString() );
159  QgsDebugMsg( msg );
160  emit errorFound( QgsGeometry::Error( msg, s ) );
161  mErrorCount++;
162  }
163  }
164 }
165 
166 void QgsGeometryValidator::validatePolygon( int idx, const QgsPolygon &polygon )
167 {
168  // check if holes are inside polygon
169  for ( int i = 1; !mStop && i < polygon.size(); i++ )
170  {
171  if ( !ringInRing( polygon[i], polygon[0] ) )
172  {
173  QString msg = QObject::tr( "ring %1 of polygon %2 not in exterior ring" ).arg( i ).arg( idx );
174  QgsDebugMsg( msg );
175  emit errorFound( QgsGeometry::Error( msg ) );
176  mErrorCount++;
177  }
178  }
179 
180  // check holes for intersections
181  for ( int i = 1; !mStop && i < polygon.size(); i++ )
182  {
183  for ( int j = i + 1; !mStop && j < polygon.size(); j++ )
184  {
185  checkRingIntersections( idx, i, polygon[i], idx, j, polygon[j] );
186  }
187  }
188 
189  // check if rings are self-intersecting
190  for ( int i = 0; !mStop && i < polygon.size(); i++ )
191  {
192  validatePolyline( i, polygon[i], true );
193  }
194 }
195 
197 {
198  mErrorCount = 0;
199 #if defined(GEOS_VERSION_MAJOR) && defined(GEOS_VERSION_MINOR) && \
200  ( (GEOS_VERSION_MAJOR==3 && GEOS_VERSION_MINOR>=3) || GEOS_VERSION_MAJOR>3)
201  QSettings settings;
202  if ( settings.value( "/qgis/digitizing/validate_geometries", 1 ).toInt() == 2 )
203  {
204  char *r = 0;
205  const GEOSGeometry *g0 = mG.asGeos();
206  GEOSContextHandle_t handle = QgsGeometry::getGEOSHandler();
207  if ( !g0 )
208  {
209  emit errorFound( QgsGeometry::Error( QObject::tr( "GEOS error:could not produce geometry for GEOS (check log window)" ) ) );
210  }
211  else
212  {
213  GEOSGeometry *g1 = 0;
214  if ( GEOSisValidDetail_r( handle, g0, GEOSVALID_ALLOW_SELFTOUCHING_RING_FORMING_HOLE, &r, &g1 ) != 1 )
215  {
216  if ( g1 )
217  {
218  const GEOSCoordSequence *cs = GEOSGeom_getCoordSeq_r( handle, g1 );
219 
220  unsigned int n;
221  if ( GEOSCoordSeq_getSize_r( handle, cs, &n ) && n == 1 )
222  {
223  double x, y;
224  GEOSCoordSeq_getX_r( handle, cs, 0, &x );
225  GEOSCoordSeq_getY_r( handle, cs, 0, &y );
226  emit errorFound( QgsGeometry::Error( QObject::tr( "GEOS error:%1" ).arg( r ), QgsPoint( x, y ) ) );
227  mErrorCount++;
228  }
229 
230  GEOSGeom_destroy_r( handle, g1 );
231  }
232  else
233  {
234  emit errorFound( QgsGeometry::Error( QObject::tr( "GEOS error:%1" ).arg( r ) ) );
235  mErrorCount++;
236  }
237 
238  GEOSFree_r( handle, r );
239  }
240  }
241 
242  return;
243  }
244 #endif
245 
246  QgsDebugMsg( "validation thread started." );
247 
248  switch ( mG.wkbType() )
249  {
250  case QGis::WKBPoint:
251  case QGis::WKBPoint25D:
252  case QGis::WKBMultiPoint:
254  break;
255 
256  case QGis::WKBLineString:
258  validatePolyline( 0, mG.asPolyline() );
259  break;
260 
263  {
265  for ( int i = 0; !mStop && i < mp.size(); i++ )
266  validatePolyline( i, mp[i] );
267  }
268  break;
269 
270  case QGis::WKBPolygon:
271  case QGis::WKBPolygon25D:
272  {
273  validatePolygon( 0, mG.asPolygon() );
274  }
275  break;
276 
279  {
281  for ( int i = 0; !mStop && i < mp.size(); i++ )
282  {
283  validatePolygon( i, mp[i] );
284  }
285 
286  for ( int i = 0; !mStop && i < mp.size(); i++ )
287  {
288  if ( mp[i].isEmpty() )
289  {
290  emit errorFound( QgsGeometry::Error( QObject::tr( "polygon %1 has no rings" ).arg( i ) ) );
291  mErrorCount++;
292  continue;
293  }
294 
295  for ( int j = i + 1; !mStop && j < mp.size(); j++ )
296  {
297  if ( mp[j].isEmpty() )
298  continue;
299 
300  if ( ringInRing( mp[i][0], mp[j][0] ) )
301  {
302  emit errorFound( QgsGeometry::Error( QObject::tr( "polygon %1 inside polygon %2" ).arg( i ).arg( j ) ) );
303  mErrorCount++;
304  }
305  else if ( ringInRing( mp[j][0], mp[i][0] ) )
306  {
307  emit errorFound( QgsGeometry::Error( QObject::tr( "polygon %1 inside polygon %2" ).arg( j ).arg( i ) ) );
308  mErrorCount++;
309  }
310  else
311  {
312  checkRingIntersections( i, 0, mp[i][0], j, 0, mp[j][0] );
313  }
314  }
315  }
316  }
317  break;
318 
319  case QGis::WKBNoGeometry:
320  case QGis::WKBUnknown:
321  QgsDebugMsg( QObject::tr( "Unknown geometry type" ) );
322  emit errorFound( QgsGeometry::Error( QObject::tr( "Unknown geometry type %1" ).arg( mG.wkbType() ) ) );
323  mErrorCount++;
324  break;
325  }
326 
327  QgsDebugMsg( "validation finished." );
328 
329  if ( mStop )
330  {
331  emit errorFound( QObject::tr( "Geometry validation was aborted." ) );
332  }
333  else if ( mErrorCount > 0 )
334  {
335  emit errorFound( QObject::tr( "Geometry has %1 errors." ).arg( mErrorCount ) );
336  }
337 #if 0
338  else
339  {
340  emit errorFound( QObject::tr( "Geometry is valid." ) );
341  }
342 #endif
343 }
344 
346 {
347  if ( mErrors )
348  *mErrors << e;
349 }
350 
352 {
353  QgsGeometryValidator *gv = new QgsGeometryValidator( g, &errors );
354  connect( gv, SIGNAL( errorFound( QgsGeometry::Error ) ), gv, SLOT( addError( QgsGeometry::Error ) ) );
355  gv->run();
356  gv->wait();
357 }
358 
359 //
360 // distance of point q from line through p in direction v
361 // return >0 => q lies left of the line
362 // <0 => q lies right of the line
363 //
364 double QgsGeometryValidator::distLine2Point( QgsPoint p, QgsVector v, QgsPoint q )
365 {
366  if ( v.length() == 0 )
367  {
368  throw QgsException( QObject::tr( "invalid line" ) );
369  }
370 
371  return ( v.x()*( q.y() - p.y() ) - v.y()*( q.x() - p.x() ) ) / v.length();
372 }
373 
374 bool QgsGeometryValidator::intersectLines( QgsPoint p, QgsVector v, QgsPoint q, QgsVector w, QgsPoint &s )
375 {
376  double d = v.y() * w.x() - v.x() * w.y();
377 
378  if ( d == 0 )
379  return false;
380 
381  double dx = q.x() - p.x();
382  double dy = q.y() - p.y();
383  double k = ( dy * w.x() - dx * w.y() ) / d;
384 
385  s = p + v * k;
386 
387  return true;
388 }
389 
390 bool QgsGeometryValidator::pointInRing( const QgsPolyline &ring, const QgsPoint &p )
391 {
392  bool inside = false;
393  int j = ring.size() - 1;
394 
395  for ( int i = 0; !mStop && i < ring.size(); i++ )
396  {
397  if ( ring[i].x() == p.x() && ring[i].y() == p.y() )
398  return true;
399 
400  if (( ring[i].y() < p.y() && ring[j].y() >= p.y() ) ||
401  ( ring[j].y() < p.y() && ring[i].y() >= p.y() ) )
402  {
403  if ( ring[i].x() + ( p.y() - ring[i].y() ) / ( ring[j].y() - ring[i].y() )*( ring[j].x() - ring[i].x() ) <= p.x() )
404  inside = !inside;
405  }
406 
407  j = i;
408  }
409 
410  return inside;
411 }
412 
413 bool QgsGeometryValidator::ringInRing( const QgsPolyline &inside, const QgsPolyline &outside )
414 {
415  for ( int i = 0; !mStop && i < inside.size(); i++ )
416  {
417  if ( !pointInRing( outside, inside[i] ) )
418  return false;
419  }
420 
421  return true;
422 }
void addError(QgsGeometry::Error)
#define QgsDebugMsg(str)
Definition: qgslogger.h:33
QgsMultiPolyline asMultiPolyline() const
Return contents of the geometry as a multi linestring if wkbType is WKBMultiLineString, otherwise an empty list.
QgsPolygon asPolygon() const
Return contents of the geometry as a polygon if wkbType is WKBPolygon, otherwise an empty list...
double y() const
Definition: qgspoint.cpp:69
A geometry is the spatial representation of a feature.
Definition: qgsgeometry.h:75
QString tr(const char *sourceText, const char *disambiguation, int n)
double x() const
Get the x value of the point.
Definition: qgspoint.h:126
const GEOSGeometry * asGeos() const
Returns a geos geometry.
QgsMultiPolygon asMultiPolygon() const
Return contents of the geometry as a multi polygon if wkbType is WKBMultiPolygon, otherwise an empty ...
int toInt(bool *ok) const
QgsVector perpVector() const
Definition: qgspoint.cpp:75
void remove(int i)
QString toString() const
String representation of the point (x,y)
Definition: qgspoint.cpp:126
QGis::WkbType wkbType() const
Returns type of the geometry as a WKB type (point / linestring / polygon etc.)
A class to represent a point.
Definition: qgspoint.h:63
A class to represent a vector.
Definition: qgspoint.h:32
double length() const
Definition: qgspoint.cpp:59
static void validateGeometry(const QgsGeometry *g, QList< QgsGeometry::Error > &errors)
Validate geometry and produce a list of geometry errors.
QgsPolyline asPolyline() const
Return contents of the geometry as a polyline if wkbType is WKBLineString, otherwise an empty list...
QgsGeometryValidator(const QgsGeometry *g, QList< QgsGeometry::Error > *errors=0)
Constructor.
QVariant value(const QString &key, const QVariant &defaultValue) const
static GEOSContextHandle_t getGEOSHandler()
Return GEOS context handle.
bool wait(unsigned long time)
void errorFound(QgsGeometry::Error)
double y() const
Get the y value of the point.
Definition: qgspoint.h:134
double x() const
Definition: qgspoint.cpp:64
bool connect(const QObject *sender, const char *signal, const QObject *receiver, const char *method, Qt::ConnectionType type)
int size() const
QString arg(qlonglong a, int fieldWidth, int base, const QChar &fillChar) const
Defines a qgis exception class.
Definition: qgsexception.h:25