QGIS API Documentation  3.27.0-Master (11ef3e5184)
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 
33 class QgsCurve;
34 class QgsLineString;
35 
36 SIP_FEATURE( ARM ) // Some parts are not available in sip bindings on ARM because of qreal double vs. float issues
37 
38 
39 
50 class 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 
82  enum Boundary
83  {
88  ZMax,
89  ZMin,
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 
264 inline 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 
285 inline 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 
299 inline 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 
341 inline 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 
407 inline 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 
441 inline 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 
510 inline 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 
537 inline 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 
556 inline 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 );
570  case ZMin: // z > MIN_Z is inside
571  return ( z > boundaryValue );
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 
581 inline 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 
632 inline 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 
675 inline 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 
724 inline 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 
730 inline 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 
736 inline 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 
742 inline 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 
748 inline 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 
754 inline 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 
760 inline 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 
766 inline 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 
772 inline 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)
780 inline 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:39
double yMaximum() const SIP_HOLDGIL
Returns the maximum y value.
Definition: qgsbox3d.h:113
bool is2d() const SIP_HOLDGIL
Returns true if the box can be considered a 2-dimensional box, i.e.
Definition: qgsbox3d.cpp:87
double zMaximum() const SIP_HOLDGIL
Returns the maximum z value.
Definition: qgsbox3d.h:141
double zMinimum() const SIP_HOLDGIL
Returns the minimum z value.
Definition: qgsbox3d.h:134
double xMinimum() const SIP_HOLDGIL
Returns the minimum x value.
Definition: qgsbox3d.h:78
double xMaximum() const SIP_HOLDGIL
Returns the maximum x value.
Definition: qgsbox3d.h:85
double yMinimum() const SIP_HOLDGIL
Returns the minimum y value.
Definition: qgsbox3d.h:106
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:36
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:59
void set(double x, double y) SIP_HOLDGIL
Sets the x and y value of the point.
Definition: qgspointxy.h:139
double y
Definition: qgspointxy.h:63
Q_GADGET double x
Definition: qgspointxy.h:62
A rectangle specified with double values.
Definition: qgsrectangle.h:42
double yMaximum() const SIP_HOLDGIL
Returns the y maximum value (top side of rectangle).
Definition: qgsrectangle.h:193
double xMaximum() const SIP_HOLDGIL
Returns the x maximum value (right side of rectangle).
Definition: qgsrectangle.h:183
double xMinimum() const SIP_HOLDGIL
Returns the x minimum value (left side of rectangle).
Definition: qgsrectangle.h:188
double yMinimum() const SIP_HOLDGIL
Returns the y minimum value (bottom side of rectangle).
Definition: qgsrectangle.h:198
bool qgsDoubleNear(double a, double b, double epsilon=4 *std::numeric_limits< double >::epsilon())
Compare two doubles (but allow some difference)
Definition: qgis.h:2527
#define SIP_SKIP
Definition: qgis_sip.h:126
#define SIP_IF_FEATURE(feature)
Definition: qgis_sip.h:176
#define SIP_FEATURE(feature)
Definition: qgis_sip.h:171
#define SIP_INOUT
Definition: qgis_sip.h:71
#define SIP_END
Definition: qgis_sip.h:203