QGIS API Documentation  2.3.0-Master
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Properties Friends Macros Groups 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 }
27 {
28 }
29 
31 // Helper simplification methods
32 
34 float QgsMapToPixelSimplifier::calculateLengthSquared2D( double x1, double y1, double x2, double y2 )
35 {
36  float vx = ( float )( x2 - x1 );
37  float vy = ( float )( y2 - y1 );
38 
39  return vx*vx + vy*vy;
40 }
41 
43 inline static QgsRectangle calculateBoundingBox( QGis::WkbType wkbType, unsigned char* wkb, size_t numPoints )
44 {
45  double xmin = std::numeric_limits<double>::max(), x, y;
46  double ymin = std::numeric_limits<double>::max();
47  double xmax = -std::numeric_limits<double>::max();
48  double ymax = -std::numeric_limits<double>::max();
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 
58  if ( xmin > x ) xmin = x;
59  if ( ymin > y ) ymin = y;
60  if ( xmax < x ) xmax = x;
61  if ( ymax < y ) ymax = y;
62  }
63 
64  return QgsRectangle( xmin, ymin, xmax, ymax );
65 }
66 
68 inline static bool generalizeWkbGeometry( QGis::WkbType wkbType, unsigned char* sourceWkb, size_t sourceWkbSize, unsigned char* targetWkb, size_t& targetWkbSize, 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  // Skip the unnecesary generalization because of is a very single geometry
78  size_t minimumSize = ( geometryType == QGis::WKBLineString ? 4 + 2 * ( sizeOfDoubleX + sizeOfDoubleY ) : 8 + 5 * ( sizeOfDoubleX + sizeOfDoubleY ) );
79  if ( writeHeader ) minimumSize += 5;
80  if ( sourceWkbSize <= minimumSize )
81  {
82  targetWkbSize = 0;
83  return false;
84  }
85 
86  double x1 = envelope.xMinimum();
87  double y1 = envelope.yMinimum();
88  double x2 = envelope.xMaximum();
89  double y2 = envelope.yMaximum();
90 
91  // Write the main header of the geometry
92  if ( writeHeader )
93  {
94  char byteOrder = QgsApplication::endian(); // byteOrder
95  memcpy( targetWkb, &byteOrder, 1 );
96  targetWkb += 1;
97 
98  memcpy( targetWkb, &geometryType, 4 ); // type
99  targetWkb += 4;
100 
101  if ( geometryType == QGis::WKBPolygon ) // numRings
102  {
103  int numRings = 1;
104  memcpy( targetWkb, &numRings, 4 );
105  targetWkb += 4;
106  }
107  }
108 
109  // Write the generalized geometry
110  if ( geometryType == QGis::WKBLineString )
111  {
112  int numPoints = 2;
113  memcpy( targetWkb, &numPoints, 4 ); // numPoints;
114  targetWkb += 4;
115 
116  memcpy( targetWkb, &x1, sizeof( double ) ); targetWkb += sizeof( double );
117  memcpy( targetWkb, &y1, sizeof( double ) ); targetWkb += sizeof( double );
118  memcpy( targetWkb, &x2, sizeof( double ) ); targetWkb += sizeof( double );
119  memcpy( targetWkb, &y2, sizeof( double ) ); targetWkb += sizeof( double );
120  }
121  else
122  {
123  int numPoints = 5;
124  memcpy( targetWkb, &numPoints, 4 ); // numPoints;
125  targetWkb += 4;
126 
127  memcpy( targetWkb, &x1, sizeof( double ) ); targetWkb += sizeof( double );
128  memcpy( targetWkb, &y1, sizeof( double ) ); targetWkb += sizeof( double );
129  memcpy( targetWkb, &x2, sizeof( double ) ); targetWkb += sizeof( double );
130  memcpy( targetWkb, &y1, sizeof( double ) ); targetWkb += sizeof( double );
131  memcpy( targetWkb, &x2, sizeof( double ) ); targetWkb += sizeof( double );
132  memcpy( targetWkb, &y2, sizeof( double ) ); targetWkb += sizeof( double );
133  memcpy( targetWkb, &x1, sizeof( double ) ); targetWkb += sizeof( double );
134  memcpy( targetWkb, &y2, sizeof( double ) ); targetWkb += sizeof( double );
135  memcpy( targetWkb, &x1, sizeof( double ) ); targetWkb += sizeof( double );
136  memcpy( targetWkb, &y1, sizeof( double ) ); targetWkb += sizeof( double );
137  }
138  targetWkbSize += targetWkb - wkb2;
139 
140  return true;
141 }
142 
144 bool QgsMapToPixelSimplifier::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, bool isaLinearRing )
145 {
146  bool canbeGeneralizable = true;
147  bool hasZValue = QGis::wkbDimensions( wkbType ) == 3;
148  bool result = false;
149 
150  // Save initial WKB settings to use when the simplification creates invalid geometries
151  unsigned char* sourcePrevWkb = sourceWkb;
152  unsigned char* targetPrevWkb = targetWkb;
153  size_t targetWkbPrevSize = targetWkbSize;
154 
155  // Can replace the geometry by its BBOX ?
156  if (( simplifyFlags & QgsMapToPixelSimplifier::SimplifyEnvelope ) && ( envelope.xMaximum() - envelope.xMinimum() ) < map2pixelTol && ( envelope.yMaximum() - envelope.yMinimum() ) < map2pixelTol )
157  {
158  canbeGeneralizable = generalizeWkbGeometry( wkbType, sourceWkb, sourceWkbSize, targetWkb, targetWkbSize, envelope, writeHeader );
159  if ( canbeGeneralizable ) return true;
160  }
161  if ( !( simplifyFlags & QgsMapToPixelSimplifier::SimplifyGeometry ) ) canbeGeneralizable = false;
162 
163  // Write the main header of the geometry
164  if ( writeHeader )
165  {
166  memcpy( targetWkb, sourceWkb, 1 ); // byteOrder
167  sourceWkb += 1;
168  targetWkb += 1;
169 
170  int geometryType;
171  memcpy( &geometryType, sourceWkb, 4 );
172  int flatType = QGis::flatType(( QGis::WkbType )geometryType );
173  memcpy( targetWkb, &flatType, 4 ); // type
174  sourceWkb += 4;
175  targetWkb += 4;
176 
177  targetWkbSize += 5;
178  }
179 
180  unsigned char* wkb1 = sourceWkb;
181  unsigned char* wkb2 = targetWkb;
182  unsigned int flatType = QGis::flatType( wkbType );
183 
184  // Write the geometry
185  if ( flatType == QGis::WKBLineString || isaLinearRing )
186  {
187  double x, y, lastX = 0, lastY = 0;
188 
189  double xmin = std::numeric_limits<double>::max();
190  double ymin = std::numeric_limits<double>::max();
191  double xmax = -std::numeric_limits<double>::max();
192  double ymax = -std::numeric_limits<double>::max();
193 
194  int sizeOfDoubleX = sizeof( double );
195  int sizeOfDoubleY = QGis::wkbDimensions( wkbType ) == 3 /*hasZValue*/ ? 2 * sizeof( double ) : sizeof( double );
196 
197  int numPoints;
198  memcpy( &numPoints, sourceWkb, 4 );
199  sourceWkb += 4;
200  if ( numPoints <= ( isaLinearRing ? 5 : 2 ) ) canbeGeneralizable = false;
201 
202  int numTargetPoints = 0;
203  memcpy( targetWkb, &numTargetPoints, 4 );
204  targetWkb += 4;
205  targetWkbSize += 4;
206 
207  double* ptr = ( double* )targetWkb;
208  map2pixelTol *= map2pixelTol; //-> Use mappixelTol for 'LengthSquare' calculations.
209 
210  // Check whether the LinearRing is really closed.
211  if ( isaLinearRing )
212  {
213  double x1, y1, x2, y2;
214 
215  unsigned char* startWkbX = sourceWkb;
216  unsigned char* startWkbY = startWkbX + sizeOfDoubleX;
217  unsigned char* finalWkbX = sourceWkb + ( numPoints - 1 ) * ( sizeOfDoubleX + sizeOfDoubleY );
218  unsigned char* finalWkbY = finalWkbX + sizeOfDoubleX;
219 
220  memcpy( &x1, startWkbX, sizeof( double ) );
221  memcpy( &y1, startWkbY, sizeof( double ) );
222  memcpy( &x2, finalWkbX, sizeof( double ) );
223  memcpy( &y2, finalWkbY, sizeof( double ) );
224 
225  isaLinearRing = ( x1 == x2 ) && ( y1 == y2 );
226  }
227 
228  // Process each vertex...
229  for ( int i = 0, numPoints_i = ( isaLinearRing ? numPoints - 1 : numPoints ); i < numPoints_i; ++i )
230  {
231  memcpy( &x, sourceWkb, sizeof( double ) ); sourceWkb += sizeOfDoubleX;
232  memcpy( &y, sourceWkb, sizeof( double ) ); sourceWkb += sizeOfDoubleY;
233 
234  if ( i == 0 || !canbeGeneralizable || QgsMapToPixelSimplifier::calculateLengthSquared2D( x, y, lastX, lastY ) > map2pixelTol || ( !isaLinearRing && ( i == 1 || i >= numPoints - 2 ) ) )
235  {
236  memcpy( ptr, &x, sizeof( double ) ); lastX = x; ptr++;
237  memcpy( ptr, &y, sizeof( double ) ); lastY = y; ptr++;
238  numTargetPoints++;
239  }
240  if ( xmin > x ) xmin = x;
241  if ( ymin > y ) ymin = y;
242  if ( xmax < x ) xmax = x;
243  if ( ymax < y ) ymax = y;
244  }
245  targetWkb = wkb2 + 4;
246 
247  // Fix the topology of the geometry
248  if ( numTargetPoints <= ( isaLinearRing ? 2 : 1 ) )
249  {
250  sourceWkb = sourcePrevWkb;
251  targetWkb = targetPrevWkb;
252  targetWkbSize = targetWkbPrevSize;
253  return generalizeWkbGeometry( wkbType, sourceWkb, sourceWkbSize, targetWkb, targetWkbSize, QgsRectangle( xmin, ymin, xmax, ymax ), writeHeader );
254  }
255  if ( isaLinearRing )
256  {
257  memcpy( &x, targetWkb + 0, sizeof( double ) );
258  memcpy( &y, targetWkb + 8, sizeof( double ) );
259  memcpy( ptr, &x, sizeof( double ) ); ptr++;
260  memcpy( ptr, &y, sizeof( double ) ); ptr++;
261  numTargetPoints++;
262  }
263  targetWkbSize += numTargetPoints * 16;
264  targetWkb = wkb2;
265 
266  memcpy( targetWkb, &numTargetPoints, 4 );
267  result = numPoints != numTargetPoints;
268  }
269  else
270  if ( flatType == QGis::WKBPolygon )
271  {
272  int numRings;
273  memcpy( &numRings, sourceWkb, 4 );
274  sourceWkb += 4;
275 
276  memcpy( targetWkb, &numRings, 4 );
277  targetWkb += 4;
278  targetWkbSize += 4;
279 
280  for ( int i = 0; i < numRings; ++i )
281  {
282  int numPoints_i;
283  memcpy( &numPoints_i, sourceWkb, 4 );
284  QgsRectangle envelope_i = numRings == 1 ? envelope : calculateBoundingBox( wkbType, sourceWkb + 4, numPoints_i );
285 
286  size_t sourceWkbSize_i = 4 + numPoints_i * ( hasZValue ? 3 : 2 ) * sizeof( double );
287  size_t targetWkbSize_i = 0;
288 
289  result |= simplifyWkbGeometry( simplifyFlags, wkbType, sourceWkb, sourceWkbSize_i, targetWkb, targetWkbSize_i, envelope_i, map2pixelTol, false, true );
290  sourceWkb += sourceWkbSize_i;
291  targetWkb += targetWkbSize_i;
292 
293  targetWkbSize += targetWkbSize_i;
294  }
295  }
296  else
297  if ( flatType == QGis::WKBMultiLineString || flatType == QGis::WKBMultiPolygon )
298  {
299  int numGeoms;
300  memcpy( &numGeoms, sourceWkb, 4 );
301  sourceWkb += 4;
302  wkb1 += 4;
303 
304  memcpy( targetWkb, &numGeoms, 4 );
305  targetWkb += 4;
306  targetWkbSize += 4;
307 
308  for ( int i = 0; i < numGeoms; ++i )
309  {
310  size_t sourceWkbSize_i = 0;
311  size_t targetWkbSize_i = 0;
312 
313  // ... calculate the wkb-size of the current child complex geometry
314  if ( flatType == QGis::WKBMultiLineString )
315  {
316  int numPoints_i;
317  memcpy( &numPoints_i, wkb1 + 5, 4 );
318  int wkbSize_i = 4 + numPoints_i * ( hasZValue ? 3 : 2 ) * sizeof( double );
319 
320  sourceWkbSize_i += 5 + wkbSize_i;
321  wkb1 += 5 + wkbSize_i;
322  }
323  else
324  {
325  int numPrings_i;
326  memcpy( &numPrings_i, wkb1 + 5, 4 );
327  sourceWkbSize_i = 9;
328  wkb1 += 9;
329 
330  for ( int j = 0; j < numPrings_i; ++j )
331  {
332  int numPoints_i;
333  memcpy( &numPoints_i, wkb1, 4 );
334  int wkbSize_i = 4 + numPoints_i * ( hasZValue ? 3 : 2 ) * sizeof( double );
335 
336  sourceWkbSize_i += wkbSize_i;
337  wkb1 += wkbSize_i;
338  }
339  }
340  result |= simplifyWkbGeometry( simplifyFlags, QGis::singleType( wkbType ), sourceWkb, sourceWkbSize_i, targetWkb, targetWkbSize_i, envelope, map2pixelTol, true, false );
341  sourceWkb += sourceWkbSize_i;
342  targetWkb += targetWkbSize_i;
343 
344  targetWkbSize += targetWkbSize_i;
345  }
346  }
347  return result;
348 }
349 
351 
354 {
355  // Can replace the geometry by its BBOX ?
356  if (( envelope.xMaximum() - envelope.xMinimum() ) < map2pixelTol && ( envelope.yMaximum() - envelope.yMinimum() ) < map2pixelTol )
357  {
358  return true;
359  }
360  return false;
361 }
362 
365 {
366  QgsGeometry* g = new QgsGeometry();
367 
368  size_t wkbSize = geometry->wkbSize();
369  unsigned char* wkb = ( unsigned char* )malloc( wkbSize );
370  memcpy( wkb, geometry->asWkb(), wkbSize );
371  g->fromWkb( wkb, wkbSize );
373 
374  return g;
375 }
376 
378 bool QgsMapToPixelSimplifier::simplifyGeometry( QgsGeometry* geometry, int simplifyFlags, double tolerance )
379 {
380  size_t targetWkbSize = 0;
381 
382  // Check whether the geometry can be simplified using the map2pixel context
383  QGis::GeometryType geometryType = geometry->type();
384  if ( !( geometryType == QGis::Line || geometryType == QGis::Polygon ) ) return false;
385 
386  QgsRectangle envelope = geometry->boundingBox();
387  QGis::WkbType wkbType = geometry->wkbType();
388 
389  unsigned char* wkb = ( unsigned char* )geometry->asWkb( );
390  size_t wkbSize = geometry->wkbSize( );
391 
392  // Simplify the geometry rewriting temporally its WKB-stream for saving calloc's.
393  if ( simplifyWkbGeometry( simplifyFlags, wkbType, wkb, wkbSize, wkb, targetWkbSize, envelope, tolerance ) )
394  {
395  unsigned char* targetWkb = ( unsigned char* )malloc( targetWkbSize );
396  memcpy( targetWkb, wkb, targetWkbSize );
397  geometry->fromWkb( targetWkb, targetWkbSize );
398  return true;
399  }
400  return false;
401 }
402 
405 {
406  return simplifyGeometry( geometry, mSimplifyFlags, mTolerance );
407 }
static WkbType singleType(WkbType type)
Definition: qgis.h:71
A rectangle specified with double values.
Definition: qgsrectangle.h:35
GeometryType
Definition: qgis.h:155
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:189
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.
WkbType
Used for symbology operations.
Definition: qgis.h:53
static endian_t endian()
Returns whether this machine uses big or little endian.
double ANALYSIS_EXPORT max(double x, double y)
returns the maximum of two doubles or the first argument if both are equal
static WkbType flatType(WkbType type)
Definition: qgis.h:99
double yMinimum() const
Get the y minimum value (bottom side of rectangle)
Definition: qgsrectangle.h:194
double xMaximum() const
Get the x maximum value (right side of rectangle)
Definition: qgsrectangle.h:179
The geometries can be fully simplified by its BoundingBox.
static bool canbeGeneralizedByMapBoundingBox(const QgsRectangle &envelope, double map2pixelTol)
Returns whether the envelope can be replaced by its BBOX when is applied the specified map2pixel cont...
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.
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:184