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