1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
1148
1149
1150
1151
1152
1153
1154
1155
1156
1157
1158
1159
1160
1161
1162
|
/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
/*
* This file is part of the LibreOffice project.
*
* This Source Code Form is subject to the terms of the Mozilla Public
* License, v. 2.0. If a copy of the MPL was not distributed with this
* file, You can obtain one at http://mozilla.org/MPL/2.0/.
*
* This file incorporates work covered by the following license notice:
*
* Licensed to the Apache Software Foundation (ASF) under one or more
* contributor license agreements. See the NOTICE file distributed
* with this work for additional information regarding copyright
* ownership. The ASF licenses this file to you under the Apache
* License, Version 2.0 (the "License"); you may not use this file
* except in compliance with the License. You may obtain a copy of
* the License at http://www.apache.org/licenses/LICENSE-2.0 .
*/
#include <basegfx/polygon/b2dtrapezoid.hxx>
#include <basegfx/range/b1drange.hxx>
#include <basegfx/polygon/b2dpolygontools.hxx>
#include <basegfx/polygon/b2dpolypolygon.hxx>
#include <osl/diagnose.h>
#include <list>
namespace basegfx::trapezoidhelper
{
// helper class to hold a simple edge. This is only used for horizontal edges
// currently, thus the YPositions will be equal. I did not create a special
// class for this since holding the pointers is more effective and also can be
// used as baseclass for the traversing edges
namespace {
class TrDeSimpleEdge
{
protected:
// pointers to start and end point
const B2DPoint* mpStart;
const B2DPoint* mpEnd;
public:
// constructor
TrDeSimpleEdge(
const B2DPoint* pStart,
const B2DPoint* pEnd)
: mpStart(pStart),
mpEnd(pEnd)
{
}
// data read access
const B2DPoint& getStart() const { return *mpStart; }
const B2DPoint& getEnd() const { return *mpEnd; }
};
}
// define vector of simple edges
typedef std::vector< TrDeSimpleEdge > TrDeSimpleEdges;
// helper class for holding a traversing edge. It will always have some
// distance in YPos. The slope (in a numerically useful form, see comments) is
// hold and used in SortValue to allow sorting traversing edges by Y, X and slope
// (in that order)
namespace {
class TrDeEdgeEntry : public TrDeSimpleEdge
{
private:
// the slope in a numerical useful form for sorting
sal_uInt32 mnSortValue;
public:
// convenience data read access
double getDeltaX() const { return mpEnd->getX() - mpStart->getX(); }
double getDeltaY() const { return mpEnd->getY() - mpStart->getY(); }
// convenience data read access. SortValue is created on demand since
// it is not always used
sal_uInt32 getSortValue() const
{
if(mnSortValue != 0)
return mnSortValue;
// get radiant; has to be in the range ]0.0 .. pi[, thus scale to full
// sal_uInt32 range for maximum precision
const double fRadiant(atan2(getDeltaY(), getDeltaX()) * (SAL_MAX_UINT32 / M_PI));
// convert to sal_uInt32 value
const_cast< TrDeEdgeEntry* >(this)->mnSortValue = sal_uInt32(fRadiant);
return mnSortValue;
}
// constructor. SortValue can be given when known, use zero otherwise
TrDeEdgeEntry(
const B2DPoint* pStart,
const B2DPoint* pEnd,
sal_uInt32 nSortValue)
: TrDeSimpleEdge(pStart, pEnd),
mnSortValue(nSortValue)
{
// force traversal of deltaY downward
if(mpEnd->getY() < mpStart->getY())
{
std::swap(mpStart, mpEnd);
}
// no horizontal edges allowed, all need to traverse vertically
OSL_ENSURE(mpEnd->getY() > mpStart->getY(), "Illegal TrDeEdgeEntry constructed (!)");
}
// data write access to StartPoint
void setStart( const B2DPoint* pNewStart)
{
OSL_ENSURE(pNewStart != nullptr, "No null pointer allowed here (!)");
if(mpStart != pNewStart)
{
mpStart = pNewStart;
// no horizontal edges allowed, all need to traverse vertically
OSL_ENSURE(mpEnd->getY() > mpStart->getY(), "Illegal TrDeEdgeEntry constructed (!)");
}
}
// data write access to EndPoint
void setEnd( const B2DPoint* pNewEnd)
{
OSL_ENSURE(pNewEnd != nullptr, "No null pointer allowed here (!)");
if(mpEnd != pNewEnd)
{
mpEnd = pNewEnd;
// no horizontal edges allowed, all need to traverse vertically
OSL_ENSURE(mpEnd->getY() > mpStart->getY(), "Illegal TrDeEdgeEntry constructed (!)");
}
}
// operator for sort support. Sort by Y, X and slope (in that order)
bool operator<(const TrDeEdgeEntry& rComp) const
{
if(fTools::equal(getStart().getY(), rComp.getStart().getY()))
{
if(fTools::equal(getStart().getX(), rComp.getStart().getX()))
{
// when start points are equal, use the direction the edge is pointing
// to. That value is created on demand and derived from atan2 in the
// range ]0.0 .. pi[ (without extremas, we always have a deltaY in this
// class) and scaled to sal_uInt32 range for best precision. 0 means no angle,
// while SAL_MAX_UINT32 means pi. Thus, the higher the value, the more left
// the edge traverses.
return (getSortValue() > rComp.getSortValue());
}
else
{
return fTools::less(getStart().getX(), rComp.getStart().getX());
}
}
else
{
return fTools::less(getStart().getY(), rComp.getStart().getY());
}
}
// method for cut support
B2DPoint getCutPointForGivenY(double fGivenY) const
{
// Calculate cut point locally (do not use interpolate) since it is numerically
// necessary to guarantee the new, equal Y-coordinate
const double fFactor((fGivenY - getStart().getY()) / getDeltaY());
const double fDeltaXNew(fFactor * getDeltaX());
return B2DPoint(getStart().getX() + fDeltaXNew, fGivenY);
}
};
}
// define double linked list of edges (for fast random insert)
typedef std::list< TrDeEdgeEntry > TrDeEdgeEntries;
// FIXME: templatize this and use it for TrDeEdgeEntries too ...
namespace {
/// Class to allow efficient allocation and release of B2DPoints
class PointBlockAllocator
{
static const size_t nBlockSize = 32;
size_t nCurPoint;
B2DPoint *mpPointBase;
/// Special case the first allocation to avoid it.
B2DPoint maFirstStackBlock[nBlockSize];
std::vector< B2DPoint * > maBlocks;
public:
PointBlockAllocator() :
nCurPoint( nBlockSize ),
mpPointBase( maFirstStackBlock )
{
}
~PointBlockAllocator()
{
while(!maBlocks.empty())
{
delete [] maBlocks.back();
maBlocks.pop_back();
}
}
B2DPoint *allocatePoint()
{
if(nCurPoint >= nBlockSize)
{
mpPointBase = new B2DPoint[nBlockSize];
maBlocks.push_back(mpPointBase);
nCurPoint = 0;
}
return mpPointBase + nCurPoint++;
}
B2DPoint *allocatePoint(const B2DTuple &rPoint)
{
B2DPoint *pPoint = allocatePoint();
*pPoint = rPoint;
return pPoint;
}
/// This is a very uncommon case but why not ...
void freeIfLast(B2DPoint const *pPoint)
{
// just re-use the last point if we can.
if ( nCurPoint > 0 && pPoint == mpPointBase + nCurPoint - 1 )
nCurPoint--;
}
};
// helper class to handle the complete trapezoid subdivision of a PolyPolygon
class TrapezoidSubdivider
{
private:
// local data
TrDeEdgeEntries maTrDeEdgeEntries;
std::vector< B2DPoint > maPoints;
/// new points allocated for cuts
PointBlockAllocator maNewPoints;
void addEdgeSorted(
TrDeEdgeEntries::iterator aCurrent,
const TrDeEdgeEntry& rNewEdge)
{
// Loop while new entry is bigger, use operator<
while(aCurrent != maTrDeEdgeEntries.end() && (*aCurrent) < rNewEdge)
{
++aCurrent;
}
// Insert before first which is smaller or equal or at end
maTrDeEdgeEntries.insert(aCurrent, rNewEdge);
}
bool splitEdgeAtGivenPoint(
TrDeEdgeEntries::reference aEdge,
const B2DPoint& rCutPoint,
const TrDeEdgeEntries::iterator& aCurrent)
{
// do not create edges without deltaY: do not split when start is identical
if(aEdge.getStart().equal(rCutPoint))
{
return false;
}
// do not create edges without deltaY: do not split when end is identical
if(aEdge.getEnd().equal(rCutPoint))
{
return false;
}
const double fOldDeltaYStart(rCutPoint.getY() - aEdge.getStart().getY());
if(fTools::lessOrEqual(fOldDeltaYStart, 0.0))
{
// do not split: the resulting edge would be horizontal
// correct it to new start point
aEdge.setStart(&rCutPoint);
return false;
}
const double fNewDeltaYStart(aEdge.getEnd().getY() - rCutPoint.getY());
if(fTools::lessOrEqual(fNewDeltaYStart, 0.0))
{
// do not split: the resulting edge would be horizontal
// correct it to new end point
aEdge.setEnd(&rCutPoint);
return false;
}
// Create new entry
const TrDeEdgeEntry aNewEdge(
&rCutPoint,
&aEdge.getEnd(),
aEdge.getSortValue());
// Correct old entry
aEdge.setEnd(&rCutPoint);
// Insert sorted (to avoid new sort)
addEdgeSorted(aCurrent, aNewEdge);
return true;
}
bool testAndCorrectEdgeIntersection(
TrDeEdgeEntries::reference aEdgeA,
TrDeEdgeEntries::reference aEdgeB,
const TrDeEdgeEntries::iterator& aCurrent)
{
// Exclude simple cases: same start or end point
if(aEdgeA.getStart().equal(aEdgeB.getStart()))
{
return false;
}
if(aEdgeA.getStart().equal(aEdgeB.getEnd()))
{
return false;
}
if(aEdgeA.getEnd().equal(aEdgeB.getStart()))
{
return false;
}
if(aEdgeA.getEnd().equal(aEdgeB.getEnd()))
{
return false;
}
// Exclude simple cases: one of the edges has no length anymore
if(aEdgeA.getStart().equal(aEdgeA.getEnd()))
{
return false;
}
if(aEdgeB.getStart().equal(aEdgeB.getEnd()))
{
return false;
}
// check if one point is on the other edge (a touch, not a cut)
const B2DVector aDeltaB(aEdgeB.getDeltaX(), aEdgeB.getDeltaY());
if(utils::isPointOnEdge(aEdgeA.getStart(), aEdgeB.getStart(), aDeltaB))
{
return splitEdgeAtGivenPoint(aEdgeB, aEdgeA.getStart(), aCurrent);
}
if(utils::isPointOnEdge(aEdgeA.getEnd(), aEdgeB.getStart(), aDeltaB))
{
return splitEdgeAtGivenPoint(aEdgeB, aEdgeA.getEnd(), aCurrent);
}
const B2DVector aDeltaA(aEdgeA.getDeltaX(), aEdgeA.getDeltaY());
if(utils::isPointOnEdge(aEdgeB.getStart(), aEdgeA.getStart(), aDeltaA))
{
return splitEdgeAtGivenPoint(aEdgeA, aEdgeB.getStart(), aCurrent);
}
if(utils::isPointOnEdge(aEdgeB.getEnd(), aEdgeA.getStart(), aDeltaA))
{
return splitEdgeAtGivenPoint(aEdgeA, aEdgeB.getEnd(), aCurrent);
}
// check for cut inside edges. Use both t-values to choose the more precise
// one later
double fCutA(0.0);
double fCutB(0.0);
if(utils::findCut(
aEdgeA.getStart(), aDeltaA,
aEdgeB.getStart(), aDeltaB,
CutFlagValue::LINE,
&fCutA,
&fCutB) != CutFlagValue::NONE)
{
// use a simple metric (length criteria) for choosing the numerically
// better cut
const double fSimpleLengthA(aDeltaA.getX() + aDeltaA.getY());
const double fSimpleLengthB(aDeltaB.getX() + aDeltaB.getY());
const bool bAIsLonger(fSimpleLengthA > fSimpleLengthB);
B2DPoint* pNewPoint = bAIsLonger
? maNewPoints.allocatePoint(aEdgeA.getStart() + (fCutA * aDeltaA))
: maNewPoints.allocatePoint(aEdgeB.getStart() + (fCutB * aDeltaB));
// try to split both edges
bool bRetval = splitEdgeAtGivenPoint(aEdgeA, *pNewPoint, aCurrent);
bRetval |= splitEdgeAtGivenPoint(aEdgeB, *pNewPoint, aCurrent);
if(!bRetval)
maNewPoints.freeIfLast(pNewPoint);
return bRetval;
}
return false;
}
void solveHorizontalEdges(TrDeSimpleEdges& rTrDeSimpleEdges)
{
if(rTrDeSimpleEdges.empty() || maTrDeEdgeEntries.empty())
return;
// there were horizontal edges. These can be excluded, but
// cuts with other edges need to be solved and added before
// ignoring them
for(const TrDeSimpleEdge & rHorEdge : rTrDeSimpleEdges)
{
// get horizontal edge as candidate; prepare its range and fixed Y
const B1DRange aRange(rHorEdge.getStart().getX(), rHorEdge.getEnd().getX());
const double fFixedY(rHorEdge.getStart().getY());
// loop over traversing edges
TrDeEdgeEntries::iterator aCurrent(maTrDeEdgeEntries.begin());
do
{
// get compare edge
TrDeEdgeEntries::reference aCompare(*aCurrent++);
if(fTools::lessOrEqual(aCompare.getEnd().getY(), fFixedY))
{
// edge ends above horizontal edge, continue
continue;
}
if(fTools::moreOrEqual(aCompare.getStart().getY(), fFixedY))
{
// edge starts below horizontal edge, continue
continue;
}
// vertical overlap, get horizontal range
const B1DRange aCompareRange(aCompare.getStart().getX(), aCompare.getEnd().getX());
if(aRange.overlaps(aCompareRange))
{
// possible cut, get cut point
const B2DPoint aSplit(aCompare.getCutPointForGivenY(fFixedY));
if(fTools::more(aSplit.getX(), aRange.getMinimum())
&& fTools::less(aSplit.getX(), aRange.getMaximum()))
{
// cut is in XRange of horizontal edge, potentially needed cut
B2DPoint* pNewPoint = maNewPoints.allocatePoint(aSplit);
if(!splitEdgeAtGivenPoint(aCompare, *pNewPoint, aCurrent))
{
maNewPoints.freeIfLast(pNewPoint);
}
}
}
}
while(aCurrent != maTrDeEdgeEntries.end()
&& fTools::less(aCurrent->getStart().getY(), fFixedY));
}
}
public:
explicit TrapezoidSubdivider(
const B2DPolyPolygon& rSourcePolyPolygon)
{
B2DPolyPolygon aSource(rSourcePolyPolygon);
TrDeSimpleEdges aTrDeSimpleEdges;
sal_uInt32 nAllPointCount(0);
// ensure there are no curves used
if(aSource.areControlPointsUsed())
{
aSource = aSource.getDefaultAdaptiveSubdivision();
}
for(const auto& aPolygonCandidate : std::as_const(aSource))
{
// 1st run: count points
const sal_uInt32 nCount(aPolygonCandidate.count());
if(nCount > 2)
{
nAllPointCount += nCount;
}
}
if(nAllPointCount)
{
// reserve needed points. CAUTION: maPoints size is NOT to be changed anymore
// after 2nd loop since pointers to it are used in the edges
maPoints.reserve(nAllPointCount);
for(const auto& aPolygonCandidate : std::as_const(aSource))
{
// 2nd run: add points
const sal_uInt32 nCount(aPolygonCandidate.count());
if(nCount > 2)
{
for(sal_uInt32 b = 0; b < nCount; b++)
{
maPoints.push_back(aPolygonCandidate.getB2DPoint(b));
}
}
}
// Moved the edge construction to a 3rd run: doing it in the 2nd run is
// possible (and I used it), but requires a working vector::reserve()
// implementation, else the vector will be reallocated and the pointers
// in the edges may be wrong. Security first here.
sal_uInt32 nStartIndex(0);
for(const auto& aPolygonCandidate : std::as_const(aSource))
{
const sal_uInt32 nCount(aPolygonCandidate.count());
if(nCount > 2)
{
// get the last point of the current polygon
B2DPoint* pPrev(&maPoints[nCount + nStartIndex - 1]);
for(sal_uInt32 b = 0; b < nCount; b++)
{
// get next point
B2DPoint* pCurr(&maPoints[nStartIndex++]);
if(fTools::equal(pPrev->getY(), pCurr->getY()))
{
// horizontal edge, check for single point
if(!fTools::equal(pPrev->getX(), pCurr->getX()))
{
// X-order not needed, just add
aTrDeSimpleEdges.emplace_back(pPrev, pCurr);
const double fMiddle((pPrev->getY() + pCurr->getY()) * 0.5);
pPrev->setY(fMiddle);
pCurr->setY(fMiddle);
}
}
else
{
// vertical edge. Positive Y-direction is guaranteed by the
// TrDeEdgeEntry constructor
maTrDeEdgeEntries.emplace_back(pPrev, pCurr, 0);
}
// prepare next step
pPrev = pCurr;
}
}
}
}
if(!maTrDeEdgeEntries.empty())
{
// single and initial sort of traversing edges
maTrDeEdgeEntries.sort();
// solve horizontal edges if there are any detected
solveHorizontalEdges(aTrDeSimpleEdges);
}
}
void Subdivide(B2DTrapezoidVector& ro_Result)
{
// This is the central subdivider. The strategy is to use the first two entries
// from the traversing edges as a potential trapezoid and do the needed corrections
// and adaptations on the way.
// There always must be two edges with the same YStart value: When adding the polygons
// in the constructor, there is always a topmost point from which two edges start; when
// the topmost is an edge, there is a start and end of this edge from which two edges
// start. All cases have two edges with same StartY (QED).
// Based on this these edges get corrected when:
// - one is longer than the other
// - they intersect
// - they intersect with other edges
// - another edge starts inside the thought trapezoid
// All this cases again produce a valid state so that the first two edges have a common
// Ystart again. Some cases lead to a restart of the process, some allow consuming the
// edges and create the intended trapezoid.
// Be careful when doing changes here: it is essential to keep all possible paths
// in valid states and to be numerically correct. This is especially needed e.g.
// by using fTools::equal(..) in the more robust small-value incarnation.
B1DRange aLeftRange;
B1DRange aRightRange;
if(!maTrDeEdgeEntries.empty())
{
// measuring shows that the relation between edges and created trapezoids is
// mostly in the 1:1 range, thus reserve as much trapezoids as edges exist.
ro_Result.reserve(ro_Result.size() + maTrDeEdgeEntries.size());
}
while(!maTrDeEdgeEntries.empty())
{
// Prepare current operator and get first edge
TrDeEdgeEntries::iterator aCurrent(maTrDeEdgeEntries.begin());
TrDeEdgeEntries::reference aLeft(*aCurrent++);
if(aCurrent == maTrDeEdgeEntries.end())
{
// Should not happen: No 2nd edge; consume the single edge
// to not have an endless loop and start next. During development
// I constantly had breakpoints here, so I am sure enough to add an
// assertion here
OSL_FAIL("Trapezoid decomposer in illegal state (!)");
maTrDeEdgeEntries.pop_front();
continue;
}
// get second edge
TrDeEdgeEntries::reference aRight(*aCurrent++);
if(!fTools::equal(aLeft.getStart().getY(), aRight.getStart().getY()))
{
// Should not happen: We have a 2nd edge, but YStart is on another
// line; consume the single edge to not have an endless loop and start
// next. During development I constantly had breakpoints here, so I am
// sure enough to add an assertion here
OSL_FAIL("Trapezoid decomposer in illegal state (!)");
maTrDeEdgeEntries.pop_front();
continue;
}
// aLeft and aRight build a thought trapezoid now. They have a common
// start line (same Y for start points). Potentially, one of the edges
// is longer than the other. It is only needed to look at the shorter
// length which build the potential trapezoid. To do so, get the end points
// locally and adapt the evtl. longer one. Use only aLeftEnd and aRightEnd
// from here on, not the aLeft.getEnd() or aRight.getEnd() accesses.
B2DPoint aLeftEnd(aLeft.getEnd());
B2DPoint aRightEnd(aRight.getEnd());
// check if end points are on the same line. If yes, no adaptation
// needs to be prepared. Also remember which one actually is longer.
const bool bEndOnSameLine(fTools::equal(aLeftEnd.getY(), aRightEnd.getY()));
bool bLeftIsLonger(false);
if(!bEndOnSameLine)
{
// check which edge is longer and correct accordingly
bLeftIsLonger = fTools::more(aLeftEnd.getY(), aRightEnd.getY());
if(bLeftIsLonger)
{
aLeftEnd = aLeft.getCutPointForGivenY(aRightEnd.getY());
}
else
{
aRightEnd = aRight.getCutPointForGivenY(aLeftEnd.getY());
}
}
// check for same start and end points
const bool bSameStartPoint(aLeft.getStart().equal(aRight.getStart()));
const bool bSameEndPoint(aLeftEnd.equal(aRightEnd));
// check the simple case that the edges form a 'blind' edge (deadend)
if(bSameStartPoint && bSameEndPoint)
{
// correct the longer edge if prepared
if(!bEndOnSameLine)
{
if(bLeftIsLonger)
{
B2DPoint* pNewPoint = maNewPoints.allocatePoint(aLeftEnd);
if(!splitEdgeAtGivenPoint(aLeft, *pNewPoint, aCurrent))
{
maNewPoints.freeIfLast(pNewPoint);
}
}
else
{
B2DPoint* pNewPoint = maNewPoints.allocatePoint(aRightEnd);
if(!splitEdgeAtGivenPoint(aRight, *pNewPoint, aCurrent))
{
maNewPoints.freeIfLast(pNewPoint);
}
}
}
// consume both edges and start next run
maTrDeEdgeEntries.pop_front();
maTrDeEdgeEntries.pop_front();
continue;
}
// check if the edges self-intersect. This can only happen when
// start and end point are different
bool bRangesSet(false);
if(!(bSameStartPoint || bSameEndPoint))
{
// get XRanges of edges
aLeftRange = B1DRange(aLeft.getStart().getX(), aLeftEnd.getX());
aRightRange = B1DRange(aRight.getStart().getX(), aRightEnd.getX());
bRangesSet = true;
// use fast range test first
if(aLeftRange.overlaps(aRightRange))
{
// real cut test and correction. If correction was needed,
// start new run
if(testAndCorrectEdgeIntersection(aLeft, aRight, aCurrent))
{
continue;
}
}
}
// now we need to check if there are intersections with other edges
// or if other edges start inside the candidate trapezoid
if(aCurrent != maTrDeEdgeEntries.end()
&& fTools::less(aCurrent->getStart().getY(), aLeftEnd.getY()))
{
// get XRanges of edges
if(!bRangesSet)
{
aLeftRange = B1DRange(aLeft.getStart().getX(), aLeftEnd.getX());
aRightRange = B1DRange(aRight.getStart().getX(), aRightEnd.getX());
}
// build full XRange for fast check
B1DRange aAllRange(aLeftRange);
aAllRange.expand(aRightRange);
// prepare loop iterator; aCurrent needs to stay unchanged for
// possibly sorted insertions of new EdgeNodes. Also prepare stop flag
TrDeEdgeEntries::iterator aLoop(aCurrent);
bool bDone(false);
do
{
// get compare edge and its XRange
TrDeEdgeEntries::reference aCompare(*aLoop++);
// avoid edges using the same start point as one of
// the edges. These can neither have their start point
// in the thought trapezoid nor cut with one of the edges
if(aCompare.getStart().equal(aRight.getStart()))
{
continue;
}
// get compare XRange
const B1DRange aCompareRange(aCompare.getStart().getX(), aCompare.getEnd().getX());
// use fast range test first
if(aAllRange.overlaps(aCompareRange))
{
// check for start point inside thought trapezoid
if(fTools::more(aCompare.getStart().getY(), aLeft.getStart().getY()))
{
// calculate the two possible split points at compare's Y
const B2DPoint aSplitLeft(aLeft.getCutPointForGivenY(aCompare.getStart().getY()));
const B2DPoint aSplitRight(aRight.getCutPointForGivenY(aCompare.getStart().getY()));
// check for start point of aCompare being inside thought
// trapezoid
if(aCompare.getStart().getX() >= aSplitLeft.getX() &&
aCompare.getStart().getX() <= aSplitRight.getX())
{
// is inside, correct and restart loop
B2DPoint* pNewLeft = maNewPoints.allocatePoint(aSplitLeft);
if(splitEdgeAtGivenPoint(aLeft, *pNewLeft, aCurrent))
{
bDone = true;
}
else
{
maNewPoints.freeIfLast(pNewLeft);
}
B2DPoint* pNewRight = maNewPoints.allocatePoint(aSplitRight);
if(splitEdgeAtGivenPoint(aRight, *pNewRight, aCurrent))
{
bDone = true;
}
else
{
maNewPoints.freeIfLast(pNewRight);
}
}
}
if(!bDone && aLeftRange.overlaps(aCompareRange))
{
// test for concrete cut of compare edge with left edge
bDone = testAndCorrectEdgeIntersection(aLeft, aCompare, aCurrent);
}
if(!bDone && aRightRange.overlaps(aCompareRange))
{
// test for concrete cut of compare edge with Right edge
bDone = testAndCorrectEdgeIntersection(aRight, aCompare, aCurrent);
}
}
}
while(!bDone
&& aLoop != maTrDeEdgeEntries.end()
&& fTools::less(aLoop->getStart().getY(), aLeftEnd.getY()));
if(bDone)
{
// something needed to be changed; start next loop
continue;
}
}
// when we get here, the intended trapezoid can be used. It needs to
// be corrected possibly (if prepared); but this is no reason not to
// use it in the same loop iteration
if(!bEndOnSameLine)
{
if(bLeftIsLonger)
{
B2DPoint* pNewPoint = maNewPoints.allocatePoint(aLeftEnd);
if(!splitEdgeAtGivenPoint(aLeft, *pNewPoint, aCurrent))
{
maNewPoints.freeIfLast(pNewPoint);
}
}
else
{
B2DPoint* pNewPoint = maNewPoints.allocatePoint(aRightEnd);
if(!splitEdgeAtGivenPoint(aRight, *pNewPoint, aCurrent))
{
maNewPoints.freeIfLast(pNewPoint);
}
}
}
// the two edges start at the same Y, they use the same DeltaY, they
// do not cut themselves and not any other edge in range. Create a
// B2DTrapezoid and consume both edges
ro_Result.emplace_back(
aLeft.getStart().getX(),
aRight.getStart().getX(),
aLeft.getStart().getY(),
aLeftEnd.getX(),
aRightEnd.getX(),
aLeftEnd.getY());
maTrDeEdgeEntries.pop_front();
maTrDeEdgeEntries.pop_front();
}
}
};
}
} // end of namespace
namespace basegfx
{
B2DTrapezoid::B2DTrapezoid(
const double& rfTopXLeft,
const double& rfTopXRight,
const double& rfTopY,
const double& rfBottomXLeft,
const double& rfBottomXRight,
const double& rfBottomY)
: mfTopXLeft(rfTopXLeft),
mfTopXRight(rfTopXRight),
mfTopY(rfTopY),
mfBottomXLeft(rfBottomXLeft),
mfBottomXRight(rfBottomXRight),
mfBottomY(rfBottomY)
{
// guarantee mfTopXRight >= mfTopXLeft
if(mfTopXLeft > mfTopXRight)
{
std::swap(mfTopXLeft, mfTopXRight);
}
// guarantee mfBottomXRight >= mfBottomXLeft
if(mfBottomXLeft > mfBottomXRight)
{
std::swap(mfBottomXLeft, mfBottomXRight);
}
// guarantee mfBottomY >= mfTopY
if(mfTopY > mfBottomY)
{
std::swap(mfTopY, mfBottomY);
std::swap(mfTopXLeft, mfBottomXLeft);
std::swap(mfTopXRight, mfBottomXRight);
}
}
B2DPolygon B2DTrapezoid::getB2DPolygon() const
{
B2DPolygon aRetval;
aRetval.append(B2DPoint(getTopXLeft(), getTopY()));
aRetval.append(B2DPoint(getTopXRight(), getTopY()));
aRetval.append(B2DPoint(getBottomXRight(), getBottomY()));
aRetval.append(B2DPoint(getBottomXLeft(), getBottomY()));
aRetval.setClosed(true);
return aRetval;
}
} // end of namespace basegfx
namespace basegfx::utils
{
// convert Source utils::PolyPolygon to trapezoids
void trapezoidSubdivide(B2DTrapezoidVector& ro_Result, const B2DPolyPolygon& rSourcePolyPolygon)
{
trapezoidhelper::TrapezoidSubdivider aTrapezoidSubdivider(rSourcePolyPolygon);
aTrapezoidSubdivider.Subdivide(ro_Result);
}
void createLineTrapezoidFromEdge(
B2DTrapezoidVector& ro_Result,
const B2DPoint& rPointA,
const B2DPoint& rPointB,
double fLineWidth)
{
if(fTools::lessOrEqual(fLineWidth, 0.0))
{
// no line width
return;
}
if(rPointA.equal(rPointB))
{
// points are equal, no edge
return;
}
const double fHalfLineWidth(0.5 * fLineWidth);
if(fTools::equal(rPointA.getX(), rPointB.getX()))
{
// vertical line
const double fLeftX(rPointA.getX() - fHalfLineWidth);
const double fRightX(rPointA.getX() + fHalfLineWidth);
ro_Result.emplace_back(
fLeftX,
fRightX,
std::min(rPointA.getY(), rPointB.getY()),
fLeftX,
fRightX,
std::max(rPointA.getY(), rPointB.getY()));
}
else if(fTools::equal(rPointA.getY(), rPointB.getY()))
{
// horizontal line
const double fLeftX(std::min(rPointA.getX(), rPointB.getX()));
const double fRightX(std::max(rPointA.getX(), rPointB.getX()));
ro_Result.emplace_back(
fLeftX,
fRightX,
rPointA.getY() - fHalfLineWidth,
fLeftX,
fRightX,
rPointA.getY() + fHalfLineWidth);
}
else
{
// diagonal line
// create perpendicular vector
const B2DVector aDelta(rPointB - rPointA);
B2DVector aPerpendicular(-aDelta.getY(), aDelta.getX());
aPerpendicular.setLength(fHalfLineWidth);
// create StartLow, StartHigh, EndLow and EndHigh
const B2DPoint aStartLow(rPointA + aPerpendicular);
const B2DPoint aStartHigh(rPointA - aPerpendicular);
const B2DPoint aEndHigh(rPointB - aPerpendicular);
const B2DPoint aEndLow(rPointB + aPerpendicular);
// create EdgeEntries
basegfx::trapezoidhelper::TrDeEdgeEntries aTrDeEdgeEntries;
aTrDeEdgeEntries.emplace_back(&aStartLow, &aStartHigh, 0);
aTrDeEdgeEntries.emplace_back(&aStartHigh, &aEndHigh, 0);
aTrDeEdgeEntries.emplace_back(&aEndHigh, &aEndLow, 0);
aTrDeEdgeEntries.emplace_back(&aEndLow, &aStartLow, 0);
aTrDeEdgeEntries.sort();
// here we know we have exactly four edges, and they do not cut, touch or
// intersect. This makes processing much easier. Get the first two as start
// edges for the thought trapezoid
basegfx::trapezoidhelper::TrDeEdgeEntries::iterator aCurrent(aTrDeEdgeEntries.begin());
basegfx::trapezoidhelper::TrDeEdgeEntries::reference aLeft(*aCurrent++);
basegfx::trapezoidhelper::TrDeEdgeEntries::reference aRight(*aCurrent++);
const bool bEndOnSameLine(fTools::equal(aLeft.getEnd().getY(), aRight.getEnd().getY()));
if(bEndOnSameLine)
{
// create two triangle trapezoids
ro_Result.emplace_back(
aLeft.getStart().getX(),
aRight.getStart().getX(),
aLeft.getStart().getY(),
aLeft.getEnd().getX(),
aRight.getEnd().getX(),
aLeft.getEnd().getY());
basegfx::trapezoidhelper::TrDeEdgeEntries::reference aLeft2(*aCurrent++);
basegfx::trapezoidhelper::TrDeEdgeEntries::reference aRight2(*aCurrent++);
ro_Result.emplace_back(
aLeft2.getStart().getX(),
aRight2.getStart().getX(),
aLeft2.getStart().getY(),
aLeft2.getEnd().getX(),
aRight2.getEnd().getX(),
aLeft2.getEnd().getY());
}
else
{
// create three trapezoids. Check which edge is longer and
// correct accordingly
const bool bLeftIsLonger(fTools::more(aLeft.getEnd().getY(), aRight.getEnd().getY()));
if(bLeftIsLonger)
{
basegfx::trapezoidhelper::TrDeEdgeEntries::reference aRight2(*aCurrent++);
basegfx::trapezoidhelper::TrDeEdgeEntries::reference aLeft2(*aCurrent++);
const B2DPoint aSplitLeft(aLeft.getCutPointForGivenY(aRight.getEnd().getY()));
const B2DPoint aSplitRight(aRight2.getCutPointForGivenY(aLeft.getEnd().getY()));
ro_Result.emplace_back(
aLeft.getStart().getX(),
aRight.getStart().getX(),
aLeft.getStart().getY(),
aSplitLeft.getX(),
aRight.getEnd().getX(),
aRight.getEnd().getY());
ro_Result.emplace_back(
aSplitLeft.getX(),
aRight.getEnd().getX(),
aRight.getEnd().getY(),
aLeft2.getStart().getX(),
aSplitRight.getX(),
aLeft2.getStart().getY());
ro_Result.emplace_back(
aLeft2.getStart().getX(),
aSplitRight.getX(),
aLeft2.getStart().getY(),
aLeft2.getEnd().getX(),
aRight2.getEnd().getX(),
aLeft2.getEnd().getY());
}
else
{
basegfx::trapezoidhelper::TrDeEdgeEntries::reference aLeft2(*aCurrent++);
basegfx::trapezoidhelper::TrDeEdgeEntries::reference aRight2(*aCurrent++);
const B2DPoint aSplitRight(aRight.getCutPointForGivenY(aLeft.getEnd().getY()));
const B2DPoint aSplitLeft(aLeft2.getCutPointForGivenY(aRight.getEnd().getY()));
ro_Result.emplace_back(
aLeft.getStart().getX(),
aRight.getStart().getX(),
aLeft.getStart().getY(),
aLeft.getEnd().getX(),
aSplitRight.getX(),
aLeft.getEnd().getY());
ro_Result.emplace_back(
aLeft.getEnd().getX(),
aSplitRight.getX(),
aLeft.getEnd().getY(),
aSplitLeft.getX(),
aRight.getEnd().getX(),
aRight2.getStart().getY());
ro_Result.emplace_back(
aSplitLeft.getX(),
aRight.getEnd().getX(),
aRight2.getStart().getY(),
aLeft2.getEnd().getX(),
aRight2.getEnd().getX(),
aLeft2.getEnd().getY());
}
}
}
}
void createLineTrapezoidFromB2DPolygon(
B2DTrapezoidVector& ro_Result,
const B2DPolygon& rPolygon,
double fLineWidth)
{
if(fTools::lessOrEqual(fLineWidth, 0.0))
{
return;
}
// ensure there are no curves used
B2DPolygon aSource(rPolygon);
if(aSource.areControlPointsUsed())
{
const double fPrecisionFactor = 0.25;
aSource = adaptiveSubdivideByDistance( aSource, fLineWidth * fPrecisionFactor );
}
const sal_uInt32 nPointCount(aSource.count());
if(!nPointCount)
{
return;
}
const sal_uInt32 nEdgeCount(aSource.isClosed() ? nPointCount : nPointCount - 1);
B2DPoint aCurrent(aSource.getB2DPoint(0));
ro_Result.reserve(ro_Result.size() + (3 * nEdgeCount));
for(sal_uInt32 a(0); a < nEdgeCount; a++)
{
const sal_uInt32 nNextIndex((a + 1) % nPointCount);
const B2DPoint aNext(aSource.getB2DPoint(nNextIndex));
createLineTrapezoidFromEdge(ro_Result, aCurrent, aNext, fLineWidth);
aCurrent = aNext;
}
}
} // end of namespace
/* vim:set shiftwidth=4 softtabstop=4 expandtab: */
|