QGIS API Documentation  2.99.0-Master (314842d)
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 #include "qgssettings.h"
21 
22 QgsGeometryValidator::QgsGeometryValidator( const QgsGeometry *g, QList<QgsGeometry::Error> *errors )
23  : QThread()
24  , mErrors( errors )
25  , mStop( false )
26  , mErrorCount( 0 )
27 {
28  Q_ASSERT( g );
29  if ( g )
30  mG = *g;
31 }
32 
34 {
35  stop();
36  wait();
37 }
38 
40 {
41  mStop = true;
42 }
43 
44 void QgsGeometryValidator::checkRingIntersections(
45  int p0, int i0, const QgsPolyline &ring0,
46  int p1, int i1, const QgsPolyline &ring1 )
47 {
48  for ( int i = 0; !mStop && i < ring0.size() - 1; i++ )
49  {
50  QgsVector v = ring0[i + 1] - ring0[i];
51 
52  for ( int j = 0; !mStop && j < ring1.size() - 1; j++ )
53  {
54  QgsVector w = ring1[j + 1] - ring1[j];
55 
56  QgsPoint s;
57  if ( intersectLines( ring0[i], v, ring1[j], w, s ) )
58  {
59  double d = -distLine2Point( ring0[i], v.perpVector(), s );
60 
61  if ( d >= 0 && d <= v.length() )
62  {
63  d = -distLine2Point( ring1[j], w.perpVector(), s );
64  if ( d > 0 && d < w.length() &&
65  ring0[i + 1] != ring1[j + 1] && ring0[i + 1] != ring1[j] &&
66  ring0[i + 0] != ring1[j + 1] && ring0[i + 0] != ring1[j] )
67  {
68  QString msg = QObject::tr( "segment %1 of ring %2 of polygon %3 intersects segment %4 of ring %5 of polygon %6 at %7" )
69  .arg( i0 ).arg( i ).arg( p0 )
70  .arg( i1 ).arg( j ).arg( p1 )
71  .arg( s.toString() );
72  QgsDebugMsg( msg );
73  emit errorFound( QgsGeometry::Error( msg, s ) );
74  mErrorCount++;
75  }
76  }
77  }
78  }
79  }
80 }
81 
82 void QgsGeometryValidator::validatePolyline( int i, QgsPolyline line, bool ring )
83 {
84  if ( ring )
85  {
86  if ( line.size() < 4 )
87  {
88  QString msg = QObject::tr( "ring %1 with less than four points" ).arg( i );
89  QgsDebugMsg( msg );
90  emit errorFound( QgsGeometry::Error( msg ) );
91  mErrorCount++;
92  return;
93  }
94 
95  if ( line[0] != line[ line.size() - 1 ] )
96  {
97  QString msg = QObject::tr( "ring %1 not closed" ).arg( i );
98  QgsDebugMsg( msg );
99  emit errorFound( QgsGeometry::Error( msg ) );
100  mErrorCount++;
101  return;
102  }
103  }
104  else if ( line.size() < 2 )
105  {
106  QString msg = QObject::tr( "line %1 with less than two points" ).arg( i );
107  QgsDebugMsg( msg );
108  emit errorFound( QgsGeometry::Error( msg ) );
109  mErrorCount++;
110  return;
111  }
112 
113  int j = 0;
114  while ( j < line.size() - 1 )
115  {
116  int n = 0;
117  while ( j < line.size() - 1 && line[j] == line[j + 1] )
118  {
119  line.remove( j );
120  n++;
121  }
122 
123  if ( n > 0 )
124  {
125  QString msg = QObject::tr( "line %1 contains %n duplicate node(s) at %2", "number of duplicate nodes", n ).arg( i ).arg( j );
126  QgsDebugMsg( msg );
127  emit errorFound( QgsGeometry::Error( msg, line[j] ) );
128  mErrorCount++;
129  }
130 
131  j++;
132  }
133 
134  for ( j = 0; !mStop && j < line.size() - 3; j++ )
135  {
136  QgsVector v = line[j + 1] - line[j];
137  double vl = v.length();
138 
139  int n = ( j == 0 && ring ) ? line.size() - 2 : line.size() - 1;
140 
141  for ( int k = j + 2; !mStop && k < n; k++ )
142  {
143  QgsVector w = line[k + 1] - line[k];
144 
145  QgsPoint s;
146  if ( !intersectLines( line[j], v, line[k], w, s ) )
147  continue;
148 
149  double d = 0.0;
150  try
151  {
152  d = -distLine2Point( line[j], v.perpVector(), s );
153  }
154  catch ( QgsException &e )
155  {
156  Q_UNUSED( e );
157  QgsDebugMsg( "Error validating: " + e.what() );
158  continue;
159  }
160  if ( d < 0 || d > vl )
161  continue;
162 
163  try
164  {
165  d = -distLine2Point( line[k], w.perpVector(), s );
166  }
167  catch ( QgsException &e )
168  {
169  Q_UNUSED( e );
170  QgsDebugMsg( "Error validating: " + e.what() );
171  continue;
172  }
173 
174  if ( d <= 0 || d >= w.length() )
175  continue;
176 
177  QString msg = QObject::tr( "segments %1 and %2 of line %3 intersect at %4" ).arg( j ).arg( k ).arg( i ).arg( s.toString() );
178  QgsDebugMsg( msg );
179  emit errorFound( QgsGeometry::Error( msg, s ) );
180  mErrorCount++;
181  }
182  }
183 }
184 
185 void QgsGeometryValidator::validatePolygon( int idx, const QgsPolygon &polygon )
186 {
187  // check if holes are inside polygon
188  for ( int i = 1; !mStop && i < polygon.size(); i++ )
189  {
190  if ( !ringInRing( polygon[i], polygon[0] ) )
191  {
192  QString msg = QObject::tr( "ring %1 of polygon %2 not in exterior ring" ).arg( i ).arg( idx );
193  QgsDebugMsg( msg );
194  emit errorFound( QgsGeometry::Error( msg ) );
195  mErrorCount++;
196  }
197  }
198 
199  // check holes for intersections
200  for ( int i = 1; !mStop && i < polygon.size(); i++ )
201  {
202  for ( int j = i + 1; !mStop && j < polygon.size(); j++ )
203  {
204  checkRingIntersections( idx, i, polygon[i], idx, j, polygon[j] );
205  }
206  }
207 
208  // check if rings are self-intersecting
209  for ( int i = 0; !mStop && i < polygon.size(); i++ )
210  {
211  validatePolyline( i, polygon[i], true );
212  }
213 }
214 
216 {
217  mErrorCount = 0;
218  QgsSettings settings;
219  if ( settings.value( QStringLiteral( "qgis/digitizing/validate_geometries" ), 1 ).toInt() == 2 )
220  {
221  char *r = nullptr;
222  GEOSGeometry *g0 = mG.exportToGeos();
223  GEOSContextHandle_t handle = QgsGeometry::getGEOSHandler();
224  if ( !g0 )
225  {
226  emit errorFound( QgsGeometry::Error( QObject::tr( "GEOS error:could not produce geometry for GEOS (check log window)" ) ) );
227  }
228  else
229  {
230  GEOSGeometry *g1 = nullptr;
231  char res = GEOSisValidDetail_r( handle, g0, GEOSVALID_ALLOW_SELFTOUCHING_RING_FORMING_HOLE, &r, &g1 );
232  GEOSGeom_destroy_r( handle, g0 );
233  if ( res != 1 )
234  {
235  if ( g1 )
236  {
237  const GEOSCoordSequence *cs = GEOSGeom_getCoordSeq_r( handle, g1 );
238 
239  unsigned int n;
240  if ( GEOSCoordSeq_getSize_r( handle, cs, &n ) && n == 1 )
241  {
242  double x, y;
243  GEOSCoordSeq_getX_r( handle, cs, 0, &x );
244  GEOSCoordSeq_getY_r( handle, cs, 0, &y );
245  emit errorFound( QgsGeometry::Error( QObject::tr( "GEOS error:%1" ).arg( r ), QgsPoint( x, y ) ) );
246  mErrorCount++;
247  }
248 
249  GEOSGeom_destroy_r( handle, g1 );
250  }
251  else
252  {
253  emit errorFound( QgsGeometry::Error( QObject::tr( "GEOS error:%1" ).arg( r ) ) );
254  mErrorCount++;
255  }
256 
257  GEOSFree_r( handle, r );
258  }
259  }
260 
261  return;
262  }
263 
264  QgsDebugMsg( "validation thread started." );
265 
267  //if ( flatType == QgsWkbTypes::Point || flatType == QgsWkbTypes::MultiPoint )
268  // break;
269  if ( flatType == QgsWkbTypes::LineString )
270  {
271  validatePolyline( 0, mG.asPolyline() );
272  }
273  else if ( flatType == QgsWkbTypes::MultiLineString )
274  {
276  for ( int i = 0; !mStop && i < mp.size(); i++ )
277  validatePolyline( i, mp[i] );
278  }
279  else if ( flatType == QgsWkbTypes::Polygon )
280  {
281  validatePolygon( 0, mG.asPolygon() );
282  }
283  else if ( flatType == QgsWkbTypes::MultiPolygon )
284  {
286  for ( int i = 0; !mStop && i < mp.size(); i++ )
287  {
288  validatePolygon( i, mp[i] );
289  }
290 
291  for ( int i = 0; !mStop && i < mp.size(); i++ )
292  {
293  if ( mp[i].isEmpty() )
294  {
295  emit errorFound( QgsGeometry::Error( QObject::tr( "polygon %1 has no rings" ).arg( i ) ) );
296  mErrorCount++;
297  continue;
298  }
299 
300  for ( int j = i + 1; !mStop && j < mp.size(); j++ )
301  {
302  if ( mp[j].isEmpty() )
303  continue;
304 
305  if ( ringInRing( mp[i][0], mp[j][0] ) )
306  {
307  emit errorFound( QgsGeometry::Error( QObject::tr( "polygon %1 inside polygon %2" ).arg( i ).arg( j ) ) );
308  mErrorCount++;
309  }
310  else if ( ringInRing( mp[j][0], mp[i][0] ) )
311  {
312  emit errorFound( QgsGeometry::Error( QObject::tr( "polygon %1 inside polygon %2" ).arg( j ).arg( i ) ) );
313  mErrorCount++;
314  }
315  else
316  {
317  checkRingIntersections( i, 0, mp[i][0], j, 0, mp[j][0] );
318  }
319  }
320  }
321  }
322 
323  else if ( flatType == QgsWkbTypes::Unknown )
324  {
325  QgsDebugMsg( QObject::tr( "Unknown geometry type" ) );
326  emit errorFound( QgsGeometry::Error( QObject::tr( "Unknown geometry type %1" ).arg( mG.wkbType() ) ) );
327  mErrorCount++;
328  }
329 
330  QgsDebugMsg( "validation finished." );
331 
332  if ( mStop )
333  {
334  emit errorFound( QgsGeometry::Error( QObject::tr( "Geometry validation was aborted." ) ) );
335  }
336  else if ( mErrorCount > 0 )
337  {
338  emit errorFound( QgsGeometry::Error( QObject::tr( "Geometry has %1 errors." ).arg( mErrorCount ) ) );
339  }
340 #if 0
341  else
342  {
343  emit errorFound( QgsGeometry::Error( QObject::tr( "Geometry is valid." ) ) );
344  }
345 #endif
346 }
347 
349 {
350  if ( mErrors )
351  *mErrors << e;
352 }
353 
354 void QgsGeometryValidator::validateGeometry( const QgsGeometry *g, QList<QgsGeometry::Error> &errors )
355 {
356  QgsGeometryValidator *gv = new QgsGeometryValidator( g, &errors );
358  gv->run();
359  gv->wait();
360 }
361 
362 //
363 // distance of point q from line through p in direction v
364 // return >0 => q lies left of the line
365 // <0 => q lies right of the line
366 //
367 double QgsGeometryValidator::distLine2Point( const QgsPoint &p, QgsVector v, const QgsPoint &q )
368 {
369  if ( qgsDoubleNear( v.length(), 0 ) )
370  {
371  throw QgsException( QObject::tr( "invalid line" ) );
372  }
373 
374  return ( v.x() * ( q.y() - p.y() ) - v.y() * ( q.x() - p.x() ) ) / v.length();
375 }
376 
377 bool QgsGeometryValidator::intersectLines( const QgsPoint &p, QgsVector v, const QgsPoint &q, QgsVector w, QgsPoint &s )
378 {
379  double d = v.y() * w.x() - v.x() * w.y();
380 
381  if ( qgsDoubleNear( d, 0 ) )
382  return false;
383 
384  double dx = q.x() - p.x();
385  double dy = q.y() - p.y();
386  double k = ( dy * w.x() - dx * w.y() ) / d;
387 
388  s = p + v * k;
389 
390  return true;
391 }
392 
393 bool QgsGeometryValidator::pointInRing( const QgsPolyline &ring, const QgsPoint &p )
394 {
395  bool inside = false;
396  int j = ring.size() - 1;
397 
398  for ( int i = 0; !mStop && i < ring.size(); i++ )
399  {
400  if ( qgsDoubleNear( ring[i].x(), p.x() ) && qgsDoubleNear( ring[i].y(), p.y() ) )
401  return true;
402 
403  if ( ( ring[i].y() < p.y() && ring[j].y() >= p.y() ) ||
404  ( ring[j].y() < p.y() && ring[i].y() >= p.y() ) )
405  {
406  if ( ring[i].x() + ( p.y() - ring[i].y() ) / ( ring[j].y() - ring[i].y() ) * ( ring[j].x() - ring[i].x() ) <= p.x() )
407  inside = !inside;
408  }
409 
410  j = i;
411  }
412 
413  return inside;
414 }
415 
416 bool QgsGeometryValidator::ringInRing( const QgsPolyline &inside, const QgsPolyline &outside )
417 {
418  for ( int i = 0; !mStop && i < inside.size(); i++ )
419  {
420  if ( !pointInRing( outside, inside[i] ) )
421  return false;
422  }
423 
424  return true;
425 }
QgsPolygon asPolygon() const
Return contents of the geometry as a polygon if wkbType is WKBPolygon, otherwise an empty list...
QgsMultiPolyline asMultiPolyline() const
Return contents of the geometry as a multi linestring if wkbType is WKBMultiLineString, otherwise an empty list.
double y
Definition: qgspoint.h:42
This class is a composition of two QSettings instances:
Definition: qgssettings.h:51
#define QgsDebugMsg(str)
Definition: qgslogger.h:36
void addError(const QgsGeometry::Error &)
QgsWkbTypes::Type wkbType() const
Returns type of the geometry as a WKB type (point / linestring / polygon etc.)
QVector< QgsPoint > QgsPolyline
Polyline is represented as a vector of points.
Definition: qgsgeometry.h:47
A geometry is the spatial representation of a feature.
Definition: qgsgeometry.h:79
bool qgsDoubleNear(double a, double b, double epsilon=4 *DBL_EPSILON)
Compare two doubles (but allow some difference)
Definition: qgis.h:198
QgsPolyline asPolyline() const
Return contents of the geometry as a polyline if wkbType is WKBLineString, otherwise an empty list...
QString what() const
Definition: qgsexception.h:38
Type
The WKB type describes the number of dimensions a geometry has.
Definition: qgswkbtypes.h:65
QVector< QgsPolygon > QgsMultiPolygon
A collection of QgsPolygons that share a common collection of attributes.
Definition: qgsgeometry.h:62
QVector< QgsPolyline > QgsPolygon
Polygon: first item of the list is outer ring, inner rings (if any) start from second item...
Definition: qgsgeometry.h:53
void errorFound(const QgsGeometry::Error &)
A class to represent a point.
Definition: qgspoint.h:37
QString toString() const
String representation of the point (x,y)
Definition: qgspoint.cpp:45
double length() const
Returns the length of the vector.
Definition: qgsvector.cpp:77
A class to represent a vector.
Definition: qgsvector.h:26
static void validateGeometry(const QgsGeometry *g, QList< QgsGeometry::Error > &errors)
Validate geometry and produce a list of geometry errors.
QVector< QgsPolyline > QgsMultiPolyline
A collection of QgsPolylines that share a common collection of attributes.
Definition: qgsgeometry.h:59
QgsVector perpVector() const
Returns the perpendicular vector to this vector (rotated 90 degrees counter-clockwise) ...
Definition: qgsvector.cpp:92
static GEOSContextHandle_t getGEOSHandler()
Return GEOS context handle.
GEOSGeometry * exportToGeos(double precision=0) const
Returns a geos geometry - caller takes ownership of the object (should be deleted with GEOSGeom_destr...
QgsMultiPolygon asMultiPolygon() const
Return contents of the geometry as a multi polygon if wkbType is WKBMultiPolygon, otherwise an empty ...
QVariant value(const QString &key, const QVariant &defaultValue=QVariant(), const Section section=Section::NoSection) const
Returns the value for setting key.
double x() const
Returns the vector&#39;s x-component.
Definition: qgsvector.cpp:82
static Type flatType(Type type)
Returns the flat type for a WKB type.
Definition: qgswkbtypes.h:422
QgsGeometryValidator(const QgsGeometry *g, QList< QgsGeometry::Error > *errors=nullptr)
Constructor.
double y() const
Returns the vector&#39;s y-component.
Definition: qgsvector.cpp:87
Defines a qgis exception class.
Definition: qgsexception.h:27
double x
Definition: qgspoint.h:41