← Back to branch summary

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

« back to all changes in this revision

Viewing changes to src/core/qgsclipper.h

  • 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/core/qgsclipper.h
4
4
                             -------------------
5
5
    begin                : March 2004
6
6
    copyright            : (C) 2005 by Gavin Macaulay
7
 
    email                : 
 
7
    email                :
8
8
 ***************************************************************************/
9
9
 
10
10
/***************************************************************************
15
15
 *   (at your option) any later version.                                   *
16
16
 *                                                                         *
17
17
 ***************************************************************************/
18
 
 /* $Id: qgsclipper.h 4502 2006-01-08 01:18:20Z timlinux $ */
 
18
/* $Id$ */
19
19
 
20
20
#ifndef QGSCLIPPER_H
21
21
#define QGSCLIPPER_H
22
22
 
23
23
#include "qgspoint.h"
24
 
#include "q3pointarray.h"
25
24
 
26
25
#include <vector>
27
26
#include <utility>
28
27
#include <cmath>
29
28
#include <iostream>
30
29
 
31
 
// The functions in this class are likely to be called from within a
32
 
// render loop and hence need to as CPU efficient as possible. 
33
 
 
34
 
// The main purpose of the functions in this class are to trim lines
35
 
// and polygons to lie within a rectangular region. This is necessary
36
 
// for drawing items to an X11 display which have a limit on the
37
 
// magnitude of the screen coordinates (+/- 32768, i.e. 16 bit integer).
38
 
 
39
 
class QgsClipper
 
30
/** \ingroup core
 
31
 * A class to trim lines and polygons to within a rectangular region.
 
32
 * The functions in this class are likely to be called from within a
 
33
 * render loop and hence need to as CPU efficient as possible.
 
34
 * The main purpose of the functions in this class are to trim lines
 
35
 *  and polygons to lie within a rectangular region. This is necessary
 
36
 *  for drawing items to an X11 display which have a limit on the
 
37
 *   magnitude of the screen coordinates (+/- 32768, i.e. 16 bit integer).
 
38
 */
 
39
 
 
40
class CORE_EXPORT QgsClipper
40
41
{
41
 
 public:
42
 
 
43
 
  // Coordinates of the rectangular box that we trim to.
44
 
  //
45
 
  // These are the limits for X11 screen coordinates. The actual
46
 
  // values are +/-32767, but we allow a little bit of space for
47
 
  // rounding errors. 
48
 
 
49
 
  // You may wonder why the clipping is done to these coordindates
50
 
  // rather than the boundaries of the qgis canvas. Reasons include:
51
 
  // - making the boundaries static const allows the compiler to
52
 
  //   optimise the code that uses these values more than if they changed
53
 
  //   for every call to the trim code.
54
 
  // - clipping takes quite a bit of CPU effort, and the less that this is
55
 
  //   done the better. More stuff would have to be clipped if the
56
 
  //   boundaries were the qgis canvas (but this may be offset by
57
 
  //   having less to draw).
58
 
  // 
59
 
  // The limit is set to 30,000 instead of 32768 because that things
60
 
  // still go wrong.
61
 
 
62
 
  static const double maxX;
63
 
  static const double minX;
64
 
  static const double maxY;
65
 
  static const double minY;
66
 
 
67
 
  // Used when testing for equivalance to 0.0
68
 
  static const double SMALL_NUM;
69
 
 
70
 
  // A handy way to refer to the four boundaries
71
 
  enum boundary {Xmax, Xmin, Ymax, Ymin};
72
 
 
73
 
  // Trims the given feature to a rectangular box. Returns the trimmed
74
 
  // feature in x and y. The shapeOpen parameter determines whether
75
 
  // the function treats the points as a closed shape (polygon), or as
76
 
  // an open shape (linestring).
77
 
  static void trimFeature(std::vector<double>& x,
78
 
                          std::vector<double>& y,
79
 
                          bool shapeOpen);
80
 
 
81
 
 private:
82
 
 
83
 
  // Trims the given feature to the given boundary. Returns the
84
 
  // trimmed feature in the outX and outY vectors.
85
 
  static void trimFeatureToBoundary(const std::vector<double>& inX,
86
 
                                    const std::vector<double>& inY,
87
 
                                    std::vector<double>& outX, 
88
 
                                    std::vector<double>& outY,
89
 
                                    boundary b, 
90
 
                                    bool shapeOpen);
91
 
 
92
 
  // Determines if a point is inside or outside the given boundary
93
 
  static bool inside(const double x, const double y, boundary b);
94
 
 
95
 
  // Calculates the intersection point between a line defined by a
96
 
  // (x1, y1), and (x2, y2) and the given boundary
97
 
  static QgsPoint intersect(const double x1, const double y1, 
98
 
                            const double x2, const double y2,
99
 
                            boundary b);
 
42
  public:
 
43
 
 
44
    // Coordinates of the rectangular box that we trim to.
 
45
    //
 
46
    // These are the limits for X11 screen coordinates. The actual
 
47
    // values are +/-32767, but we allow a little bit of space for
 
48
    // rounding errors.
 
49
 
 
50
    // You may wonder why the clipping is done to these coordindates
 
51
    // rather than the boundaries of the qgis canvas. Reasons include:
 
52
    // - making the boundaries static const allows the compiler to
 
53
    //   optimise the code that uses these values more than if they changed
 
54
    //   for every call to the trim code.
 
55
    // - clipping takes quite a bit of CPU effort, and the less that this is
 
56
    //   done the better. More stuff would have to be clipped if the
 
57
    //   boundaries were the qgis canvas (but this may be offset by
 
58
    //   having less to draw).
 
59
    //
 
60
    // The limit is set to 30,000 instead of 32768 because that things
 
61
    // still go wrong.
 
62
 
 
63
    static const double MAX_X;
 
64
    static const double MIN_X;
 
65
    static const double MAX_Y;
 
66
    static const double MIN_Y;
 
67
 
 
68
 
 
69
    // A handy way to refer to the four boundaries
 
70
    enum Boundary {XMax, XMin, YMax, YMin};
 
71
 
 
72
    // Trims the given feature to a rectangular box. Returns the trimmed
 
73
    // feature in x and y. The shapeOpen parameter determines whether
 
74
    // the function treats the points as a closed shape (polygon), or as
 
75
    // an open shape (linestring).
 
76
    static void trimFeature( std::vector<double>& x,
 
77
                             std::vector<double>& y,
 
78
                             bool shapeOpen );
 
79
 
 
80
  private:
 
81
 
 
82
    // Used when testing for equivalance to 0.0
 
83
    static const double SMALL_NUM;
 
84
 
 
85
    // Trims the given feature to the given boundary. Returns the
 
86
    // trimmed feature in the outX and outY vectors.
 
87
    static void trimFeatureToBoundary( const std::vector<double>& inX,
 
88
                                       const std::vector<double>& inY,
 
89
                                       std::vector<double>& outX,
 
90
                                       std::vector<double>& outY,
 
91
                                       Boundary b,
 
92
                                       bool shapeOpen );
 
93
 
 
94
    // Determines if a point is inside or outside the given boundary
 
95
    static bool inside( const double x, const double y, Boundary b );
 
96
 
 
97
    // Calculates the intersection point between a line defined by a
 
98
    // (x1, y1), and (x2, y2) and the given boundary
 
99
    static QgsPoint intersect( const double x1, const double y1,
 
100
                               const double x2, const double y2,
 
101
                               Boundary b );
100
102
};
101
103
 
