QGIS API Documentation 3.36.0-Maidenhead (09951dc0acf)
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 "qgsgeometry.h"
19#include "qgslogger.h"
20#include "qgsgeos.h"
22#include "qgscurvepolygon.h"
23#include "qgscurve.h"
24#include "qgsvertexid.h"
25
26QgsGeometryValidator::QgsGeometryValidator( const QgsGeometry &geometry, QVector<QgsGeometry::Error> *errors, Qgis::GeometryValidationEngine method )
27 : mGeometry( geometry )
28 , mErrors( errors )
29 , mStop( false )
30 , mErrorCount( 0 )
31 , mMethod( method )
32{
33}
34
40
42{
43 mStop = true;
44}
45
46void QgsGeometryValidator::checkRingIntersections( int partIndex0, int ringIndex0, const QgsCurve *ring0, int partIndex1, int ringIndex1, const QgsCurve *ring1 )
47{
48 const QgsLineString *ringLine0 = qgsgeometry_cast< const QgsLineString * >( ring0 );
49 std::unique_ptr< QgsLineString > segmentisedRing0;
50 if ( !ringLine0 )
51 {
52 segmentisedRing0.reset( qgsgeometry_cast< QgsLineString * >( ring0->segmentize() ) );
53 ringLine0 = segmentisedRing0.get();
54 }
55
56 const QgsLineString *ringLine1 = qgsgeometry_cast< const QgsLineString * >( ring1 );
57 std::unique_ptr< QgsLineString > segmentisedRing1;
58 if ( !ringLine1 )
59 {
60 segmentisedRing1.reset( qgsgeometry_cast< QgsLineString * >( ring1->segmentize() ) );
61 ringLine1 = segmentisedRing1.get();
62 }
63
64 Q_ASSERT( ringLine0 );
65 Q_ASSERT( ringLine1 );
66
67 for ( int i = 0; !mStop && i < ringLine0->numPoints() - 1; i++ )
68 {
69 const double ring0XAti = ringLine0->xAt( i );
70 const double ring0YAti = ringLine0->yAt( i );
71 const QgsVector v( ringLine0->xAt( i + 1 ) - ring0XAti, ringLine0->yAt( i + 1 ) - ring0YAti );
72
73 for ( int j = 0; !mStop && j < ringLine1->numPoints() - 1; j++ )
74 {
75 const double ring1XAtj = ringLine1->xAt( j );
76 const double ring1YAtj = ringLine1->yAt( j );
77 const QgsVector w( ringLine1->xAt( j + 1 ) - ring1XAtj, ringLine1->yAt( j + 1 ) - ring1YAtj );
78
79 double sX;
80 double sY;
81 if ( intersectLines( ring0XAti, ring0YAti, v, ring1XAtj, ring1YAtj, w, sX, sY ) )
82 {
83 double d = -distLine2Point( ring0XAti, ring0YAti, v.perpVector(), sX, sY );
84
85 if ( d >= 0 && d <= v.length() )
86 {
87 d = -distLine2Point( ring1XAtj, ring1YAtj, w.perpVector(), sX, sY );
88 if ( d > 0 && d < w.length() &&
89 ringLine0->pointN( i + 1 ) != ringLine1->pointN( j + 1 ) && ringLine0->pointN( i + 1 ) != ringLine1->pointN( j ) &&
90 ringLine0->pointN( i + 0 ) != ringLine1->pointN( j + 1 ) && ringLine0->pointN( i + 0 ) != ringLine1->pointN( j ) )
91 {
92 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" )
93 .arg( i ).arg( ringIndex0 ).arg( partIndex0 )
94 .arg( j ).arg( ringIndex1 ).arg( partIndex1 )
95 .arg( sX ).arg( sY );
96 emit errorFound( QgsGeometry::Error( msg, QgsPointXY( sX, sY ) ) );
97 mErrorCount++;
98 }
99 }
100 }
101 }
102 }
103}
104
105void QgsGeometryValidator::validatePolyline( int i, const QgsLineString *line, bool ring )
106{
107 if ( !line )
108 return;
109
110 if ( ring )
111 {
112 if ( line->numPoints() < 4 )
113 {
114 const QString msg = QObject::tr( "ring %1 with less than four points" ).arg( i );
115 QgsDebugMsgLevel( msg, 2 );
116 emit errorFound( QgsGeometry::Error( msg ) );
117 mErrorCount++;
118 return;
119 }
120
121 if ( !line->isClosed() )
122 {
123 const QgsPoint startPoint = line->startPoint();
124 const QgsPoint endPoint = line->endPoint();
125 QString msg;
126 if ( line->is3D() && line->isClosed2D() )
127 {
128 msg = QObject::tr( "ring %1 not closed, Z mismatch: %2 vs %3" ).arg( i ).arg( startPoint.z() ).arg( endPoint.z() );
129 }
130 else
131 {
132 msg = QObject::tr( "ring %1 not closed" ).arg( i );
133 QgsDebugMsgLevel( msg, 2 );
134 }
135 emit errorFound( QgsGeometry::Error( msg, QgsPointXY( startPoint.x(), startPoint.y() ) ) );
136 mErrorCount++;
137 return;
138 }
139 }
140 else if ( line->numPoints() < 2 )
141 {
142 const QString msg = QObject::tr( "line %1 with less than two points" ).arg( i );
143 QgsDebugMsgLevel( msg, 2 );
144 emit errorFound( QgsGeometry::Error( msg ) );
145 mErrorCount++;
146 return;
147 }
148
149 std::unique_ptr< QgsLineString > noDupes;
150
151 // test for duplicate nodes, and if we find any flag errors and then remove them so that the subsequent
152 // tests work OK.
153 const QVector< QgsVertexId > duplicateNodes = line->collectDuplicateNodes( 1E-8 );
154 if ( !duplicateNodes.empty() )
155 {
156 noDupes.reset( line->clone() );
157 for ( int j = duplicateNodes.size() - 1; j >= 0; j-- )
158 {
159 const QgsVertexId duplicateVertex = duplicateNodes.at( j );
160 const QgsPointXY duplicationLocation = noDupes->vertexAt( duplicateVertex );
161 noDupes->deleteVertex( duplicateVertex );
162 int n = 1;
163
164 // count how many other points exist at this location too
165 for ( int k = j - 1; k >= 0; k-- )
166 {
167 const QgsVertexId prevDupe = duplicateNodes.at( k );
168 const QgsPoint prevPoint = noDupes->vertexAt( prevDupe );
169 if ( qgsDoubleNear( duplicationLocation.x(), prevPoint.x(), 1E-8 ) && qgsDoubleNear( duplicationLocation.y(), prevPoint.y(), 1E-8 ) )
170 {
171 noDupes->deleteVertex( prevDupe );
172 n++;
173 }
174 else
175 {
176 break;
177 }
178 }
179
180 j -= n - 1;
181
182 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 );
183 QgsDebugMsgLevel( msg, 2 );
184 emit errorFound( QgsGeometry::Error( msg, duplicationLocation ) );
185 mErrorCount++;
186 }
187 line = noDupes.get();
188 }
189
190 // segment Intersection
191 for ( int j = 0; !mStop && j < line->numPoints() - 3; j++ )
192 {
193 const int n = ( j == 0 && ring ) ? line->numPoints() - 2 : line->numPoints() - 1;
194 for ( int k = j + 2; !mStop && k < n; k++ )
195 {
196 double intersectionPointX = std::numeric_limits<double>::quiet_NaN();
197 double intersectionPointY = std::numeric_limits<double>::quiet_NaN();
198 bool isIntersection = false;
199 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 ) )
200 {
201 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 );
202 QgsDebugMsgLevel( msg, 2 );
203 emit errorFound( QgsGeometry::Error( msg, QgsPointXY( intersectionPointX, intersectionPointY ) ) );
204 mErrorCount++;
205 }
206 }
207 }
208}
209
210void QgsGeometryValidator::validatePolygon( int partIndex, const QgsCurvePolygon *polygon )
211{
212 // check if holes are inside polygon
213 for ( int i = 0; !mStop && i < polygon->numInteriorRings(); ++i )
214 {
215 if ( !ringInRing( polygon->interiorRing( i ), polygon->exteriorRing() ) )
216 {
217 const QString msg = QObject::tr( "ring %1 of polygon %2 not in exterior ring" ).arg( i + 1 ).arg( partIndex );
218 QgsDebugMsgLevel( msg, 2 );
219 emit errorFound( QgsGeometry::Error( msg ) );
220 mErrorCount++;
221 }
222 }
223
224 // check holes for intersections
225 for ( int i = 0; !mStop && i < polygon->numInteriorRings(); i++ )
226 {
227 for ( int j = i + 1; !mStop && j < polygon->numInteriorRings(); j++ )
228 {
229 checkRingIntersections( partIndex, i + 1, polygon->interiorRing( i ),
230 partIndex, j + 1, polygon->interiorRing( j ) );
231 }
232 }
233
234 // check if rings are self-intersecting
235 validatePolyline( 0, qgsgeometry_cast< const QgsLineString * >( polygon->exteriorRing() ), true );
236 for ( int i = 0; !mStop && i < polygon->numInteriorRings(); i++ )
237 {
238 validatePolyline( i + 1, qgsgeometry_cast< const QgsLineString * >( polygon->interiorRing( i ) ), true );
239 }
240}
241
243{
244 mErrorCount = 0;
245 if ( mGeometry.isNull() )
246 {
247 return;
248 }
249
250 switch ( mMethod )
251 {
253 {
254 // avoid calling geos for trivial point geometries
256 {
257 return;
258 }
259
260 const QgsGeos geos( mGeometry.constGet() );
261 QString error;
262 QgsGeometry errorLoc;
263 if ( !geos.isValid( &error, true, &errorLoc ) )
264 {
265 if ( errorLoc.isNull() )
266 {
267 emit errorFound( QgsGeometry::Error( error ) );
268 mErrorCount++;
269 }
270 else
271 {
272 const QgsPointXY point = errorLoc.asPoint();
273 emit errorFound( QgsGeometry::Error( error, point ) );
274 mErrorCount++;
275 }
276 }
277
278 break;
279 }
280
282 {
283 switch ( QgsWkbTypes::flatType( mGeometry.constGet()->wkbType() ) )
284 {
287 break;
288
290 validatePolyline( 0, qgsgeometry_cast< const QgsLineString * >( mGeometry.constGet() ) );
291 break;
292
294 {
295 const QgsGeometryCollection *collection = qgsgeometry_cast< const QgsGeometryCollection * >( mGeometry.constGet() );
296 for ( int i = 0; !mStop && i < collection->numGeometries(); i++ )
297 validatePolyline( i, qgsgeometry_cast< const QgsLineString * >( collection->geometryN( i ) ) );
298 break;
299 }
300
303 validatePolygon( 0, qgsgeometry_cast< const QgsCurvePolygon * >( mGeometry.constGet() ) );
304 break;
305
308 {
309 const QgsGeometryCollection *collection = qgsgeometry_cast< const QgsGeometryCollection * >( mGeometry.constGet() );
310 for ( int i = 0; !mStop && i < collection->numGeometries(); i++ )
311 validatePolygon( i, qgsgeometry_cast< const QgsCurvePolygon * >( collection->geometryN( i ) ) );
312
313 for ( int i = 0; !mStop && i < collection->numGeometries(); i++ )
314 {
315 const QgsCurvePolygon *poly = qgsgeometry_cast< const QgsCurvePolygon * >( collection->geometryN( i ) );
316 if ( !poly->exteriorRing() || poly->exteriorRing()->isEmpty() )
317 {
318 emit errorFound( QgsGeometry::Error( QObject::tr( "Polygon %1 has no rings" ).arg( i ) ) );
319 mErrorCount++;
320 continue;
321 }
322
323 for ( int j = i + 1; !mStop && j < collection->numGeometries(); j++ )
324 {
325 const QgsCurvePolygon *poly2 = qgsgeometry_cast< const QgsCurvePolygon * >( collection->geometryN( j ) );
326 if ( !poly2->exteriorRing() || poly2->exteriorRing()->isEmpty() )
327 continue;
328
329 if ( ringInRing( poly->exteriorRing(),
330 poly2->exteriorRing() ) )
331 {
332 emit errorFound( QgsGeometry::Error( QObject::tr( "Polygon %1 lies inside polygon %2" ).arg( i ).arg( j ) ) );
333 mErrorCount++;
334 }
335 else if ( ringInRing( poly2->exteriorRing(),
336 poly->exteriorRing() ) )
337 {
338 emit errorFound( QgsGeometry::Error( QObject::tr( "Polygon %1 lies inside polygon %2" ).arg( j ).arg( i ) ) );
339 mErrorCount++;
340 }
341 else
342 {
343 checkRingIntersections( i, 0, poly->exteriorRing(),
344 j, 0, poly2->exteriorRing() );
345 }
346 }
347 }
348 break;
349 }
350
352 {
353 emit errorFound( QgsGeometry::Error( QObject::tr( "Unknown geometry type %1" ).arg( qgsEnumValueToKey( mGeometry.wkbType() ) ) ) );
354 mErrorCount++;
355 break;
356 }
357
358 default:
359 break;
360 }
361
362 if ( mStop )
363 {
364 emit validationFinished( QObject::tr( "Geometry validation was aborted." ) );
365 }
366 else if ( mErrorCount > 0 )
367 {
368 emit validationFinished( QObject::tr( "Geometry has %n error(s).", nullptr, mErrorCount ) );
369 }
370 else
371 {
372 emit validationFinished( QObject::tr( "Geometry is valid." ) );
373 }
374 break;
375 }
376 }
377}
378
380{
381 if ( mErrors )
382 *mErrors << e;
383}
384
385void QgsGeometryValidator::validateGeometry( const QgsGeometry &geometry, QVector<QgsGeometry::Error> &errors, Qgis::GeometryValidationEngine method )
386{
387 QgsGeometryValidator *gv = new QgsGeometryValidator( geometry, &errors, method );
389 gv->run();
390 gv->wait();
391}
392
393//
394// distance of point q from line through p in direction v
395// return >0 => q lies left of the line
396// <0 => q lies right of the line
397//
398double QgsGeometryValidator::distLine2Point( double px, double py, QgsVector v, double qX, double qY )
399{
400 const double l = v.length();
401 if ( qgsDoubleNear( l, 0 ) )
402 {
403 throw QgsException( QObject::tr( "invalid line" ) );
404 }
405
406 return ( v.x() * ( qY - py ) - v.y() * ( qX - px ) ) / l;
407}
408
409bool QgsGeometryValidator::intersectLines( double px, double py, QgsVector v, double qx, double qy, QgsVector w, double &sX, double &sY )
410{
411 const double d = v.y() * w.x() - v.x() * w.y();
412
413 if ( qgsDoubleNear( d, 0 ) )
414 return false;
415
416 const double dx = qx - px;
417 const double dy = qy - py;
418 const double k = ( dy * w.x() - dx * w.y() ) / d;
419
420 sX = px + v.x() * k;
421 sY = py + v.y() * k;
422
423 return true;
424}
425
426bool QgsGeometryValidator::pointInRing( const QgsCurve *ring, double pX, double pY )
427{
428 if ( !ring->boundingBox().contains( pX, pY ) )
429 return false;
430
431 bool inside = false;
432 int j = ring->numPoints() - 1;
433
434 for ( int i = 0; !mStop && i < ring->numPoints(); i++ )
435 {
436 const double xAti = ring->xAt( i );
437 const double yAti = ring->yAt( i );
438 const double xAtj = ring->xAt( j );
439 const double yAtj = ring->yAt( j );
440
441 if ( qgsDoubleNear( xAti, pX ) && qgsDoubleNear( yAti, pY ) )
442 return true;
443
444 if ( ( yAti < pY && yAtj >= pY ) ||
445 ( yAtj < pY && yAti >= pY ) )
446 {
447 if ( xAti + ( pY - yAti ) / ( yAtj - yAti ) * ( xAtj - xAti ) <= pX )
448 inside = !inside;
449 }
450
451 j = i;
452 }
453
454 return inside;
455}
456
457bool QgsGeometryValidator::ringInRing( const QgsCurve *inside, const QgsCurve *outside )
458{
459 if ( !outside->boundingBox().contains( inside->boundingBox() ) )
460 return false;
461
462 for ( int i = 0; !mStop && i < inside->numPoints(); i++ )
463 {
464 if ( !pointInRing( outside, inside->xAt( i ), inside->yAt( i ) ) )
465 return false;
466 }
467
468 return true;
469}
GeometryValidationEngine
Available engines for validating geometries.
Definition qgis.h:1638
@ QgisInternal
Use internal QgsGeometryValidator method.
@ Geos
Use GEOS validation methods.
@ 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:98
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:522
bool deleteVertex(QgsVertexId position) override
Deletes a vertex within the geometry.
Definition qgspoint.cpp:456
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:36
QString qgsEnumValueToKey(const T &value, bool *returnOk=nullptr)
Returns the value for the given key of an enum.
Definition qgis.h:5335
bool qgsDoubleNear(double a, double b, double epsilon=4 *std::numeric_limits< double >::epsilon())
Compare two doubles (but allow some difference)
Definition qgis.h:5144
#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