QGIS API Documentation 3.37.0-Master (fdefdf9c27f)
qgsclipper.cpp
Go to the documentation of this file.
1/***************************************************************************
2 qgsclipper.cpp - a class that clips line
3 segments and polygons
4 -------------------
5 begin : March 2004
6 copyright : (C) 2005 by Gavin Macaulay
7 email :
8 ***************************************************************************/
9
10/***************************************************************************
11 * *
12 * This program is free software; you can redistribute it and/or modify *
13 * it under the terms of the GNU General Public License as published by *
14 * the Free Software Foundation; either version 2 of the License, or *
15 * (at your option) any later version. *
16 * *
17 ***************************************************************************/
18
19#include "qgsclipper.h"
20#include "qgsgeometry.h"
21#include "qgslogger.h"
22
23// Where has all the code gone?
24
25// It's been inlined, so its in the qgsclipper.h file.
26
27// But the static members must be initialized outside the class! (or GCC 4 dies)
28
29// Qt also does clipping when the coordinates go over +/- 32767
30// moreover from Qt 4.6, Qt clips also when the width/height of a painter path
31// is more than 32767. Since we want to avoid clipping by Qt (because it is slow)
32// we set coordinate limit to less than 32767 / 2
33const double QgsClipper::MAX_X = 16000;
34const double QgsClipper::MIN_X = -16000;
35const double QgsClipper::MAX_Y = 16000;
36const double QgsClipper::MIN_Y = -16000;
37
38const double QgsClipper::SMALL_NUM = 1e-12;
39
40void QgsClipper::clipped3dLine( const QVector< double > &xIn, const QVector< double > &yIn, const QVector<double> &zIn, QVector<double> &x, QVector<double> &y, QVector<double> &z, const QgsBox3D &clipExtent )
41{
42 double p0x, p0y, p0z, p1x = 0.0, p1y = 0.0, p1z = 0.0; //original coordinates
43 double p1x_c, p1y_c, p1z_c; //clipped end coordinates
44 double lastClipX = 0.0, lastClipY = 0.0, lastClipZ = 0.0; // last successfully clipped coordinates
45
46 const int nPoints = xIn.size();
47
48 x.reserve( nPoints );
49 y.reserve( nPoints );
50 z.reserve( nPoints );
51
52 const double *sourceX = xIn.data();
53 const double *sourceY = yIn.data();
54 const double *sourceZ = zIn.data();
55
56 for ( int i = 0; i < nPoints; ++i )
57 {
58 if ( i == 0 )
59 {
60 p1x = *sourceX++;
61 p1y = *sourceY++;
62 p1z = *sourceZ++;
63 }
64 else
65 {
66 p0x = p1x;
67 p0y = p1y;
68 p0z = p1z;
69
70 p1x = *sourceX++;
71 p1y = *sourceY++;
72 p1z = *sourceZ++;
73
74 p1x_c = p1x;
75 p1y_c = p1y;
76 p1z_c = p1z;
77
78 // TODO: should be in 3D
79 if ( clipLineSegment( clipExtent, p0x, p0y, p0z, p1x_c, p1y_c, p1z_c ) )
80 {
81 bool newLine = !x.isEmpty() && ( !qgsDoubleNear( p0x, lastClipX )
82 || !qgsDoubleNear( p0y, lastClipY )
83 || !qgsDoubleNear( p0z, lastClipZ ) );
84 if ( newLine )
85 {
86 //add edge points to connect old and new line
87 // TODO: should be (really) in 3D
88 connectSeparatedLines( lastClipX, lastClipY, lastClipZ, p0x, p0y, p0z, clipExtent, x, y, z );
89 }
90 if ( x.isEmpty() || newLine )
91 {
92 //add first point
93 x << p0x;
94 y << p0y;
95 z << p0z;
96 }
97
98 //add second point
99 lastClipX = p1x_c;
100 lastClipY = p1y_c;
101 lastClipZ = p1z_c;
102 x << p1x_c;
103 y << p1y_c;
104 z << p1z_c;
105 }
106 }
107 }
108}
109
110QPolygonF QgsClipper::clippedLine( const QgsCurve &curve, const QgsRectangle &clipExtent )
111{
112 return clippedLine( curve.asQPolygonF(), clipExtent );
113}
114
115QPolygonF QgsClipper::clippedLine( const QPolygonF &curve, const QgsRectangle &clipExtent )
116{
117 const int nPoints = curve.size();
118
119 double p0x, p0y, p1x = 0.0, p1y = 0.0; //original coordinates
120 double p1x_c, p1y_c; //clipped end coordinates
121 double lastClipX = 0.0, lastClipY = 0.0; //last successfully clipped coords
122
123 QPolygonF line;
124 line.reserve( nPoints + 1 );
125
126 const QPointF *curveData = curve.data();
127
128 for ( int i = 0; i < nPoints; ++i )
129 {
130 if ( i == 0 )
131 {
132 p1x = curveData->x();
133 p1y = curveData->y();
134 }
135 else
136 {
137 p0x = p1x;
138 p0y = p1y;
139
140 p1x = curveData->x();
141 p1y = curveData->y();
142
143 p1x_c = p1x;
144 p1y_c = p1y;
145 if ( clipLineSegment( clipExtent.xMinimum(), clipExtent.xMaximum(), clipExtent.yMinimum(), clipExtent.yMaximum(),
146 p0x, p0y, p1x_c, p1y_c ) )
147 {
148 const bool newLine = !line.isEmpty() && ( !qgsDoubleNear( p0x, lastClipX ) || !qgsDoubleNear( p0y, lastClipY ) );
149 if ( newLine )
150 {
151 //add edge points to connect old and new line
152 connectSeparatedLines( lastClipX, lastClipY, p0x, p0y, clipExtent, line );
153 }
154 if ( line.empty() || newLine )
155 {
156 //add first point
157 line << QPointF( p0x, p0y );
158 }
159
160 //add second point
161 lastClipX = p1x_c;
162 lastClipY = p1y_c;
163 line << QPointF( p1x_c, p1y_c );
164 }
165 }
166 curveData++;
167 }
168 return line;
169}
170
171void QgsClipper::connectSeparatedLines( double x0, double y0, double x1, double y1,
172 const QgsRectangle &clipRect, QPolygonF &pts )
173{
174 //test the different edge combinations...
175 if ( qgsDoubleNear( x0, clipRect.xMinimum() ) )
176 {
177 if ( qgsDoubleNear( x1, clipRect.xMinimum() ) )
178 {
179 return;
180 }
181 else if ( qgsDoubleNear( y1, clipRect.yMaximum() ) )
182 {
183 pts << QPointF( clipRect.xMinimum(), clipRect.yMaximum() );
184 return;
185 }
186 else if ( qgsDoubleNear( x1, clipRect.xMaximum() ) )
187 {
188 pts << QPointF( clipRect.xMinimum(), clipRect.yMaximum() );
189 pts << QPointF( clipRect.xMaximum(), clipRect.yMaximum() );
190 return;
191 }
192 else if ( qgsDoubleNear( y1, clipRect.yMinimum() ) )
193 {
194 pts << QPointF( clipRect.xMinimum(), clipRect.yMinimum() );
195 return;
196 }
197 }
198 else if ( qgsDoubleNear( y0, clipRect.yMaximum() ) )
199 {
200 if ( qgsDoubleNear( y1, clipRect.yMaximum() ) )
201 {
202 return;
203 }
204 else if ( qgsDoubleNear( x1, clipRect.xMaximum() ) )
205 {
206 pts << QPointF( clipRect.xMaximum(), clipRect.yMaximum() );
207 return;
208 }
209 else if ( qgsDoubleNear( y1, clipRect.yMinimum() ) )
210 {
211 pts << QPointF( clipRect.xMaximum(), clipRect.yMaximum() );
212 pts << QPointF( clipRect.xMaximum(), clipRect.yMinimum() );
213 return;
214 }
215 else if ( qgsDoubleNear( x1, clipRect.xMinimum() ) )
216 {
217 pts << QPointF( clipRect.xMinimum(), clipRect.yMaximum() );
218 return;
219 }
220 }
221 else if ( qgsDoubleNear( x0, clipRect.xMaximum() ) )
222 {
223 if ( qgsDoubleNear( x1, clipRect.xMaximum() ) )
224 {
225 return;
226 }
227 else if ( qgsDoubleNear( y1, clipRect.yMinimum() ) )
228 {
229 pts << QPointF( clipRect.xMaximum(), clipRect.yMinimum() );
230 return;
231 }
232 else if ( qgsDoubleNear( x1, clipRect.xMinimum() ) )
233 {
234 pts << QPointF( clipRect.xMaximum(), clipRect.yMinimum() );
235 pts << QPointF( clipRect.xMinimum(), clipRect.yMinimum() );
236 return;
237 }
238 else if ( qgsDoubleNear( y1, clipRect.yMaximum() ) )
239 {
240 pts << QPointF( clipRect.xMaximum(), clipRect.yMaximum() );
241 return;
242 }
243 }
244 else if ( qgsDoubleNear( y0, clipRect.yMinimum() ) )
245 {
246 if ( qgsDoubleNear( y1, clipRect.yMinimum() ) )
247 {
248 return;
249 }
250 else if ( qgsDoubleNear( x1, clipRect.xMinimum() ) )
251 {
252 pts << QPointF( clipRect.xMinimum(), clipRect.yMinimum() );
253 return;
254 }
255 else if ( qgsDoubleNear( y1, clipRect.yMaximum() ) )
256 {
257 pts << QPointF( clipRect.xMinimum(), clipRect.yMinimum() );
258 pts << QPointF( clipRect.xMinimum(), clipRect.yMaximum() );
259 return;
260 }
261 else if ( qgsDoubleNear( x1, clipRect.xMaximum() ) )
262 {
263 pts << QPointF( clipRect.xMaximum(), clipRect.yMinimum() );
264 return;
265 }
266 }
267}
268
269void QgsClipper::connectSeparatedLines( double x0, double y0, double z0, double x1, double y1, double z1,
270 const QgsBox3D &clipRect, QVector< double > &ptsX, QVector< double > &ptsY, QVector<double> &ptsZ )
271{
272 // TODO: really relevant and sufficient?
273 double meanZ = ( z0 + z1 ) / 2.0;
274
275 //test the different edge combinations...
276 if ( qgsDoubleNear( x0, clipRect.xMinimum() ) )
277 {
278 if ( qgsDoubleNear( x1, clipRect.xMinimum() ) )
279 {
280 return;
281 }
282 else if ( qgsDoubleNear( y1, clipRect.yMaximum() ) )
283 {
284 ptsX << clipRect.xMinimum();
285 ptsY << clipRect.yMaximum();
286 ptsZ << meanZ;
287 return;
288 }
289 else if ( qgsDoubleNear( x1, clipRect.xMaximum() ) )
290 {
291 ptsX << clipRect.xMinimum();
292 ptsY << clipRect.yMaximum();
293 ptsZ << meanZ;
294 ptsX << clipRect.xMaximum();
295 ptsY << clipRect.yMaximum();
296 ptsZ << meanZ;
297 return;
298 }
299 else if ( qgsDoubleNear( y1, clipRect.yMinimum() ) )
300 {
301 ptsX << clipRect.xMinimum();
302 ptsY << clipRect.yMinimum();
303 ptsZ << meanZ;
304 return;
305 }
306 }
307 else if ( qgsDoubleNear( y0, clipRect.yMaximum() ) )
308 {
309 if ( qgsDoubleNear( y1, clipRect.yMaximum() ) )
310 {
311 return;
312 }
313 else if ( qgsDoubleNear( x1, clipRect.xMaximum() ) )
314 {
315 ptsX << clipRect.xMaximum();
316 ptsY << clipRect.yMaximum();
317 ptsZ << meanZ;
318 return;
319 }
320 else if ( qgsDoubleNear( y1, clipRect.yMinimum() ) )
321 {
322 ptsX << clipRect.xMaximum();
323 ptsY << clipRect.yMaximum();
324 ptsZ << meanZ;
325 ptsX << clipRect.xMaximum();
326 ptsY << clipRect.yMinimum();
327 ptsZ << meanZ;
328 return;
329 }
330 else if ( qgsDoubleNear( x1, clipRect.xMinimum() ) )
331 {
332 ptsX << clipRect.xMinimum();
333 ptsY << clipRect.yMaximum();
334 ptsZ << meanZ;
335 return;
336 }
337 }
338 else if ( qgsDoubleNear( x0, clipRect.xMaximum() ) )
339 {
340 if ( qgsDoubleNear( x1, clipRect.xMaximum() ) )
341 {
342 return;
343 }
344 else if ( qgsDoubleNear( y1, clipRect.yMinimum() ) )
345 {
346 ptsX << clipRect.xMaximum();
347 ptsY << clipRect.yMinimum();
348 ptsZ << meanZ;
349 return;
350 }
351 else if ( qgsDoubleNear( x1, clipRect.xMinimum() ) )
352 {
353 ptsX << clipRect.xMaximum();
354 ptsY << clipRect.yMinimum();
355 ptsZ << meanZ;
356 ptsX << clipRect.xMinimum();
357 ptsY << clipRect.yMinimum();
358 ptsZ << meanZ;
359 return;
360 }
361 else if ( qgsDoubleNear( y1, clipRect.yMaximum() ) )
362 {
363 ptsX << clipRect.xMaximum();
364 ptsY << clipRect.yMaximum();
365 ptsZ << meanZ;
366 return;
367 }
368 }
369 else if ( qgsDoubleNear( y0, clipRect.yMinimum() ) )
370 {
371 if ( qgsDoubleNear( y1, clipRect.yMinimum() ) )
372 {
373 return;
374 }
375 else if ( qgsDoubleNear( x1, clipRect.xMinimum() ) )
376 {
377 ptsX << clipRect.xMinimum();
378 ptsY << clipRect.yMinimum();
379 ptsZ << meanZ;
380 return;
381 }
382 else if ( qgsDoubleNear( y1, clipRect.yMaximum() ) )
383 {
384 ptsX << clipRect.xMinimum();
385 ptsY << clipRect.yMinimum();
386 ptsZ << meanZ;
387 ptsX << clipRect.xMinimum();
388 ptsY << clipRect.yMaximum();
389 ptsZ << meanZ;
390 return;
391 }
392 else if ( qgsDoubleNear( x1, clipRect.xMaximum() ) )
393 {
394 ptsX << clipRect.xMaximum();
395 ptsY << clipRect.yMinimum();
396 ptsZ << meanZ;
397 return;
398 }
399 }
400}
401
A 3-dimensional box composed of x, y, z coordinates.
Definition: qgsbox3d.h:43
double yMaximum() const
Returns the maximum y value.
Definition: qgsbox3d.h:197
double xMinimum() const
Returns the minimum x value.
Definition: qgsbox3d.h:162
double xMaximum() const
Returns the maximum x value.
Definition: qgsbox3d.h:169
double yMinimum() const
Returns the minimum y value.
Definition: qgsbox3d.h:190
static bool clipLineSegment(double left, double right, double bottom, double top, double &x0, double &y0, double &x1, double &y1)
Clips a line segment to a rectangle.
Definition: qgsclipper.h:780
static const double MAX_X
Maximum X-coordinate of the rectangular box used for clipping.
Definition: qgsclipper.h:72
static const double MIN_Y
Minimum Y-coordinate of the rectangular box used for clipping.
Definition: qgsclipper.h:78
static const double MAX_Y
Maximum Y-coordinate of the rectangular box used for clipping.
Definition: qgsclipper.h:76
static QPolygonF clippedLine(const QgsCurve &curve, const QgsRectangle &clipExtent)
Takes a linestring and clips it to clipExtent.
Definition: qgsclipper.cpp:110
static const double MIN_X
Minimum X-coordinate of the rectangular box used for clipping.
Definition: qgsclipper.h:74
static void clipped3dLine(const QVector< double > &xIn, const QVector< double > &yIn, const QVector< double > &zIn, QVector< double > &x, QVector< double > &y, QVector< double > &z, const QgsBox3D &clipExtent)
Takes a line with 3D coordinates and clips it to clipExtent.
Definition: qgsclipper.cpp:40
Abstract base class for curved geometry type.
Definition: qgscurve.h:35
virtual QPolygonF asQPolygonF() const
Returns a QPolygonF representing the points.
Definition: qgscurve.cpp:266
A rectangle specified with double values.
Definition: qgsrectangle.h:42
double xMinimum() const
Returns the x minimum value (left side of rectangle).
Definition: qgsrectangle.h:201
double yMinimum() const
Returns the y minimum value (bottom side of rectangle).
Definition: qgsrectangle.h:211
double xMaximum() const
Returns the x maximum value (right side of rectangle).
Definition: qgsrectangle.h:196
double yMaximum() const
Returns the y maximum value (top side of rectangle).
Definition: qgsrectangle.h:206
bool qgsDoubleNear(double a, double b, double epsilon=4 *std::numeric_limits< double >::epsilon())
Compare two doubles (but allow some difference)
Definition: qgis.h:5207