QGIS API Documentation 3.43.0-Master (c67cf405802)
qgsclipper.h
Go to the documentation of this file.
1/***************************************************************************
2 qgsclipper.h - 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#ifndef QGSCLIPPER_H
20#define QGSCLIPPER_H
21
22#include "qgis_core.h"
23#include "qgis_sip.h"
24#include "qgspointxy.h"
25#include "qgsrectangle.h"
26
27#include <QVector>
28#include <QPolygonF>
29
30#include "qgsbox3d.h"
31#include "qgsabstractgeometry.h"
32
33class QgsCurve;
34class QgsLineString;
35
36SIP_FEATURE( ARM ) // Some parts are not available in sip bindings on ARM because of qreal double vs. float issues
37
38
39
51class CORE_EXPORT QgsClipper
52{
53 public:
54
55 // These are the limits for X11 screen coordinates. The actual
56 // values are +/-32767, but we allow a little bit of space for
57 // rounding errors.
58
59 // You may wonder why the clipping is done to these coordinates
60 // rather than the boundaries of the qgis canvas. Reasons include:
61 // - making the boundaries static const allows the compiler to
62 // optimise the code that uses these values more than if they changed
63 // for every call to the trim code.
64 // - clipping takes quite a bit of CPU effort, and the less that this is
65 // done the better. More stuff would have to be clipped if the
66 // boundaries were the qgis canvas (but this may be offset by
67 // having less to draw).
68 //
69 // The limit is set to 30,000 instead of 32768 because that things
70 // still go wrong.
71
73 static const double MAX_X;
75 static const double MIN_X;
77 static const double MAX_Y;
79 static const double MIN_Y;
80
81
92
101 static void trimFeature( QVector<double> &x,
102 QVector<double> &y,
103 bool shapeOpen );
104
111 static void trimPolygon( QPolygonF &pts, const QgsRectangle &clipRect );
112
119 static void trimPolygon( QVector< double > &x, QVector< double > &y, QVector< double> &z, const QgsBox3D &clipRect ) SIP_SKIP;
120
126 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 ) SIP_SKIP;
127
134 static QPolygonF clippedLine( const QgsCurve &curve, const QgsRectangle &clipExtent );
135
143 static QPolygonF clippedLine( const QPolygonF &curve, const QgsRectangle &clipExtent );
144
162 static bool clipLineSegment( double left, double right, double bottom, double top, double &x0 SIP_INOUT, double &y0 SIP_INOUT, double &x1 SIP_INOUT, double &y1 SIP_INOUT );
163
164 private:
165
166 // Used when testing for equivalence to 0.0
167 static const double SMALL_NUM;
168
169 // Trims the given feature to the given boundary. Returns the
170 // trimmed feature in the outX and outY vectors.
171 static inline void trimFeatureToBoundary( const QVector<double> &inX,
172 const QVector<double> &inY,
173 QVector<double> &outX,
174 QVector<double> &outY,
175 Boundary b,
176 bool shapeOpen );
177
178 static inline void trimPolygonToBoundary( const QPolygonF &inPts, QPolygonF &outPts, const QgsRectangle &rect, Boundary b, double boundaryValue );
179
180 static inline void trimPolygonToBoundary( const QVector<double> &inX, const QVector<double> &inY, const QVector< double > &inZ,
181 QVector<double> &outX, QVector<double> &outY, QVector<double> &outZ, const QgsBox3D &rect, Boundary boundary, double boundaryValue );
182
183 // Determines if a point is inside or outside the given boundary
184 static inline bool inside( double x, double y, Boundary b );
185
186 static inline bool inside( QPointF pt, Boundary b, double val );
187
188 static inline bool inside( double x, double y, double z, Boundary boundary, double boundaryValue );
189
190 // Calculates the intersection point between a line defined by a
191 // (x1, y1), and (x2, y2) and the given boundary
192 static inline QgsPointXY intersect( double x1, double y1,
193 double x2, double y2,
194 Boundary b );
195
196 static inline QPointF intersectRect( QPointF pt1,
197 QPointF pt2,
198 Boundary b, const QgsRectangle &rect );
199
200 static inline void intersectRect( double x1, double y1, double z1, double x2, double y2, double z2,
201 double &xOut, double &yOut, double &zOut,
202 Boundary boundary, const QgsBox3D &rect );
203
204 static bool clipLineSegment( const QgsBox3D &extent, double &x0, double &y0, double &z0, double &x1, double &y1, double &z1 );
205
215 static void connectSeparatedLines( double x0, double y0, double x1, double y1,
216 const QgsRectangle &clipRect, QPolygonF &pts );
217
231 static void connectSeparatedLines( double x0, double y0, double z0, double x1, double y1, double z1,
232 const QgsBox3D &clipRect, QVector< double > &ptsX, QVector< double > &ptsY, QVector<double> &ptsZ );
233
234 //low level clip methods for fast clip algorithm
235 static void clipStartTop( double &x0, double &y0, double x1, double y1, double yMax );
236 static void clipStartBottom( double &x0, double &y0, double x1, double y1, double yMin );
237 static void clipStartRight( double &x0, double &y0, double x1, double y1, double xMax );
238 static void clipStartLeft( double &x0, double &y0, double &x1, double &y1, double xMin );
239 static void clipEndTop( double x0, double y0, double &x1, double &y1, double yMax );
240 static void clipEndBottom( double x0, double y0, double &x1, double &y1, double yMin );
241 static void clipEndRight( double x0, double y0, double &x1, double &y1, double xMax );
242 static void clipEndLeft( double x0, double y0, double &x1, double &y1, double xMin );
243};
244
245#include "qgslinestring.h"
246#include "qgspoint.h"
247
248#ifndef SIP_RUN
249// The inline functions
250
251// Trim the feature using Sutherland and Hodgman's
252// polygon-clipping algorithm. See J. D. Foley, A. van Dam,
253// S. K. Feiner, and J. F. Hughes, Computer Graphics, Principles and
254// Practice. Addison-Wesley Systems Programming Series,
255// Addison-Wesley, 2nd ed., 1991.
256
257// I understand that this is not the most efficient algorithm, but is
258// one (the only?) that is guaranteed to always give the correct
259// result.
260
261inline void QgsClipper::trimFeature( QVector<double> &x,
262 QVector<double> &y,
263 bool shapeOpen )
264{
265 QVector<double> tmpX;
266 QVector<double> tmpY;
267 trimFeatureToBoundary( x, y, tmpX, tmpY, XMax, shapeOpen );
268
269 x.clear();
270 y.clear();
271 trimFeatureToBoundary( tmpX, tmpY, x, y, YMax, shapeOpen );
272
273 tmpX.clear();
274 tmpY.clear();
275 trimFeatureToBoundary( x, y, tmpX, tmpY, XMin, shapeOpen );
276
277 x.clear();
278 y.clear();
279 trimFeatureToBoundary( tmpX, tmpY, x, y, YMin, shapeOpen );
280}
281
282inline void QgsClipper::trimPolygon( QPolygonF &pts, const QgsRectangle &clipRect )
283{
284 QPolygonF tmpPts;
285 tmpPts.reserve( pts.size() );
286
287 trimPolygonToBoundary( pts, tmpPts, clipRect, XMax, clipRect.xMaximum() );
288 pts.resize( 0 );
289 trimPolygonToBoundary( tmpPts, pts, clipRect, YMax, clipRect.yMaximum() );
290 tmpPts.resize( 0 );
291 trimPolygonToBoundary( pts, tmpPts, clipRect, XMin, clipRect.xMinimum() );
292 pts.resize( 0 );
293 trimPolygonToBoundary( tmpPts, pts, clipRect, YMin, clipRect.yMinimum() );
294}
295
296inline void QgsClipper::trimPolygon( QVector<double> &x, QVector<double> &y, QVector<double> &z, const QgsBox3D &clipRect )
297{
298 QVector< double > tempX;
299 QVector< double > tempY;
300 QVector< double > tempZ;
301 const int size = x.size();
302 tempX.reserve( size );
303 tempY.reserve( size );
304 tempZ.reserve( size );
305
306 trimPolygonToBoundary( x, y, z, tempX, tempY, tempZ, clipRect, XMax, clipRect.xMaximum() );
307 x.resize( 0 );
308 y.resize( 0 );
309 z.resize( 0 );
310 trimPolygonToBoundary( tempX, tempY, tempZ, x, y, z, clipRect, YMax, clipRect.yMaximum() );
311 tempX.resize( 0 );
312 tempY.resize( 0 );
313 tempZ.resize( 0 );
314 trimPolygonToBoundary( x, y, z, tempX, tempY, tempZ, clipRect, XMin, clipRect.xMinimum() );
315 x.resize( 0 );
316 y.resize( 0 );
317 z.resize( 0 );
318 trimPolygonToBoundary( tempX, tempY, tempZ, x, y, z, clipRect, YMin, clipRect.yMinimum() );
319
320 if ( !clipRect.is2d() )
321 {
322 tempX.resize( 0 );
323 tempY.resize( 0 );
324 tempZ.resize( 0 );
325 trimPolygonToBoundary( x, y, z, tempX, tempY, tempZ, clipRect, ZMax, clipRect.zMaximum() );
326 x.resize( 0 );
327 y.resize( 0 );
328 z.resize( 0 );
329 trimPolygonToBoundary( tempX, tempY, tempZ, x, y, z, clipRect, ZMin, clipRect.zMinimum() );
330 }
331}
332
333// An auxiliary function that is part of the polygon trimming
334// code. Will trim the given polygon to the given boundary and return
335// the trimmed polygon in the out pointer. Uses Sutherland and
336// Hodgman's polygon-clipping algorithm.
337
338inline void QgsClipper::trimFeatureToBoundary(
339 const QVector<double> &inX,
340 const QVector<double> &inY,
341 QVector<double> &outX,
342 QVector<double> &outY,
343 Boundary b, bool shapeOpen )
344{
345 // The shapeOpen parameter selects whether this function treats the
346 // shape as open or closed. False is appropriate for polygons and
347 // true for polylines.
348
349 int i1 = inX.size() - 1; // start with last point
350
351 // and compare to the first point initially.
352 for ( int i2 = 0; i2 < inX.size() ; ++i2 )
353 {
354 // look at each edge of the polygon in turn
355
356 //ignore segments with nan or inf coordinates
357 if ( std::isnan( inX[i2] ) || std::isnan( inY[i2] ) || std::isinf( inX[i2] ) || std::isinf( inY[i2] )
358 || std::isnan( inX[i1] ) || std::isnan( inY[i1] ) || std::isinf( inX[i1] ) || std::isinf( inY[i1] ) )
359 {
360 i1 = i2;
361 continue;
362 }
363
364
365 if ( inside( inX[i2], inY[i2], b ) ) // end point of edge is inside boundary
366 {
367 if ( inside( inX[i1], inY[i1], b ) )
368 {
369 outX.push_back( inX[i2] );
370 outY.push_back( inY[i2] );
371 }
372 else
373 {
374 // edge crosses into the boundary, so trim back to the boundary, and
375 // store both ends of the new edge
376 if ( !( i2 == 0 && shapeOpen ) )
377 {
378 const QgsPointXY p = intersect( inX[i1], inY[i1], inX[i2], inY[i2], b );
379 outX.push_back( p.x() );
380 outY.push_back( p.y() );
381 }
382
383 outX.push_back( inX[i2] );
384 outY.push_back( inY[i2] );
385 }
386 }
387 else // end point of edge is outside boundary
388 {
389 // start point is in boundary, so need to trim back
390 if ( inside( inX[i1], inY[i1], b ) )
391 {
392 if ( !( i2 == 0 && shapeOpen ) )
393 {
394 const QgsPointXY p = intersect( inX[i1], inY[i1], inX[i2], inY[i2], b );
395 outX.push_back( p.x() );
396 outY.push_back( p.y() );
397 }
398 }
399 }
400 i1 = i2;
401 }
402}
403
404inline void QgsClipper::trimPolygonToBoundary( const QPolygonF &inPts, QPolygonF &outPts, const QgsRectangle &rect, Boundary b, double boundaryValue )
405{
406 int i1 = inPts.size() - 1; // start with last point
407
408 // and compare to the first point initially.
409 for ( int i2 = 0; i2 < inPts.size() ; ++i2 )
410 {
411 // look at each edge of the polygon in turn
412 if ( inside( inPts[i2], b, boundaryValue ) ) // end point of edge is inside boundary
413 {
414 if ( inside( inPts[i1], b, boundaryValue ) )
415 {
416 outPts.append( inPts[i2] );
417 }
418 else
419 {
420 // edge crosses into the boundary, so trim back to the boundary, and
421 // store both ends of the new edge
422 outPts.append( intersectRect( inPts[i1], inPts[i2], b, rect ) );
423 outPts.append( inPts[i2] );
424 }
425 }
426 else // end point of edge is outside boundary
427 {
428 // start point is in boundary, so need to trim back
429 if ( inside( inPts[i1], b, boundaryValue ) )
430 {
431 outPts.append( intersectRect( inPts[i1], inPts[i2], b, rect ) );
432 }
433 }
434 i1 = i2;
435 }
436}
437
438inline void QgsClipper::trimPolygonToBoundary( const QVector<double> &inX, const QVector<double> &inY, const QVector< double > &inZ,
439 QVector<double> &outX, QVector<double> &outY, QVector<double> &outZ, const QgsBox3D &rect, Boundary boundary, double boundaryValue )
440{
441 const double len = inX.length();
442 if ( len == 0 )
443 {
444 outX.clear();
445 outY.clear();
446 outZ.clear();
447 return;
448 }
449
450 double inI1X = inX.at( len - 1 ); // start with last point
451 double inI1Y = inY.at( len - 1 );
452 double inI1Z = inZ.at( len - 1 );
453
454 double xTemp;
455 double yTemp;
456 double zTemp;
457
458 // and compare to the first point initially.
459 for ( int i2 = 0; i2 < len; ++i2 )
460 {
461 double inI2X = inX.at( i2 );
462 double inI2Y = inY.at( i2 );
463 double inI2Z = inZ.at( i2 );
464
465 // look at each edge of the polygon in turn
466 if ( inside( inI2X, inI2Y, inI2Z, boundary, boundaryValue ) ) // end point of edge is inside boundary
467 {
468 if ( inside( inI1X, inI1Y, inI1Z, boundary, boundaryValue ) )
469 {
470 outX << inI2X;
471 outY << inI2Y;
472 outZ << inI2Z;
473 }
474 else
475 {
476 // edge crosses into the boundary, so trim back to the boundary, and
477 // store both ends of the new edge
478 intersectRect( inI1X, inI1Y, inI1Z, inI2X, inI2Y, inI2Z, xTemp, yTemp, zTemp, boundary, rect ) ;
479 outX << xTemp;
480 outY << yTemp;
481 outZ << zTemp;
482 outX << inI2X;
483 outY << inI2Y;
484 outZ << inI2Z;
485 }
486 }
487 else // end point of edge is outside boundary
488 {
489 // start point is in boundary, so need to trim back
490 if ( inside( inI1X, inI1Y, inI1Z, boundary, boundaryValue ) )
491 {
492 intersectRect( inI1X, inI1Y, inI1Z, inI2X, inI2Y, inI2Z, xTemp, yTemp, zTemp, boundary, rect );
493 outX << xTemp;
494 outY << yTemp;
495 outZ << zTemp;
496 }
497 }
498 inI1X = inI2X;
499 inI1Y = inI2Y;
500 inI1Z = inI2Z;
501 }
502}
503
504// An auxiliary function to trimPolygonToBoundarY() that returns
505// whether a point is inside or outside the given boundary.
506
507inline bool QgsClipper::inside( const double x, const double y, Boundary b )
508{
509 switch ( b )
510 {
511 case XMax: // x < MAX_X is inside
512 if ( x < MAX_X )
513 return true;
514 break;
515 case XMin: // x > MIN_X is inside
516 if ( x > MIN_X )
517 return true;
518 break;
519 case YMax: // y < MAX_Y is inside
520 if ( y < MAX_Y )
521 return true;
522 break;
523 case YMin: // y > MIN_Y is inside
524 if ( y > MIN_Y )
525 return true;
526 break;
527 case ZMax: // z < MAX_Z is inside
528 case ZMin: // z > MIN_Z is inside
529 return false;
530 }
531 return false;
532}
533
534inline bool QgsClipper::inside( QPointF pt, Boundary b, double val )
535{
536 switch ( b )
537 {
538 case XMax: // x < MAX_X is inside
539 return ( pt.x() < val );
540 case XMin: // x > MIN_X is inside
541 return ( pt.x() > val );
542 case YMax: // y < MAX_Y is inside
543 return ( pt.y() < val );
544 case YMin: // y > MIN_Y is inside
545 return ( pt.y() > val );
546 case ZMax: // z < MAX_Z is inside
547 case ZMin: // z > MIN_Z is inside
548 return false;
549 }
550 return false;
551}
552
553inline bool QgsClipper::inside( double x, double y, double z, Boundary boundary, double boundaryValue )
554{
555 switch ( boundary )
556 {
557 case XMax: // x < MAX_X is inside
558 return ( x < boundaryValue );
559 case XMin: // x > MIN_X is inside
560 return ( x > boundaryValue );
561 case YMax: // y < MAX_Y is inside
562 return ( y < boundaryValue );
563 case YMin: // y > MIN_Y is inside
564 return ( y > boundaryValue );
565 case ZMax: // z < MAX_Z is inside
566 return z < boundaryValue || std::isnan( z ) ;
567 case ZMin: // z > MIN_Z is inside
568 return z > boundaryValue || std::isnan( z );
569 }
570 return false;
571}
572
573
574// An auxiliary function to trimPolygonToBoundarY() that calculates and
575// returns the intersection of the line defined by the given points
576// and the given boundary.
577
578inline QgsPointXY QgsClipper::intersect( const double x1, const double y1,
579 const double x2, const double y2,
580 Boundary b )
581{
582 // This function assumes that the two given points (x1, y1), and
583 // (x2, y2) cross the given boundary. Making this assumption allows
584 // some optimisations.
585
586 double r_n = SMALL_NUM, r_d = SMALL_NUM;
587
588 switch ( b )
589 {
590 case XMax: // x = MAX_X boundary
591 r_n = -( x1 - MAX_X ) * ( MAX_Y - MIN_Y );
592 r_d = ( x2 - x1 ) * ( MAX_Y - MIN_Y );
593 break;
594 case XMin: // x = MIN_X boundary
595 r_n = -( x1 - MIN_X ) * ( MAX_Y - MIN_Y );
596 r_d = ( x2 - x1 ) * ( MAX_Y - MIN_Y );
597 break;
598 case YMax: // y = MAX_Y boundary
599 r_n = ( y1 - MAX_Y ) * ( MAX_X - MIN_X );
600 r_d = -( y2 - y1 ) * ( MAX_X - MIN_X );
601 break;
602 case YMin: // y = MIN_Y boundary
603 r_n = ( y1 - MIN_Y ) * ( MAX_X - MIN_X );
604 r_d = -( y2 - y1 ) * ( MAX_X - MIN_X );
605 break;
606 case ZMax: // z < MAX_Z is inside
607 case ZMin: // z > MIN_Z is inside
608 break;
609 }
610
611 QgsPointXY p;
612
613 if ( std::fabs( r_d ) > SMALL_NUM && std::fabs( r_n ) > SMALL_NUM )
614 {
615 // they cross
616 const double r = r_n / r_d;
617 p.set( x1 + r * ( x2 - x1 ), y1 + r * ( y2 - y1 ) );
618 }
619 else
620 {
621 // Should never get here, but if we do for some reason, cause a
622 // clunk because something else is wrong if we do.
623 Q_ASSERT( std::fabs( r_d ) > SMALL_NUM && std::fabs( r_n ) > SMALL_NUM );
624 }
625
626 return p;
627}
628
629inline QPointF QgsClipper::intersectRect( QPointF pt1,
630 QPointF pt2,
631 Boundary b, const QgsRectangle &rect )
632{
633 // This function assumes that the two given points (x1, y1), and
634 // (x2, y2) cross the given boundary. Making this assumption allows
635 // some optimisations.
636
637 double r_n = SMALL_NUM, r_d = SMALL_NUM;
638 const double x1 = pt1.x(), x2 = pt2.x();
639 const double y1 = pt1.y(), y2 = pt2.y();
640
641 switch ( b )
642 {
643 case XMax: // x = MAX_X boundary
644 r_n = -( x1 - rect.xMaximum() ) * ( rect.yMaximum() - rect.yMinimum() );
645 r_d = ( x2 - x1 ) * ( rect.yMaximum() - rect.yMinimum() );
646 break;
647 case XMin: // x = MIN_X boundary
648 r_n = -( x1 - rect.xMinimum() ) * ( rect.yMaximum() - rect.yMinimum() );
649 r_d = ( x2 - x1 ) * ( rect.yMaximum() - rect.yMinimum() );
650 break;
651 case YMax: // y = MAX_Y boundary
652 r_n = ( y1 - rect.yMaximum() ) * ( rect.xMaximum() - rect.xMinimum() );
653 r_d = -( y2 - y1 ) * ( rect.xMaximum() - rect.xMinimum() );
654 break;
655 case YMin: // y = MIN_Y boundary
656 r_n = ( y1 - rect.yMinimum() ) * ( rect.xMaximum() - rect.xMinimum() );
657 r_d = -( y2 - y1 ) * ( rect.xMaximum() - rect.xMinimum() );
658 break;
659 case ZMax: // z < MAX_Z is inside
660 case ZMin: // z > MIN_Z is inside
661 break;
662 }
663
664 double r = 0;
665 if ( !qgsDoubleNear( r_d, 0.0 ) )
666 {
667 r = r_n / r_d;
668 }
669 return QPointF( x1 + r * ( x2 - x1 ), y1 + r * ( y2 - y1 ) );
670}
671
672inline void QgsClipper::intersectRect( const double x1, const double y1, const double z1,
673 const double x2, const double y2, const double z2,
674 double &xOut, double &yOut, double &zOut,
675 Boundary boundary, const QgsBox3D &rect )
676{
677 // This function assumes that the two given points (x1, y1, z1), and
678 // (x2, y2, z2) cross the given boundary. Making this assumption allows
679 // some optimisations.
680
681 double r_n = SMALL_NUM, r_d = SMALL_NUM;
682
683 switch ( boundary )
684 {
685 case XMax: // x = MAX_X boundary
686 r_n = -( x1 - rect.xMaximum() ) * ( rect.yMaximum() - rect.yMinimum() );
687 r_d = ( x2 - x1 ) * ( rect.yMaximum() - rect.yMinimum() );
688 break;
689 case XMin: // x = MIN_X boundary
690 r_n = -( x1 - rect.xMinimum() ) * ( rect.yMaximum() - rect.yMinimum() );
691 r_d = ( x2 - x1 ) * ( rect.yMaximum() - rect.yMinimum() );
692 break;
693 case YMax: // y = MAX_Y boundary
694 r_n = ( y1 - rect.yMaximum() ) * ( rect.xMaximum() - rect.xMinimum() );
695 r_d = -( y2 - y1 ) * ( rect.xMaximum() - rect.xMinimum() );
696 break;
697 case YMin: // y = MIN_Y boundary
698 r_n = ( y1 - rect.yMinimum() ) * ( rect.xMaximum() - rect.xMinimum() );
699 r_d = -( y2 - y1 ) * ( rect.xMaximum() - rect.xMinimum() );
700 break;
701 case ZMax: // z = MAX_Z boundary
702 r_n = ( z1 - rect.zMaximum() );
703 r_d = -( z2 - z1 );
704 break;
705 case ZMin: // z = MIN_Z boundary
706 r_n = ( z1 - rect.zMinimum() );
707 r_d = -( z2 - z1 );
708 break;
709 }
710
711 double r = 0;
712 if ( !qgsDoubleNear( r_d, 0.0 ) )
713 {
714 r = r_n / r_d;
715 }
716 xOut = x1 + r * ( x2 - x1 );
717 yOut = y1 + r * ( y2 - y1 );
718 zOut = z1 + r * ( z2 - z1 );
719}
720
721inline void QgsClipper::clipStartTop( double &x0, double &y0, double x1, double y1, double yMax )
722{
723 x0 += ( x1 - x0 ) * ( yMax - y0 ) / ( y1 - y0 );
724 y0 = yMax;
725}
726
727inline void QgsClipper::clipStartBottom( double &x0, double &y0, double x1, double y1, double yMin )
728{
729 x0 += ( x1 - x0 ) * ( yMin - y0 ) / ( y1 - y0 );
730 y0 = yMin;
731}
732
733inline void QgsClipper::clipStartRight( double &x0, double &y0, double x1, double y1, double xMax )
734{
735 y0 += ( y1 - y0 ) * ( xMax - x0 ) / ( x1 - x0 );
736 x0 = xMax;
737}
738
739inline void QgsClipper::clipStartLeft( double &x0, double &y0, double &x1, double &y1, double xMin )
740{
741 y0 += ( y1 - y0 ) * ( xMin - x0 ) / ( x1 - x0 );
742 x0 = xMin;
743}
744
745inline void QgsClipper::clipEndTop( double x0, double y0, double &x1, double &y1, double yMax )
746{
747 x1 += ( x1 - x0 ) * ( yMax - y1 ) / ( y1 - y0 );
748 y1 = yMax;
749}
750
751inline void QgsClipper::clipEndBottom( double x0, double y0, double &x1, double &y1, double yMin )
752{
753 x1 += ( x1 - x0 ) * ( yMin - y1 ) / ( y1 - y0 );
754 y1 = yMin;
755}
756
757inline void QgsClipper::clipEndRight( double x0, double y0, double &x1, double &y1, double xMax )
758{
759 y1 += ( y1 - y0 ) * ( xMax - x1 ) / ( x1 - x0 );
760 x1 = xMax;
761}
762
763inline void QgsClipper::clipEndLeft( double x0, double y0, double &x1, double &y1, double xMin )
764{
765 y1 += ( y1 - y0 ) * ( xMin - x1 ) / ( x1 - x0 );
766 x1 = xMin;
767}
768
769inline bool QgsClipper::clipLineSegment( const QgsBox3D &clipExtent, double &x0, double &y0, double &, double &x1, double &y1, double & )
770{
771 // TODO: while waiting for a valid 3d solution, using the 2d one:
772 return clipLineSegment( clipExtent.xMinimum(), clipExtent.xMaximum(), clipExtent.yMinimum(), clipExtent.yMaximum(),
773 x0, y0, x1, y1 );
774}
775
776//'Fast clipping' algorithm (Sobkow et al. 1987, Computers & Graphics Vol.11, 4, p.459-467)
777inline bool QgsClipper::clipLineSegment( double xLeft, double xRight, double yBottom, double yTop, double &x0, double &y0, double &x1, double &y1 )
778{
779 int lineCode = 0;
780
781 if ( y1 < yBottom )
782 lineCode |= 4;
783 else if ( y1 > yTop )
784 lineCode |= 8;
785
786 if ( x1 > xRight )
787 lineCode |= 2;
788 else if ( x1 < xLeft )
789 lineCode |= 1;
790
791 if ( y0 < yBottom )
792 lineCode |= 64;
793 else if ( y0 > yTop )
794 lineCode |= 128;
795
796 if ( x0 > xRight )
797 lineCode |= 32;
798 else if ( x0 < xLeft )
799 lineCode |= 16;
800
801 switch ( lineCode )
802 {
803 case 0: //completely inside
804 return true;
805
806 case 1:
807 clipEndLeft( x0, y0, x1, y1, xLeft );
808 return true;
809
810 case 2:
811 clipEndRight( x0, y0, x1, y1, xRight );
812 return true;
813
814 case 4:
815 clipEndBottom( x0, y0, x1, y1, yBottom );
816 return true;
817
818 case 5:
819 clipEndLeft( x0, y0, x1, y1, xLeft );
820 if ( y1 < yBottom )
821 clipEndBottom( x0, y0, x1, y1, yBottom );
822 return true;
823
824 case 6:
825 clipEndRight( x0, y0, x1, y1, xRight );
826 if ( y1 < yBottom )
827 clipEndBottom( x0, y0, x1, y1, yBottom );
828 return true;
829
830 case 8:
831 clipEndTop( x0, y0, x1, y1, yTop );
832 return true;
833
834 case 9:
835 clipEndLeft( x0, y0, x1, y1, xLeft );
836 if ( y1 > yTop )
837 clipEndTop( x0, y0, x1, y1, yTop );
838 return true;
839
840 case 10:
841 clipEndRight( x0, y0, x1, y1, xRight );
842 if ( y1 > yTop )
843 clipEndTop( x0, y0, x1, y1, yTop );
844 return true;
845
846 case 16:
847 clipStartLeft( x0, y0, x1, y1, xLeft );
848 return true;
849
850 case 18:
851 clipStartLeft( x0, y0, x1, y1, xLeft );
852 clipEndRight( x0, y0, x1, y1, xRight );
853 return true;
854
855 case 20:
856 clipStartLeft( x0, y0, x1, y1, xLeft );
857 if ( y0 < yBottom )
858 return false;
859 clipEndBottom( x0, y0, x1, y1, yBottom );
860 return true;
861
862 case 22:
863 clipStartLeft( x0, y0, x1, y1, xLeft );
864 if ( y0 < yBottom )
865 return false;
866 clipEndBottom( x0, y0, x1, y1, yBottom );
867 if ( x1 > xRight )
868 clipEndRight( x0, y0, x1, y1, xRight );
869 return true;
870
871 case 24:
872 clipStartLeft( x0, y0, x1, y1, xLeft );
873 if ( y0 > yTop )
874 return false;
875 clipEndTop( x0, y0, x1, y1, yTop );
876 return true;
877
878 case 26:
879 clipStartLeft( x0, y0, x1, y1, xLeft );
880 if ( y0 > yTop )
881 return false;
882 clipEndTop( x0, y0, x1, y1, yTop );
883 if ( x1 > xRight )
884 clipEndRight( x0, y0, x1, y1, xRight );
885 return true;
886
887 case 32:
888 clipStartRight( x0, y0, x1, y1, xRight );
889 return true;
890
891 case 33:
892 clipStartRight( x0, y0, x1, y1, xRight );
893 clipEndLeft( x0, y0, x1, y1, xLeft );
894 return true;
895
896 case 36:
897 clipStartRight( x0, y0, x1, y1, xRight );
898 if ( y0 < yBottom )
899 return false;
900 clipEndBottom( x0, y0, x1, y1, yBottom );
901 return true;
902
903 case 37:
904 clipStartRight( x0, y0, x1, y1, xRight );
905 if ( y0 < yBottom )
906 return false;
907 clipEndBottom( x0, y0, x1, y1, yBottom );
908 if ( x1 < xLeft )
909 clipEndLeft( x0, y0, x1, y1, xLeft );
910 return true;
911
912 case 40:
913 clipStartRight( x0, y0, x1, y1, xRight );
914 if ( y0 > yTop )
915 return false;
916 clipEndTop( x0, y0, x1, y1, yTop );
917 return true;
918
919 case 41:
920 clipStartRight( x0, y0, x1, y1, xRight );
921 if ( y0 > yTop )
922 return false;
923 clipEndTop( x0, y0, x1, y1, yTop );
924 if ( x1 < xLeft )
925 clipEndLeft( x0, y0, x1, y1, xLeft );
926 return true;
927
928 case 64:
929 clipStartBottom( x0, y0, x1, y1, yBottom );
930 return true;
931
932 case 65:
933 clipStartBottom( x0, y0, x1, y1, yBottom );
934 if ( x0 < xLeft )
935 return false;
936 clipEndLeft( x0, y0, x1, y1, xLeft );
937 if ( y1 < yBottom )
938 clipEndBottom( x0, y0, x1, y1, yBottom );
939 return true;
940
941 case 66:
942 clipStartBottom( x0, y0, x1, y1, yBottom );
943 if ( x0 > xRight )
944 return false;
945 clipEndRight( x0, y0, x1, y1, xRight );
946 return true;
947
948 case 72:
949 clipStartBottom( x0, y0, x1, y1, yBottom );
950 clipEndTop( x0, y0, x1, y1, yTop );
951 return true;
952
953 case 73:
954 clipStartBottom( x0, y0, x1, y1, yBottom );
955 if ( x0 < xLeft )
956 return false;
957 clipEndLeft( x0, y0, x1, y1, xLeft );
958 if ( y1 > yTop )
959 clipEndTop( x0, y0, x1, y1, yTop );
960 return true;
961
962 case 74:
963 clipStartBottom( x0, y0, x1, y1, yBottom );
964 if ( x0 > xRight )
965 return false;
966 clipEndRight( x0, y0, x1, y1, xRight );
967 if ( y1 > yTop )
968 clipEndTop( x0, y0, x1, y1, yTop );
969 return true;
970
971 case 80:
972 clipStartLeft( x0, y0, x1, y1, xLeft );
973 if ( y0 < yBottom )
974 clipStartBottom( x0, y0, x1, y1, yBottom );
975 return true;
976
977 case 82:
978 clipEndRight( x0, y0, x1, y1, xRight );
979 if ( y1 < yBottom )
980 return false;
981 clipStartBottom( x0, y0, x1, y1, yBottom );
982 if ( x0 < xLeft )
983 clipStartLeft( x0, y0, x1, y1, xLeft );
984 return true;
985
986 case 88:
987 clipEndTop( x0, y0, x1, y1, yTop );
988 if ( x1 < xLeft )
989 return false;
990 clipStartBottom( x0, y0, x1, y1, yBottom );
991 if ( x0 < xLeft )
992 clipStartLeft( x0, y0, x1, y1, xLeft );
993 return true;
994
995 case 90:
996 clipStartLeft( x0, y0, x1, y1, xLeft );
997 if ( y0 > yTop )
998 return false;
999 clipEndRight( x0, y0, x1, y1, xRight );
1000 if ( y1 < yBottom )
1001 return false;
1002 if ( y0 < yBottom )
1003 clipStartBottom( x0, y0, x1, y1, yBottom );
1004 if ( y1 > yTop )
1005 clipEndTop( x0, y0, x1, y1, yTop );
1006 return true;
1007
1008 case 96:
1009 clipStartRight( x0, y0, x1, y1, xRight );
1010 if ( y0 < yBottom )
1011 clipStartBottom( x0, y0, x1, y1, yBottom );
1012 return true;
1013
1014 case 97:
1015 clipEndLeft( x0, y0, x1, y1, xLeft );
1016 if ( y1 < yBottom )
1017 return false;
1018 clipStartBottom( x0, y0, x1, y1, yBottom );
1019 if ( x0 > xRight )
1020 clipStartRight( x0, y0, x1, y1, xRight );
1021 return true;
1022
1023 case 104:
1024 clipEndTop( x0, y0, x1, y1, yTop );
1025 if ( x1 > xRight )
1026 return false;
1027 clipStartRight( x0, y0, x1, y1, xRight );
1028 if ( y0 < yBottom )
1029 clipStartBottom( x0, y0, x1, y1, yBottom );
1030 return true;
1031
1032 case 105:
1033 clipEndLeft( x0, y0, x1, y1, xLeft );
1034 if ( y1 < yBottom )
1035 return false;
1036 clipStartRight( x0, y0, x1, y1, xRight );
1037 if ( y0 > yTop )
1038 return false;
1039 if ( y1 > yTop )
1040 clipEndTop( x0, y0, x1, y1, yTop );
1041 if ( y0 < yBottom )
1042 clipStartBottom( x0, y0, x1, y1, yBottom );
1043 return true;
1044
1045 case 128:
1046 clipStartTop( x0, y0, x1, y1, yTop );
1047 return true;
1048
1049 case 129:
1050 clipStartTop( x0, y0, x1, y1, yTop );
1051 if ( x0 < xLeft )
1052 return false;
1053 clipEndLeft( x0, y0, x1, y1, xLeft );
1054 return true;
1055
1056 case 130:
1057 clipStartTop( x0, y0, x1, y1, yTop );
1058 if ( x0 > xRight )
1059 return false;
1060 clipEndRight( x0, y0, x1, y1, xRight );
1061 return true;
1062
1063 case 132:
1064 clipStartTop( x0, y0, x1, y1, yTop );
1065 clipEndBottom( x0, y0, x1, y1, yBottom );
1066 return true;
1067
1068 case 133:
1069 clipStartTop( x0, y0, x1, y1, yTop );
1070 if ( x0 < xLeft )
1071 return false;
1072 clipEndLeft( x0, y0, x1, y1, xLeft );
1073 if ( y1 < yBottom )
1074 clipEndBottom( x0, y0, x1, y1, yBottom );
1075 return true;
1076
1077 case 134:
1078 clipStartTop( x0, y0, x1, y1, yTop );
1079 if ( x0 > xRight )
1080 return false;
1081 clipEndRight( x0, y0, x1, y1, xRight );
1082 if ( y1 < yBottom )
1083 clipEndBottom( x0, y0, x1, y1, yBottom );
1084 return true;
1085
1086 case 144:
1087 clipStartLeft( x0, y0, x1, y1, xLeft );
1088 if ( y0 > yTop )
1089 clipStartTop( x0, y0, x1, y1, yTop );
1090 return true;
1091
1092 case 146:
1093 clipEndRight( x0, y0, x1, y1, xRight );
1094 if ( y1 > yTop )
1095 return false;
1096 clipStartTop( x0, y0, x1, y1, yTop );
1097 if ( x0 < xLeft )
1098 clipStartLeft( x0, y0, x1, y1, xLeft );
1099 return true;
1100
1101 case 148:
1102 clipEndBottom( x0, y0, x1, y1, yBottom );
1103 if ( x1 < xLeft )
1104 return false;
1105 clipStartLeft( x0, y0, x1, y1, xLeft );
1106 if ( y0 > yTop )
1107 clipStartTop( x0, y0, x1, y1, yTop );
1108 return true;
1109
1110 case 150:
1111 clipStartLeft( x0, y0, x1, y1, xLeft );
1112 if ( y0 < yBottom )
1113 return false;
1114 clipEndRight( x0, y0, x1, y1, xRight );
1115 if ( y1 > yTop )
1116 return false;
1117 if ( y0 > yTop )
1118 clipStartTop( x0, y0, x1, y1, yTop );
1119 if ( y1 < yBottom )
1120 clipEndBottom( x0, y0, x1, y1, yBottom );
1121 return true;
1122
1123 case 160:
1124 clipStartRight( x0, y0, x1, y1, xRight );
1125 if ( y0 > yTop )
1126 clipStartTop( x0, y0, x1, y1, yTop );
1127 return true;
1128
1129 case 161:
1130 clipEndLeft( x0, y0, x1, y1, xLeft );
1131 if ( y1 > yTop )
1132 return false;
1133 clipStartTop( x0, y0, x1, y1, yTop );
1134 if ( x0 > xRight )
1135 clipStartRight( x0, y0, x1, y1, xRight );
1136 return true;
1137
1138 case 164:
1139 clipEndBottom( x0, y0, x1, y1, yBottom );
1140 if ( x1 > xRight )
1141 return false;
1142 clipStartRight( x0, y0, x1, y1, xRight );
1143 if ( y0 > yTop )
1144 clipStartTop( x0, y0, x1, y1, yTop );
1145 return true;
1146
1147 case 165:
1148 clipEndLeft( x0, y0, x1, y1, xLeft );
1149 if ( y1 > yTop )
1150 return false;
1151 clipStartRight( x0, y0, x1, y1, xRight );
1152 if ( y0 < yBottom )
1153 return false;
1154 if ( y1 < yBottom )
1155 clipEndBottom( x0, y0, x1, y1, yBottom );
1156 if ( y0 > yTop )
1157 clipStartTop( x0, y0, x1, y1, yTop );
1158 return true;
1159 }
1160
1161 return false;
1162
1163}
1164#endif // SIP_RUN
1165
1166
1167#endif
QgsBox3D
A 3-dimensional box composed of x, y, z coordinates.
Definition qgsbox3d.h:43
QgsBox3D::yMaximum
double yMaximum() const
Returns the maximum y value.
Definition qgsbox3d.h:231
QgsBox3D::xMinimum
double xMinimum() const
Returns the minimum x value.
Definition qgsbox3d.h:196
QgsBox3D::zMaximum
double zMaximum() const
Returns the maximum z value.
Definition qgsbox3d.h:259
QgsBox3D::xMaximum
double xMaximum() const
Returns the maximum x value.
Definition qgsbox3d.h:203
QgsBox3D::is2d
bool is2d() const
Returns true if the box can be considered a 2-dimensional box, i.e.
Definition qgsbox3d.cpp:134
QgsBox3D::zMinimum
double zMinimum() const
Returns the minimum z value.
Definition qgsbox3d.h:252
QgsBox3D::yMinimum
double yMinimum() const
Returns the minimum y value.
Definition qgsbox3d.h:224
QgsClipper
Trims lines and polygons to within a rectangular region.
Definition qgsclipper.h:52
QgsClipper::trimPolygon
static void trimPolygon(QPolygonF &pts, const QgsRectangle &clipRect)
Trims the given polygon to a rectangular box, by modifying the given polygon in place.
Definition qgsclipper.h:282
QgsClipper::clipLineSegment
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:777
QgsClipper::Boundary
Boundary
A handy way to refer to the four boundaries.
Definition qgsclipper.h:84
QgsClipper::ZMin
@ ZMin
Minimum Z.
Definition qgsclipper.h:90
QgsClipper::ZMax
@ ZMax
Maximum Z.
Definition qgsclipper.h:89
QgsClipper::MAX_X
static const double MAX_X
Maximum X-coordinate of the rectangular box used for clipping.
Definition qgsclipper.h:73
QgsClipper::MIN_Y
static const double MIN_Y
Minimum Y-coordinate of the rectangular box used for clipping.
Definition qgsclipper.h:79
QgsClipper::MAX_Y
static const double MAX_Y
Maximum Y-coordinate of the rectangular box used for clipping.
Definition qgsclipper.h:77
QgsClipper::MIN_X
static const double MIN_X
Minimum X-coordinate of the rectangular box used for clipping.
Definition qgsclipper.h:75
QgsClipper::trimFeature
static void trimFeature(QVector< double > &x, QVector< double > &y, bool shapeOpen)
Trims the given feature to a rectangular box.
Definition qgsclipper.h:261
QgsCurve
Abstract base class for curved geometry type.
Definition qgscurve.h:35
QgsCurve::boundary
QgsAbstractGeometry * boundary() const override
Returns the closure of the combinatorial boundary of the geometry (ie the topological boundary of the...
Definition qgscurve.cpp:149
QgsLineString
Line string geometry type, with support for z-dimension and m-values.
Definition qgslinestring.h:45
QgsPointXY
Represents a 2D point.
Definition qgspointxy.h:60
QgsPointXY::set
void set(double x, double y)
Sets the x and y value of the point.
Definition qgspointxy.h:136
QgsPointXY::y
double y
Definition qgspointxy.h:64
QgsPointXY::x
double x
Definition qgspointxy.h:63
QgsRectangle
A rectangle specified with double values.
Definition qgsrectangle.h:44
QgsRectangle::xMinimum
double xMinimum
Definition qgsrectangle.h:47
QgsRectangle::yMinimum
double yMinimum
Definition qgsrectangle.h:49
QgsRectangle::xMaximum
double xMaximum
Definition qgsrectangle.h:48
QgsRectangle::yMaximum
double yMaximum
Definition qgsrectangle.h:50
qgsDoubleNear
bool qgsDoubleNear(double a, double b, double epsilon=4 *std::numeric_limits< double >::epsilon())
Compare two doubles (but allow some difference)
Definition qgis.h:6286
qgis_sip.h
SIP_SKIP
#define SIP_SKIP
Definition qgis_sip.h:126
SIP_FEATURE
#define SIP_FEATURE(feature)
Definition qgis_sip.h:176
SIP_INOUT
#define SIP_INOUT
Definition qgis_sip.h:71
Generated on Tue Apr 8 2025 15:57:40 for QGIS API Documentation by doxygen 1.9.8