QGIS API Documentation  2.8.2-Wien
 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 }
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 
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 
152 bool QgsMapToPixelSimplifier::simplifyWkbGeometry(
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 = 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
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  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  unsigned char* startWkbX = sourceWkb;
234  unsigned char* startWkbY = startWkbX + sizeOfDoubleX;
235  unsigned char* finalWkbX = sourceWkb + ( numPoints - 1 ) * ( sizeOfDoubleX + sizeOfDoubleY );
236  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 targetWkbSize = 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  unsigned char* wkb = ( unsigned char* )geometry->asWkb();
432  size_t wkbSize = geometry->wkbSize();
433 
434  // Simplify the geometry rewriting temporally its WKB-stream for saving calloc's.
435  if ( simplifyWkbGeometry( simplifyFlags, wkbType, wkb, wkbSize, wkb, targetWkbSize, envelope, tolerance ) )
436  {
437  unsigned char* targetWkb = new unsigned char[targetWkbSize];
438  memcpy( targetWkb, wkb, targetWkbSize );
439  geometry->fromWkb( targetWkb, targetWkbSize );
440  return true;
441  }
442  return false;
443 }
444 
447 {
448  return simplifyGeometry( geometry, mSimplifyFlags, mTolerance );
449 }