← Back to branch summary

~ubuntu-branches/ubuntu/wily/qgis/wily

« back to all changes in this revision

Viewing changes to src/app/qgsmaptoolsimplify.cpp

  • Committer: Bazaar Package Importer
  • Author(s): Johan Van de Wauw
  • Date: 2010-07-11 20:23:24 UTC
  • mfrom: (3.1.4 squeeze)
  • Revision ID: james.westby@ubuntu.com-20100711202324-5ktghxa7hracohmr
Tags: 1.4.0+12730-3ubuntu1
https://launchpad.net/bugs/540941
* Merge from Debian unstable (LP: #540941).
* Fix compilation issues with QT 4.7
* Add build-depends on libqt4-webkit-dev 

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/app/qgsmaptoolsimplify.cpp
 
1
/***************************************************************************
 
2
    qgsmaptoolsimplify.cpp  - simplify vector layer features
 
3
    ---------------------
 
4
    begin                : April 2009
 
5
    copyright            : (C) 2009 by Richard Kostecky
 
6
    email                : csf dot kostej at mail dot com
 
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 "qgsmaptoolsimplify.h"
 
17
 
 
18
#include "qgsgeometry.h"
 
19
#include "qgsmapcanvas.h"
 
20
#include "qgsrubberband.h"
 
21
#include "qgsvectorlayer.h"
 
22
#include "qgstolerance.h"
 
23
 
 
24
#include <QMouseEvent>
 
25
#include <QMessageBox>
 
26
 
 
27
#include <cmath>
 
28
#include <cfloat>
 
29
 
 
30
QgsSimplifyDialog::QgsSimplifyDialog( QWidget* parent )
 
31
    : QDialog( parent )
 
32
{
 
33
  setupUi( this );
 
34
  connect( horizontalSlider, SIGNAL( valueChanged( int ) ),
 
35
           this, SLOT( valueChanged( int ) ) );
 
36
  connect( okButton, SIGNAL( clicked() ),
 
37
           this, SLOT( simplify() ) );
 
38
 
 
39
}
 
40
 
 
41
void QgsSimplifyDialog::valueChanged( int value )
 
42
{
 
43
  emit toleranceChanged( value );
 
44
}
 
45
 
 
46
void QgsSimplifyDialog::simplify()
 
47
{
 
48
  emit storeSimplified();
 
49
}
 
50
 
 
51
void QgsSimplifyDialog::setRange( int minValue, int maxValue )
 
52
{
 
53
  // let's have 20 page steps
 
54
  horizontalSlider->setPageStep(( maxValue - minValue ) / 20 );
 
55
 
 
56
  horizontalSlider->setMinimum(( minValue - 1 < 0 ? 0 : minValue - 1 ) );// -1 for count with minimum tolerance end caused by double imprecision
 
57
  horizontalSlider->setMaximum( maxValue );
 
58
 
 
59
}
 
60
 
 
61
 
 
62
QgsMapToolSimplify::QgsMapToolSimplify( QgsMapCanvas* canvas )
 
63
    : QgsMapToolEdit( canvas ), mRubberBand( 0 )
 
64
{
 
65
  mSimplifyDialog = new QgsSimplifyDialog( canvas->topLevelWidget() );
 
66
  connect( mSimplifyDialog, SIGNAL( toleranceChanged( int ) ),
 
67
           this, SLOT( toleranceChanged( int ) ) );
 
68
  connect( mSimplifyDialog, SIGNAL( storeSimplified() ),
 
69
           this, SLOT( storeSimplified() ) );
 
70
  connect( mSimplifyDialog, SIGNAL( finished( int ) ),
 
71
           this, SLOT( removeRubberBand() ) );
 
72
}
 
73
 
 
74
QgsMapToolSimplify::~QgsMapToolSimplify()
 
75
{
 
76
  removeRubberBand();
 
77
  delete mSimplifyDialog;
 
78
}
 
79
 
 
80
 
 
81
void QgsMapToolSimplify::toleranceChanged( int tolerance )
 
82
{
 
83
  mTolerance = double( tolerance ) / toleranceDivider;
 
84
 
 
85
  // create a copy of selected feature and do the simplification
 
86
  QgsFeature f = mSelectedFeature;
 
87
  //QgsSimplifyFeature::simplifyLine(f, mTolerance);
 
88
  if ( mTolerance > 0 )
 
89
  {
 
90
    if ( mSelectedFeature.geometry()->type() == QGis::Line )
 
91
    {
 
92
      QgsSimplifyFeature::simplifyLine( f, mTolerance );
 
93
    }
 
94
    else
 
95
    {
 
96
      QgsSimplifyFeature::simplifyPolygon( f, mTolerance );
 
97
    }
 
98
  }
 
99
  mRubberBand->setToGeometry( f.geometry(), false );
 
100
}
 
101
 
 
102
 
 
103
void QgsMapToolSimplify::storeSimplified()
 
104
{
 
105
  QgsVectorLayer * vlayer = currentVectorLayer();
 
106
  if ( mSelectedFeature.geometry()->type() == QGis::Line )
 
107
  {
 
108
    QgsSimplifyFeature::simplifyLine( mSelectedFeature, mTolerance );
 
109
  }
 
110
  else
 
111
  {
 
112
    QgsSimplifyFeature::simplifyPolygon( mSelectedFeature, mTolerance );
 
113
  }
 
114
 
 
115
  vlayer->beginEditCommand( tr( "Geometry simplified" ) );
 
116
  vlayer->changeGeometry( mSelectedFeature.id(), mSelectedFeature.geometry() );
 
117
  vlayer->endEditCommand();
 
118
 
 
119
  mCanvas->refresh();
 
120
}
 
121
 
 
122
int QgsMapToolSimplify::calculateDivider( double minimum, double maximum )
 
123
{
 
124
  double tmp = minimum;
 
125
  long i = 1;
 
126
  if ( minimum == 0 )
 
127
  { //exception if min = 0 than divider must be counted from maximum
 
128
    tmp = maximum;
 
129
  }
 
130
  //count divider in such way so it can be used as whole number
 
131
  while ( tmp < 1 )
 
132
  {
 
133
    tmp = tmp * 10;
 
134
    i = i * 10;
 
135
  }
 
136
  if ( minimum == 0 )
 
137
  { //special case that minimum is 0 to have more than 1 step
 
138
    i = i * 100000;
 
139
  }
 
140
//taking care of problem when multiplication would overflow maxint
 
141
  while ( int( i * maximum ) < 0 )
 
142
  {
 
143
    i = i / 10;
 
144
  }
 
145
  return i;
 
146
}
 
147
 
 
148
bool QgsMapToolSimplify::calculateSliderBoudaries()
 
149
{
 
150
  double minTolerance = -1, maxTolerance = -1;
 
151
 
 
152
  double tol = 0.000001;
 
153
  bool found = false;
 
154
  bool isLine = mSelectedFeature.geometry()->type() == QGis::Line;
 
155
  QVector<QgsPoint> pts = getPointList( mSelectedFeature );
 
156
  int size = pts.size();
 
157
  if ( size == 0 || ( isLine && size <= 2 ) || ( !isLine && size <= 4 ) )
 
158
  {
 
159
    return false;
 
160
  }
 
161
 
 
162
  // calculate minimum tolerance where no vertex is excluded
 
163
  bool maximized = false;
 
164
  int count = 0;
 
165
  while ( !found )
 
166
  {
 
167
    count++;
 
168
    if ( count == 30 && !maximized )
 
169
    { //special case when tolerance is tool low to be correct so it's similat to 0
 
170
      // else in some special cases this algorithm would create infinite loop
 
171
      found = true;
 
172
      minTolerance = 0;
 
173
    }
 
174
 
 
175
    if ( QgsSimplifyFeature::simplifyPoints( pts, tol ).size() < size )
 
176
    { //some vertexes were already excluded
 
177
      if ( maximized ) //if we were already in second direction end
 
178
      {
 
179
        found = true;
 
180
        minTolerance = tol / 2;
 
181
      }
 
182
      else //only lowering tolerance till it's low enough to have all vertexes
 
183
      {
 
184
        tol = tol / 2;
 
185
      }
 
186
    }
 
187
    else
 
188
    { // simplified feature has all vertexes therefore no need we need higher tolerance also ending flag set
 
189
      // when some tolerance will exclude some of vertexes
 
190
      maximized = true;
 
191
      tol = tol * 2;
 
192
    }
 
193
  }
 
194
  found = false;
 
195
  int requiredCnt = ( isLine ? 2 : 4 ); //4 for polygon is correct because first and last points are the same
 
196
  bool bottomFound = false;
 
197
  double highTol = DBL_MAX, lowTol = DBL_MIN;// two boundaries to be used when no directly correct solution is found
 
198
  // calculate minimum tolerance where minimum (requiredCnt) of vertexes are left in geometry
 
199
  while ( !found )
 
200
  {
 
201
 
 
202
    int foundVertexes = QgsSimplifyFeature::simplifyPoints( pts, tol ).size();
 
203
    if ( foundVertexes < requiredCnt + 1 )
 
204
    { //required or lower number of verticies found
 
205
      if ( foundVertexes == requiredCnt )
 
206
      {
 
207
        found = true;
 
208
        maxTolerance = tol;
 
209
      }
 
210
      else
 
211
      { //solving problem that polygon would have less than minimum alowed vertexes
 
212
        bottomFound = true;
 
213
        highTol = tol;
 
214
        tol = ( highTol + lowTol ) / 2;
 
215
        if ( doubleNear( highTol, lowTol ) )
 
216
        { //solving problem that two points are in same distance from  line, so they will be both excluded at same time
 
217
          //so some time more than required count of vertices can stay
 
218
          found = true;
 
219
          maxTolerance = lowTol;
 
220
        }
 
221
      }
 
222
    }
 
223
    else
 
224
    {
 
225
      if ( bottomFound )
 
226
      {
 
227
        lowTol = tol;
 
228
        tol = ( highTol + lowTol ) / 2;
 
229
        if ( doubleNear( highTol, lowTol ) )
 
230
        { //solving problem that two points are in same distance from  line, so they will be both excluded at same time
 
231
          //so some time more than required count of vertices can stay
 
232
          found = true;
 
233
          maxTolerance = lowTol;
 
234
        }
 
235
      }
 
236
      else
 
237
      { //still too much verticies left so we need to increase tolerance
 
238
        lowTol = tol;
 
239
        tol = tol * 2;
 
240
      }
 
241
    }
 
242
  }
 
243
  toleranceDivider = calculateDivider( minTolerance, maxTolerance );
 
244
  // set min and max
 
245
  mSimplifyDialog->setRange( int( minTolerance * toleranceDivider ),
 
246
                             int( maxTolerance * toleranceDivider ) );
 
247
  return true;
 
248
}
 
249
 
 
250
 
 
251
void QgsMapToolSimplify::canvasPressEvent( QMouseEvent * e )
 
252
{
 
253
  QgsVectorLayer * vlayer = currentVectorLayer();
 
254
  QgsPoint layerCoords = mCanvas->getCoordinateTransform()->toMapPoint( e->pos().x(), e->pos().y() );
 
255
 
 
256
  double r = QgsTolerance::vertexSearchRadius( vlayer, mCanvas->mapRenderer() );
 
257
  QgsRectangle selectRect = QgsRectangle( layerCoords.x() - r, layerCoords.y() - r,
 
258
                                          layerCoords.x() + r, layerCoords.y() + r );
 
259
  vlayer->select( QgsAttributeList(), selectRect, true );
 
260
 
 
261
  QgsGeometry* geometry = QgsGeometry::fromPoint( layerCoords );
 
262
  double minDistance = 10000000;
 
263
  double currentDistance;
 
264
  QgsFeature f;
 
265
 
 
266
  mSelectedFeature.setValid( FALSE );
 
267
 
 
268
  while ( vlayer->nextFeature( f ) )
 
269
  {
 
270
    currentDistance = geometry->distance( *( f.geometry() ) );
 
271
    if ( currentDistance < minDistance )
 
272
    {
 
273
      minDistance = currentDistance;
 
274
      mSelectedFeature = f;
 
275
    }
 
276
  }
 
277
  if ( mSelectedFeature.geometry()->isMultipart() )
 
278
  {
 
279
    QMessageBox::critical( 0, tr( "Unsupported operation" ), tr( "Multipart features are not supported for simplification." ) );
 
280
    return;
 
281
  }
 
282
  // delete previous rubberband (if any)
 
283
  removeRubberBand();
 
284
 
 
285
  if ( mSelectedFeature.isValid() )
 
286
  {
 
287
    mRubberBand = new QgsRubberBand( mCanvas );
 
288
    mRubberBand->setToGeometry( mSelectedFeature.geometry(), false );
 
289
    mRubberBand->setColor( Qt::red );
 
290
    mRubberBand->setWidth( 2 );
 
291
    mRubberBand->show();
 
292
    //calculate boudaries for slidebar
 
293
    if ( calculateSliderBoudaries() )
 
294
    {
 
295
      // show dialog as a non-modal window
 
296
      mSimplifyDialog->show();
 
297
    }
 
298
    else
 
299
    {
 
300
      QMessageBox::warning( 0, tr( "Unsupported operation" ), tr( "This feature cannot be simplified. Check if feature has enough vertices to be simplified." ) );
 
301
    }
 
302
  }
 
303
}
 
304
 
 
305
void QgsMapToolSimplify::removeRubberBand()
 
306
{
 
307
  delete mRubberBand;
 
308
  mRubberBand = 0;
 
309
}
 
310
 
 
311
void QgsMapToolSimplify::deactivate()
 
312
{
 
313
  if ( mSimplifyDialog->isVisible() )
 
314
    mSimplifyDialog->close();
 
315
  removeRubberBand();
 
316
  QgsMapTool::deactivate();
 
317
}
 
318
 
 
319
 
 
320
QVector<QgsPoint> QgsMapToolSimplify::getPointList( QgsFeature& f )
 
321
{
 
322
  QgsGeometry* line = f.geometry();
 
323
  if (( line->type() != QGis::Line && line->type() != QGis::Polygon ) || line->isMultipart() )
 
324
  {
 
325
    return QVector<QgsPoint>();
 
326
  }
 
327
  if (( line->type() == QGis::Line ) )
 
328
  {
 
329
    return line->asPolyline();
 
330
  }
 
331
  else
 
332
  {
 
333
    if ( line->asPolygon().size() > 1 )
 
334
    {
 
335
      return QVector<QgsPoint>();
 
336
    }
 
337
    return line->asPolygon()[0];
 
338
  }
 
339
}
 
340
 
 
341
 
 
342
 
 
343
bool QgsSimplifyFeature::simplifyLine( QgsFeature& lineFeature,  double tolerance )
 
344
{
 
345
  QgsGeometry* line = lineFeature.geometry();
 
346
  if ( line->type() != QGis::Line )
 
347
  {
 
348
    return FALSE;
 
349
  }
 
350
 
 
351
  QVector<QgsPoint> resultPoints = simplifyPoints( line->asPolyline(), tolerance );
 
352
  lineFeature.setGeometry( QgsGeometry::fromPolyline( resultPoints ) );
 
353
  return TRUE;
 
354
}
 
355
 
 
356
bool QgsSimplifyFeature::simplifyPolygon( QgsFeature& polygonFeature,  double tolerance )
 
357
{
 
358
  QgsGeometry* polygon = polygonFeature.geometry();
 
359
  if ( polygon->type() != QGis::Polygon )
 
360
  {
 
361
    return FALSE;
 
362
  }
 
363
 
 
364
  QVector<QgsPoint> resultPoints = simplifyPoints( polygon->asPolygon()[0], tolerance );
 
365
  //resultPoints.push_back(resultPoints[0]);
 
366
  QVector<QgsPolyline> poly;
 
367
  poly.append( resultPoints );
 
368
  polygonFeature.setGeometry( QgsGeometry::fromPolygon( poly ) );
 
369
  return TRUE;
 
370
}
 
371
 
 
372
 
 
373
QVector<QgsPoint> QgsSimplifyFeature::simplifyPoints( const QVector<QgsPoint>& pts, double tolerance )
 
374
{
 
375
  //just safety precaution
 
376
  if ( tolerance < 0 )
 
377
    return pts;
 
378
  // Douglas-Peucker simplification algorithm
 
379
 
 
380
  int anchor  = 0;
 
381
  int floater = pts.size() - 1;
 
382
 
 
383
  QList<StackEntry> stack;
 
384
  StackEntry temporary;
 
385
  StackEntry entry = {anchor, floater};
 
386
  stack.append( entry );
 
387
 
 
388
  QSet<int> keep;
 
389
  double anchorX;
 
390
  double anchorY;
 
391
  double seg_len;
 
392
  double max_dist;
 
393
  int farthest;
 
394
  double dist_to_seg;
 
395
  double vecX;
 
396
  double vecY;
 
397
 
 
398
  while ( !stack.empty() )
 
399
  {
 
400
    temporary = stack.takeLast();
 
401
    anchor = temporary.anchor;
 
402
    floater = temporary.floater;
 
403
    // initialize line segment
 
404
    if ( pts[floater] != pts[anchor] )
 
405
    {
 
406
      anchorX = pts[floater].x() - pts[anchor].x();
 
407
      anchorY = pts[floater].y() - pts[anchor].y();
 
408
      seg_len = sqrt( anchorX * anchorX + anchorY * anchorY );
 
409
      // get the unit vector
 
410
      anchorX /= seg_len;
 
411
      anchorY /= seg_len;
 
412
    }
 
413
    else
 
414
    {
 
415
      anchorX = anchorY = seg_len = 0.0;
 
416
    }
 
417
    // inner loop:
 
418
    max_dist = 0.0;
 
419
    farthest = anchor + 1;
 
420
    for ( int i = anchor + 1; i < floater; i++ )
 
421
    {
 
422
      dist_to_seg = 0.0;
 
423
      // compare to anchor
 
424
      vecX = pts[i].x() - pts[anchor].x();
 
425
      vecY = pts[i].y() - pts[anchor].y();
 
426
      seg_len = sqrt( vecX * vecX + vecY * vecY );
 
427
      // dot product:
 
428
      double proj = vecX * anchorX + vecY * anchorY;
 
429
      if ( proj < 0.0 )
 
430
      {
 
431
        dist_to_seg = seg_len;
 
432
      }
 
433
      else
 
434
      {
 
435
        // compare to floater
 
436
        vecX = pts[i].x() - pts[floater].x();
 
437
        vecY = pts[i].y() - pts[floater].y();
 
438
        seg_len = sqrt( vecX * vecX + vecY * vecY );
 
439
        // dot product:
 
440
        proj = vecX * ( -anchorX ) + vecY * ( -anchorY );
 
441
        if ( proj < 0.0 )
 
442
        {
 
443
          dist_to_seg = seg_len;
 
444
        }
 
445
        else
 
446
        {  // calculate perpendicular distance to line (pythagorean theorem):
 
447
          dist_to_seg = sqrt( fabs( seg_len * seg_len - proj * proj ) );
 
448
        }
 
449
        if ( max_dist < dist_to_seg )
 
450
        {
 
451
          max_dist = dist_to_seg;
 
452
          farthest = i;
 
453
        }
 
454
      }
 
455
    }
 
456
    if ( max_dist <= tolerance )
 
457
    { // # use line segment
 
458
      keep.insert( anchor );
 
459
      keep.insert( floater );
 
460
    }
 
461
    else
 
462
    {
 
463
      StackEntry s = {anchor, farthest};
 
464
      stack.append( s );
 
465
 
 
466
      StackEntry r = {farthest, floater};
 
467
      stack.append( r );
 
468
    }
 
469
  }
 
470
 
 
471
  QList<int> keep2 = keep.toList();
 
472
  qSort( keep2 );
 
473
 
 
474
  QVector<QgsPoint> result;
 
475
  int position;
 
476
  while ( !keep2.empty() )
 
477
  {
 
478
    position = keep2.takeFirst();
 
479
    result.append( pts[position] );
 
480
  }
 
481
  return result;
 
482
}