QGIS API Documentation  2.10.1-Pisa
qgsmaptopixelgeometrysimplifier.cpp
Go to the documentation of this file.
1 /***************************************************************************
2  qgsmaptopixelgeometrysimplifier.cpp
3  ---------------------
4  begin : December 2013
5  copyright : (C) 2013 by Alvaro Huarte
6  email : http://wiki.osgeo.org/wiki/Alvaro_Huarte
7
8  ***************************************************************************
9  * *
10  * This program is free software; you can redistribute it and/or modify *
12  * the Free Software Foundation; either version 2 of the License, or *
13  * (at your option) any later version. *
14  * *
15  ***************************************************************************/
16
17 #include <limits>
19 #include "qgsapplication.h"
20
21 QgsMapToPixelSimplifier::QgsMapToPixelSimplifier( int simplifyFlags, double tolerance )
22  : mSimplifyFlags( simplifyFlags )
23  , mTolerance( tolerance )
24 {
25 }
26
28 {
29 }
30
32 // Helper simplification methods
33
35 float QgsMapToPixelSimplifier::calculateLengthSquared2D( double x1, double y1, double x2, double y2 )
36 {
37  float vx = ( float )( x2 - x1 );
38  float vy = ( float )( y2 - y1 );
39
40  return vx*vx + vy*vy;
41 }
42
44 inline static QgsRectangle calculateBoundingBox( QGis::WkbType wkbType, const unsigned char* wkb, size_t numPoints )
45 {
46  double x, y;
47  QgsRectangle r;
48  r.setMinimal();
49
50  int sizeOfDoubleX = sizeof( double );
51  int sizeOfDoubleY = QGis::wkbDimensions( wkbType ) == 3 /*hasZValue*/ ? 2 * sizeof( double ) : sizeof( double );
52
53  for ( size_t i = 0; i < numPoints; ++i )
54  {
55  memcpy( &x, wkb, sizeof( double ) ); wkb += sizeOfDoubleX;
56  memcpy( &y, wkb, sizeof( double ) ); wkb += sizeOfDoubleY;
57  r.combineExtentWith( x, y );
58  }
59
60  return r;
61 }
62
65  QGis::WkbType wkbType,
66  const unsigned char* sourceWkb, size_t sourceWkbSize,
67  unsigned char* targetWkb, size_t& targetWkbSize,
68  const QgsRectangle& envelope, bool writeHeader )
69 {
70  Q_UNUSED( sourceWkb );
71  unsigned char* wkb2 = targetWkb;
72  unsigned int geometryType = QGis::singleType( QGis::flatType( wkbType ) );
73
74  int sizeOfDoubleX = sizeof( double );
75  int sizeOfDoubleY = QGis::wkbDimensions( wkbType ) == 3 /*hasZValue*/ ? 2 * sizeof( double ) : sizeof( double );
76
77  // If the geometry is already minimal skip the generalization
78  size_t minimumSize = geometryType == QGis::WKBLineString ? 4 + 2 * ( sizeOfDoubleX + sizeOfDoubleY ) : 8 + 5 * ( sizeOfDoubleX + sizeOfDoubleY );
79
81  minimumSize += 5;
82
83  if ( sourceWkbSize <= minimumSize )
84  {
85  targetWkbSize = 0;
86  return false;
87  }
88
89  double x1 = envelope.xMinimum();
90  double y1 = envelope.yMinimum();
91  double x2 = envelope.xMaximum();
92  double y2 = envelope.yMaximum();
93
94  // Write the main header of the geometry
96  {
97  char byteOrder = QgsApplication::endian(); // byteOrder
98  memcpy( targetWkb, &byteOrder, 1 );
99  targetWkb += 1;
100
101  memcpy( targetWkb, &geometryType, 4 ); // type
102  targetWkb += 4;
103
104  if ( geometryType == QGis::WKBPolygon ) // numRings
105  {
106  int numRings = 1;
107  memcpy( targetWkb, &numRings, 4 );
108  targetWkb += 4;
109  }
110  }
111
112  // Write the generalized geometry
113  if ( geometryType == QGis::WKBLineString )
114  {
115  int numPoints = 2;
116  memcpy( targetWkb, &numPoints, 4 ); // numPoints;
117  targetWkb += 4;
118
119  memcpy( targetWkb, &x1, sizeof( double ) ); targetWkb += sizeof( double );
120  memcpy( targetWkb, &y1, sizeof( double ) ); targetWkb += sizeof( double );
121
122  memcpy( targetWkb, &x2, sizeof( double ) ); targetWkb += sizeof( double );
123  memcpy( targetWkb, &y2, sizeof( double ) ); targetWkb += sizeof( double );
124  }
125  else
126  {
127  int numPoints = 5;
128  memcpy( targetWkb, &numPoints, 4 ); // numPoints;
129  targetWkb += 4;
130
131  memcpy( targetWkb, &x1, sizeof( double ) ); targetWkb += sizeof( double );
132  memcpy( targetWkb, &y1, sizeof( double ) ); targetWkb += sizeof( double );
133
134  memcpy( targetWkb, &x2, sizeof( double ) ); targetWkb += sizeof( double );
135  memcpy( targetWkb, &y1, sizeof( double ) ); targetWkb += sizeof( double );
136
137  memcpy( targetWkb, &x2, sizeof( double ) ); targetWkb += sizeof( double );
138  memcpy( targetWkb, &y2, sizeof( double ) ); targetWkb += sizeof( double );
139
140  memcpy( targetWkb, &x1, sizeof( double ) ); targetWkb += sizeof( double );
141  memcpy( targetWkb, &y2, sizeof( double ) ); targetWkb += sizeof( double );
142
143  memcpy( targetWkb, &x1, sizeof( double ) ); targetWkb += sizeof( double );
144  memcpy( targetWkb, &y1, sizeof( double ) ); targetWkb += sizeof( double );
145  }
146  targetWkbSize += targetWkb - wkb2;
147
148  return true;
149 }
150
152 bool QgsMapToPixelSimplifier::simplifyWkbGeometry(
153  int simplifyFlags, QGis::WkbType wkbType,
154  const unsigned char* sourceWkb, size_t sourceWkbSize,
155  unsigned char* targetWkb, size_t& targetWkbSize,
156  const QgsRectangle& envelope, double map2pixelTol,
157  bool writeHeader, bool isaLinearRing )
158 {
159  bool isGeneralizable = true;
160  bool hasZValue = QGis::wkbDimensions( wkbType ) == 3;
161  bool result = false;
162
163  // Save initial WKB settings to use when the simplification creates invalid geometries
164  const unsigned char* sourcePrevWkb = sourceWkb;
165  unsigned char* targetPrevWkb = targetWkb;
166  size_t targetWkbPrevSize = targetWkbSize;
167
168  // Can replace the geometry by its BBOX ?
169  if (( simplifyFlags & QgsMapToPixelSimplifier::SimplifyEnvelope ) &&
170  isGeneralizableByMapBoundingBox( envelope, map2pixelTol ) )
171  {
172  isGeneralizable = generalizeWkbGeometryByBoundingBox( wkbType, sourceWkb, sourceWkbSize, targetWkb, targetWkbSize, envelope, writeHeader );
173  if ( isGeneralizable )
174  return true;
175  }
176
177  if ( !( simplifyFlags & QgsMapToPixelSimplifier::SimplifyGeometry ) )
178  isGeneralizable = false;
179
180  // Write the main header of the geometry
182  {
183  targetWkb[0] = sourceWkb[0]; // byteOrder
184  sourceWkb += 1;
185  targetWkb += 1;
186
187  int geometryType;
188  memcpy( &geometryType, sourceWkb, 4 );
189  int flatType = QGis::flatType(( QGis::WkbType )geometryType );
190  memcpy( targetWkb, &flatType, 4 ); // type
191  sourceWkb += 4;
192  targetWkb += 4;
193
194  targetWkbSize += 5;
195  }
196
197  const unsigned char* wkb1 = sourceWkb;
198  unsigned char* wkb2 = targetWkb;
199  unsigned int flatType = QGis::flatType( wkbType );
200
201  // Write the geometry
202  if ( flatType == QGis::WKBLineString || isaLinearRing )
203  {
204  double x, y, lastX = 0, lastY = 0;
205  QgsRectangle r;
206  r.setMinimal();
207
208  int sizeOfDoubleX = sizeof( double );
209  int sizeOfDoubleY = QGis::wkbDimensions( wkbType ) == 3 /*hasZValue*/ ? 2 * sizeof( double ) : sizeof( double );
210
211  int numPoints;
212  memcpy( &numPoints, sourceWkb, 4 );
213  sourceWkb += 4;
214  if ( numPoints <= ( isaLinearRing ? 5 : 2 ) )
215  isGeneralizable = false;
216
217  int numTargetPoints = 0;
218  memcpy( targetWkb, &numTargetPoints, 4 );
219  targetWkb += 4;
220  targetWkbSize += 4;
221
222  double* ptr = ( double* )targetWkb;
223  map2pixelTol *= map2pixelTol; //-> Use mappixelTol for 'LengthSquare' calculations.
224
225  bool isLongSegment;
226  bool hasLongSegments = false; //-> To avoid replace the simplified geometry by its BBOX when there are 'long' segments.
227
228  // Check whether the LinearRing is really closed.
229  if ( isaLinearRing )
230  {
231  double x1, y1, x2, y2;
232
233  const unsigned char* startWkbX = sourceWkb;
234  const unsigned char* startWkbY = startWkbX + sizeOfDoubleX;
235  const unsigned char* finalWkbX = sourceWkb + ( numPoints - 1 ) * ( sizeOfDoubleX + sizeOfDoubleY );
236  const unsigned char* finalWkbY = finalWkbX + sizeOfDoubleX;
237
238  memcpy( &x1, startWkbX, sizeof( double ) );
239  memcpy( &y1, startWkbY, sizeof( double ) );
240  memcpy( &x2, finalWkbX, sizeof( double ) );
241  memcpy( &y2, finalWkbY, sizeof( double ) );
242
243  isaLinearRing = ( x1 == x2 ) && ( y1 == y2 );
244  }
245
246  // Process each vertex...
247  for ( int i = 0; i < numPoints; ++i )
248  {
249  memcpy( &x, sourceWkb, sizeof( double ) ); sourceWkb += sizeOfDoubleX;
250  memcpy( &y, sourceWkb, sizeof( double ) ); sourceWkb += sizeOfDoubleY;
251
252  isLongSegment = false;
253
254  if ( i == 0 ||
255  !isGeneralizable ||
256  ( isLongSegment = ( calculateLengthSquared2D( x, y, lastX, lastY ) > map2pixelTol ) ) ||
257  ( !isaLinearRing && ( i == 1 || i >= numPoints - 2 ) ) )
258  {
259  memcpy( ptr, &x, sizeof( double ) ); lastX = x; ptr++;
260  memcpy( ptr, &y, sizeof( double ) ); lastY = y; ptr++;
261  numTargetPoints++;
262
263  hasLongSegments |= isLongSegment;
264  }
265
266  r.combineExtentWith( x, y );
267  }
268  targetWkb = wkb2 + 4;
269
270  if ( numTargetPoints < ( isaLinearRing ? 4 : 2 ) )
271  {
272  // we simplified the geometry too much!
273  if ( !hasLongSegments )
274  {
275  // approximate the geometry's shape by its bounding box
276  // (rect for linear ring / one segment for line string)
277  unsigned char* targetTempWkb = targetWkb;
278  size_t targetWkbTempSize = targetWkbSize;
279
280  sourceWkb = sourcePrevWkb;
281  targetWkb = targetPrevWkb;
282  targetWkbSize = targetWkbPrevSize;
283  if ( generalizeWkbGeometryByBoundingBox( wkbType, sourceWkb, sourceWkbSize, targetWkb, targetWkbSize, r, writeHeader ) )
284  return true;
285
286  targetWkb = targetTempWkb;
287  targetWkbSize = targetWkbTempSize;
288  }
289  else
290  {
291  // Bad luck! The simplified geometry is invalid and approximation by bounding box
292  // would create artifacts due to long segments. Worst of all, we may have overwritten
293  // the original coordinates by the simplified ones (source and target WKB ptr can be the same)
294  // so we cannot even undo the changes here. We will return invalid geometry and hope that
295  // other pieces of QGIS will survive that :-/
296  }
297  }
298  if ( isaLinearRing )
299  {
300  // make sure we keep the linear ring closed
301  memcpy( &x, targetWkb + 0, sizeof( double ) );
302  memcpy( &y, targetWkb + sizeof( double ), sizeof( double ) );
303  if ( lastX != x || lastY != y )
304  {
305  memcpy( ptr, &x, sizeof( double ) ); ptr++;
306  memcpy( ptr, &y, sizeof( double ) ); ptr++;
307  numTargetPoints++;
308  }
309  }
310  targetWkbSize += numTargetPoints * sizeof( double ) * 2;
311  targetWkb = wkb2;
312
313  memcpy( targetWkb, &numTargetPoints, 4 );
314  result = numPoints != numTargetPoints;
315  }
316  else if ( flatType == QGis::WKBPolygon )
317  {
318  int numRings;
319  memcpy( &numRings, sourceWkb, 4 );
320  sourceWkb += 4;
321
322  memcpy( targetWkb, &numRings, 4 );
323  targetWkb += 4;
324  targetWkbSize += 4;
325
326  for ( int i = 0; i < numRings; ++i )
327  {
328  int numPoints_i;
329  memcpy( &numPoints_i, sourceWkb, 4 );
330  QgsRectangle envelope_i = numRings == 1 ? envelope : calculateBoundingBox( wkbType, sourceWkb + 4, numPoints_i );
331
332  size_t sourceWkbSize_i = 4 + numPoints_i * ( hasZValue ? 3 : 2 ) * sizeof( double );
333  size_t targetWkbSize_i = 0;
334
335  result |= simplifyWkbGeometry( simplifyFlags, wkbType, sourceWkb, sourceWkbSize_i, targetWkb, targetWkbSize_i, envelope_i, map2pixelTol, false, true );
336  sourceWkb += sourceWkbSize_i;
337  targetWkb += targetWkbSize_i;
338
339  targetWkbSize += targetWkbSize_i;
340  }
341  }
342  else if ( flatType == QGis::WKBMultiLineString || flatType == QGis::WKBMultiPolygon )
343  {
344  int numGeoms;
345  memcpy( &numGeoms, sourceWkb, 4 );
346  sourceWkb += 4;
347  wkb1 += 4;
348
349  memcpy( targetWkb, &numGeoms, 4 );
350  targetWkb += 4;
351  targetWkbSize += 4;
352
353  for ( int i = 0; i < numGeoms; ++i )
354  {
355  size_t sourceWkbSize_i = 0;
356  size_t targetWkbSize_i = 0;
357
358  // ... calculate the wkb-size of the current child complex geometry
359  if ( flatType == QGis::WKBMultiLineString )
360  {
361  int numPoints_i;
362  memcpy( &numPoints_i, wkb1 + 5, 4 );
363  int wkbSize_i = 4 + numPoints_i * ( hasZValue ? 3 : 2 ) * sizeof( double );
364
365  sourceWkbSize_i += 5 + wkbSize_i;
366  wkb1 += 5 + wkbSize_i;
367  }
368  else
369  {
370  int numPrings_i;
371  memcpy( &numPrings_i, wkb1 + 5, 4 );
372  sourceWkbSize_i = 9;
373  wkb1 += 9;
374
375  for ( int j = 0; j < numPrings_i; ++j )
376  {
377  int numPoints_i;
378  memcpy( &numPoints_i, wkb1, 4 );
379  int wkbSize_i = 4 + numPoints_i * ( hasZValue ? 3 : 2 ) * sizeof( double );
380
381  sourceWkbSize_i += wkbSize_i;
382  wkb1 += wkbSize_i;
383  }
384  }
385  result |= simplifyWkbGeometry( simplifyFlags, QGis::singleType( wkbType ), sourceWkb, sourceWkbSize_i, targetWkb, targetWkbSize_i, envelope, map2pixelTol, true, false );
386  sourceWkb += sourceWkbSize_i;
387  targetWkb += targetWkbSize_i;
388
389  targetWkbSize += targetWkbSize_i;
390  }
391  }
392  return result;
393 }
394
396
398 bool QgsMapToPixelSimplifier::isGeneralizableByMapBoundingBox( const QgsRectangle& envelope, double map2pixelTol )
399 {
400  // Can replace the geometry by its BBOX ?
401  return envelope.width() < map2pixelTol && envelope.height() < map2pixelTol;
402 }
403
406 {
407  QgsGeometry* g = new QgsGeometry();
408
409  size_t wkbSize = geometry->wkbSize();
410  unsigned char* wkb = ( unsigned char* )malloc( wkbSize );
411  memcpy( wkb, geometry->asWkb(), wkbSize );
412  g->fromWkb( wkb, wkbSize );
414
415  return g;
416 }
417
419 bool QgsMapToPixelSimplifier::simplifyGeometry( QgsGeometry* geometry, int simplifyFlags, double tolerance )
420 {
421  size_t finalWkbSize = 0;
422
423  // Check whether the geometry can be simplified using the map2pixel context
424  QGis::GeometryType geometryType = geometry->type();
425  if ( !( geometryType == QGis::Line || geometryType == QGis::Polygon ) )
426  return false;
427
428  QgsRectangle envelope = geometry->boundingBox();
429  QGis::WkbType wkbType = geometry->wkbType();
430
431  const unsigned char* wkb = geometry->asWkb();
432  size_t wkbSize = geometry->wkbSize();
433
434  unsigned char* targetWkb = new unsigned char[wkbSize];
435  memcpy( targetWkb, wkb, wkbSize );
436
437  if ( simplifyWkbGeometry( simplifyFlags, wkbType, wkb, wkbSize, targetWkb, finalWkbSize, envelope, tolerance ) )
438  {
439  unsigned char* finalWkb = new unsigned char[finalWkbSize];
440  memcpy( finalWkb, targetWkb, finalWkbSize );
441  geometry->fromWkb( finalWkb, finalWkbSize );
442  delete [] targetWkb;
443  return true;
444  }
445  delete [] targetWkb;
446  return false;
447 }
448
451 {
452  return simplifyGeometry( geometry, mSimplifyFlags, mTolerance );
453 }
static WkbType singleType(WkbType type)
Definition: qgis.h:71
A rectangle specified with double values.
Definition: qgsrectangle.h:35
void setMinimal()
Set a rectangle so that min corner is at max and max corner is at min.
GeometryType
Definition: qgis.h:155
static QgsRectangle calculateBoundingBox(QGis::WkbType wkbType, const unsigned char *wkb, size_t numPoints)
Returns the BBOX of the specified WKB-point stream.
size_t wkbSize() const
Returns the size of the WKB in asWkb().
double yMaximum() const
Get the y maximum value (top side of rectangle)
Definition: qgsrectangle.h:192
virtual bool simplifyGeometry(QgsGeometry *geometry) const override
Simplifies the specified geometry.
QgsRectangle boundingBox() const
Returns the bounding box of this feature.
QGis::GeometryType type() const
Returns type of the geometry as a QGis::GeometryType.
A geometry is the spatial representation of a feature.
Definition: qgsgeometry.h:75
virtual QgsGeometry * simplify(QgsGeometry *geometry) const override
Returns a simplified version the specified geometry.
WkbType
Used for symbology operations.
Definition: qgis.h:53
static endian_t endian()
Returns whether this machine uses big or little endian.
static WkbType flatType(WkbType type)
Definition: qgis.h:99
static bool isGeneralizableByMapBoundingBox(const QgsRectangle &envelope, double map2pixelTol)
Returns whether the envelope can be replaced by its BBOX when is applied the specified map2pixel cont...
void combineExtentWith(QgsRectangle *rect)
expand the rectangle so that covers both the original rectangle and the given rectangle ...
double yMinimum() const
Get the y minimum value (bottom side of rectangle)
Definition: qgsrectangle.h:197
double xMaximum() const
Get the x maximum value (right side of rectangle)
Definition: qgsrectangle.h:182
The geometries can be fully simplified by its BoundingBox.
QgsMapToPixelSimplifier(int simplifyFlags, double tolerance)
static float calculateLengthSquared2D(double x1, double y1, double x2, double y2)
Returns the squared 2D-distance of the vector defined by the two points specified.
QGis::WkbType wkbType() const
Returns type of the geometry as a WKB type (point / linestring / polygon etc.)
static bool generalizeWkbGeometryByBoundingBox(QGis::WkbType wkbType, const unsigned char *sourceWkb, size_t sourceWkbSize, unsigned char *targetWkb, size_t &targetWkbSize, const QgsRectangle &envelope, bool writeHeader)
Generalize the WKB-geometry using the BBOX of the original geometry.
double mTolerance
Distance tolerance for the simplification.
static int wkbDimensions(WkbType type)
Definition: qgis.h:139
void fromWkb(unsigned char *wkb, size_t length)
Set the geometry, feeding in the buffer containing OGC Well-Known Binary and the buffer's length...
int mSimplifyFlags
Current simplification flags.
The geometries can be simplified using the current map2pixel context state.
double width() const
Width of the rectangle.
Definition: qgsrectangle.h:202
const unsigned char * asWkb() const
Returns the buffer containing this geometry in WKB format.
double xMinimum() const
Get the x minimum value (left side of rectangle)
Definition: qgsrectangle.h:187
double height() const
Height of the rectangle.
Definition: qgsrectangle.h:207