Branch data Line data Source code
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 : 0 : QgsGeometryValidator::QgsGeometryValidator( const QgsGeometry &geometry, QVector<QgsGeometry::Error> *errors, QgsGeometry::ValidationMethod method )
25 : 0 : : mGeometry( geometry )
26 : 0 : , mErrors( errors )
27 : 0 : , mStop( false )
28 : 0 : , mErrorCount( 0 )
29 : 0 : , mMethod( method )
30 : 0 : {
31 : 0 : }
32 : :
33 : 0 : QgsGeometryValidator::~QgsGeometryValidator()
34 : 0 : {
35 : 0 : stop();
36 : 0 : wait();
37 : 0 : }
38 : :
39 : 0 : void QgsGeometryValidator::stop()
40 : : {
41 : 0 : mStop = true;
42 : 0 : }
43 : :
44 : 0 : void QgsGeometryValidator::checkRingIntersections( int partIndex0, int ringIndex0, const QgsLineString *ring0, int partIndex1, int ringIndex1, const QgsLineString *ring1 )
45 : : {
46 : 0 : for ( int i = 0; !mStop && i < ring0->numPoints() - 1; i++ )
47 : : {
48 : 0 : const double ring0XAti = ring0->xAt( i );
49 : 0 : const double ring0YAti = ring0->yAt( i );
50 : 0 : QgsVector v( ring0->xAt( i + 1 ) - ring0XAti, ring0->yAt( i + 1 ) - ring0YAti );
51 : :
52 : 0 : for ( int j = 0; !mStop && j < ring1->numPoints() - 1; j++ )
53 : : {
54 : 0 : const double ring1XAtj = ring1->xAt( j );
55 : 0 : const double ring1YAtj = ring1->yAt( j );
56 : 0 : QgsVector w( ring1->xAt( j + 1 ) - ring1XAtj, ring1->yAt( j + 1 ) - ring1YAtj );
57 : :
58 : : double sX;
59 : : double sY;
60 : 0 : if ( intersectLines( ring0XAti, ring0YAti, v, ring1XAtj, ring1YAtj, w, sX, sY ) )
61 : : {
62 : 0 : double d = -distLine2Point( ring0XAti, ring0YAti, v.perpVector(), sX, sY );
63 : :
64 : 0 : if ( d >= 0 && d <= v.length() )
65 : : {
66 : 0 : d = -distLine2Point( ring1XAtj, ring1YAtj, w.perpVector(), sX, sY );
67 : 0 : if ( d > 0 && d < w.length() &&
68 : 0 : ring0->pointN( i + 1 ) != ring1->pointN( j + 1 ) && ring0->pointN( i + 1 ) != ring1->pointN( j ) &&
69 : 0 : ring0->pointN( i + 0 ) != ring1->pointN( j + 1 ) && ring0->pointN( i + 0 ) != ring1->pointN( j ) )
70 : : {
71 : 0 : 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 : 0 : .arg( i ).arg( ringIndex0 ).arg( partIndex0 )
73 : 0 : .arg( j ).arg( ringIndex1 ).arg( partIndex1 )
74 : 0 : .arg( sX ).arg( sY );
75 : 0 : emit errorFound( QgsGeometry::Error( msg, QgsPointXY( sX, sY ) ) );
76 : 0 : mErrorCount++;
77 : 0 : }
78 : 0 : }
79 : 0 : }
80 : 0 : }
81 : 0 : }
82 : 0 : }
83 : :
84 : 0 : void QgsGeometryValidator::validatePolyline( int i, const QgsLineString *line, bool ring )
85 : : {
86 : 0 : if ( !line )
87 : 0 : return;
88 : :
89 : 0 : if ( ring )
90 : : {
91 : 0 : if ( line->numPoints() < 4 )
92 : : {
93 : 0 : QString msg = QObject::tr( "ring %1 with less than four points" ).arg( i );
94 : 0 : QgsDebugMsgLevel( msg, 2 );
95 : 0 : emit errorFound( QgsGeometry::Error( msg ) );
96 : 0 : mErrorCount++;
97 : : return;
98 : 0 : }
99 : :
100 : 0 : if ( !line->isClosed() )
101 : : {
102 : 0 : QString msg = QObject::tr( "ring %1 not closed" ).arg( i );
103 : 0 : QgsDebugMsgLevel( msg, 2 );
104 : 0 : emit errorFound( QgsGeometry::Error( msg ) );
105 : 0 : mErrorCount++;
106 : : return;
107 : 0 : }
108 : 0 : }
109 : 0 : else if ( line->numPoints() < 2 )
110 : : {
111 : 0 : QString msg = QObject::tr( "line %1 with less than two points" ).arg( i );
112 : 0 : QgsDebugMsgLevel( msg, 2 );
113 : 0 : emit errorFound( QgsGeometry::Error( msg ) );
114 : 0 : mErrorCount++;
115 : : return;
116 : 0 : }
117 : :
118 : 0 : 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 : 0 : const QVector< QgsVertexId > duplicateNodes = line->collectDuplicateNodes( 1E-8 );
123 : 0 : if ( !duplicateNodes.empty() )
124 : : {
125 : 0 : noDupes.reset( line->clone() );
126 : 0 : for ( int j = duplicateNodes.size() - 1; j >= 0; j-- )
127 : : {
128 : 0 : const QgsVertexId duplicateVertex = duplicateNodes.at( j );
129 : 0 : const QgsPointXY duplicationLocation = noDupes->vertexAt( duplicateVertex );
130 : 0 : noDupes->deleteVertex( duplicateVertex );
131 : 0 : int n = 1;
132 : :
133 : : // count how many other points exist at this location too
134 : 0 : for ( int k = j - 1; k >= 0; k-- )
135 : : {
136 : 0 : const QgsVertexId prevDupe = duplicateNodes.at( k );
137 : 0 : const QgsPoint prevPoint = noDupes->vertexAt( prevDupe );
138 : 0 : if ( qgsDoubleNear( duplicationLocation.x(), prevPoint.x(), 1E-8 ) && qgsDoubleNear( duplicationLocation.y(), prevPoint.y(), 1E-8 ) )
139 : : {
140 : 0 : noDupes->deleteVertex( prevDupe );
141 : 0 : n++;
142 : 0 : }
143 : : else
144 : : {
145 : 0 : break;
146 : : }
147 : 0 : }
148 : :
149 : 0 : j -= n - 1;
150 : :
151 : 0 : 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 : 0 : QgsDebugMsgLevel( msg, 2 );
153 : 0 : emit errorFound( QgsGeometry::Error( msg, duplicationLocation ) );
154 : 0 : mErrorCount++;
155 : 0 : }
156 : 0 : line = noDupes.get();
157 : 0 : }
158 : :
159 : 0 : for ( int j = 0; !mStop && j < line->numPoints() - 3; j++ )
160 : : {
161 : 0 : const double xAtJ = line->xAt( j );
162 : 0 : const double yAtJ = line->yAt( j );
163 : 0 : QgsVector v( line->xAt( j + 1 ) - xAtJ, line->yAt( j + 1 ) - yAtJ );
164 : 0 : double vl = v.length();
165 : :
166 : 0 : int n = ( j == 0 && ring ) ? line->numPoints() - 2 : line->numPoints() - 1;
167 : :
168 : 0 : for ( int k = j + 2; !mStop && k < n; k++ )
169 : : {
170 : 0 : const double xAtK = line->xAt( k );
171 : 0 : const double yAtK = line->yAt( k );
172 : :
173 : 0 : QgsVector w( line->xAt( k + 1 ) - xAtK, line->yAt( k + 1 ) - yAtK );
174 : :
175 : : double sX;
176 : : double sY;
177 : 0 : if ( !intersectLines( xAtJ, yAtJ, v, xAtK, yAtK, w, sX, sY ) )
178 : 0 : continue;
179 : :
180 : 0 : double d = 0.0;
181 : : try
182 : : {
183 : 0 : d = -distLine2Point( xAtJ, yAtJ, v.perpVector(), sX, sY );
184 : 0 : }
185 : : catch ( QgsException &e )
186 : : {
187 : 0 : Q_UNUSED( e )
188 : 0 : QgsDebugMsg( "Error validating: " + e.what() );
189 : : continue;
190 : 0 : }
191 : 0 : if ( d < 0 || d > vl )
192 : 0 : continue;
193 : :
194 : : try
195 : : {
196 : 0 : d = -distLine2Point( xAtK, yAtK, w.perpVector(), sX, sY );
197 : 0 : }
198 : : catch ( QgsException &e )
199 : : {
200 : 0 : Q_UNUSED( e )
201 : 0 : QgsDebugMsg( "Error validating: " + e.what() );
202 : : continue;
203 : 0 : }
204 : :
205 : 0 : if ( d <= 0 || d >= w.length() )
206 : 0 : continue;
207 : :
208 : 0 : 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 : 0 : QgsDebugMsgLevel( msg, 2 );
210 : 0 : emit errorFound( QgsGeometry::Error( msg, QgsPointXY( sX, sY ) ) );
211 : 0 : mErrorCount++;
212 : 0 : }
213 : 0 : }
214 : 0 : }
215 : :
216 : 0 : void QgsGeometryValidator::validatePolygon( int partIndex, const QgsPolygon *polygon )
217 : : {
218 : : // check if holes are inside polygon
219 : 0 : for ( int i = 0; !mStop && i < polygon->numInteriorRings(); ++i )
220 : : {
221 : 0 : if ( !ringInRing( static_cast< const QgsLineString * >( polygon->interiorRing( i ) ), static_cast< const QgsLineString * >( polygon->exteriorRing() ) ) )
222 : : {
223 : 0 : QString msg = QObject::tr( "ring %1 of polygon %2 not in exterior ring" ).arg( i + 1 ).arg( partIndex );
224 : 0 : QgsDebugMsg( msg );
225 : 0 : emit errorFound( QgsGeometry::Error( msg ) );
226 : 0 : mErrorCount++;
227 : 0 : }
228 : 0 : }
229 : :
230 : : // check holes for intersections
231 : 0 : for ( int i = 0; !mStop && i < polygon->numInteriorRings(); i++ )
232 : : {
233 : 0 : for ( int j = i + 1; !mStop && j < polygon->numInteriorRings(); j++ )
234 : : {
235 : 0 : checkRingIntersections( partIndex, i + 1, qgsgeometry_cast< QgsLineString * >( polygon->interiorRing( i ) ),
236 : 0 : partIndex, j + 1, qgsgeometry_cast< QgsLineString * >( polygon->interiorRing( j ) ) );
237 : 0 : }
238 : 0 : }
239 : :
240 : : // check if rings are self-intersecting
241 : 0 : validatePolyline( 0, qgsgeometry_cast< const QgsLineString * >( polygon->exteriorRing() ), true );
242 : 0 : for ( int i = 0; !mStop && i < polygon->numInteriorRings(); i++ )
243 : : {
244 : 0 : validatePolyline( i + 1, qgsgeometry_cast< const QgsLineString * >( polygon->interiorRing( i ) ), true );
245 : 0 : }
246 : 0 : }
247 : :
248 : 0 : void QgsGeometryValidator::run()
249 : : {
250 : 0 : mErrorCount = 0;
251 : 0 : if ( mGeometry.isNull() )
252 : : {
253 : 0 : return;
254 : : }
255 : :
256 : 0 : switch ( mMethod )
257 : : {
258 : : case QgsGeometry::ValidatorGeos:
259 : : {
260 : : // avoid calling geos for trivial point geometries
261 : 0 : if ( QgsWkbTypes::geometryType( mGeometry.wkbType() ) == QgsWkbTypes::PointGeometry )
262 : : {
263 : 0 : return;
264 : : }
265 : :
266 : 0 : QgsGeos geos( mGeometry.constGet() );
267 : 0 : QString error;
268 : 0 : QgsGeometry errorLoc;
269 : 0 : if ( !geos.isValid( &error, true, &errorLoc ) )
270 : : {
271 : 0 : if ( errorLoc.isNull() )
272 : : {
273 : 0 : emit errorFound( QgsGeometry::Error( error ) );
274 : 0 : mErrorCount++;
275 : 0 : }
276 : : else
277 : : {
278 : 0 : const QgsPointXY point = errorLoc.asPoint();
279 : 0 : emit errorFound( QgsGeometry::Error( error, point ) );
280 : 0 : mErrorCount++;
281 : : }
282 : 0 : }
283 : :
284 : : break;
285 : 0 : }
286 : :
287 : : case QgsGeometry::ValidatorQgisInternal:
288 : : {
289 : 0 : switch ( QgsWkbTypes::flatType( mGeometry.constGet()->wkbType() ) )
290 : : {
291 : : case QgsWkbTypes::Point:
292 : : case QgsWkbTypes::MultiPoint:
293 : 0 : break;
294 : :
295 : : case QgsWkbTypes::LineString:
296 : 0 : validatePolyline( 0, qgsgeometry_cast< const QgsLineString * >( mGeometry.constGet() ) );
297 : 0 : break;
298 : :
299 : : case QgsWkbTypes::MultiLineString:
300 : : {
301 : 0 : const QgsGeometryCollection *collection = qgsgeometry_cast< const QgsGeometryCollection * >( mGeometry.constGet() );
302 : 0 : for ( int i = 0; !mStop && i < collection->numGeometries(); i++ )
303 : 0 : validatePolyline( i, qgsgeometry_cast< const QgsLineString * >( collection->geometryN( i ) ) );
304 : 0 : break;
305 : : }
306 : :
307 : : case QgsWkbTypes::Polygon:
308 : 0 : validatePolygon( 0, qgsgeometry_cast< const QgsPolygon * >( mGeometry.constGet() ) );
309 : 0 : break;
310 : :
311 : : case QgsWkbTypes::MultiPolygon:
312 : : {
313 : 0 : const QgsGeometryCollection *collection = qgsgeometry_cast< const QgsGeometryCollection * >( mGeometry.constGet() );
314 : 0 : for ( int i = 0; !mStop && i < collection->numGeometries(); i++ )
315 : 0 : validatePolygon( i, qgsgeometry_cast< const QgsPolygon * >( collection->geometryN( i ) ) );
316 : :
317 : 0 : for ( int i = 0; !mStop && i < collection->numGeometries(); i++ )
318 : : {
319 : 0 : const QgsPolygon *poly = qgsgeometry_cast< const QgsPolygon * >( collection->geometryN( i ) );
320 : 0 : if ( !poly->exteriorRing() || poly->exteriorRing()->isEmpty() )
321 : : {
322 : 0 : emit errorFound( QgsGeometry::Error( QObject::tr( "Polygon %1 has no rings" ).arg( i ) ) );
323 : 0 : mErrorCount++;
324 : 0 : continue;
325 : : }
326 : :
327 : 0 : for ( int j = i + 1; !mStop && j < collection->numGeometries(); j++ )
328 : : {
329 : 0 : const QgsPolygon *poly2 = qgsgeometry_cast< const QgsPolygon * >( collection->geometryN( j ) );
330 : 0 : if ( !poly2->exteriorRing() || poly2->exteriorRing()->isEmpty() )
331 : 0 : continue;
332 : :
333 : 0 : if ( ringInRing( qgsgeometry_cast< const QgsLineString * >( poly->exteriorRing() ),
334 : 0 : qgsgeometry_cast< const QgsLineString * >( poly2->exteriorRing() ) ) )
335 : : {
336 : 0 : emit errorFound( QgsGeometry::Error( QObject::tr( "Polygon %1 lies inside polygon %2" ).arg( i ).arg( j ) ) );
337 : 0 : mErrorCount++;
338 : 0 : }
339 : 0 : else if ( ringInRing( static_cast< const QgsLineString * >( poly2->exteriorRing() ),
340 : 0 : static_cast< const QgsLineString * >( poly->exteriorRing() ) ) )
341 : : {
342 : 0 : emit errorFound( QgsGeometry::Error( QObject::tr( "Polygon %1 lies inside polygon %2" ).arg( j ).arg( i ) ) );
343 : 0 : mErrorCount++;
344 : 0 : }
345 : : else
346 : : {
347 : 0 : checkRingIntersections( i, 0, qgsgeometry_cast< const QgsLineString * >( poly->exteriorRing() ),
348 : 0 : j, 0, qgsgeometry_cast< const QgsLineString * >( poly2->exteriorRing() ) );
349 : : }
350 : 0 : }
351 : 0 : }
352 : 0 : break;
353 : : }
354 : :
355 : : case QgsWkbTypes::Unknown:
356 : : {
357 : 0 : emit errorFound( QgsGeometry::Error( QObject::tr( "Unknown geometry type %1" ).arg( mGeometry.wkbType() ) ) );
358 : 0 : mErrorCount++;
359 : 0 : break;
360 : : }
361 : :
362 : : default:
363 : 0 : break;
364 : : }
365 : :
366 : 0 : if ( mStop )
367 : : {
368 : 0 : emit validationFinished( QObject::tr( "Geometry validation was aborted." ) );
369 : 0 : }
370 : 0 : else if ( mErrorCount > 0 )
371 : : {
372 : 0 : emit validationFinished( QObject::tr( "Geometry has %1 errors." ).arg( mErrorCount ) );
373 : 0 : }
374 : : else
375 : : {
376 : 0 : emit validationFinished( QObject::tr( "Geometry is valid." ) );
377 : : }
378 : 0 : break;
379 : : }
380 : : }
381 : 0 : }
382 : :
383 : 0 : void QgsGeometryValidator::addError( const QgsGeometry::Error &e )
384 : : {
385 : 0 : if ( mErrors )
386 : 0 : *mErrors << e;
387 : 0 : }
388 : :
389 : 0 : void QgsGeometryValidator::validateGeometry( const QgsGeometry &geometry, QVector<QgsGeometry::Error> &errors, QgsGeometry::ValidationMethod method )
390 : : {
391 : 0 : QgsGeometryValidator *gv = new QgsGeometryValidator( geometry, &errors, method );
392 : 0 : connect( gv, &QgsGeometryValidator::errorFound, gv, &QgsGeometryValidator::addError );
393 : 0 : gv->run();
394 : 0 : gv->wait();
395 : 0 : }
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 : 0 : double QgsGeometryValidator::distLine2Point( double px, double py, QgsVector v, double qX, double qY )
403 : : {
404 : 0 : const double l = v.length();
405 : 0 : if ( qgsDoubleNear( l, 0 ) )
406 : : {
407 : 0 : throw QgsException( QObject::tr( "invalid line" ) );
408 : : }
409 : :
410 : 0 : return ( v.x() * ( qY - py ) - v.y() * ( qX - px ) ) / l;
411 : 0 : }
412 : :
413 : 0 : bool QgsGeometryValidator::intersectLines( double px, double py, QgsVector v, double qx, double qy, QgsVector w, double &sX, double &sY )
414 : : {
415 : 0 : double d = v.y() * w.x() - v.x() * w.y();
416 : :
417 : 0 : if ( qgsDoubleNear( d, 0 ) )
418 : 0 : return false;
419 : :
420 : 0 : double dx = qx - px;
421 : 0 : double dy = qy - py;
422 : 0 : double k = ( dy * w.x() - dx * w.y() ) / d;
423 : :
424 : 0 : sX = px + v.x() * k;
425 : 0 : sY = py + v.y() * k;
426 : :
427 : 0 : return true;
428 : 0 : }
429 : :
430 : 0 : bool QgsGeometryValidator::pointInRing( const QgsLineString *ring, double pX, double pY )
431 : : {
432 : 0 : if ( !ring->boundingBox().contains( pX, pY ) )
433 : 0 : return false;
434 : :
435 : 0 : bool inside = false;
436 : 0 : int j = ring->numPoints() - 1;
437 : :
438 : 0 : for ( int i = 0; !mStop && i < ring->numPoints(); i++ )
439 : : {
440 : 0 : const double xAti = ring->xAt( i );
441 : 0 : const double yAti = ring->yAt( i );
442 : 0 : const double xAtj = ring->xAt( j );
443 : 0 : const double yAtj = ring->yAt( j );
444 : :
445 : 0 : if ( qgsDoubleNear( xAti, pX ) && qgsDoubleNear( yAti, pY ) )
446 : 0 : return true;
447 : :
448 : 0 : if ( ( yAti < pY && yAtj >= pY ) ||
449 : 0 : ( yAtj < pY && yAti >= pY ) )
450 : : {
451 : 0 : if ( xAti + ( pY - yAti ) / ( yAtj - yAti ) * ( xAtj - xAti ) <= pX )
452 : 0 : inside = !inside;
453 : 0 : }
454 : :
455 : 0 : j = i;
456 : 0 : }
457 : :
458 : 0 : return inside;
459 : 0 : }
460 : :
461 : 0 : bool QgsGeometryValidator::ringInRing( const QgsLineString *inside, const QgsLineString *outside )
462 : : {
463 : 0 : if ( !outside->boundingBox().contains( inside->boundingBox() ) )
464 : 0 : return false;
465 : :
466 : 0 : for ( int i = 0; !mStop && i < inside->numPoints(); i++ )
467 : : {
468 : 0 : if ( !pointInRing( outside, inside->xAt( i ), inside->yAt( i ) ) )
469 : 0 : return false;
470 : 0 : }
471 : :
472 : 0 : return true;
473 : 0 : }
|