102
104
// The inline functions
105
107
// polygon-clipping algorithm. See J. D. Foley, A. van Dam,
106
108
// S. K. Feiner, and J. F. Hughes, Computer Graphics, Principles and
107
109
// Practice. Addison-Wesley Systems Programming Series,
108
 
// Addison-Wesley, 2nd ed., 1991. 
 
110
// Addison-Wesley, 2nd ed., 1991.
109
111
 
110
112
// I understand that this is not the most efficient algorithm, but is
111
113
// one (the only?) that is guaranteed to always give the correct
112
 
// result. 
 
114
// result.
113
115
 
114
 
inline void QgsClipper::trimFeature(std::vector<double>& x,
115
 
                                    std::vector<double>& y,
116
 
                                    bool shapeOpen)
 
116
inline void QgsClipper::trimFeature( std::vector<double>& x,
 
117
                                     std::vector<double>& y,
 
118
                                     bool shapeOpen )
117
119
{
118
120
  std::vector<double> tmpX;
119
121
  std::vector<double> tmpY;
120
 
  trimFeatureToBoundary(x, y, tmpX, tmpY, Xmax, shapeOpen);
 
122
  trimFeatureToBoundary( x, y, tmpX, tmpY, XMax, shapeOpen );
121
123
 
122
124
  x.clear();
123
125
  y.clear();
124
 
  trimFeatureToBoundary(tmpX, tmpY, x, y, Ymax, shapeOpen);
 
126
  trimFeatureToBoundary( tmpX, tmpY, x, y, YMax, shapeOpen );
125
127
 
126
128
  tmpX.clear();
127
129
  tmpY.clear();
128
 
  trimFeatureToBoundary(x, y, tmpX, tmpY, Xmin, shapeOpen);
 
130
  trimFeatureToBoundary( x, y, tmpX, tmpY, XMin, shapeOpen );
129
131
 
130
132
  x.clear();
131
133
  y.clear();
132
 
  trimFeatureToBoundary(tmpX, tmpY, x, y, Ymin, shapeOpen);
 
134
  trimFeatureToBoundary( tmpX, tmpY, x, y, YMin, shapeOpen );
133
135
}
134
136
 
