summaryrefslogtreecommitdiffstats
path: root/basegfx/source/polygon/b2dtrapezoid.cxx
blob: 5648aa3be81c031378433346ce275a8cfccc1bd5 (plain)
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
1163
1164
1165
1166
1167
1168
1169
1170
1171
/* -*- 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 / F_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
            sal_uInt32                  mnInitialEdgeEntryCount;
            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)
            :   mnInitialEdgeEntryCount(0),
                maTrDeEdgeEntries(),
                maPoints(),
                maNewPoints()
            {
                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 : 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 : 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 : 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);
                                    mnInitialEdgeEntryCount++;
                                }

                                // 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. Do
                    // not use maTrDeEdgeEntries.size() since that may be a non-constant time
                    // operation for Lists. Instead, use mnInitialEdgeEntryCount which will contain
                    // the roughly counted adds to the List
                    ro_Result.reserve(ro_Result.size() + mnInitialEdgeEntryCount);
                }

                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: */