QGIS API Documentation  2.5.0-Master
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Properties Friends Macros Modules Pages
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 *
11  * it under the terms of the GNU General Public License as published by *
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, 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 
64 inline static bool generalizeWkbGeometry(
65  QGis::WkbType wkbType,
66  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 
80  if ( writeHeader )
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
95  if ( writeHeader )
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 
153  int simplifyFlags, QGis::WkbType wkbType,
154  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  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 = generalizeWkbGeometry( 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
181  if ( writeHeader )
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  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  // Check whether the LinearRing is really closed.
226  if ( isaLinearRing )
227  {
228  double x1, y1, x2, y2;
229 
230  unsigned char* startWkbX = sourceWkb;
231  unsigned char* startWkbY = startWkbX + sizeOfDoubleX;
232  unsigned char* finalWkbX = sourceWkb + ( numPoints - 1 ) * ( sizeOfDoubleX + sizeOfDoubleY );
233  unsigned char* finalWkbY = finalWkbX + sizeOfDoubleX;
234 
235  memcpy( &x1, startWkbX, sizeof( double ) );
236  memcpy( &y1, startWkbY, sizeof( double ) );
237  memcpy( &x2, finalWkbX, sizeof( double ) );
238  memcpy( &y2, finalWkbY, sizeof( double ) );
239 
240  isaLinearRing = ( x1 == x2 ) && ( y1 == y2 );
241  }
242 
243  // Process each vertex...
244  for ( int i = 0; i < numPoints; ++i )
245  {
246  memcpy( &x, sourceWkb, sizeof( double ) ); sourceWkb += sizeOfDoubleX;
247  memcpy( &y, sourceWkb, sizeof( double ) ); sourceWkb += sizeOfDoubleY;
248 
249  if ( i == 0 ||
250  !isGeneralizable ||
251  calculateLengthSquared2D( x, y, lastX, lastY ) > map2pixelTol ||
252  ( !isaLinearRing && ( i == 1 || i >= numPoints - 2 ) ) )
253  {
254  memcpy( ptr, &x, sizeof( double ) ); lastX = x; ptr++;
255  memcpy( ptr, &y, sizeof( double ) ); lastY = y; ptr++;
256  numTargetPoints++;
257  }
258 
259  r.combineExtentWith( x, y );
260  }
261  targetWkb = wkb2 + 4;
262 
263  // Fix the topology of the geometry
264  if ( numTargetPoints <= ( isaLinearRing ? 2 : 1 ) )
265  {
266  unsigned char* targetTempWkb = targetWkb;
267  int targetWkbTempSize = targetWkbSize;
268 
269  sourceWkb = sourcePrevWkb;
270  targetWkb = targetPrevWkb;
271  targetWkbSize = targetWkbPrevSize;
272  if ( generalizeWkbGeometry( wkbType, sourceWkb, sourceWkbSize, targetWkb, targetWkbSize, r, writeHeader ) )
273  return true;
274 
275  targetWkb = targetTempWkb;
276  targetWkbSize = targetWkbTempSize;
277  }
278  if ( isaLinearRing )
279  {
280  memcpy( &x, targetWkb + 0, sizeof( double ) );
281  memcpy( &y, targetWkb + sizeof( double ), sizeof( double ) );
282  if ( lastX != x || lastY != y )
283  {
284  memcpy( ptr, &x, sizeof( double ) ); ptr++;
285  memcpy( ptr, &y, sizeof( double ) ); ptr++;
286  numTargetPoints++;
287  }
288  }
289  targetWkbSize += numTargetPoints * sizeof( double ) * 2;
290  targetWkb = wkb2;
291 
292  memcpy( targetWkb, &numTargetPoints, 4 );
293  result = numPoints != numTargetPoints;
294  }
295  else if ( flatType == QGis::WKBPolygon )
296  {
297  int numRings;
298  memcpy( &numRings, sourceWkb, 4 );
299  sourceWkb += 4;
300 
301  memcpy( targetWkb, &numRings, 4 );
302  targetWkb += 4;
303  targetWkbSize += 4;
304 
305  for ( int i = 0; i < numRings; ++i )
306  {
307  int numPoints_i;
308  memcpy( &numPoints_i, sourceWkb, 4 );
309  QgsRectangle envelope_i = numRings == 1 ? envelope : calculateBoundingBox( wkbType, sourceWkb + 4, numPoints_i );
310 
311  size_t sourceWkbSize_i = 4 + numPoints_i * ( hasZValue ? 3 : 2 ) * sizeof( double );
312  size_t targetWkbSize_i = 0;
313 
314  result |= simplifyWkbGeometry( simplifyFlags, wkbType, sourceWkb, sourceWkbSize_i, targetWkb, targetWkbSize_i, envelope_i, map2pixelTol, false, true );
315  sourceWkb += sourceWkbSize_i;
316  targetWkb += targetWkbSize_i;
317 
318  targetWkbSize += targetWkbSize_i;
319  }
320  }
321  else if ( flatType == QGis::WKBMultiLineString || flatType == QGis::WKBMultiPolygon )
322  {
323  int numGeoms;
324  memcpy( &numGeoms, sourceWkb, 4 );
325  sourceWkb += 4;
326  wkb1 += 4;
327 
328  memcpy( targetWkb, &numGeoms, 4 );
329  targetWkb += 4;
330  targetWkbSize += 4;
331 
332  for ( int i = 0; i < numGeoms; ++i )
333  {
334  size_t sourceWkbSize_i = 0;
335  size_t targetWkbSize_i = 0;
336 
337  // ... calculate the wkb-size of the current child complex geometry
338  if ( flatType == QGis::WKBMultiLineString )
339  {
340  int numPoints_i;
341  memcpy( &numPoints_i, wkb1 + 5, 4 );
342  int wkbSize_i = 4 + numPoints_i * ( hasZValue ? 3 : 2 ) * sizeof( double );
343 
344  sourceWkbSize_i += 5 + wkbSize_i;
345  wkb1 += 5 + wkbSize_i;
346  }
347  else
348  {
349  int numPrings_i;
350  memcpy( &numPrings_i, wkb1 + 5, 4 );
351  sourceWkbSize_i = 9;
352  wkb1 += 9;
353 
354  for ( int j = 0; j < numPrings_i; ++j )
355  {
356  int numPoints_i;
357  memcpy( &numPoints_i, wkb1, 4 );
358  int wkbSize_i = 4 + numPoints_i * ( hasZValue ? 3 : 2 ) * sizeof( double );
359 
360  sourceWkbSize_i += wkbSize_i;
361  wkb1 += wkbSize_i;
362  }
363  }
364  result |= simplifyWkbGeometry( simplifyFlags, QGis::singleType( wkbType ), sourceWkb, sourceWkbSize_i, targetWkb, targetWkbSize_i, envelope, map2pixelTol, true, false );
365  sourceWkb += sourceWkbSize_i;
366  targetWkb += targetWkbSize_i;
367 
368  targetWkbSize += targetWkbSize_i;
369  }
370  }
371  return result;
372 }
373 
375 
377 bool QgsMapToPixelSimplifier::isGeneralizableByMapBoundingBox( const QgsRectangle& envelope, double map2pixelTol )
378 {
379  // Can replace the geometry by its BBOX ?
380  return envelope.width() < map2pixelTol && envelope.height() < map2pixelTol;
381 }
382 
385 {
386  QgsGeometry* g = new QgsGeometry();
387 
388  size_t wkbSize = geometry->wkbSize();
389  unsigned char* wkb = ( unsigned char* )malloc( wkbSize );
390  memcpy( wkb, geometry->asWkb(), wkbSize );
391  g->fromWkb( wkb, wkbSize );
393 
394  return g;
395 }
396 
398 bool QgsMapToPixelSimplifier::simplifyGeometry( QgsGeometry* geometry, int simplifyFlags, double tolerance )
399 {
400  size_t targetWkbSize = 0;
401 
402  // Check whether the geometry can be simplified using the map2pixel context
403  QGis::GeometryType geometryType = geometry->type();
404  if ( !( geometryType == QGis::Line || geometryType == QGis::Polygon ) )
405  return false;
406 
407  QgsRectangle envelope = geometry->boundingBox();
408  QGis::WkbType wkbType = geometry->wkbType();
409 
410  unsigned char* wkb = ( unsigned char* )geometry->asWkb( );
411  size_t wkbSize = geometry->wkbSize( );
412 
413  // Simplify the geometry rewriting temporally its WKB-stream for saving calloc's.
414  if ( simplifyWkbGeometry( simplifyFlags, wkbType, wkb, wkbSize, wkb, targetWkbSize, envelope, tolerance ) )
415  {
416  unsigned char* targetWkb = new unsigned char[targetWkbSize];
417  memcpy( targetWkb, wkb, targetWkbSize );
418  geometry->fromWkb( targetWkb, targetWkbSize );
419  return true;
420  }
421  return false;
422 }
423 
426 {
427  return simplifyGeometry( geometry, mSimplifyFlags, mTolerance );
428 }
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.
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:194
static bool generalizeWkbGeometry(QGis::WkbType wkbType, 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.
QGis::GeometryType type()
Returns type of the vector.
static QgsRectangle calculateBoundingBox(QGis::WkbType wkbType, unsigned char *wkb, size_t numPoints)
Returns the BBOX of the specified WKB-point stream.
GeometryType
Definition: qgis.h:155
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:199
double xMaximum() const
Get the x maximum value (right side of rectangle)
Definition: qgsrectangle.h:184
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 wkb (point / linestring / polygon etc.)
double mTolerance
Distance tolerance for the simplification.
virtual QgsGeometry * simplify(QgsGeometry *geometry) const
Returns a simplified version the specified geometry.
QgsRectangle boundingBox()
Returns the bounding box of this feature.
static int wkbDimensions(WkbType type)
Definition: qgis.h:139
virtual bool simplifyGeometry(QgsGeometry *geometry) const
Simplifies the specified geometry.
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...
static bool simplifyWkbGeometry(int simplifyFlags, QGis::WkbType wkbType, unsigned char *sourceWkb, size_t sourceWkbSize, unsigned char *targetWkb, size_t &targetWkbSize, const QgsRectangle &envelope, double map2pixelTol, bool writeHeader=true, bool isaLinearRing=false)
Simplify the WKB-geometry using the specified tolerance.
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:204
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:189
double height() const
Height of the rectangle.
Definition: qgsrectangle.h:209