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