135
137
// An auxilary function that is part of the polygon trimming
138
140
// Hodgman's polygon-clipping algorithm.
139
141
 
140
142
inline void QgsClipper::trimFeatureToBoundary(
141
 
            const std::vector<double>& inX, 
142
 
            const std::vector<double>& inY, 
143
 
            std::vector<double>& outX, 
144
 
            std::vector<double>& outY, 
145
 
            boundary b, bool shapeOpen)
 
143
  const std::vector<double>& inX,
 
144
  const std::vector<double>& inY,
 
145
  std::vector<double>& outX,
 
146
  std::vector<double>& outY,
 
147
  Boundary b, bool shapeOpen )
146
148
{
147
149
  // The shapeOpen parameter selects whether this function treats the
148
150
  // shape as open or closed. False is appropriate for polygons and
149
151
  // true for polylines.
150
152
 
151
 
  int i1 = inX.size() - 1; // start with last point
 
153
  unsigned int i1 = inX.size() - 1; // start with last point
152
154
 
153
155
  // and compare to the first point initially.
154
 
  for (int i2 = 0; i2 < inX.size() ; ++i2)
 
156
  for ( unsigned int i2 = 0; i2 < inX.size() ; ++i2 )
155
157
  { // look at each edge of the polygon in turn
156
 
    if (inside(inX[i2], inY[i2], b)) // end point of edge is inside boundary
 
158
    if ( inside( inX[i2], inY[i2], b ) ) // end point of edge is inside boundary
157
159
    {
158
 
      if (inside(inX[i1], inY[i1], b)) 
 
160
      if ( inside( inX[i1], inY[i1], b ) )
159
161
      {
160
 
        outX.push_back( inX[i2] );
161
 
        outY.push_back( inY[i2] );
 
162
        outX.push_back( inX[i2] );
 
163
        outY.push_back( inY[i2] );
162
164
      }
163
165
      else
164
166
      {
165
 
        // edge crosses into the boundary, so trim back to the boundary, and
166
 
        // store both ends of the new edge
167
 
        if (!(i2 == 0 && shapeOpen))
168
 
        {
169
 
          QgsPoint p = intersect(inX[i1], inY[i1], inX[i2], inY[i2], b);
170
 
          outX.push_back( p.x() );
171
 
          outY.push_back( p.y() );
172
 
        }
 
167
        // edge crosses into the boundary, so trim back to the boundary, and
 
168
        // store both ends of the new edge
 
169
        if ( !( i2 == 0 && shapeOpen ) )
 
170
        {
 
171
          QgsPoint p = intersect( inX[i1], inY[i1], inX[i2], inY[i2], b );
 
172
          outX.push_back( p.x() );
 
173
          outY.push_back( p.y() );
 
174
        }
173
175
 
174
 
        outX.push_back( inX[i2] );
175
 
        outY.push_back( inY[i2] );
 
176
        outX.push_back( inX[i2] );
 
177
        outY.push_back( inY[i2] );
176
178
      }
177
179
    }
178
180
    else // end point of edge is outside boundary
179
181
    {
180
182
      // start point is in boundary, so need to trim back
181
 
      if (inside(inX[i1], inY[i1], b))
 
183
      if ( inside( inX[i1], inY[i1], b ) )
182
184
      {
183
 
        if (!(i2 == 0 && shapeOpen))
184
 
        {
185
 
          QgsPoint p = intersect(inX[i1], inY[i1], inX[i2], inY[i2], b);
186
 
          outX.push_back( p.x() );
187
 
          outY.push_back( p.y() );
188
 
        }
 
185
        if ( !( i2 == 0 && shapeOpen ) )
 
186
        {
 
187
          QgsPoint p = intersect( inX[i1], inY[i1], inX[i2], inY[i2], b );
 
188
          outX.push_back( p.x() );
 
189
          outY.push_back( p.y() );
 
190
        }
189
191
      }
190
192
    }
191
193
    i1 = i2;
193
195
}
194
196
 
195
197
// An auxilary function to trimPolygonToBoundarY() that returns
196
 
// whether a point is inside or outside the given boundary. 
 
198
// whether a point is inside or outside the given boundary.
197
199
 
198
 
inline bool QgsClipper::inside(const double x, const double y, boundary b)
 
200
inline bool QgsClipper::inside( const double x, const double y, Boundary b )
199
201
{
200
 
  switch (b)
 
202
  switch ( b )
201
203
  {
202
 
  case Xmax: // x < maxX is inside
203
 
    if (x < maxX)
204
 
      return true;
205
 
    break;
206
 
  case Xmin: // x > minX is inside
207
 
    if (x > minX)
208
 
      return true;
209
 
    break;
210
 
  case Ymax: // y < maxY is inside
211
 
    if (y < maxY)
212
 
      return true;
213
 
    break;
214
 
  case Ymin: // y > minY is inside
215
 
    if (y > minY)
216
 
      return true;
217
 
    break;
 
204
    case XMax: // x < MAX_X is inside
 
205
      if ( x < MAX_X )
 
206
        return true;
 
207
      break;
 
208
    case XMin: // x > MIN_X is inside
 
209
      if ( x > MIN_X )
 
210
        return true;
 
211
      break;
 
212
    case YMax: // y < MAX_Y is inside
 
213
      if ( y < MAX_Y )
 
214
        return true;
 
215
      break;
 
216
    case YMin: // y > MIN_Y is inside
 
217
      if ( y > MIN_Y )
 
218
        return true;
 
219
      break;
218
220
  }
219
221
  return false;
220
222
}
224
226
// returns the intersection of the line defined by the given points
225
227
// and the given boundary.
226
228
 
227
 
inline QgsPoint QgsClipper::intersect(const double x1, const double y1, 
228
 
                                      const double x2, const double y2,
229
 
                                      boundary b)
 
229
inline QgsPoint QgsClipper::intersect( const double x1, const double y1,
 
230
                                       const double x2, const double y2,
 
231
                                       Boundary b )
230
232
{
231
233
  // This function assumes that the two given points (x1, y1), and
232
234
  // (x2, y2) cross the given boundary. Making this assumption allows
233
 
  // some optimisations. 
234
 
 
235
 
  double r_n, r_d;
236
 
 
237
 
  switch (b)
 
235
  // some optimisations.
 
236
 
 
237
  double r_n = SMALL_NUM, r_d = SMALL_NUM;
 
238
 
 
239
  switch ( b )
238
240
  {
239
 
  case Xmax: // x = maxX boundary
240
 
    r_n = -(x1 - maxX) * (maxY - minY);
241
 
    r_d =  (x2 - x1)   * (maxY - minY);
242
 
    break;
243
 
  case Xmin: // x = minX boundary
244
 
    r_n = -(x1 - minX) * (maxY - minY);
245
 
    r_d =  (x2 - x1)   * (maxY - minY);
246
 
    break;
247
 
  case Ymax: // y = maxY boundary
248
 
    r_n =  (y1 - maxY) * (maxX - minX);
249
 
    r_d = -(y2 - y1)   * (maxX - minX);
250
 
    break;
251
 
  case Ymin: // y = minY boundary
252
 
    r_n =  (y1 - minY) * (maxX - minX);
253
 
    r_d = -(y2 - y1)   * (maxX - minX);
254
 
    break;
 
241
    case XMax: // x = MAX_X boundary
 
242
      r_n = -( x1 - MAX_X ) * ( MAX_Y - MIN_Y );
 
243
      r_d = ( x2 - x1 )   * ( MAX_Y - MIN_Y );
 
244
      break;
 
245
    case XMin: // x = MIN_X boundary
 
246
      r_n = -( x1 - MIN_X ) * ( MAX_Y - MIN_Y );
 
247
      r_d = ( x2 - x1 )   * ( MAX_Y - MIN_Y );
 
248
      break;
 
249
    case YMax: // y = MAX_Y boundary
 
250
      r_n = ( y1 - MAX_Y ) * ( MAX_X - MIN_X );
 
251
      r_d = -( y2 - y1 )   * ( MAX_X - MIN_X );
 
252
      break;
 
253
    case YMin: // y = MIN_Y boundary
 
254
      r_n = ( y1 - MIN_Y ) * ( MAX_X - MIN_X );
 
255
      r_d = -( y2 - y1 )   * ( MAX_X - MIN_X );
 
256
      break;
255
257
  }
256
258
 
257
259
  QgsPoint p;
258
260
 
259
 
  if (std::abs(r_d) > SMALL_NUM && std::abs(r_n) > SMALL_NUM)
 
261
  if ( std::abs( r_d ) > SMALL_NUM && std::abs( r_n ) > SMALL_NUM )
260
262
  { // they cross
261
263
    double r = r_n / r_d;
262
 
    p.set(x1 + r*(x2 - x1), y1 + r*(y2 - y1));
 
264
    p.set( x1 + r*( x2 - x1 ), y1 + r*( y2 - y1 ) );
263
265
  }
264
266
  else
265
267
  {
266
268
    // Should never get here, but if we do for some reason, cause a
267
269
    // clunk because something else is wrong if we do.
268
 
    Q_ASSERT(std::abs(r_d) > SMALL_NUM && std::abs(r_n) > SMALL_NUM);
 
270
    Q_ASSERT( std::abs( r_d ) > SMALL_NUM && std::abs( r_n ) > SMALL_NUM );
269
271
  }
270
272
 
271
273
  return p;