summaryrefslogtreecommitdiff
path: root/basegfx/source/polygon/b2dlinegeometry.cxx
blob: 190a413dfd00c8623a73ae0fff370aafbc7ddd7e (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
/* -*- 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 <osl/diagnose.h>
#include <basegfx/polygon/b2dlinegeometry.hxx>
#include <basegfx/point/b2dpoint.hxx>
#include <basegfx/vector/b2dvector.hxx>
#include <basegfx/polygon/b2dpolygontools.hxx>
#include <basegfx/polygon/b2dpolypolygontools.hxx>
#include <basegfx/range/b2drange.hxx>
#include <basegfx/matrix/b2dhommatrix.hxx>
#include <basegfx/curve/b2dcubicbezier.hxx>
#include <basegfx/matrix/b2dhommatrixtools.hxx>
#include <com/sun/star/drawing/LineCap.hpp>
#include <basegfx/polygon/b2dpolypolygoncutter.hxx>
#include <basegfx/polygon/b2dpolygontriangulator.hxx>

namespace basegfx
{
    namespace utils
    {
        B2DPolyPolygon createAreaGeometryForLineStartEnd(
            const B2DPolygon& rCandidate,
            const B2DPolyPolygon& rArrow,
            bool bStart,
            double fWidth,
            double fCandidateLength,
            double fDockingPosition, // 0->top, 1->bottom
            double* pConsumedLength,
            double fShift)
        {
            B2DPolyPolygon aRetval;
            assert((rCandidate.count() > 1) && "createAreaGeometryForLineStartEnd: Line polygon has too less points (!)");
            assert((rArrow.count() > 0) && "createAreaGeometryForLineStartEnd: Empty arrow utils::PolyPolygon (!)");
            assert((fWidth > 0.0) && "createAreaGeometryForLineStartEnd: Width too small (!)");
            assert((fDockingPosition >= 0.0 && fDockingPosition <= 1.0) &&
                "createAreaGeometryForLineStartEnd: fDockingPosition out of range [0.0 .. 1.0] (!)");

            if(fWidth < 0.0)
            {
                fWidth = -fWidth;
            }

            if(rCandidate.count() > 1 && rArrow.count() && !fTools::equalZero(fWidth))
            {
                if(fDockingPosition < 0.0)
                {
                    fDockingPosition = 0.0;
                }
                else if(fDockingPosition > 1.0)
                {
                    fDockingPosition = 1.0;
                }

                // init return value from arrow
                aRetval.append(rArrow);

                // get size of the arrow
                const B2DRange aArrowSize(getRange(rArrow));

                // build ArrowTransform; center in X, align with axis in Y
                B2DHomMatrix aArrowTransform(basegfx::utils::createTranslateB2DHomMatrix(
                    -aArrowSize.getCenter().getX(), -aArrowSize.getMinimum().getY()));

                // scale to target size
                const double fArrowScale(fWidth / (aArrowSize.getWidth()));
                aArrowTransform.scale(fArrowScale, fArrowScale);

                // get arrow size in Y
                B2DPoint aUpperCenter(aArrowSize.getCenter().getX(), aArrowSize.getMaximum().getY());
                aUpperCenter *= aArrowTransform;
                const double fArrowYLength(B2DVector(aUpperCenter).getLength());

                // move arrow to have docking position centered
                aArrowTransform.translate(0.0, -fArrowYLength * fDockingPosition + fShift);

                // prepare polygon length
                if(fTools::equalZero(fCandidateLength))
                {
                    fCandidateLength = getLength(rCandidate);
                }

                // get the polygon vector we want to plant this arrow on
                const double fConsumedLength(fArrowYLength * (1.0 - fDockingPosition) - fShift);
                const B2DVector aHead(rCandidate.getB2DPoint(bStart ? 0 : rCandidate.count() - 1));
                const B2DVector aTail(getPositionAbsolute(rCandidate,
                    bStart ? fConsumedLength : fCandidateLength - fConsumedLength, fCandidateLength));

                // from that vector, take the needed rotation and add rotate for arrow to transformation
                const B2DVector aTargetDirection(aHead - aTail);
                const double fRotation(atan2(aTargetDirection.getY(), aTargetDirection.getX()) + F_PI2);

                // rotate around docking position
                aArrowTransform.rotate(fRotation);

                // move arrow docking position to polygon head
                aArrowTransform.translate(aHead.getX(), aHead.getY());

                // transform retval and close
                aRetval.transform(aArrowTransform);
                aRetval.setClosed(true);

                // if pConsumedLength is asked for, fill it
                if(pConsumedLength)
                {
                    *pConsumedLength = fConsumedLength;
                }
            }

            return aRetval;
        }
    } // end of namespace utils
} // end of namespace basegfx

namespace basegfx
{
    // anonymous namespace for local helpers
    namespace
    {
        bool impIsSimpleEdge(const B2DCubicBezier& rCandidate, double fMaxCosQuad, double fMaxPartOfEdgeQuad)
        {
            // isBezier() is true, already tested by caller
            const B2DVector aEdge(rCandidate.getEndPoint() - rCandidate.getStartPoint());

            if(aEdge.equalZero())
            {
                // start and end point the same, but control vectors used -> balloon curve loop
                // is not a simple edge
                return false;
            }

            // get tangentA and scalar with edge
            const B2DVector aTangentA(rCandidate.getTangent(0.0));
            const double fScalarAE(aEdge.scalar(aTangentA));

            if(fTools::lessOrEqual(fScalarAE, 0.0))
            {
                // angle between TangentA and Edge is bigger or equal 90 degrees
                return false;
            }

            // get self-scalars for E and A
            const double fScalarE(aEdge.scalar(aEdge));
            const double fScalarA(aTangentA.scalar(aTangentA));
            const double fLengthCompareE(fScalarE * fMaxPartOfEdgeQuad);

            if(fTools::moreOrEqual(fScalarA, fLengthCompareE))
            {
                // length of TangentA is more than fMaxPartOfEdge of length of edge
                return false;
            }

            if(fTools::lessOrEqual(fScalarAE * fScalarAE, fScalarA * fScalarE * fMaxCosQuad))
            {
                // angle between TangentA and Edge is bigger or equal angle defined by fMaxCos
                return false;
            }

            // get tangentB and scalar with edge
            const B2DVector aTangentB(rCandidate.getTangent(1.0));
            const double fScalarBE(aEdge.scalar(aTangentB));

            if(fTools::lessOrEqual(fScalarBE, 0.0))
            {
                // angle between TangentB and Edge is bigger or equal 90 degrees
                return false;
            }

            // get self-scalar for B
            const double fScalarB(aTangentB.scalar(aTangentB));

            if(fTools::moreOrEqual(fScalarB, fLengthCompareE))
            {
                // length of TangentB is more than fMaxPartOfEdge of length of edge
                return false;
            }

            if(fTools::lessOrEqual(fScalarBE * fScalarBE, fScalarB * fScalarE * fMaxCosQuad))
            {
                // angle between TangentB and Edge is bigger or equal defined by fMaxCos
                return false;
            }

            return true;
        }

        void impSubdivideToSimple(const B2DCubicBezier& rCandidate, B2DPolygon& rTarget, double fMaxCosQuad, double fMaxPartOfEdgeQuad, sal_uInt32 nMaxRecursionDepth)
        {
            if(!nMaxRecursionDepth || impIsSimpleEdge(rCandidate, fMaxCosQuad, fMaxPartOfEdgeQuad))
            {
                rTarget.appendBezierSegment(rCandidate.getControlPointA(), rCandidate.getControlPointB(), rCandidate.getEndPoint());
            }
            else
            {
                B2DCubicBezier aLeft, aRight;
                rCandidate.split(0.5, &aLeft, &aRight);

                impSubdivideToSimple(aLeft, rTarget, fMaxCosQuad, fMaxPartOfEdgeQuad, nMaxRecursionDepth - 1);
                impSubdivideToSimple(aRight, rTarget, fMaxCosQuad, fMaxPartOfEdgeQuad, nMaxRecursionDepth - 1);
            }
        }

        B2DPolygon subdivideToSimple(const B2DPolygon& rCandidate, double fMaxCosQuad, double fMaxPartOfEdgeQuad)
        {
            const sal_uInt32 nPointCount(rCandidate.count());

            if(rCandidate.areControlPointsUsed() && nPointCount)
            {
                const sal_uInt32 nEdgeCount(rCandidate.isClosed() ? nPointCount : nPointCount - 1);
                B2DPolygon aRetval;
                B2DCubicBezier aEdge;

                // prepare edge for loop
                aEdge.setStartPoint(rCandidate.getB2DPoint(0));
                aRetval.append(aEdge.getStartPoint());

                for(sal_uInt32 a(0); a < nEdgeCount; a++)
                {
                    // fill B2DCubicBezier
                    const sal_uInt32 nNextIndex((a + 1) % nPointCount);
                    aEdge.setControlPointA(rCandidate.getNextControlPoint(a));
                    aEdge.setControlPointB(rCandidate.getPrevControlPoint(nNextIndex));
                    aEdge.setEndPoint(rCandidate.getB2DPoint(nNextIndex));

                    // get rid of unnecessary bezier segments
                    aEdge.testAndSolveTrivialBezier();

                    if(aEdge.isBezier())
                    {
                        // before splitting recursively with internal simple criteria, use
                        // ExtremumPosFinder to remove those
                        std::vector< double > aExtremumPositions;

                        aExtremumPositions.reserve(4);
                        aEdge.getAllExtremumPositions(aExtremumPositions);

                        const sal_uInt32 nCount(aExtremumPositions.size());

                        if(nCount)
                        {
                            if(nCount > 1)
                            {
                                // create order from left to right
                                std::sort(aExtremumPositions.begin(), aExtremumPositions.end());
                            }

                            for(sal_uInt32 b(0); b < nCount;)
                            {
                                // split aEdge at next split pos
                                B2DCubicBezier aLeft;
                                const double fSplitPos(aExtremumPositions[b++]);

                                aEdge.split(fSplitPos, &aLeft, &aEdge);
                                aLeft.testAndSolveTrivialBezier();

                                // consume left part
                                if(aLeft.isBezier())
                                {
                                    impSubdivideToSimple(aLeft, aRetval, fMaxCosQuad, fMaxPartOfEdgeQuad, 6);
                                }
                                else
                                {
                                    aRetval.append(aLeft.getEndPoint());
                                }

                                if(b < nCount)
                                {
                                    // correct the remaining split positions to fit to shortened aEdge
                                    const double fScaleFactor(1.0 / (1.0 - fSplitPos));

                                    for(sal_uInt32 c(b); c < nCount; c++)
                                    {
                                        aExtremumPositions[c] = (aExtremumPositions[c] - fSplitPos) * fScaleFactor;
                                    }
                                }
                            }

                            // test the shortened rest of aEdge
                            aEdge.testAndSolveTrivialBezier();

                            // consume right part
                            if(aEdge.isBezier())
                            {
                                impSubdivideToSimple(aEdge, aRetval, fMaxCosQuad, fMaxPartOfEdgeQuad, 6);
                            }
                            else
                            {
                                aRetval.append(aEdge.getEndPoint());
                            }
                        }
                        else
                        {
                            impSubdivideToSimple(aEdge, aRetval, fMaxCosQuad, fMaxPartOfEdgeQuad, 6);
                        }
                    }
                    else
                    {
                        // straight edge, add point
                        aRetval.append(aEdge.getEndPoint());
                    }

                    // prepare edge for next step
                    aEdge.setStartPoint(aEdge.getEndPoint());
                }

                // copy closed flag and check for double points
                aRetval.setClosed(rCandidate.isClosed());
                aRetval.removeDoublePoints();

                return aRetval;
            }
            else
            {
                return rCandidate;
            }
        }

        B2DPolygon createAreaGeometryForEdge(
            const B2DCubicBezier& rEdge,
            double fHalfLineWidth,
            bool bStartRound,
            bool bEndRound,
            bool bStartSquare,
            bool bEndSquare,
            basegfx::triangulator::B2DTriangleVector* pTriangles)
        {
            // create polygon for edge
            // Unfortunately, while it would be geometrically correct to not add
            // the in-between points EdgeEnd and EdgeStart, it leads to rounding
            // errors when converting to integer polygon coordinates for painting
            if(rEdge.isBezier())
            {
                // prepare target and data common for upper and lower
                B2DPolygon aBezierPolygon;
                const B2DVector aPureEdgeVector(rEdge.getEndPoint() - rEdge.getStartPoint());
                const double fEdgeLength(aPureEdgeVector.getLength());
                const bool bIsEdgeLengthZero(fTools::equalZero(fEdgeLength));
                B2DVector aTangentA(rEdge.getTangent(0.0)); aTangentA.normalize();
                B2DVector aTangentB(rEdge.getTangent(1.0)); aTangentB.normalize();
                const B2DVector aNormalizedPerpendicularA(getPerpendicular(aTangentA));
                const B2DVector aNormalizedPerpendicularB(getPerpendicular(aTangentB));

                // create upper displacement vectors and check if they cut
                const B2DVector aPerpendStartA(aNormalizedPerpendicularA * -fHalfLineWidth);
                const B2DVector aPerpendEndA(aNormalizedPerpendicularB * -fHalfLineWidth);
                double fCutA(0.0);
                const CutFlagValue aCutA(utils::findCut(
                    rEdge.getStartPoint(), aPerpendStartA,
                    rEdge.getEndPoint(), aPerpendEndA,
                    CutFlagValue::ALL, &fCutA));
                const bool bCutA(aCutA != CutFlagValue::NONE);

                // create lower displacement vectors and check if they cut
                const B2DVector aPerpendStartB(aNormalizedPerpendicularA * fHalfLineWidth);
                const B2DVector aPerpendEndB(aNormalizedPerpendicularB * fHalfLineWidth);
                double fCutB(0.0);
                const CutFlagValue aCutB(utils::findCut(
                    rEdge.getEndPoint(), aPerpendEndB,
                    rEdge.getStartPoint(), aPerpendStartB,
                    CutFlagValue::ALL, &fCutB));
                const bool bCutB(aCutB != CutFlagValue::NONE);

                // check if cut happens
                const bool bCut(bCutA || bCutB);
                B2DPoint aCutPoint;

                // create left edge
                if(bStartRound || bStartSquare)
                {
                    if(bStartRound)
                    {
                        basegfx::B2DPolygon aStartPolygon(utils::createHalfUnitCircle());

                        aStartPolygon.transform(
                            utils::createScaleShearXRotateTranslateB2DHomMatrix(
                                fHalfLineWidth, fHalfLineWidth,
                                0.0,
                                atan2(aTangentA.getY(), aTangentA.getX()) + F_PI2,
                                rEdge.getStartPoint().getX(), rEdge.getStartPoint().getY()));
                        aBezierPolygon.append(aStartPolygon);
                    }
                    else // bStartSquare
                    {
                        const basegfx::B2DPoint aStart(rEdge.getStartPoint() - (aTangentA * fHalfLineWidth));

                        if(bCutB)
                        {
                            aBezierPolygon.append(rEdge.getStartPoint() + aPerpendStartB);
                        }

                        aBezierPolygon.append(aStart + aPerpendStartB);
                        aBezierPolygon.append(aStart + aPerpendStartA);

                        if(bCutA)
                        {
                            aBezierPolygon.append(rEdge.getStartPoint() + aPerpendStartA);
                        }
                    }
                }
                else
                {
                    // append original in-between point
                    aBezierPolygon.append(rEdge.getStartPoint());
                }

                // create upper edge.
                {
                    if(bCutA)
                    {
                        // calculate cut point and add
                        aCutPoint = rEdge.getStartPoint() + (aPerpendStartA * fCutA);
                        aBezierPolygon.append(aCutPoint);
                    }
                    else
                    {
                        // create scaled bezier segment
                        const B2DPoint aStart(rEdge.getStartPoint() + aPerpendStartA);
                        const B2DPoint aEnd(rEdge.getEndPoint() + aPerpendEndA);
                        const B2DVector aEdge(aEnd - aStart);
                        const double fLength(aEdge.getLength());
                        const double fScale(bIsEdgeLengthZero ? 1.0 : fLength / fEdgeLength);
                        const B2DVector fRelNext(rEdge.getControlPointA() - rEdge.getStartPoint());
                        const B2DVector fRelPrev(rEdge.getControlPointB() - rEdge.getEndPoint());

                        aBezierPolygon.append(aStart);
                        aBezierPolygon.appendBezierSegment(aStart + (fRelNext * fScale), aEnd + (fRelPrev * fScale), aEnd);
                    }
                }

                // create right edge
                if(bEndRound || bEndSquare)
                {
                    if(bEndRound)
                    {
                        basegfx::B2DPolygon aEndPolygon(utils::createHalfUnitCircle());

                        aEndPolygon.transform(
                            utils::createScaleShearXRotateTranslateB2DHomMatrix(
                                fHalfLineWidth, fHalfLineWidth,
                                0.0,
                                atan2(aTangentB.getY(), aTangentB.getX()) - F_PI2,
                                rEdge.getEndPoint().getX(), rEdge.getEndPoint().getY()));
                        aBezierPolygon.append(aEndPolygon);
                    }
                    else // bEndSquare
                    {
                        const basegfx::B2DPoint aEnd(rEdge.getEndPoint() + (aTangentB * fHalfLineWidth));

                        if(bCutA)
                        {
                            aBezierPolygon.append(rEdge.getEndPoint() + aPerpendEndA);
                        }

                        aBezierPolygon.append(aEnd + aPerpendEndA);
                        aBezierPolygon.append(aEnd + aPerpendEndB);

                        if(bCutB)
                        {
                            aBezierPolygon.append(rEdge.getEndPoint() + aPerpendEndB);
                        }
                    }
                }
                else
                {
                    // append original in-between point
                    aBezierPolygon.append(rEdge.getEndPoint());
                }

                // create lower edge.
                {
                    if(bCutB)
                    {
                        // calculate cut point and add
                        aCutPoint = rEdge.getEndPoint() + (aPerpendEndB * fCutB);
                        aBezierPolygon.append(aCutPoint);
                    }
                    else
                    {
                        // create scaled bezier segment
                        const B2DPoint aStart(rEdge.getEndPoint() + aPerpendEndB);
                        const B2DPoint aEnd(rEdge.getStartPoint() + aPerpendStartB);
                        const B2DVector aEdge(aEnd - aStart);
                        const double fLength(aEdge.getLength());
                        const double fScale(bIsEdgeLengthZero ? 1.0 : fLength / fEdgeLength);
                        const B2DVector fRelNext(rEdge.getControlPointB() - rEdge.getEndPoint());
                        const B2DVector fRelPrev(rEdge.getControlPointA() - rEdge.getStartPoint());

                        aBezierPolygon.append(aStart);
                        aBezierPolygon.appendBezierSegment(aStart + (fRelNext * fScale), aEnd + (fRelPrev * fScale), aEnd);
                    }
                }

                // close
                aBezierPolygon.setClosed(true);

                if(bStartRound || bEndRound)
                {
                    // double points possible when round caps are used at start or end
                    aBezierPolygon.removeDoublePoints();
                }

                if(bCut && ((bStartRound || bStartSquare) && (bEndRound || bEndSquare)))
                {
                    // When cut exists and both ends are extended with caps, a self-intersecting polygon
                    // is created; one cut point is known, but there is a 2nd one in the caps geometry.
                    // Solve by using tooling.
                    // Remark: This nearly never happens due to curve preparations to extreme points
                    // and maximum angle turning, but I constructed a test case and checked that it is
                    // working properly.
                    const B2DPolyPolygon aTemp(utils::solveCrossovers(aBezierPolygon));
                    const sal_uInt32 nTempCount(aTemp.count());

                    if(nTempCount)
                    {
                        if(nTempCount > 1)
                        {
                            // as expected, multiple polygons (with same orientation). Remove
                            // the one which contains aCutPoint, or better take the one without
                            for (sal_uInt32 a(0); a < nTempCount; a++)
                            {
                                aBezierPolygon = aTemp.getB2DPolygon(a);

                                const sal_uInt32 nCandCount(aBezierPolygon.count());

                                for(sal_uInt32 b(0); b < nCandCount; b++)
                                {
                                    if(aCutPoint.equal(aBezierPolygon.getB2DPoint(b)))
                                    {
                                        aBezierPolygon.clear();
                                        break;
                                    }
                                }

                                if(aBezierPolygon.count())
                                {
                                    break;
                                }
                            }

                            OSL_ENSURE(aBezierPolygon.count(), "Error in line geometry creation, could not solve self-intersection (!)");
                        }
                        else
                        {
                            // none found, use result
                            aBezierPolygon = aTemp.getB2DPolygon(0);
                        }
                    }
                    else
                    {
                        OSL_ENSURE(false, "Error in line geometry creation, could not solve self-intersection (!)");
                    }
                }

                if(nullptr != pTriangles)
                {
                    const basegfx::triangulator::B2DTriangleVector aResult(
                        basegfx::triangulator::triangulate(
                            aBezierPolygon));
                    pTriangles->insert(pTriangles->end(), aResult.begin(), aResult.end());
                    aBezierPolygon.clear();
                }

                // return
                return aBezierPolygon;
            }
            else
            {
                // Get start and  end point, create tangent and set to needed length
                B2DVector aTangent(rEdge.getEndPoint() - rEdge.getStartPoint());
                aTangent.setLength(fHalfLineWidth);

                // prepare return value
                B2DPolygon aEdgePolygon;

                // buffered angle
                double fAngle(0.0);
                bool bAngle(false);

                // buffered perpendicular
                B2DVector aPerpend;
                bool bPerpend(false);

                // create left vertical
                if(bStartRound)
                {
                    aEdgePolygon = utils::createHalfUnitCircle();
                    fAngle = atan2(aTangent.getY(), aTangent.getX());
                    bAngle = true;
                    aEdgePolygon.transform(
                        utils::createScaleShearXRotateTranslateB2DHomMatrix(
                            fHalfLineWidth, fHalfLineWidth,
                            0.0,
                            fAngle + F_PI2,
                            rEdge.getStartPoint().getX(), rEdge.getStartPoint().getY()));
                }
                else
                {
                    aPerpend.setX(-aTangent.getY());
                    aPerpend.setY(aTangent.getX());
                    bPerpend = true;

                    if(bStartSquare)
                    {
                        const basegfx::B2DPoint aStart(rEdge.getStartPoint() - aTangent);

                        aEdgePolygon.append(aStart + aPerpend);
                        aEdgePolygon.append(aStart - aPerpend);
                    }
                    else
                    {
                        aEdgePolygon.append(rEdge.getStartPoint() + aPerpend);
                        aEdgePolygon.append(rEdge.getStartPoint()); // keep the in-between point for numerical reasons
                        aEdgePolygon.append(rEdge.getStartPoint() - aPerpend);
                    }
                }

                // create right vertical
                if(bEndRound)
                {
                    basegfx::B2DPolygon aEndPolygon(utils::createHalfUnitCircle());

                    if(!bAngle)
                    {
                        fAngle = atan2(aTangent.getY(), aTangent.getX());
                    }

                    aEndPolygon.transform(
                        utils::createScaleShearXRotateTranslateB2DHomMatrix(
                            fHalfLineWidth, fHalfLineWidth,
                            0.0,
                            fAngle - F_PI2,
                            rEdge.getEndPoint().getX(), rEdge.getEndPoint().getY()));
                    aEdgePolygon.append(aEndPolygon);
                }
                else
                {
                    if(!bPerpend)
                    {
                        aPerpend.setX(-aTangent.getY());
                        aPerpend.setY(aTangent.getX());
                    }

                    if(bEndSquare)
                    {
                        const basegfx::B2DPoint aEnd(rEdge.getEndPoint() + aTangent);

                        aEdgePolygon.append(aEnd - aPerpend);
                        aEdgePolygon.append(aEnd + aPerpend);
                    }
                    else
                    {
                        aEdgePolygon.append(rEdge.getEndPoint() - aPerpend);
                        aEdgePolygon.append(rEdge.getEndPoint()); // keep the in-between point for numerical reasons
                        aEdgePolygon.append(rEdge.getEndPoint() + aPerpend);
                    }
                }

                // close and return
                aEdgePolygon.setClosed(true);

                if(nullptr != pTriangles)
                {
                    const basegfx::triangulator::B2DTriangleVector aResult(
                        basegfx::triangulator::triangulate(
                            aEdgePolygon));
                    pTriangles->insert(pTriangles->end(), aResult.begin(), aResult.end());
                    aEdgePolygon.clear();
                }

                return aEdgePolygon;
            }
        }

        B2DPolygon createAreaGeometryForJoin(
            const B2DVector& rTangentPrev,
            const B2DVector& rTangentEdge,
            const B2DVector& rPerpendPrev,
            const B2DVector& rPerpendEdge,
            const B2DPoint& rPoint,
            double fHalfLineWidth,
            B2DLineJoin eJoin,
            double fMiterMinimumAngle,
            basegfx::triangulator::B2DTriangleVector* pTriangles)
        {
            assert((fHalfLineWidth > 0.0) && "createAreaGeometryForJoin: LineWidth too small (!)");
            assert((eJoin != B2DLineJoin::NONE) && "createAreaGeometryForJoin: B2DLineJoin::NONE not allowed (!)");

            // LineJoin from tangent rPerpendPrev to tangent rPerpendEdge in rPoint
            B2DPolygon aEdgePolygon;
            const B2DPoint aStartPoint(rPoint + rPerpendPrev);
            const B2DPoint aEndPoint(rPoint + rPerpendEdge);

            // test if for Miter, the angle is too small and the fallback
            // to bevel needs to be used
            if(eJoin == B2DLineJoin::Miter)
            {
                const double fAngle(fabs(rPerpendPrev.angle(rPerpendEdge)));

                if((F_PI - fAngle) < fMiterMinimumAngle)
                {
                    // fallback to bevel
                    eJoin = B2DLineJoin::Bevel;
                }
            }

            switch(eJoin)
            {
                case B2DLineJoin::Miter :
                {
                    if(nullptr != pTriangles)
                    {
                        pTriangles->emplace_back(
                            aEndPoint,
                            rPoint,
                            aStartPoint);
                    }
                    else
                    {
                        aEdgePolygon.append(aEndPoint);
                        aEdgePolygon.append(rPoint);
                        aEdgePolygon.append(aStartPoint);
                    }

                    // Look for the cut point between start point along rTangentPrev and
                    // end point along rTangentEdge. -rTangentEdge should be used, but since
                    // the cut value is used for interpolating along the first edge, the negation
                    // is not needed since the same fCut will be found on the first edge.
                    // If it exists, insert it to complete the mitered fill polygon.
                    double fCutPos(0.0);
                    utils::findCut(aStartPoint, rTangentPrev, aEndPoint, rTangentEdge, CutFlagValue::ALL, &fCutPos);

                    if(fCutPos != 0.0)
                    {
                        const B2DPoint aCutPoint(aStartPoint + (rTangentPrev * fCutPos));

                        if(nullptr != pTriangles)
                        {
                            pTriangles->emplace_back(
                                aStartPoint,
                                aCutPoint,
                                aEndPoint);
                        }
                        else
                        {
                            aEdgePolygon.append(aCutPoint);
                        }
                    }

                    break;
                }
                case B2DLineJoin::Round :
                {
                    // use tooling to add needed EllipseSegment
                    double fAngleStart(atan2(rPerpendPrev.getY(), rPerpendPrev.getX()));
                    double fAngleEnd(atan2(rPerpendEdge.getY(), rPerpendEdge.getX()));

                    // atan2 results are [-PI .. PI], consolidate to [0.0 .. 2PI]
                    if(fAngleStart < 0.0)
                    {
                        fAngleStart += F_2PI;
                    }

                    if(fAngleEnd < 0.0)
                    {
                        fAngleEnd += F_2PI;
                    }

                    const B2DPolygon aBow(utils::createPolygonFromEllipseSegment(rPoint, fHalfLineWidth, fHalfLineWidth, fAngleStart, fAngleEnd));

                    if(aBow.count() > 1)
                    {
                        if(nullptr != pTriangles)
                        {
                            for(sal_uInt32 a(0); a < aBow.count() - 1; a++)
                            {
                                pTriangles->emplace_back(
                                    0 == a ? aStartPoint : aBow.getB2DPoint(a),
                                    rPoint,
                                    aBow.count() - 1 == a + 1 ? aEndPoint : aBow.getB2DPoint(a + 1));
                            }
                        }
                        else
                        {
                            // #i101491#
                            // use the original start/end positions; the ones from bow creation may be numerically
                            // different due to their different creation. To guarantee good merging quality with edges
                            // and edge roundings (and to reduce point count)
                            aEdgePolygon = aBow;
                            aEdgePolygon.setB2DPoint(0, aStartPoint);
                            aEdgePolygon.setB2DPoint(aEdgePolygon.count() - 1, aEndPoint);
                            aEdgePolygon.append(rPoint);
                        }

                        break;
                    }
                    else
                    {
                        [[fallthrough]]; // wanted fall-through to default
                    }
                }
                default: // B2DLineJoin::Bevel
                {
                    if(nullptr != pTriangles)
                    {
                        pTriangles->emplace_back(
                            aEndPoint,
                            rPoint,
                            aStartPoint);
                    }
                    else
                    {
                        aEdgePolygon.append(aEndPoint);
                        aEdgePolygon.append(rPoint);
                        aEdgePolygon.append(aStartPoint);
                    }

                    break;
                }
            }

            // create last polygon part for edge
            aEdgePolygon.setClosed(true);

            return aEdgePolygon;
        }
    } // end of anonymous namespace

    namespace utils
    {
        B2DPolyPolygon createAreaGeometry(
            const B2DPolygon& rCandidate,
            double fHalfLineWidth,
            B2DLineJoin eJoin,
            css::drawing::LineCap eCap,
            double fMaxAllowedAngle,
            double fMaxPartOfEdge,
            double fMiterMinimumAngle,
            basegfx::triangulator::B2DTriangleVector* pTriangles)
        {
            if(fMaxAllowedAngle > F_PI2)
            {
                fMaxAllowedAngle = F_PI2;
            }
            else if(fMaxAllowedAngle < 0.01 * F_PI2)
            {
                fMaxAllowedAngle = 0.01 * F_PI2;
            }

            if(fMaxPartOfEdge > 1.0)
            {
                fMaxPartOfEdge = 1.0;
            }
            else if(fMaxPartOfEdge < 0.01)
            {
                fMaxPartOfEdge = 0.01;
            }

            if(fMiterMinimumAngle > F_PI)
            {
                fMiterMinimumAngle = F_PI;
            }
            else if(fMiterMinimumAngle < 0.01 * F_PI)
            {
                fMiterMinimumAngle = 0.01 * F_PI;
            }

            B2DPolygon aCandidate(rCandidate);
            const double fMaxCos(cos(fMaxAllowedAngle));

            aCandidate.removeDoublePoints();
            aCandidate = subdivideToSimple(aCandidate, fMaxCos * fMaxCos, fMaxPartOfEdge * fMaxPartOfEdge);

            const sal_uInt32 nPointCount(aCandidate.count());

            if(nPointCount)
            {
                B2DPolyPolygon aRetval;
                const bool bIsClosed(aCandidate.isClosed());
                const sal_uInt32 nEdgeCount(bIsClosed ? nPointCount : nPointCount - 1);
                const bool bLineCap(!bIsClosed && eCap != css::drawing::LineCap_BUTT);

                if(nEdgeCount)
                {
                    B2DCubicBezier aEdge;
                    B2DCubicBezier aPrev;

                    const bool bEventuallyCreateLineJoin(eJoin != B2DLineJoin::NONE);
                    // prepare edge
                    aEdge.setStartPoint(aCandidate.getB2DPoint(0));

                    if(bIsClosed && bEventuallyCreateLineJoin)
                    {
                        // prepare previous edge
                        const sal_uInt32 nPrevIndex(nPointCount - 1);
                        aPrev.setStartPoint(aCandidate.getB2DPoint(nPrevIndex));
                        aPrev.setControlPointA(aCandidate.getNextControlPoint(nPrevIndex));
                        aPrev.setControlPointB(aCandidate.getPrevControlPoint(0));
                        aPrev.setEndPoint(aEdge.getStartPoint());
                    }

                    for(sal_uInt32 a(0); a < nEdgeCount; a++)
                    {
                        // fill current Edge
                        const sal_uInt32 nNextIndex((a + 1) % nPointCount);
                        aEdge.setControlPointA(aCandidate.getNextControlPoint(a));
                        aEdge.setControlPointB(aCandidate.getPrevControlPoint(nNextIndex));
                        aEdge.setEndPoint(aCandidate.getB2DPoint(nNextIndex));

                        // check and create linejoin
                        if(bEventuallyCreateLineJoin && (bIsClosed || a != 0))
                        {
                            B2DVector aTangentPrev(aPrev.getTangent(1.0)); aTangentPrev.normalize();
                            B2DVector aTangentEdge(aEdge.getTangent(0.0)); aTangentEdge.normalize();
                            B2VectorOrientation aOrientation(getOrientation(aTangentPrev, aTangentEdge));

                            if(aOrientation == B2VectorOrientation::Neutral)
                            {
                                   // they are parallel or empty; if they are both not zero and point
                                   // in opposite direction, a half-circle is needed
                                   if(!aTangentPrev.equalZero() && !aTangentEdge.equalZero())
                                   {
                                    const double fAngle(fabs(aTangentPrev.angle(aTangentEdge)));

                                    if(fTools::equal(fAngle, F_PI))
                                    {
                                        // for half-circle production, fallback to positive
                                        // orientation
                                        aOrientation = B2VectorOrientation::Positive;
                                    }
                                }
                            }

                            if(aOrientation == B2VectorOrientation::Positive)
                            {
                                const B2DVector aPerpendPrev(getPerpendicular(aTangentPrev) * -fHalfLineWidth);
                                const B2DVector aPerpendEdge(getPerpendicular(aTangentEdge) * -fHalfLineWidth);

                                aRetval.append(
                                    createAreaGeometryForJoin(
                                        aTangentPrev,
                                        aTangentEdge,
                                        aPerpendPrev,
                                        aPerpendEdge,
                                        aEdge.getStartPoint(),
                                        fHalfLineWidth,
                                        eJoin,
                                        fMiterMinimumAngle,
                                        pTriangles));
                            }
                            else if(aOrientation == B2VectorOrientation::Negative)
                            {
                                const B2DVector aPerpendPrev(getPerpendicular(aTangentPrev) * fHalfLineWidth);
                                const B2DVector aPerpendEdge(getPerpendicular(aTangentEdge) * fHalfLineWidth);

                                aRetval.append(
                                    createAreaGeometryForJoin(
                                        aTangentEdge,
                                        aTangentPrev,
                                        aPerpendEdge,
                                        aPerpendPrev,
                                        aEdge.getStartPoint(),
                                        fHalfLineWidth,
                                        eJoin,
                                        fMiterMinimumAngle,
                                        pTriangles));
                            }
                        }

                        // create geometry for edge
                        const bool bLast(a + 1 == nEdgeCount);

                        if(bLineCap)
                        {
                            const bool bFirst(!a);

                            aRetval.append(
                                createAreaGeometryForEdge(
                                    aEdge,
                                    fHalfLineWidth,
                                    bFirst && eCap == css::drawing::LineCap_ROUND,
                                    bLast && eCap == css::drawing::LineCap_ROUND,
                                    bFirst && eCap == css::drawing::LineCap_SQUARE,
                                    bLast && eCap == css::drawing::LineCap_SQUARE,
                                    pTriangles));
                        }
                        else
                        {
                            aRetval.append(
                                createAreaGeometryForEdge(
                                    aEdge,
                                    fHalfLineWidth,
                                    false,
                                    false,
                                    false,
                                    false,
                                    pTriangles));
                        }

                        // prepare next step
                        if(!bLast)
                        {
                            if(bEventuallyCreateLineJoin)
                            {
                                aPrev = aEdge;
                            }

                            aEdge.setStartPoint(aEdge.getEndPoint());
                        }
                    }
                }
                else
                {
                    // point count, but no edge count -> single point
                    const basegfx::B2DPolygon aCircle(
                        createPolygonFromCircle(
                            aCandidate.getB2DPoint(0),
                            fHalfLineWidth));

                    if(nullptr != pTriangles)
                    {
                        const basegfx::triangulator::B2DTriangleVector aResult(
                            basegfx::triangulator::triangulate(
                                aCircle));
                        pTriangles->insert(pTriangles->end(), aResult.begin(), aResult.end());
                    }
                    else
                    {
                        aRetval.append(aCircle);
                    }
                }

                return aRetval;
            }
            else
            {
                return B2DPolyPolygon(rCandidate);
            }
        }
    } // end of namespace utils
} // end of namespace basegfx

/* vim:set shiftwidth=4 softtabstop=4 expandtab: */