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