QGIS API Documentation  3.21.0-Master (5b68dc587e)
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 #include "qgsgeometrycollection.h"
22 #include "qgspolygon.h"
23 
24 QgsGeometryValidator::QgsGeometryValidator( const QgsGeometry &geometry, QVector<QgsGeometry::Error> *errors, Qgis::GeometryValidationEngine method )
25  : mGeometry( geometry )
26  , mErrors( errors )
27  , mStop( false )
28  , mErrorCount( 0 )
29  , mMethod( method )
30 {
31 }
32 
34 {
35  stop();
36  wait();
37 }
38 
40 {
41  mStop = true;
42 }
43 
44 void QgsGeometryValidator::checkRingIntersections( int partIndex0, int ringIndex0, const QgsLineString *ring0, int partIndex1, int ringIndex1, const QgsLineString *ring1 )
45 {
46  for ( int i = 0; !mStop && i < ring0->numPoints() - 1; i++ )
47  {
48  const double ring0XAti = ring0->xAt( i );
49  const double ring0YAti = ring0->yAt( i );
50  const QgsVector v( ring0->xAt( i + 1 ) - ring0XAti, ring0->yAt( i + 1 ) - ring0YAti );
51 
52  for ( int j = 0; !mStop && j < ring1->numPoints() - 1; j++ )
53  {
54  const double ring1XAtj = ring1->xAt( j );
55  const double ring1YAtj = ring1->yAt( j );
56  const QgsVector w( ring1->xAt( j + 1 ) - ring1XAtj, ring1->yAt( j + 1 ) - ring1YAtj );
57 
58  double sX;
59  double sY;
60  if ( intersectLines( ring0XAti, ring0YAti, v, ring1XAtj, ring1YAtj, w, sX, sY ) )
61  {
62  double d = -distLine2Point( ring0XAti, ring0YAti, v.perpVector(), sX, sY );
63 
64  if ( d >= 0 && d <= v.length() )
65  {
66  d = -distLine2Point( ring1XAtj, ring1YAtj, w.perpVector(), sX, sY );
67  if ( d > 0 && d < w.length() &&
68  ring0->pointN( i + 1 ) != ring1->pointN( j + 1 ) && ring0->pointN( i + 1 ) != ring1->pointN( j ) &&
69  ring0->pointN( i + 0 ) != ring1->pointN( j + 1 ) && ring0->pointN( i + 0 ) != ring1->pointN( j ) )
70  {
71  const QString msg = QObject::tr( "segment %1 of ring %2 of polygon %3 intersects segment %4 of ring %5 of polygon %6 at %7, %8" )
72  .arg( i ).arg( ringIndex0 ).arg( partIndex0 )
73  .arg( j ).arg( ringIndex1 ).arg( partIndex1 )
74  .arg( sX ).arg( sY );
75  emit errorFound( QgsGeometry::Error( msg, QgsPointXY( sX, sY ) ) );
76  mErrorCount++;
77  }
78  }
79  }
80  }
81  }
82 }
83 
84 void QgsGeometryValidator::validatePolyline( int i, const QgsLineString *line, bool ring )
85 {
86  if ( !line )
87  return;
88 
89  if ( ring )
90  {
91  if ( line->numPoints() < 4 )
92  {
93  const QString msg = QObject::tr( "ring %1 with less than four points" ).arg( i );
94  QgsDebugMsgLevel( msg, 2 );
95  emit errorFound( QgsGeometry::Error( msg ) );
96  mErrorCount++;
97  return;
98  }
99 
100  if ( !line->isClosed() )
101  {
102  const QgsPoint startPoint = line->startPoint();
103  const QgsPoint endPoint = line->endPoint();
104  QString msg;
105  if ( line->is3D() && line->isClosed2D() )
106  {
107  msg = QObject::tr( "ring %1 not closed, Z mismatch: %2 vs %3" ).arg( i ).arg( startPoint.z() ).arg( endPoint.z() );
108  }
109  else
110  {
111  msg = QObject::tr( "ring %1 not closed" ).arg( i );
112  QgsDebugMsgLevel( msg, 2 );
113  }
114  emit errorFound( QgsGeometry::Error( msg, QgsPointXY( startPoint.x(), startPoint.y() ) ) );
115  mErrorCount++;
116  return;
117  }
118  }
119  else if ( line->numPoints() < 2 )
120  {
121  const QString msg = QObject::tr( "line %1 with less than two points" ).arg( i );
122  QgsDebugMsgLevel( msg, 2 );
123  emit errorFound( QgsGeometry::Error( msg ) );
124  mErrorCount++;
125  return;
126  }
127 
128  std::unique_ptr< QgsLineString > noDupes;
129 
130  // test for duplicate nodes, and if we find any flag errors and then remove them so that the subsequent
131  // tests work OK.
132  const QVector< QgsVertexId > duplicateNodes = line->collectDuplicateNodes( 1E-8 );
133  if ( !duplicateNodes.empty() )
134  {
135  noDupes.reset( line->clone() );
136  for ( int j = duplicateNodes.size() - 1; j >= 0; j-- )
137  {
138  const QgsVertexId duplicateVertex = duplicateNodes.at( j );
139  const QgsPointXY duplicationLocation = noDupes->vertexAt( duplicateVertex );
140  noDupes->deleteVertex( duplicateVertex );
141  int n = 1;
142 
143  // count how many other points exist at this location too
144  for ( int k = j - 1; k >= 0; k-- )
145  {
146  const QgsVertexId prevDupe = duplicateNodes.at( k );
147  const QgsPoint prevPoint = noDupes->vertexAt( prevDupe );
148  if ( qgsDoubleNear( duplicationLocation.x(), prevPoint.x(), 1E-8 ) && qgsDoubleNear( duplicationLocation.y(), prevPoint.y(), 1E-8 ) )
149  {
150  noDupes->deleteVertex( prevDupe );
151  n++;
152  }
153  else
154  {
155  break;
156  }
157  }
158 
159  j -= n - 1;
160 
161  const QString msg = QObject::tr( "line %1 contains %n duplicate nodes starting at vertex %2", "number of duplicate nodes", n + 1 ).arg( i + 1 ).arg( duplicateVertex.vertex - n + 1 );
162  QgsDebugMsgLevel( msg, 2 );
163  emit errorFound( QgsGeometry::Error( msg, duplicationLocation ) );
164  mErrorCount++;
165  }
166  line = noDupes.get();
167  }
168 
169  for ( int j = 0; !mStop && j < line->numPoints() - 3; j++ )
170  {
171  const double xAtJ = line->xAt( j );
172  const double yAtJ = line->yAt( j );
173  const QgsVector v( line->xAt( j + 1 ) - xAtJ, line->yAt( j + 1 ) - yAtJ );
174  const double vl = v.length();
175 
176  const int n = ( j == 0 && ring ) ? line->numPoints() - 2 : line->numPoints() - 1;
177 
178  for ( int k = j + 2; !mStop && k < n; k++ )
179  {
180  const double xAtK = line->xAt( k );
181  const double yAtK = line->yAt( k );
182 
183  const QgsVector w( line->xAt( k + 1 ) - xAtK, line->yAt( k + 1 ) - yAtK );
184 
185  double sX;
186  double sY;
187  if ( !intersectLines( xAtJ, yAtJ, v, xAtK, yAtK, w, sX, sY ) )
188  continue;
189 
190  double d = 0.0;
191  try
192  {
193  d = -distLine2Point( xAtJ, yAtJ, v.perpVector(), sX, sY );
194  }
195  catch ( QgsException &e )
196  {
197  Q_UNUSED( e )
198  QgsDebugMsg( "Error validating: " + e.what() );
199  continue;
200  }
201  if ( d < 0 || d > vl )
202  continue;
203 
204  try
205  {
206  d = -distLine2Point( xAtK, yAtK, w.perpVector(), sX, sY );
207  }
208  catch ( QgsException &e )
209  {
210  Q_UNUSED( e )
211  QgsDebugMsg( "Error validating: " + e.what() );
212  continue;
213  }
214 
215  if ( d <= 0 || d >= w.length() )
216  continue;
217 
218  const QString msg = QObject::tr( "segments %1 and %2 of line %3 intersect at %4, %5" ).arg( j ).arg( k ).arg( i ).arg( sX ).arg( sY );
219  QgsDebugMsgLevel( msg, 2 );
220  emit errorFound( QgsGeometry::Error( msg, QgsPointXY( sX, sY ) ) );
221  mErrorCount++;
222  }
223  }
224 }
225 
226 void QgsGeometryValidator::validatePolygon( int partIndex, const QgsPolygon *polygon )
227 {
228  // check if holes are inside polygon
229  for ( int i = 0; !mStop && i < polygon->numInteriorRings(); ++i )
230  {
231  if ( !ringInRing( static_cast< const QgsLineString * >( polygon->interiorRing( i ) ), static_cast< const QgsLineString * >( polygon->exteriorRing() ) ) )
232  {
233  const QString msg = QObject::tr( "ring %1 of polygon %2 not in exterior ring" ).arg( i + 1 ).arg( partIndex );
234  QgsDebugMsg( msg );
235  emit errorFound( QgsGeometry::Error( msg ) );
236  mErrorCount++;
237  }
238  }
239 
240  // check holes for intersections
241  for ( int i = 0; !mStop && i < polygon->numInteriorRings(); i++ )
242  {
243  for ( int j = i + 1; !mStop && j < polygon->numInteriorRings(); j++ )
244  {
245  checkRingIntersections( partIndex, i + 1, qgsgeometry_cast< QgsLineString * >( polygon->interiorRing( i ) ),
246  partIndex, j + 1, qgsgeometry_cast< QgsLineString * >( polygon->interiorRing( j ) ) );
247  }
248  }
249 
250  // check if rings are self-intersecting
251  validatePolyline( 0, qgsgeometry_cast< const QgsLineString * >( polygon->exteriorRing() ), true );
252  for ( int i = 0; !mStop && i < polygon->numInteriorRings(); i++ )
253  {
254  validatePolyline( i + 1, qgsgeometry_cast< const QgsLineString * >( polygon->interiorRing( i ) ), true );
255  }
256 }
257 
259 {
260  mErrorCount = 0;
261  if ( mGeometry.isNull() )
262  {
263  return;
264  }
265 
266  switch ( mMethod )
267  {
268  case Qgis::GeometryValidationEngine::Geos:
269  {
270  // avoid calling geos for trivial point geometries
272  {
273  return;
274  }
275 
276  const QgsGeos geos( mGeometry.constGet() );
277  QString error;
278  QgsGeometry errorLoc;
279  if ( !geos.isValid( &error, true, &errorLoc ) )
280  {
281  if ( errorLoc.isNull() )
282  {
283  emit errorFound( QgsGeometry::Error( error ) );
284  mErrorCount++;
285  }
286  else
287  {
288  const QgsPointXY point = errorLoc.asPoint();
289  emit errorFound( QgsGeometry::Error( error, point ) );
290  mErrorCount++;
291  }
292  }
293 
294  break;
295  }
296 
297  case Qgis::GeometryValidationEngine::QgisInternal:
298  {
299  switch ( QgsWkbTypes::flatType( mGeometry.constGet()->wkbType() ) )
300  {
301  case QgsWkbTypes::Point:
303  break;
304 
306  validatePolyline( 0, qgsgeometry_cast< const QgsLineString * >( mGeometry.constGet() ) );
307  break;
308 
310  {
311  const QgsGeometryCollection *collection = qgsgeometry_cast< const QgsGeometryCollection * >( mGeometry.constGet() );
312  for ( int i = 0; !mStop && i < collection->numGeometries(); i++ )
313  validatePolyline( i, qgsgeometry_cast< const QgsLineString * >( collection->geometryN( i ) ) );
314  break;
315  }
316 
318  validatePolygon( 0, qgsgeometry_cast< const QgsPolygon * >( mGeometry.constGet() ) );
319  break;
320 
322  {
323  const QgsGeometryCollection *collection = qgsgeometry_cast< const QgsGeometryCollection * >( mGeometry.constGet() );
324  for ( int i = 0; !mStop && i < collection->numGeometries(); i++ )
325  validatePolygon( i, qgsgeometry_cast< const QgsPolygon * >( collection->geometryN( i ) ) );
326 
327  for ( int i = 0; !mStop && i < collection->numGeometries(); i++ )
328  {
329  const QgsPolygon *poly = qgsgeometry_cast< const QgsPolygon * >( collection->geometryN( i ) );
330  if ( !poly->exteriorRing() || poly->exteriorRing()->isEmpty() )
331  {
332  emit errorFound( QgsGeometry::Error( QObject::tr( "Polygon %1 has no rings" ).arg( i ) ) );
333  mErrorCount++;
334  continue;
335  }
336 
337  for ( int j = i + 1; !mStop && j < collection->numGeometries(); j++ )
338  {
339  const QgsPolygon *poly2 = qgsgeometry_cast< const QgsPolygon * >( collection->geometryN( j ) );
340  if ( !poly2->exteriorRing() || poly2->exteriorRing()->isEmpty() )
341  continue;
342 
343  if ( ringInRing( qgsgeometry_cast< const QgsLineString * >( poly->exteriorRing() ),
344  qgsgeometry_cast< const QgsLineString * >( poly2->exteriorRing() ) ) )
345  {
346  emit errorFound( QgsGeometry::Error( QObject::tr( "Polygon %1 lies inside polygon %2" ).arg( i ).arg( j ) ) );
347  mErrorCount++;
348  }
349  else if ( ringInRing( static_cast< const QgsLineString * >( poly2->exteriorRing() ),
350  static_cast< const QgsLineString * >( poly->exteriorRing() ) ) )
351  {
352  emit errorFound( QgsGeometry::Error( QObject::tr( "Polygon %1 lies inside polygon %2" ).arg( j ).arg( i ) ) );
353  mErrorCount++;
354  }
355  else
356  {
357  checkRingIntersections( i, 0, qgsgeometry_cast< const QgsLineString * >( poly->exteriorRing() ),
358  j, 0, qgsgeometry_cast< const QgsLineString * >( poly2->exteriorRing() ) );
359  }
360  }
361  }
362  break;
363  }
364 
366  {
367  emit errorFound( QgsGeometry::Error( QObject::tr( "Unknown geometry type %1" ).arg( mGeometry.wkbType() ) ) );
368  mErrorCount++;
369  break;
370  }
371 
372  default:
373  break;
374  }
375 
376  if ( mStop )
377  {
378  emit validationFinished( QObject::tr( "Geometry validation was aborted." ) );
379  }
380  else if ( mErrorCount > 0 )
381  {
382  emit validationFinished( QObject::tr( "Geometry has %1 errors." ).arg( mErrorCount ) );
383  }
384  else
385  {
386  emit validationFinished( QObject::tr( "Geometry is valid." ) );
387  }
388  break;
389  }
390  }
391 }
392 
394 {
395  if ( mErrors )
396  *mErrors << e;
397 }
398 
399 void QgsGeometryValidator::validateGeometry( const QgsGeometry &geometry, QVector<QgsGeometry::Error> &errors, Qgis::GeometryValidationEngine method )
400 {
401  QgsGeometryValidator *gv = new QgsGeometryValidator( geometry, &errors, method );
403  gv->run();
404  gv->wait();
405 }
406 
407 //
408 // distance of point q from line through p in direction v
409 // return >0 => q lies left of the line
410 // <0 => q lies right of the line
411 //
412 double QgsGeometryValidator::distLine2Point( double px, double py, QgsVector v, double qX, double qY )
413 {
414  const double l = v.length();
415  if ( qgsDoubleNear( l, 0 ) )
416  {
417  throw QgsException( QObject::tr( "invalid line" ) );
418  }
419 
420  return ( v.x() * ( qY - py ) - v.y() * ( qX - px ) ) / l;
421 }
422 
423 bool QgsGeometryValidator::intersectLines( double px, double py, QgsVector v, double qx, double qy, QgsVector w, double &sX, double &sY )
424 {
425  const double d = v.y() * w.x() - v.x() * w.y();
426 
427  if ( qgsDoubleNear( d, 0 ) )
428  return false;
429 
430  const double dx = qx - px;
431  const double dy = qy - py;
432  const double k = ( dy * w.x() - dx * w.y() ) / d;
433 
434  sX = px + v.x() * k;
435  sY = py + v.y() * k;
436 
437  return true;
438 }
439 
440 bool QgsGeometryValidator::pointInRing( const QgsLineString *ring, double pX, double pY )
441 {
442  if ( !ring->boundingBox().contains( pX, pY ) )
443  return false;
444 
445  bool inside = false;
446  int j = ring->numPoints() - 1;
447 
448  for ( int i = 0; !mStop && i < ring->numPoints(); i++ )
449  {
450  const double xAti = ring->xAt( i );
451  const double yAti = ring->yAt( i );
452  const double xAtj = ring->xAt( j );
453  const double yAtj = ring->yAt( j );
454 
455  if ( qgsDoubleNear( xAti, pX ) && qgsDoubleNear( yAti, pY ) )
456  return true;
457 
458  if ( ( yAti < pY && yAtj >= pY ) ||
459  ( yAtj < pY && yAti >= pY ) )
460  {
461  if ( xAti + ( pY - yAti ) / ( yAtj - yAti ) * ( xAtj - xAti ) <= pX )
462  inside = !inside;
463  }
464 
465  j = i;
466  }
467 
468  return inside;
469 }
470 
471 bool QgsGeometryValidator::ringInRing( const QgsLineString *inside, const QgsLineString *outside )
472 {
473  if ( !outside->boundingBox().contains( inside->boundingBox() ) )
474  return false;
475 
476  for ( int i = 0; !mStop && i < inside->numPoints(); i++ )
477  {
478  if ( !pointInRing( outside, inside->xAt( i ), inside->yAt( i ) ) )
479  return false;
480  }
481 
482  return true;
483 }
GeometryValidationEngine
Available engines for validating geometries.
Definition: qgis.h:687
bool is3D() const SIP_HOLDGIL
Returns true if the geometry is 3D and contains a z-value.
virtual bool isEmpty() const
Returns true if the geometry is empty.
QgsWkbTypes::Type wkbType() const SIP_HOLDGIL
Returns the WKB type of the geometry.
const QgsCurve * interiorRing(int i) const SIP_HOLDGIL
Retrieves an interior ring from the curve polygon.
const QgsCurve * exteriorRing() const SIP_HOLDGIL
Returns the curve polygon's exterior ring.
int numInteriorRings() const SIP_HOLDGIL
Returns the number of interior rings contained with the curve polygon.
QgsRectangle boundingBox() const override
Returns the minimal bounding box for the geometry.
Definition: qgscurve.cpp:237
Defines a QGIS exception class.
Definition: qgsexception.h:35
QString what() const
Definition: qgsexception.h:48
Geometry collection.
int numGeometries() const SIP_HOLDGIL
Returns the number of geometries within the collection.
const QgsAbstractGeometry * geometryN(int n) const
Returns a const reference to a geometry from within the collection.
void validationFinished(const QString &summary)
Sent when the validation is finished.
void errorFound(const QgsGeometry::Error &error)
Sent when an error has been found during the validation process.
QgsGeometryValidator(const QgsGeometry &geometry, QVector< QgsGeometry::Error > *errors=nullptr, Qgis::GeometryValidationEngine method=Qgis::GeometryValidationEngine::QgisInternal)
Constructor for QgsGeometryValidator.
static void validateGeometry(const QgsGeometry &geometry, QVector< QgsGeometry::Error > &errors, Qgis::GeometryValidationEngine method=Qgis::GeometryValidationEngine::QgisInternal)
Validate geometry and produce a list of geometry errors.
void addError(const QgsGeometry::Error &)
A geometry error.
Definition: qgsgeometry.h:2248
A geometry is the spatial representation of a feature.
Definition: qgsgeometry.h:124
const QgsAbstractGeometry * constGet() const SIP_HOLDGIL
Returns a non-modifiable (const) reference to the underlying abstract geometry primitive.
QgsWkbTypes::Type wkbType() const SIP_HOLDGIL
Returns type of the geometry as a WKB type (point / linestring / polygon etc.)
Q_GADGET bool isNull
Definition: qgsgeometry.h:126
QgsPointXY asPoint() const
Returns the contents of the geometry as a 2-dimensional point.
Does vector analysis using the geos library and handles import, export, exception handling*.
Definition: qgsgeos.h:104
Line string geometry type, with support for z-dimension and m-values.
Definition: qgslinestring.h:44
QgsPoint startPoint() const override SIP_HOLDGIL
Returns the starting point of the curve.
bool isClosed() const override SIP_HOLDGIL
Returns true if the curve is closed.
QgsPoint endPoint() const override SIP_HOLDGIL
Returns the end point of the curve.
int numPoints() const override SIP_HOLDGIL
Returns the number of points in the curve.
QgsPoint pointN(int i) const
Returns the specified point from inside the line string.
bool isClosed2D() const override SIP_HOLDGIL
Returns true if the curve is closed.
double yAt(int index) const override
Returns the y-coordinate of the specified node in the line string.
QVector< QgsVertexId > collectDuplicateNodes(double epsilon=4 *std::numeric_limits< double >::epsilon(), bool useZValues=false) const
Returns a list of any duplicate nodes contained in the geometry, within the specified tolerance.
QgsLineString * clone() const override
Clones the geometry by performing a deep copy.
double xAt(int index) const override
Returns the x-coordinate of the specified node in the line string.
A class to represent a 2D point.
Definition: qgspointxy.h:59
double y
Definition: qgspointxy.h:63
Q_GADGET double x
Definition: qgspointxy.h:62
Point geometry type, with support for z-dimension and m-values.
Definition: qgspoint.h:49
Q_GADGET double x
Definition: qgspoint.h:52
QgsPoint vertexAt(QgsVertexId) const override
Returns the point corresponding to a specified vertex id.
Definition: qgspoint.cpp:525
bool deleteVertex(QgsVertexId position) override
Deletes a vertex within the geometry.
Definition: qgspoint.cpp:459
double z
Definition: qgspoint.h:54
double y
Definition: qgspoint.h:53
Polygon geometry type.
Definition: qgspolygon.h:34
bool contains(const QgsRectangle &rect) const SIP_HOLDGIL
Returns true when rectangle contains other rectangle.
Definition: qgsrectangle.h:363
A class to represent a vector.
Definition: qgsvector.h:30
double y() const SIP_HOLDGIL
Returns the vector's y-component.
Definition: qgsvector.h:156
double x() const SIP_HOLDGIL
Returns the vector's x-component.
Definition: qgsvector.h:147
double length() const SIP_HOLDGIL
Returns the length of the vector.
Definition: qgsvector.h:128
static GeometryType geometryType(Type type) SIP_HOLDGIL
Returns the geometry type for a WKB type, e.g., both MultiPolygon and CurvePolygon would have a Polyg...
Definition: qgswkbtypes.h:938
static Type flatType(Type type) SIP_HOLDGIL
Returns the flat type for a WKB type.
Definition: qgswkbtypes.h:702
Contains geos related utilities and functions.
Definition: qgsgeos.h:42
bool qgsDoubleNear(double a, double b, double epsilon=4 *std::numeric_limits< double >::epsilon())
Compare two doubles (but allow some difference)
Definition: qgis.h:1234
#define QgsDebugMsgLevel(str, level)
Definition: qgslogger.h:39
#define QgsDebugMsg(str)
Definition: qgslogger.h:38
Utility class for identifying a unique vertex within a geometry.
int vertex
Vertex number.