22
22
23
23
#include " qgis.h"
24
24
#include " qgspoint.h"
25
+ #include " qgsrectangle.h"
25
26
26
27
#include < vector>
27
28
#include < utility>
28
29
30
+ #include < QPolygonF>
31
+
29
32
/* * \ingroup core
30
33
* A class to trim lines and polygons to within a rectangular region.
31
34
* The functions in this class are likely to be called from within a
@@ -76,6 +79,12 @@ class CORE_EXPORT QgsClipper
76
79
std::vector<double >& y,
77
80
bool shapeOpen );
78
81
82
+ /* *Reads a polyline from WKB and clips it to clipExtent
83
+ @param wkb pointer to the start of the line wkb
84
+ @param clipExtent clipping bounds
85
+ @param line out: clipped line coordinates*/
86
+ static unsigned char * clippedLineWKB ( unsigned char * wkb, const QgsRectangle& clipExtent, QPolygonF& line );
87
+
79
88
private:
80
89
81
90
// Used when testing for equivalance to 0.0
@@ -98,6 +107,30 @@ class CORE_EXPORT QgsClipper
98
107
static QgsPoint intersect ( const double x1, const double y1,
99
108
const double x2, const double y2,
100
109
Boundary b );
110
+
111
+ // Implementation of 'Fast clipping' algorithm (Sobkow et al. 1987, Computers & Graphics Vol.11, 4, p.459-467)
112
+ static bool clipLineSegment ( double xLeft, double xRight, double yBottom, double yTop, double & x0, double & y0, double & x1, double & y1 );
113
+
114
+ /* *Connects two lines splitted by the clip (by inserting points on the clip border)
115
+ @param x0 x-coordinate of the first line end
116
+ @param y0 y-coordinate of the first line end
117
+ @param x1 x-coordinate of the second line start
118
+ @param y1 y-coordinate of the second line start
119
+ @param clipRect clip rectangle
120
+ @param pts: in/out array of clipped points
121
+ @param writePtr in/out: writing poisiton in the wkb array*/
122
+ static void connectSeparatedLines ( double x0, double y0, double x1, double y1,
123
+ const QgsRectangle& clipRect, QPolygonF& pts );
124
+
125
+ // low level clip methods for fast clip algorithm
126
+ static void clipStartTop ( double & x0, double & y0, const double & x1, const double & y1, double yMax );
127
+ static void clipStartBottom ( double & x0, double & y0, const double & x1, const double & y1, double yMin );
128
+ static void clipStartRight ( double & x0, double & y0, const double & x1, const double & y1, double xMax );
129
+ static void clipStartLeft ( double & x0, double & y0, const double & x1, const double & y1, double xMin );
130
+ static void clipEndTop ( const double & x0, const double & y0, double & x1, double & y1, double yMax );
131
+ static void clipEndBottom ( const double & x0, const double & y0, double & x1, double & y1, double yMin );
132
+ static void clipEndRight ( const double & x0, const double & y0, double & x1, double & y1, double xMax );
133
+ static void clipEndLeft ( const double & x0, const double & y0, double & x1, double & y1, double xMin );
101
134
};
102
135
103
136
// The inline functions
@@ -283,5 +316,442 @@ inline QgsPoint QgsClipper::intersect( const double x1, const double y1,
283
316
return p;
284
317
}
285
318
319
+ inline void QgsClipper::clipStartTop ( double & x0, double & y0, const double & x1, const double & y1, double yMax )
320
+ {
321
+ x0 += ( x1 - x0 ) * ( yMax - y0 ) / ( y1 - y0 );
322
+ y0 = yMax;
323
+ }
324
+
325
+ inline void QgsClipper::clipStartBottom ( double & x0, double & y0, const double & x1, const double & y1, double yMin )
326
+ {
327
+ x0 += ( x1 - x0 ) * ( yMin - y0 ) / ( y1 - y0 );
328
+ y0 = yMin;
329
+ }
330
+
331
+ inline void QgsClipper::clipStartRight ( double & x0, double & y0, const double & x1, const double & y1, double xMax )
332
+ {
333
+ y0 += ( y1 - y0 ) * ( xMax - x0 ) / ( x1 - x0 );
334
+ x0 = xMax;
335
+ }
336
+
337
+ inline void QgsClipper::clipStartLeft ( double & x0, double & y0, const double & x1, const double & y1, double xMin )
338
+ {
339
+ y0 += ( y1 - y0 ) * ( xMin - x0 ) / ( x1 - x0 );
340
+ x0 = xMin;
341
+ }
342
+
343
+ inline void QgsClipper::clipEndTop ( const double & x0, const double & y0, double & x1, double & y1, double yMax )
344
+ {
345
+ x1 += ( x1 - x0 ) * ( yMax - y1 ) / ( y1 - y0 );
346
+ y1 = yMax;
347
+ }
348
+
349
+ inline void QgsClipper::clipEndBottom ( const double & x0, const double & y0, double & x1, double & y1, double yMin )
350
+ {
351
+ x1 += ( x1 - x0 ) * ( yMin - y1 ) / ( y1 - y0 );
352
+ y1 = yMin;
353
+ }
354
+
355
+ inline void QgsClipper::clipEndRight ( const double & x0, const double & y0, double & x1, double & y1, double xMax )
356
+ {
357
+ y1 += ( y1 - y0 ) * ( xMax - x1 ) / ( x1 - x0 );
358
+ x1 = xMax;
359
+ }
360
+
361
+ inline void QgsClipper::clipEndLeft ( const double & x0, const double & y0, double & x1, double & y1, double xMin )
362
+ {
363
+ y1 += ( y1 - y0 ) * ( xMin - x1 ) / ( x1 - x0 );
364
+ x1 = xMin;
365
+ }
366
+
367
+ // 'Fast clipping' algorithm (Sobkow et al. 1987, Computers & Graphics Vol.11, 4, p.459-467)
368
+ inline bool QgsClipper::clipLineSegment ( double xLeft, double xRight, double yBottom, double yTop, double & x0, double & y0, double & x1, double & y1 )
369
+ {
370
+ int lineCode = 0 ;
371
+
372
+ if ( y1 < yBottom )
373
+ lineCode |= 4 ;
374
+ else if ( y1 > yTop )
375
+ lineCode |= 8 ;
376
+
377
+ if ( x1 > xRight )
378
+ lineCode |= 2 ;
379
+ else if ( x1 < xLeft )
380
+ lineCode |= 1 ;
381
+
382
+ if ( y0 < yBottom )
383
+ lineCode |= 64 ;
384
+ else if ( y0 > yTop )
385
+ lineCode |= 128 ;
386
+
387
+ if ( x0 > xRight )
388
+ lineCode |= 32 ;
389
+ else if ( x0 < xLeft )
390
+ lineCode |= 16 ;
391
+
392
+ switch ( lineCode )
393
+ {
394
+ case 0 : // completely inside
395
+ return true ;
396
+
397
+ case 1 :
398
+ clipEndLeft ( x0, y0, x1, y1, xLeft );
399
+ return true ;
400
+
401
+ case 2 :
402
+ clipEndRight ( x0, y0, x1, y1, xRight );
403
+ return true ;
404
+
405
+ case 4 :
406
+ clipEndBottom ( x0, y0, x1, y1, yBottom );
407
+ return true ;
408
+
409
+ case 5 :
410
+ clipEndLeft ( x0, y0, x1, y1, xLeft );
411
+ if ( y1 < yBottom )
412
+ clipEndBottom ( x0, y0, x1, y1, yBottom );
413
+ return true ;
414
+
415
+ case 6 :
416
+ clipEndRight ( x0, y0, x1, y1, xRight );
417
+ if ( y1 < yBottom )
418
+ clipEndBottom ( x0, y0, x1, y1, yBottom );
419
+ return true ;
420
+
421
+ case 8 :
422
+ clipEndTop ( x0, y0, x1, y1, yTop );
423
+ return true ;
424
+
425
+ case 9 :
426
+ clipEndLeft ( x0, y0, x1, y1, xLeft );
427
+ if ( y1 > yTop )
428
+ clipEndTop ( x0, y0, x1, y1, yTop );
429
+ return true ;
430
+
431
+ case 10 :
432
+ clipEndRight ( x0, y0, x1, y1, xRight );
433
+ if ( y1 > yTop )
434
+ clipEndTop ( x0, y0, x1, y1, yTop );
435
+ return true ;
436
+
437
+ case 16 :
438
+ clipStartLeft ( x0, y0, x1, y1, xLeft );
439
+ return true ;
440
+
441
+ case 18 :
442
+ clipStartLeft ( x0, y0, x1, y1, xLeft );
443
+ clipEndRight ( x0, y0, x1, y1, xRight );
444
+ return true ;
445
+
446
+ case 20 :
447
+ clipStartLeft ( x0, y0, x1, y1, xLeft );
448
+ if ( y0 < yBottom )
449
+ return false ;
450
+ clipEndBottom ( x0, y0, x1, y1, yBottom );
451
+ return true ;
452
+
453
+ case 22 :
454
+ clipStartLeft ( x0, y0, x1, y1, xLeft );
455
+ if ( y0 < yBottom )
456
+ return false ;
457
+ clipEndBottom ( x0, y0, x1, y1, yBottom );
458
+ if ( x1 > xRight )
459
+ clipEndRight ( x0, y0, x1, y1, xRight );
460
+ return true ;
461
+
462
+ case 24 :
463
+ clipStartLeft ( x0, y0, x1, y1, xLeft );
464
+ if ( y0 > yTop )
465
+ return false ;
466
+ clipEndTop ( x0, y0, x1, y1, yTop );
467
+ return true ;
468
+
469
+ case 26 :
470
+ clipStartLeft ( x0, y0, x1, y1, xLeft );
471
+ if ( y0 > yTop )
472
+ return false ;
473
+ clipEndTop ( x0, y0, x1, y1, yTop );
474
+ if ( x1 > xRight )
475
+ clipEndRight ( x0, y0, x1, y1, xRight );
476
+ return true ;
477
+
478
+ case 32 :
479
+ clipStartRight ( x0, y0, x1, y1, xRight );
480
+ return true ;
481
+
482
+ case 33 :
483
+ clipStartRight ( x0, y0, x1, y1, xRight );
484
+ clipEndLeft ( x0, y0, x1, y1, xLeft );
485
+ return true ;
486
+
487
+ case 36 :
488
+ clipStartRight ( x0, y0, x1, y1, xRight );
489
+ if ( y0 < yBottom )
490
+ return false ;
491
+ clipEndBottom ( x0, y0, x1, y1, yBottom );
492
+ return true ;
493
+
494
+ case 37 :
495
+ clipStartRight ( x0, y0, x1, y1, xRight );
496
+ if ( y0 < yBottom )
497
+ return false ;
498
+ clipEndBottom ( x0, y0, x1, y1, yBottom );
499
+ if ( x1 < xLeft )
500
+ clipEndLeft ( x0, y0, x1, y1, xLeft );
501
+ return true ;
502
+
503
+ case 40 :
504
+ clipStartRight ( x0, y0, x1, y1, xRight );
505
+ if ( y0 > yTop )
506
+ return false ;
507
+ clipEndTop ( x0, y0, x1, y1, yTop );
508
+ return true ;
509
+
510
+ case 41 :
511
+ clipStartRight ( x0, y0, x1, y1, xRight );
512
+ if ( y0 > yTop )
513
+ return false ;
514
+ clipEndTop ( x0, y0, x1, y1, yTop );
515
+ if ( x1 < xLeft )
516
+ clipEndLeft ( x0, y0, x1, y1, xLeft );
517
+ return true ;
518
+
519
+ case 64 :
520
+ clipStartBottom ( x0, y0, x1, y1, yBottom );
521
+ return true ;
522
+
523
+ case 65 :
524
+ clipStartBottom ( x0, y0, x1, y1, yBottom );
525
+ if ( x0 < xLeft )
526
+ return false ;
527
+ clipEndLeft ( x0, y0, x1, y1, xLeft );
528
+ if ( y1 < yBottom )
529
+ clipEndBottom ( x0, y0, x1, y1, yBottom );
530
+ return true ;
531
+
532
+ case 66 :
533
+ clipStartBottom ( x0, y0, x1, y1, yBottom );
534
+ if ( x0 > xRight )
535
+ return false ;
536
+ clipEndRight ( x0, y0, x1, y1, xRight );
537
+ return true ;
538
+
539
+ case 72 :
540
+ clipStartBottom ( x0, y0, x1, y1, yBottom );
541
+ clipEndTop ( x0, y0, x1, y1, yTop );
542
+ return true ;
543
+
544
+ case 73 :
545
+ clipStartBottom ( x0, y0, x1, y1, yBottom );
546
+ if ( x0 < xLeft )
547
+ return false ;
548
+ clipEndLeft ( x0, y0, x1, y1, xLeft );
549
+ if ( y1 > yTop )
550
+ clipEndTop ( x0, y0, x1, y1, yTop );
551
+ return true ;
552
+
553
+ case 74 :
554
+ clipStartBottom ( x0, y0, x1, y1, yBottom );
555
+ if ( x0 > xRight )
556
+ return false ;
557
+ clipEndRight ( x0, y0, x1, y1, xRight );
558
+ if ( y1 > yTop )
559
+ clipEndTop ( x0, y0, x1, y1, yTop );
560
+ return true ;
561
+
562
+ case 80 :
563
+ clipStartLeft ( x0, y0, x1, y1, xLeft );
564
+ if ( y0 < yBottom )
565
+ clipStartBottom ( x0, y0, x1, y1, yBottom );
566
+ return true ;
567
+
568
+ case 82 :
569
+ clipEndRight ( x0, y0, x1, y1, xRight );
570
+ if ( y1 < yBottom )
571
+ return false ;
572
+ clipStartBottom ( x0, y0, x1, y1, yBottom );
573
+ if ( x0 < xLeft )
574
+ clipStartLeft ( x0, y0, x1, y1, xLeft );
575
+ return true ;
576
+
577
+ case 88 :
578
+ clipEndTop ( x0, y0, x1, y1, yTop );
579
+ if ( x1 < xLeft )
580
+ return false ;
581
+ clipStartBottom ( x0, y0, x1, y1, yBottom );
582
+ if ( x0 < xLeft )
583
+ clipStartLeft ( x0, y0, x1, y1, xLeft );
584
+ return true ;
585
+
586
+ case 90 :
587
+ clipStartLeft ( x0, y0, x1, y1, xLeft );
588
+ if ( y0 > yTop )
589
+ return false ;
590
+ clipEndRight ( x0, y0, x1, y1, xRight );
591
+ if ( y1 < yBottom )
592
+ return false ;
593
+ if ( y0 < yBottom )
594
+ clipStartBottom ( x0, y0, x1, y1, yBottom );
595
+ if ( y1 > yTop )
596
+ clipEndTop ( x0, y0, x1, y1, yTop );
597
+ return true ;
598
+
599
+ case 96 :
600
+ clipStartRight ( x0, y0, x1, y1, xRight );
601
+ if ( y0 < yBottom )
602
+ clipStartBottom ( x0, y0, x1, y1, yBottom );
603
+ return true ;
604
+
605
+ case 97 :
606
+ clipEndLeft ( x0, y0, x1, y1, xLeft );
607
+ if ( y1 < yBottom )
608
+ return false ;
609
+ clipStartBottom ( x0, y0, x1, y1, yBottom );
610
+ if ( x0 > xRight )
611
+ clipStartRight ( x0, y0, x1, y1, xRight );
612
+ return true ;
613
+
614
+ case 104 :
615
+ clipEndTop ( x0, y0, x1, y1, yTop );
616
+ if ( x1 > xRight )
617
+ return false ;
618
+ clipStartRight ( x0, y0, x1, y1, xRight );
619
+ if ( y0 < yBottom )
620
+ clipStartBottom ( x0, y0, x1, y1, yBottom );
621
+ return true ;
622
+
623
+ case 105 :
624
+ clipEndLeft ( x0, y0, x1, y1, xLeft );
625
+ if ( y1 < yBottom )
626
+ return false ;
627
+ clipStartRight ( x0, y0, x1, y1, xRight );
628
+ if ( y0 > yTop )
629
+ return false ;
630
+ if ( y1 > yTop )
631
+ clipEndTop ( x0, y0, x1, y1, yTop );
632
+ if ( y0 < yBottom )
633
+ clipStartBottom ( x0, y0, x1, y1, yBottom );
634
+ return true ;
635
+
636
+ case 128 :
637
+ clipStartTop ( x0, y0, x1, y1, yTop );
638
+ return true ;
639
+
640
+ case 129 :
641
+ clipStartTop ( x0, y0, x1, y1, yTop );
642
+ if ( x0 < xLeft )
643
+ return false ;
644
+ clipEndLeft ( x0, y0, x1, y1, xLeft );
645
+ return true ;
646
+
647
+ case 130 :
648
+ clipStartTop ( x0, y0, x1, y1, yTop );
649
+ if ( x0 > xRight )
650
+ return false ;
651
+ clipEndRight ( x0, y0, x1, y1, xRight );
652
+ return true ;
653
+
654
+ case 132 :
655
+ clipStartTop ( x0, y0, x1, y1, yTop );
656
+ clipEndBottom ( x0, y0, x1, y1, yBottom );
657
+ return true ;
658
+
659
+ case 133 :
660
+ clipStartTop ( x0, y0, x1, y1, yTop );
661
+ if ( x0 < xLeft )
662
+ return false ;
663
+ clipEndLeft ( x0, y0, x1, y1, xLeft );
664
+ if ( y1 < yBottom )
665
+ clipEndBottom ( x0, y0, x1, y1, yBottom );
666
+ return true ;
667
+
668
+ case 134 :
669
+ clipStartTop ( x0, y0, x1, y1, yTop );
670
+ if ( x0 > xRight )
671
+ return false ;
672
+ clipEndRight ( x0, y0, x1, y1, xRight );
673
+ if ( y1 < yBottom )
674
+ clipEndBottom ( x0, y0, x1, y1, yBottom );
675
+ return true ;
676
+
677
+ case 144 :
678
+ clipStartLeft ( x0, y0, x1, y1, xLeft );
679
+ if ( y0 > yTop )
680
+ clipStartTop ( x0, y0, x1, y1, yTop );
681
+ return true ;
682
+
683
+ case 146 :
684
+ clipEndRight ( x0, y0, x1, y1, xRight );
685
+ if ( y1 > yTop )
686
+ return false ;
687
+ clipStartTop ( x0, y0, x1, y1, yTop );
688
+ if ( x0 < xLeft )
689
+ clipStartLeft ( x0, y0, x1, y1, xLeft );
690
+ return true ;
691
+
692
+ case 148 :
693
+ clipEndBottom ( x0, y0, x1, y1, yBottom );
694
+ if ( x1 < xLeft )
695
+ return false ;
696
+ clipStartLeft ( x0, y0, x1, y1, xLeft );
697
+ if ( y0 > yTop )
698
+ clipStartTop ( x0, y0, x1, y1, yTop );
699
+ return true ;
700
+
701
+ case 150 :
702
+ clipStartLeft ( x0, y0, x1, y1, xLeft );
703
+ if ( y0 < yBottom )
704
+ return false ;
705
+ clipEndRight ( x0, y0, x1, y1, xRight );
706
+ if ( y1 > yTop )
707
+ return false ;
708
+ if ( y0 > yTop )
709
+ clipStartTop ( x0, y0, x1, y1, yTop );
710
+ if ( y1 < yBottom )
711
+ clipEndBottom ( x0, y0, x1, y1, yBottom );
712
+ return true ;
713
+
714
+ case 160 :
715
+ clipStartRight ( x0, y0, x1, y1, xRight );
716
+ if ( y0 > yTop )
717
+ clipStartTop ( x0, y0, x1, y1, yTop );
718
+ return true ;
719
+
720
+ case 161 :
721
+ clipEndLeft ( x0, y0, x1, y1, xLeft );
722
+ if ( y1 > yTop )
723
+ return false ;
724
+ clipStartTop ( x0, y0, x1, y1, yTop );
725
+ if ( x0 > xRight )
726
+ clipStartRight ( x0, y0, x1, y1, xRight );
727
+ return true ;
728
+
729
+ case 164 :
730
+ clipEndBottom ( x0, y0, x1, y1, yBottom );
731
+ if ( x1 > xRight )
732
+ return false ;
733
+ clipStartRight ( x0, y0, x1, y1, xRight );
734
+ if ( y0 > yTop )
735
+ clipStartTop ( x0, y0, x1, y1, yTop );
736
+ return true ;
737
+
738
+ case 165 :
739
+ clipEndLeft ( x0, y0, x1, y1, xLeft );
740
+ if ( y1 > yTop )
741
+ return false ;
742
+ clipStartRight ( x0, y0, x1, y1, xRight );
743
+ if ( y0 < yBottom )
744
+ return false ;
745
+ if ( y1 < yBottom )
746
+ clipEndBottom ( x0, y0, x1, y1, yBottom );
747
+ if ( y0 > yTop )
748
+ clipStartTop ( x0, y0, x1, y1, yTop );
749
+ return true ;
750
+ }
751
+
752
+ return false ;
753
+
754
+ }
755
+
286
756
287
757
#endif
0 commit comments