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