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