QGIS API Documentation  2.7.0-Master
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Modules Pages
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 
21 #include <QSettings>
22 
23 QgsGeometryValidator::QgsGeometryValidator( QgsGeometry *g, QList<QgsGeometry::Error> *errors )
24  : QThread()
25  , mErrors( errors )
26  , mStop( false )
27  , mErrorCount( 0 )
28 {
29  Q_ASSERT( g );
30  if ( g )
31  mG = *g;
32 }
33 
35 {
36  stop();
37  wait();
38 }
39 
41 {
42  mStop = true;
43 }
44 
45 void QgsGeometryValidator::checkRingIntersections(
46  int p0, int i0, const QgsPolyline &ring0,
47  int p1, int i1, const QgsPolyline &ring1 )
48 {
49  for ( int i = 0; !mStop && i < ring0.size() - 1; i++ )
50  {
51  QgsVector v = ring0[i+1] - ring0[i];
52 
53  for ( int j = 0; !mStop && j < ring1.size() - 1; j++ )
54  {
55  QgsVector w = ring1[j+1] - ring1[j];
56 
57  QgsPoint s;
58  if ( intersectLines( ring0[i], v, ring1[j], w, s ) )
59  {
60  double d = -distLine2Point( ring0[i], v.perpVector(), s );
61 
62  if ( d >= 0 && d <= v.length() )
63  {
64  d = -distLine2Point( ring1[j], w.perpVector(), s );
65  if ( d > 0 && d < w.length() )
66  {
67  QString msg = QObject::tr( "segment %1 of ring %2 of polygon %3 intersects segment %4 of ring %5 of polygon %6 at %7" )
68  .arg( i0 ).arg( i ).arg( p0 )
69  .arg( i1 ).arg( j ).arg( p1 )
70  .arg( s.toString() );
71  QgsDebugMsg( msg );
72  emit errorFound( QgsGeometry::Error( msg, s ) );
73  mErrorCount++;
74  }
75  }
76  }
77  }
78  }
79 }
80 
81 void QgsGeometryValidator::validatePolyline( int i, QgsPolyline line, bool ring )
82 {
83  if ( ring )
84  {
85  if ( line.size() < 4 )
86  {
87  QString msg = QObject::tr( "ring %1 with less than four points" ).arg( i );
88  QgsDebugMsg( msg );
89  emit errorFound( QgsGeometry::Error( msg ) );
90  mErrorCount++;
91  return;
92  }
93 
94  if ( line[0] != line[ line.size()-1 ] )
95  {
96  QString msg = QObject::tr( "ring %1 not closed" ).arg( i );
97  QgsDebugMsg( msg );
98  emit errorFound( QgsGeometry::Error( msg ) );
99  mErrorCount++;
100  return;
101  }
102  }
103  else if ( line.size() < 2 )
104  {
105  QString msg = QObject::tr( "line %1 with less than two points" ).arg( i );
106  QgsDebugMsg( msg );
107  emit errorFound( QgsGeometry::Error( msg ) );
108  mErrorCount++;
109  return;
110  }
111 
112  int j = 0;
113  while ( j < line.size() - 1 )
114  {
115  int n = 0;
116  while ( j < line.size() - 1 && line[j] == line[j+1] )
117  {
118  line.remove( j );
119  n++;
120  }
121 
122  if ( n > 0 )
123  {
124  QString msg = QObject::tr( "line %1 contains %n duplicate node(s) at %2", "number of duplicate nodes", n ).arg( i ).arg( j );
125  QgsDebugMsg( msg );
126  emit errorFound( QgsGeometry::Error( msg, line[j] ) );
127  mErrorCount++;
128  }
129 
130  j++;
131  }
132 
133  for ( j = 0; !mStop && j < line.size() - 3; j++ )
134  {
135  QgsVector v = line[j+1] - line[j];
136  double vl = v.length();
137 
138  int n = ( j == 0 && ring ) ? line.size() - 2 : line.size() - 1;
139 
140  for ( int k = j + 2; !mStop && k < n; k++ )
141  {
142  QgsVector w = line[k+1] - line[k];
143 
144  QgsPoint s;
145  if ( !intersectLines( line[j], v, line[k], w, s ) )
146  continue;
147 
148  double d = -distLine2Point( line[j], v.perpVector(), s );
149  if ( d < 0 || d > vl )
150  continue;
151 
152  d = -distLine2Point( line[k], w.perpVector(), s );
153  if ( d <= 0 || d >= w.length() )
154  continue;
155 
156  QString msg = QObject::tr( "segments %1 and %2 of line %3 intersect at %4" ).arg( j ).arg( k ).arg( i ).arg( s.toString() );
157  QgsDebugMsg( msg );
158  emit errorFound( QgsGeometry::Error( msg, s ) );
159  mErrorCount++;
160  }
161  }
162 }
163 
164 void QgsGeometryValidator::validatePolygon( int idx, const QgsPolygon &polygon )
165 {
166  // check if holes are inside polygon
167  for ( int i = 1; !mStop && i < polygon.size(); i++ )
168  {
169  if ( !ringInRing( polygon[i], polygon[0] ) )
170  {
171  QString msg = QObject::tr( "ring %1 of polygon %2 not in exterior ring" ).arg( i ).arg( idx );
172  QgsDebugMsg( msg );
173  emit errorFound( QgsGeometry::Error( msg ) );
174  mErrorCount++;
175  }
176  }
177 
178  // check holes for intersections
179  for ( int i = 1; !mStop && i < polygon.size(); i++ )
180  {
181  for ( int j = i + 1; !mStop && j < polygon.size(); j++ )
182  {
183  checkRingIntersections( idx, i, polygon[i], idx, j, polygon[j] );
184  }
185  }
186 
187  // check if rings are self-intersecting
188  for ( int i = 0; !mStop && i < polygon.size(); i++ )
189  {
190  validatePolyline( i, polygon[i], true );
191  }
192 }
193 
195 {
196  mErrorCount = 0;
197 #if defined(GEOS_VERSION_MAJOR) && defined(GEOS_VERSION_MINOR) && \
198  ( (GEOS_VERSION_MAJOR==3 && GEOS_VERSION_MINOR>=3) || GEOS_VERSION_MAJOR>3)
199  QSettings settings;
200  if ( settings.value( "/qgis/digitizing/validate_geometries", 1 ).toInt() == 2 )
201  {
202  char *r = 0;
203  const GEOSGeometry *g0 = mG.asGeos();
204  GEOSContextHandle_t handle = QgsGeometry::getGEOSHandler();
205  if ( !g0 )
206  {
207  emit errorFound( QgsGeometry::Error( QObject::tr( "GEOS error:could not produce geometry for GEOS (check log window)" ) ) );
208  }
209  else
210  {
211  GEOSGeometry *g1 = 0;
212  if ( GEOSisValidDetail_r( handle, g0, GEOSVALID_ALLOW_SELFTOUCHING_RING_FORMING_HOLE, &r, &g1 ) != 1 )
213  {
214  if ( g1 )
215  {
216  const GEOSCoordSequence *cs = GEOSGeom_getCoordSeq_r( handle, g1 );
217 
218  unsigned int n;
219  if ( GEOSCoordSeq_getSize_r( handle, cs, &n ) && n == 1 )
220  {
221  double x, y;
222  GEOSCoordSeq_getX_r( handle, cs, 0, &x );
223  GEOSCoordSeq_getY_r( handle, cs, 0, &y );
224  emit errorFound( QgsGeometry::Error( QObject::tr( "GEOS error:%1" ).arg( r ), QgsPoint( x, y ) ) );
225  mErrorCount++;
226  }
227 
228  GEOSGeom_destroy_r( handle, g1 );
229  }
230  else
231  {
232  emit errorFound( QgsGeometry::Error( QObject::tr( "GEOS error:%1" ).arg( r ) ) );
233  mErrorCount++;
234  }
235 
236  GEOSFree_r( handle, r );
237  }
238  }
239 
240  return;
241  }
242 #endif
243 
244  QgsDebugMsg( "validation thread started." );
245 
246  switch ( mG.wkbType() )
247  {
248  case QGis::WKBPoint:
249  case QGis::WKBPoint25D:
250  case QGis::WKBMultiPoint:
252  break;
253 
254  case QGis::WKBLineString:
256  validatePolyline( 0, mG.asPolyline() );
257  break;
258 
261  {
263  for ( int i = 0; !mStop && i < mp.size(); i++ )
264  validatePolyline( i, mp[i] );
265  }
266  break;
267 
268  case QGis::WKBPolygon:
269  case QGis::WKBPolygon25D:
270  {
271  validatePolygon( 0, mG.asPolygon() );
272  }
273  break;
274 
277  {
279  for ( int i = 0; !mStop && i < mp.size(); i++ )
280  {
281  validatePolygon( i, mp[i] );
282  }
283 
284  for ( int i = 0; !mStop && i < mp.size(); i++ )
285  {
286  if ( mp[i].isEmpty() )
287  {
288  emit errorFound( QgsGeometry::Error( QObject::tr( "polygon %1 has no rings" ).arg( i ) ) );
289  mErrorCount++;
290  continue;
291  }
292 
293  for ( int j = i + 1; !mStop && j < mp.size(); j++ )
294  {
295  if ( mp[j].isEmpty() )
296  continue;
297 
298  if ( ringInRing( mp[i][0], mp[j][0] ) )
299  {
300  emit errorFound( QgsGeometry::Error( QObject::tr( "polygon %1 inside polygon %2" ).arg( i ).arg( j ) ) );
301  mErrorCount++;
302  }
303  else if ( ringInRing( mp[j][0], mp[i][0] ) )
304  {
305  emit errorFound( QgsGeometry::Error( QObject::tr( "polygon %1 inside polygon %2" ).arg( j ).arg( i ) ) );
306  mErrorCount++;
307  }
308  else
309  {
310  checkRingIntersections( i, 0, mp[i][0], j, 0, mp[j][0] );
311  }
312  }
313  }
314  }
315  break;
316 
317  case QGis::WKBNoGeometry:
318  case QGis::WKBUnknown:
319  QgsDebugMsg( QObject::tr( "Unknown geometry type" ) );
320  emit errorFound( QgsGeometry::Error( QObject::tr( "Unknown geometry type %1" ).arg( mG.wkbType() ) ) );
321  mErrorCount++;
322  break;
323  }
324 
325  QgsDebugMsg( "validation finished." );
326 
327  if ( mStop )
328  {
329  emit errorFound( QObject::tr( "Geometry validation was aborted." ) );
330  }
331  else if ( mErrorCount > 0 )
332  {
333  emit errorFound( QObject::tr( "Geometry has %1 errors." ).arg( mErrorCount ) );
334  }
335 #if 0
336  else
337  {
338  emit errorFound( QObject::tr( "Geometry is valid." ) );
339  }
340 #endif
341 }
342 
344 {
345  if ( mErrors )
346  *mErrors << e;
347 }
348 
349 void QgsGeometryValidator::validateGeometry( QgsGeometry *g, QList<QgsGeometry::Error> &errors )
350 {
351  QgsGeometryValidator *gv = new QgsGeometryValidator( g, &errors );
352  connect( gv, SIGNAL( errorFound( QgsGeometry::Error ) ), gv, SLOT( addError( QgsGeometry::Error ) ) );
353  gv->run();
354  gv->wait();
355 }
356 
357 //
358 // distance of point q from line through p in direction v
359 // return >0 => q lies left of the line
360 // <0 => q lies right of the line
361 //
362 double QgsGeometryValidator::distLine2Point( QgsPoint p, QgsVector v, QgsPoint q )
363 {
364  if ( v.length() == 0 )
365  {
366  throw QgsException( QObject::tr( "invalid line" ) );
367  }
368 
369  return ( v.x()*( q.y() - p.y() ) - v.y()*( q.x() - p.x() ) ) / v.length();
370 }
371 
372 bool QgsGeometryValidator::intersectLines( QgsPoint p, QgsVector v, QgsPoint q, QgsVector w, QgsPoint &s )
373 {
374  double d = v.y() * w.x() - v.x() * w.y();
375 
376  if ( d == 0 )
377  return false;
378 
379  double dx = q.x() - p.x();
380  double dy = q.y() - p.y();
381  double k = ( dy * w.x() - dx * w.y() ) / d;
382 
383  s = p + v * k;
384 
385  return true;
386 }
387 
388 bool QgsGeometryValidator::pointInRing( const QgsPolyline &ring, const QgsPoint &p )
389 {
390  bool inside = false;
391  int j = ring.size() - 1;
392 
393  for ( int i = 0; !mStop && i < ring.size(); i++ )
394  {
395  if ( ring[i].x() == p.x() && ring[i].y() == p.y() )
396  return true;
397 
398  if (( ring[i].y() < p.y() && ring[j].y() >= p.y() ) ||
399  ( ring[j].y() < p.y() && ring[i].y() >= p.y() ) )
400  {
401  if ( ring[i].x() + ( p.y() - ring[i].y() ) / ( ring[j].y() - ring[i].y() )*( ring[j].x() - ring[i].x() ) <= p.x() )
402  inside = !inside;
403  }
404 
405  j = i;
406  }
407 
408  return inside;
409 }
410 
411 bool QgsGeometryValidator::ringInRing( const QgsPolyline &inside, const QgsPolyline &outside )
412 {
413  for ( int i = 0; !mStop && i < inside.size(); i++ )
414  {
415  if ( !pointInRing( outside, inside[i] ) )
416  return false;
417  }
418 
419  return true;
420 }
static void validateGeometry(QgsGeometry *g, QList< QgsGeometry::Error > &errors)
Validate geometry and produce a list of geometry errors.
void addError(QgsGeometry::Error)
#define QgsDebugMsg(str)
Definition: qgslogger.h:33
QgsMultiPolyline asMultiPolyline() const
return contents of the geometry as a multi linestring if wkbType is WKBMultiLineString, otherwise an empty list
QVector< QgsPoint > QgsPolyline
polyline is represented as a vector of points
Definition: qgsgeometry.h:33
QgsPolygon asPolygon() const
return contents of the geometry as a polygon if wkbType is WKBPolygon, otherwise an empty list ...
double y() const
Definition: qgspoint.cpp:69
double x() const
Definition: qgspoint.h:126
const GEOSGeometry * asGeos() const
Returns a geos geometry.
QgsMultiPolygon asMultiPolygon() const
return contents of the geometry as a multi polygon if wkbType is WKBMultiPolygon, otherwise an empty ...
QgsVector perpVector() const
Definition: qgspoint.cpp:75
QVector< QgsPolygon > QgsMultiPolygon
a collection of QgsPolygons that share a common collection of attributes
Definition: qgsgeometry.h:48
QString toString() const
String representation of the point (x,y)
Definition: qgspoint.cpp:126
QgsGeometryValidator(QgsGeometry *g, QList< QgsGeometry::Error > *errors=0)
Constructor.
QGis::WkbType wkbType() const
Returns type of wkb (point / linestring / polygon etc.)
QVector< QgsPolyline > QgsPolygon
polygon: first item of the list is outer ring, inner rings (if any) start from second item ...
Definition: qgsgeometry.h:39
A class to represent a point.
Definition: qgspoint.h:63
A class to represent a vector.
Definition: qgspoint.h:32
double length() const
Definition: qgspoint.cpp:59
QVector< QgsPolyline > QgsMultiPolyline
a collection of QgsPolylines that share a common collection of attributes
Definition: qgsgeometry.h:45
QgsPolyline asPolyline() const
return contents of the geometry as a polyline if wkbType is WKBLineString, otherwise an empty list ...
static GEOSContextHandle_t getGEOSHandler()
return GEOS context handle
void errorFound(QgsGeometry::Error)
double y() const
Definition: qgspoint.h:134
double x() const
Definition: qgspoint.cpp:64
Defines a qgis exception class.
Definition: qgsexception.h:25
#define tr(sourceText)