basegfx/source/polygon/b2dlinegeometry.cxx

   1 /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
   2 /*
   3  * This file is part of the LibreOffice project.
   4  *
   5  * This Source Code Form is subject to the terms of the Mozilla Public
   6  * License, v. 2.0. If a copy of the MPL was not distributed with this
   7  * file, You can obtain one at http://mozilla.org/MPL/2.0/.
   8  *
   9  * This file incorporates work covered by the following license notice:
  10  *
  11  *   Licensed to the Apache Software Foundation (ASF) under one or more
  12  *   contributor license agreements. See the NOTICE file distributed
  13  *   with this work for additional information regarding copyright
  14  *   ownership. The ASF licenses this file to you under the Apache
  15  *   License, Version 2.0 (the "License"); you may not use this file
  16  *   except in compliance with the License. You may obtain a copy of
  17  *   the License at http://www.apache.org/licenses/LICENSE-2.0 .
  18  */
  19
  20 #include <osl/diagnose.h>
  21 #include <sal/log.hxx>
  22 #include <basegfx/polygon/b2dlinegeometry.hxx>
  23 #include <basegfx/point/b2dpoint.hxx>
  24 #include <basegfx/vector/b2dvector.hxx>
  25 #include <basegfx/polygon/b2dpolygontools.hxx>
  26 #include <basegfx/polygon/b2dpolypolygontools.hxx>
  27 #include <basegfx/range/b2drange.hxx>
  28 #include <basegfx/matrix/b2dhommatrix.hxx>
  29 #include <basegfx/curve/b2dcubicbezier.hxx>
  30 #include <basegfx/matrix/b2dhommatrixtools.hxx>
  31 #include <com/sun/star/drawing/LineCap.hpp>
  32 #include <basegfx/polygon/b2dpolypolygoncutter.hxx>
  33 #include <basegfx/polygon/b2dpolygontriangulator.hxx>
  34
  35 namespace basegfx::utils
  36 {
  37         B2DPolyPolygon createAreaGeometryForLineStartEnd(
  38             const B2DPolygon& rCandidate,
  39             const B2DPolyPolygon& rArrow,
  40             bool bStart,
  41             double fWidth,
  42             double fCandidateLength,
  43             double fDockingPosition, // 0->top, 1->bottom
  44             double* pConsumedLength,
  45             double fShift)
  46         {
  47             B2DPolyPolygon aRetval;
  48             assert((rCandidate.count() > 1) && "createAreaGeometryForLineStartEnd: Line polygon has too few points");
  49             assert((rArrow.count() > 0) && "createAreaGeometryForLineStartEnd: Empty arrow utils::PolyPolygon");
  50             assert((fWidth > 0.0) && "createAreaGeometryForLineStartEnd: Width too small");
  51             assert((fDockingPosition >= 0.0 && fDockingPosition <= 1.0) &&
  52                 "createAreaGeometryForLineStartEnd: fDockingPosition out of range [0.0 .. 1.0]");
  53
  54             if(fWidth < 0.0)
  55             {
  56                 fWidth = -fWidth;
  57             }
  58
  59             if(rCandidate.count() > 1 && rArrow.count() && !fTools::equalZero(fWidth))
  60             {
  61                 if(fDockingPosition < 0.0)
  62                 {
  63                     fDockingPosition = 0.0;
  64                 }
  65                 else if(fDockingPosition > 1.0)
  66                 {
  67                     fDockingPosition = 1.0;
  68                 }
  69
  70                 // init return value from arrow
  71                 aRetval.append(rArrow);
  72
  73                 // get size of the arrow
  74                 const B2DRange aArrowSize(getRange(rArrow));
  75
  76                 // build ArrowTransform; center in X, align with axis in Y
  77                 B2DHomMatrix aArrowTransform(basegfx::utils::createTranslateB2DHomMatrix(
  78                     -aArrowSize.getCenter().getX(), -aArrowSize.getMinimum().getY()));
  79
  80                 // scale to target size
  81                 const double fArrowScale(fWidth / (aArrowSize.getWidth()));
  82                 aArrowTransform.scale(fArrowScale, fArrowScale);
  83
  84                 // get arrow size in Y
  85                 B2DPoint aUpperCenter(aArrowSize.getCenter().getX(), aArrowSize.getMaximum().getY());
  86                 aUpperCenter *= aArrowTransform;
  87                 const double fArrowYLength(B2DVector(aUpperCenter).getLength());
  88
  89                 // move arrow to have docking position centered
  90                 aArrowTransform.translate(0.0, -fArrowYLength * fDockingPosition + fShift);
  91
  92                 // prepare polygon length
  93                 if(fTools::equalZero(fCandidateLength))
  94                 {
  95                     fCandidateLength = getLength(rCandidate);
  96                 }
  97
  98                 // get the polygon vector we want to plant this arrow on
  99                 const double fConsumedLength(fArrowYLength * (1.0 - fDockingPosition) - fShift);
 100                 const B2DVector aHead(rCandidate.getB2DPoint(bStart ? 0 : rCandidate.count() - 1));
 101                 const B2DVector aTail(getPositionAbsolute(rCandidate,
 102                     bStart ? fConsumedLength : fCandidateLength - fConsumedLength, fCandidateLength));
 103
 104                 // from that vector, take the needed rotation and add rotate for arrow to transformation
 105                 const B2DVector aTargetDirection(aHead - aTail);
 106                 const double fRotation(atan2(aTargetDirection.getY(), aTargetDirection.getX()) + M_PI_2);
 107
 108                 // rotate around docking position
 109                 aArrowTransform.rotate(fRotation);
 110
 111                 // move arrow docking position to polygon head
 112                 aArrowTransform.translate(aHead.getX(), aHead.getY());
 113
 114                 // transform retval and close
 115                 aRetval.transform(aArrowTransform);
 116                 aRetval.setClosed(true);
 117
 118                 // if pConsumedLength is asked for, fill it
 119                 if(pConsumedLength)
 120                 {
 121                     *pConsumedLength = fConsumedLength;
 122                 }
 123             }
 124
 125             return aRetval;
 126         }
 127 } // end of namespace
 128
 129 namespace basegfx
 130 {
 131     // anonymous namespace for local helpers
 132     namespace
 133     {
 134         bool impIsSimpleEdge(const B2DCubicBezier& rCandidate, double fMaxCosQuad, double fMaxPartOfEdgeQuad)
 135         {
 136             // isBezier() is true, already tested by caller
 137             const B2DVector aEdge(rCandidate.getEndPoint() - rCandidate.getStartPoint());
 138
 139             if(aEdge.equalZero())
 140             {
 141                 // start and end point the same, but control vectors used -> balloon curve loop
 142                 // is not a simple edge
 143                 return false;
 144             }
 145
 146             // get tangentA and scalar with edge
 147             const B2DVector aTangentA(rCandidate.getTangent(0.0));
 148             const double fScalarAE(aEdge.scalar(aTangentA));
 149
 150             if(fScalarAE <= 0.0)
 151             {
 152                 // angle between TangentA and Edge is bigger or equal 90 degrees
 153                 return false;
 154             }
 155
 156             // get self-scalars for E and A
 157             const double fScalarE(aEdge.scalar(aEdge));
 158             const double fScalarA(aTangentA.scalar(aTangentA));
 159             const double fLengthCompareE(fScalarE * fMaxPartOfEdgeQuad);
 160
 161             if(fTools::moreOrEqual(fScalarA, fLengthCompareE))
 162             {
 163                 // length of TangentA is more than fMaxPartOfEdge of length of edge
 164                 return false;
 165             }
 166
 167             if(fTools::lessOrEqual(fScalarAE * fScalarAE, fScalarA * fScalarE * fMaxCosQuad))
 168             {
 169                 // angle between TangentA and Edge is bigger or equal angle defined by fMaxCos
 170                 return false;
 171             }
 172
 173             // get tangentB and scalar with edge
 174             const B2DVector aTangentB(rCandidate.getTangent(1.0));
 175             const double fScalarBE(aEdge.scalar(aTangentB));
 176
 177             if(fScalarBE <= 0.0)
 178             {
 179                 // angle between TangentB and Edge is bigger or equal 90 degrees
 180                 return false;
 181             }
 182
 183             // get self-scalar for B
 184             const double fScalarB(aTangentB.scalar(aTangentB));
 185
 186             if(fTools::moreOrEqual(fScalarB, fLengthCompareE))
 187             {
 188                 // length of TangentB is more than fMaxPartOfEdge of length of edge
 189                 return false;
 190             }
 191
 192             if(fTools::lessOrEqual(fScalarBE * fScalarBE, fScalarB * fScalarE * fMaxCosQuad))
 193             {
 194                 // angle between TangentB and Edge is bigger or equal defined by fMaxCos
 195                 return false;
 196             }
 197
 198             return true;
 199         }
 200
 201         void impSubdivideToSimple(const B2DCubicBezier& rCandidate, B2DPolygon& rTarget, double fMaxCosQuad, double fMaxPartOfEdgeQuad, sal_uInt32 nMaxRecursionDepth)
 202         {
 203             if(!nMaxRecursionDepth || impIsSimpleEdge(rCandidate, fMaxCosQuad, fMaxPartOfEdgeQuad))
 204             {
 205                 rTarget.appendBezierSegment(rCandidate.getControlPointA(), rCandidate.getControlPointB(), rCandidate.getEndPoint());
 206             }
 207             else
 208             {
 209                 B2DCubicBezier aLeft, aRight;
 210                 rCandidate.split(0.5, &aLeft, &aRight);
 211
 212                 impSubdivideToSimple(aLeft, rTarget, fMaxCosQuad, fMaxPartOfEdgeQuad, nMaxRecursionDepth - 1);
 213                 impSubdivideToSimple(aRight, rTarget, fMaxCosQuad, fMaxPartOfEdgeQuad, nMaxRecursionDepth - 1);
 214             }
 215         }
 216
 217         B2DPolygon subdivideToSimple(const B2DPolygon& rCandidate, double fMaxCosQuad, double fMaxPartOfEdgeQuad)
 218         {
 219             const sal_uInt32 nPointCount(rCandidate.count());
 220
 221             if(rCandidate.areControlPointsUsed() && nPointCount)
 222             {
 223                 const sal_uInt32 nEdgeCount(rCandidate.isClosed() ? nPointCount : nPointCount - 1);
 224                 B2DPolygon aRetval;
 225                 B2DCubicBezier aEdge;
 226
 227                 // prepare edge for loop
 228                 aEdge.setStartPoint(rCandidate.getB2DPoint(0));
 229                 aRetval.append(aEdge.getStartPoint());
 230
 231                 for(sal_uInt32 a(0); a < nEdgeCount; a++)
 232                 {
 233                     // fill B2DCubicBezier
 234                     const sal_uInt32 nNextIndex((a + 1) % nPointCount);
 235                     aEdge.setControlPointA(rCandidate.getNextControlPoint(a));
 236                     aEdge.setControlPointB(rCandidate.getPrevControlPoint(nNextIndex));
 237                     aEdge.setEndPoint(rCandidate.getB2DPoint(nNextIndex));
 238
 239                     // get rid of unnecessary bezier segments
 240                     aEdge.testAndSolveTrivialBezier();
 241
 242                     if(aEdge.isBezier())
 243                     {
 244                         // before splitting recursively with internal simple criteria, use
 245                         // ExtremumPosFinder to remove those
 246                         std::vector< double > aExtremumPositions;
 247
 248                         aExtremumPositions.reserve(4);
 249                         aEdge.getAllExtremumPositions(aExtremumPositions);
 250
 251                         const sal_uInt32 nCount(aExtremumPositions.size());
 252
 253                         if(nCount)
 254                         {
 255                             if(nCount > 1)
 256                             {
 257                                 // create order from left to right
 258                                 std::sort(aExtremumPositions.begin(), aExtremumPositions.end());
 259                             }
 260
 261                             for(sal_uInt32 b(0); b < nCount;)
 262                             {
 263                                 // split aEdge at next split pos
 264                                 B2DCubicBezier aLeft;
 265                                 const double fSplitPos(aExtremumPositions[b++]);
 266
 267                                 aEdge.split(fSplitPos, &aLeft, &aEdge);
 268                                 aLeft.testAndSolveTrivialBezier();
 269
 270                                 // consume left part
 271                                 if(aLeft.isBezier())
 272                                 {
 273                                     impSubdivideToSimple(aLeft, aRetval, fMaxCosQuad, fMaxPartOfEdgeQuad, 6);
 274                                 }
 275                                 else
 276                                 {
 277                                     aRetval.append(aLeft.getEndPoint());
 278                                 }
 279
 280                                 if(b < nCount)
 281                                 {
 282                                     // correct the remaining split positions to fit to shortened aEdge
 283                                     const double fScaleFactor(1.0 / (1.0 - fSplitPos));
 284
 285                                     for(sal_uInt32 c(b); c < nCount; c++)
 286                                     {
 287                                         aExtremumPositions[c] = (aExtremumPositions[c] - fSplitPos) * fScaleFactor;
 288                                     }
 289                                 }
 290                             }
 291
 292                             // test the shortened rest of aEdge
 293                             aEdge.testAndSolveTrivialBezier();
 294
 295                             // consume right part
 296                             if(aEdge.isBezier())
 297                             {
 298                                 impSubdivideToSimple(aEdge, aRetval, fMaxCosQuad, fMaxPartOfEdgeQuad, 6);
 299                             }
 300                             else
 301                             {
 302                                 aRetval.append(aEdge.getEndPoint());
 303                             }
 304                         }
 305                         else
 306                         {
 307                             impSubdivideToSimple(aEdge, aRetval, fMaxCosQuad, fMaxPartOfEdgeQuad, 6);
 308                         }
 309                     }
 310                     else
 311                     {
 312                         // straight edge, add point
 313                         aRetval.append(aEdge.getEndPoint());
 314                     }
 315
 316                     // prepare edge for next step
 317                     aEdge.setStartPoint(aEdge.getEndPoint());
 318                 }
 319
 320                 // copy closed flag and check for double points
 321                 aRetval.setClosed(rCandidate.isClosed());
 322                 aRetval.removeDoublePoints();
 323
 324                 return aRetval;
 325             }
 326             else
 327             {
 328                 return rCandidate;
 329             }
 330         }
 331
 332         B2DPolygon createAreaGeometryForEdge(
 333             const B2DCubicBezier& rEdge,
 334             double fHalfLineWidth,
 335             bool bStartRound,
 336             bool bEndRound,
 337             bool bStartSquare,
 338             bool bEndSquare)
 339         {
 340             // create polygon for edge
 341             // Unfortunately, while it would be geometrically correct to not add
 342             // the in-between points EdgeEnd and EdgeStart, it leads to rounding
 343             // errors when converting to integer polygon coordinates for painting
 344             if(rEdge.isBezier())
 345             {
 346                 // prepare target and data common for upper and lower
 347                 B2DPolygon aBezierPolygon;
 348                 const B2DVector aPureEdgeVector(rEdge.getEndPoint() - rEdge.getStartPoint());
 349                 const double fEdgeLength(aPureEdgeVector.getLength());
 350                 const bool bIsEdgeLengthZero(fTools::equalZero(fEdgeLength));
 351                 B2DVector aTangentA(rEdge.getTangent(0.0)); aTangentA.normalize();
 352                 B2DVector aTangentB(rEdge.getTangent(1.0)); aTangentB.normalize();
 353                 const B2DVector aNormalizedPerpendicularA(getPerpendicular(aTangentA));
 354                 const B2DVector aNormalizedPerpendicularB(getPerpendicular(aTangentB));
 355
 356                 // create upper displacement vectors and check if they cut
 357                 const B2DVector aPerpendStartA(aNormalizedPerpendicularA * -fHalfLineWidth);
 358                 const B2DVector aPerpendEndA(aNormalizedPerpendicularB * -fHalfLineWidth);
 359                 double fCutA(0.0);
 360                 const CutFlagValue aCutA(utils::findCut(
 361                     rEdge.getStartPoint(), aPerpendStartA,
 362                     rEdge.getEndPoint(), aPerpendEndA,
 363                     CutFlagValue::ALL, &fCutA));
 364                 const bool bCutA(aCutA != CutFlagValue::NONE);
 365
 366                 // create lower displacement vectors and check if they cut
 367                 const B2DVector aPerpendStartB(aNormalizedPerpendicularA * fHalfLineWidth);
 368                 const B2DVector aPerpendEndB(aNormalizedPerpendicularB * fHalfLineWidth);
 369                 double fCutB(0.0);
 370                 const CutFlagValue aCutB(utils::findCut(
 371                     rEdge.getEndPoint(), aPerpendEndB,
 372                     rEdge.getStartPoint(), aPerpendStartB,
 373                     CutFlagValue::ALL, &fCutB));
 374                 const bool bCutB(aCutB != CutFlagValue::NONE);
 375
 376                 // check if cut happens
 377                 const bool bCut(bCutA || bCutB);
 378                 B2DPoint aCutPoint;
 379
 380                 // create left edge
 381                 if(bStartRound || bStartSquare)
 382                 {
 383                     if(bStartRound)
 384                     {
 385                         basegfx::B2DPolygon aStartPolygon(utils::createHalfUnitCircle());
 386
 387                         aStartPolygon.transform(
 388                             utils::createScaleShearXRotateTranslateB2DHomMatrix(
 389                                 fHalfLineWidth, fHalfLineWidth,
 390                                 0.0,
 391                                 atan2(aTangentA.getY(), aTangentA.getX()) + M_PI_2,
 392                                 rEdge.getStartPoint().getX(), rEdge.getStartPoint().getY()));
 393                         aBezierPolygon.append(aStartPolygon);
 394                     }
 395                     else // bStartSquare
 396                     {
 397                         const basegfx::B2DPoint aStart(rEdge.getStartPoint() - (aTangentA * fHalfLineWidth));
 398
 399                         if(bCutB)
 400                         {
 401                             aBezierPolygon.append(rEdge.getStartPoint() + aPerpendStartB);
 402                         }
 403
 404                         aBezierPolygon.append(aStart + aPerpendStartB);
 405                         aBezierPolygon.append(aStart + aPerpendStartA);
 406
 407                         if(bCutA)
 408                         {
 409                             aBezierPolygon.append(rEdge.getStartPoint() + aPerpendStartA);
 410                         }
 411                     }
 412                 }
 413                 else
 414                 {
 415                     // append original in-between point
 416                     aBezierPolygon.append(rEdge.getStartPoint());
 417                 }
 418
 419                 // create upper edge.
 420                 {
 421                     if(bCutA)
 422                     {
 423                         // calculate cut point and add
 424                         aCutPoint = rEdge.getStartPoint() + (aPerpendStartA * fCutA);
 425                         aBezierPolygon.append(aCutPoint);
 426                     }
 427                     else
 428                     {
 429                         // create scaled bezier segment
 430                         const B2DPoint aStart(rEdge.getStartPoint() + aPerpendStartA);
 431                         const B2DPoint aEnd(rEdge.getEndPoint() + aPerpendEndA);
 432                         const B2DVector aEdge(aEnd - aStart);
 433                         const double fLength(aEdge.getLength());
 434                         const double fScale(bIsEdgeLengthZero ? 1.0 : fLength / fEdgeLength);
 435                         const B2DVector fRelNext(rEdge.getControlPointA() - rEdge.getStartPoint());
 436                         const B2DVector fRelPrev(rEdge.getControlPointB() - rEdge.getEndPoint());
 437
 438                         aBezierPolygon.append(aStart);
 439                         aBezierPolygon.appendBezierSegment(aStart + (fRelNext * fScale), aEnd + (fRelPrev * fScale), aEnd);
 440                     }
 441                 }
 442
 443                 // create right edge
 444                 if(bEndRound || bEndSquare)
 445                 {
 446                     if(bEndRound)
 447                     {
 448                         basegfx::B2DPolygon aEndPolygon(utils::createHalfUnitCircle());
 449
 450                         aEndPolygon.transform(
 451                             utils::createScaleShearXRotateTranslateB2DHomMatrix(
 452                                 fHalfLineWidth, fHalfLineWidth,
 453                                 0.0,
 454                                 atan2(aTangentB.getY(), aTangentB.getX()) - M_PI_2,
 455                                 rEdge.getEndPoint().getX(), rEdge.getEndPoint().getY()));
 456                         aBezierPolygon.append(aEndPolygon);
 457                     }
 458                     else // bEndSquare
 459                     {
 460                         const basegfx::B2DPoint aEnd(rEdge.getEndPoint() + (aTangentB * fHalfLineWidth));
 461
 462                         if(bCutA)
 463                         {
 464                             aBezierPolygon.append(rEdge.getEndPoint() + aPerpendEndA);
 465                         }
 466
 467                         aBezierPolygon.append(aEnd + aPerpendEndA);
 468                         aBezierPolygon.append(aEnd + aPerpendEndB);
 469
 470                         if(bCutB)
 471                         {
 472                             aBezierPolygon.append(rEdge.getEndPoint() + aPerpendEndB);
 473                         }
 474                     }
 475                 }
 476                 else
 477                 {
 478                     // append original in-between point
 479                     aBezierPolygon.append(rEdge.getEndPoint());
 480                 }
 481
 482                 // create lower edge.
 483                 {
 484                     if(bCutB)
 485                     {
 486                         // calculate cut point and add
 487                         aCutPoint = rEdge.getEndPoint() + (aPerpendEndB * fCutB);
 488                         aBezierPolygon.append(aCutPoint);
 489                     }
 490                     else
 491                     {
 492                         // create scaled bezier segment
 493                         const B2DPoint aStart(rEdge.getEndPoint() + aPerpendEndB);
 494                         const B2DPoint aEnd(rEdge.getStartPoint() + aPerpendStartB);
 495                         const B2DVector aEdge(aEnd - aStart);
 496                         const double fLength(aEdge.getLength());
 497                         const double fScale(bIsEdgeLengthZero ? 1.0 : fLength / fEdgeLength);
 498                         const B2DVector fRelNext(rEdge.getControlPointB() - rEdge.getEndPoint());
 499                         const B2DVector fRelPrev(rEdge.getControlPointA() - rEdge.getStartPoint());
 500
 501                         aBezierPolygon.append(aStart);
 502                         aBezierPolygon.appendBezierSegment(aStart + (fRelNext * fScale), aEnd + (fRelPrev * fScale), aEnd);
 503                     }
 504                 }
 505
 506                 // close
 507                 aBezierPolygon.setClosed(true);
 508
 509                 if(bStartRound || bEndRound)
 510                 {
 511                     // double points possible when round caps are used at start or end
 512                     aBezierPolygon.removeDoublePoints();
 513                 }
 514
 515                 if(bCut && ((bStartRound || bStartSquare) && (bEndRound || bEndSquare)))
 516                 {
 517                     // When cut exists and both ends are extended with caps, a self-intersecting polygon
 518                     // is created; one cut point is known, but there is a 2nd one in the caps geometry.
 519                     // Solve by using tooling.
 520                     // Remark: This nearly never happens due to curve preparations to extreme points
 521                     // and maximum angle turning, but I constructed a test case and checked that it is
 522                     // working properly.
 523                     const B2DPolyPolygon aTemp(utils::solveCrossovers(aBezierPolygon));
 524                     const sal_uInt32 nTempCount(aTemp.count());
 525
 526                     if(nTempCount)
 527                     {
 528                         if(nTempCount > 1)
 529                         {
 530                             // as expected, multiple polygons (with same orientation). Remove
 531                             // the one which contains aCutPoint, or better take the one without
 532                             for (sal_uInt32 a(0); a < nTempCount; a++)
 533                             {
 534                                 aBezierPolygon = aTemp.getB2DPolygon(a);
 535
 536                                 const sal_uInt32 nCandCount(aBezierPolygon.count());
 537
 538                                 for(sal_uInt32 b(0); b < nCandCount; b++)
 539                                 {
 540                                     if(aCutPoint.equal(aBezierPolygon.getB2DPoint(b)))
 541                                     {
 542                                         aBezierPolygon.clear();
 543                                         break;
 544                                     }
 545                                 }
 546
 547                                 if(aBezierPolygon.count())
 548                                 {
 549                                     break;
 550                                 }
 551                             }
 552
 553                             OSL_ENSURE(aBezierPolygon.count(), "Error in line geometry creation, could not solve self-intersection (!)");
 554                         }
 555                         else
 556                         {
 557                             // none found, use result
 558                             aBezierPolygon = aTemp.getB2DPolygon(0);
 559                         }
 560                     }
 561                     else
 562                     {
 563                         OSL_ENSURE(false, "Error in line geometry creation, could not solve self-intersection (!)");
 564                     }
 565                 }
 566
 567                 // return
 568                 return aBezierPolygon;
 569             }
 570             else
 571             {
 572                 // Get start and  end point, create tangent and set to needed length
 573                 B2DVector aTangent(rEdge.getEndPoint() - rEdge.getStartPoint());
 574                 aTangent.setLength(fHalfLineWidth);
 575
 576                 // prepare return value
 577                 B2DPolygon aEdgePolygon;
 578
 579                 // buffered angle
 580                 double fAngle(0.0);
 581                 bool bAngle(false);
 582
 583                 // buffered perpendicular
 584                 B2DVector aPerpend;
 585                 bool bPerpend(false);
 586
 587                 // create left vertical
 588                 if(bStartRound)
 589                 {
 590                     aEdgePolygon = utils::createHalfUnitCircle();
 591                     fAngle = atan2(aTangent.getY(), aTangent.getX());
 592                     bAngle = true;
 593                     aEdgePolygon.transform(
 594                         utils::createScaleShearXRotateTranslateB2DHomMatrix(
 595                             fHalfLineWidth, fHalfLineWidth,
 596                             0.0,
 597                             fAngle + M_PI_2,
 598                             rEdge.getStartPoint().getX(), rEdge.getStartPoint().getY()));
 599                 }
 600                 else
 601                 {
 602                     aPerpend.setX(-aTangent.getY());
 603                     aPerpend.setY(aTangent.getX());
 604                     bPerpend = true;
 605
 606                     if(bStartSquare)
 607                     {
 608                         const basegfx::B2DPoint aStart(rEdge.getStartPoint() - aTangent);
 609
 610                         aEdgePolygon.append(aStart + aPerpend);
 611                         aEdgePolygon.append(aStart - aPerpend);
 612                     }
 613                     else
 614                     {
 615                         aEdgePolygon.append(rEdge.getStartPoint() + aPerpend);
 616                         aEdgePolygon.append(rEdge.getStartPoint()); // keep the in-between point for numerical reasons
 617                         aEdgePolygon.append(rEdge.getStartPoint() - aPerpend);
 618                     }
 619                 }
 620
 621                 // create right vertical
 622                 if(bEndRound)
 623                 {
 624                     basegfx::B2DPolygon aEndPolygon(utils::createHalfUnitCircle());
 625
 626                     if(!bAngle)
 627                     {
 628                         fAngle = atan2(aTangent.getY(), aTangent.getX());
 629                     }
 630
 631                     aEndPolygon.transform(
 632                         utils::createScaleShearXRotateTranslateB2DHomMatrix(
 633                             fHalfLineWidth, fHalfLineWidth,
 634                             0.0,
 635                             fAngle - M_PI_2,
 636                             rEdge.getEndPoint().getX(), rEdge.getEndPoint().getY()));
 637                     aEdgePolygon.append(aEndPolygon);
 638                 }
 639                 else
 640                 {
 641                     if(!bPerpend)
 642                     {
 643                         aPerpend.setX(-aTangent.getY());
 644                         aPerpend.setY(aTangent.getX());
 645                     }
 646
 647                     if(bEndSquare)
 648                     {
 649                         const basegfx::B2DPoint aEnd(rEdge.getEndPoint() + aTangent);
 650
 651                         aEdgePolygon.append(aEnd - aPerpend);
 652                         aEdgePolygon.append(aEnd + aPerpend);
 653                     }
 654                     else
 655                     {
 656                         aEdgePolygon.append(rEdge.getEndPoint() - aPerpend);
 657                         aEdgePolygon.append(rEdge.getEndPoint()); // keep the in-between point for numerical reasons
 658                         aEdgePolygon.append(rEdge.getEndPoint() + aPerpend);
 659                     }
 660                 }
 661
 662                 // close and return
 663                 aEdgePolygon.setClosed(true);
 664
 665                 return aEdgePolygon;
 666             }
 667         }
 668
 669         B2DPolygon createAreaGeometryForJoin(
 670             const B2DVector& rTangentPrev,
 671             const B2DVector& rTangentEdge,
 672             const B2DVector& rPerpendPrev,
 673             const B2DVector& rPerpendEdge,
 674             const B2DPoint& rPoint,
 675             double fHalfLineWidth,
 676             B2DLineJoin eJoin,
 677             double fMiterMinimumAngle)
 678         {
 679             SAL_WARN_IF(fHalfLineWidth <= 0.0,"basegfx","createAreaGeometryForJoin: LineWidth too small (!)");
 680             assert((eJoin != B2DLineJoin::NONE) && "createAreaGeometryForJoin: B2DLineJoin::NONE not allowed (!)");
 681
 682             // LineJoin from tangent rPerpendPrev to tangent rPerpendEdge in rPoint
 683             B2DPolygon aEdgePolygon;
 684             const B2DPoint aStartPoint(rPoint + rPerpendPrev);
 685             const B2DPoint aEndPoint(rPoint + rPerpendEdge);
 686
 687             // test if for Miter, the angle is too small and the fallback
 688             // to bevel needs to be used
 689             if(eJoin == B2DLineJoin::Miter)
 690             {
 691                 const double fAngle(fabs(rPerpendPrev.angle(rPerpendEdge)));
 692
 693                 if((M_PI - fAngle) < fMiterMinimumAngle)
 694                 {
 695                     // fallback to bevel
 696                     eJoin = B2DLineJoin::Bevel;
 697                 }
 698             }
 699
 700             switch(eJoin)
 701             {
 702                 case B2DLineJoin::Miter :
 703                 {
 704                     aEdgePolygon.append(aEndPoint);
 705                     aEdgePolygon.append(rPoint);
 706                     aEdgePolygon.append(aStartPoint);
 707
 708                     // Look for the cut point between start point along rTangentPrev and
 709                     // end point along rTangentEdge. -rTangentEdge should be used, but since
 710                     // the cut value is used for interpolating along the first edge, the negation
 711                     // is not needed since the same fCut will be found on the first edge.
 712                     // If it exists, insert it to complete the mitered fill polygon.
 713                     double fCutPos(0.0);
 714                     utils::findCut(aStartPoint, rTangentPrev, aEndPoint, rTangentEdge, CutFlagValue::ALL, &fCutPos);
 715
 716                     if(fCutPos != 0.0)
 717                     {
 718                         const B2DPoint aCutPoint(aStartPoint + (rTangentPrev * fCutPos));
 719                         aEdgePolygon.append(aCutPoint);
 720                     }
 721
 722                     break;
 723                 }
 724                 case B2DLineJoin::Round :
 725                 {
 726                     // use tooling to add needed EllipseSegment
 727                     double fAngleStart(atan2(rPerpendPrev.getY(), rPerpendPrev.getX()));
 728                     double fAngleEnd(atan2(rPerpendEdge.getY(), rPerpendEdge.getX()));
 729
 730                     // atan2 results are [-PI .. PI], consolidate to [0.0 .. 2PI]
 731                     if(fAngleStart < 0.0)
 732                     {
 733                         fAngleStart += 2 * M_PI;
 734                     }
 735
 736                     if(fAngleEnd < 0.0)
 737                     {
 738                         fAngleEnd += 2 * M_PI;
 739                     }
 740
 741                     const B2DPolygon aBow(utils::createPolygonFromEllipseSegment(rPoint, fHalfLineWidth, fHalfLineWidth, fAngleStart, fAngleEnd));
 742
 743                     if(aBow.count() > 1)
 744                     {
 745                         // #i101491#
 746                         // use the original start/end positions; the ones from bow creation may be numerically
 747                         // different due to their different creation. To guarantee good merging quality with edges
 748                         // and edge roundings (and to reduce point count)
 749                         aEdgePolygon = aBow;
 750                         aEdgePolygon.setB2DPoint(0, aStartPoint);
 751                         aEdgePolygon.setB2DPoint(aEdgePolygon.count() - 1, aEndPoint);
 752                         aEdgePolygon.append(rPoint);
 753
 754                         break;
 755                     }
 756                     else
 757                     {
 758                         [[fallthrough]]; // wanted fall-through to default
 759                     }
 760                 }
 761                 default: // B2DLineJoin::Bevel
 762                 {
 763                     aEdgePolygon.append(aEndPoint);
 764                     aEdgePolygon.append(rPoint);
 765                     aEdgePolygon.append(aStartPoint);
 766
 767                     break;
 768                 }
 769             }
 770
 771             // create last polygon part for edge
 772             aEdgePolygon.setClosed(true);
 773
 774             return aEdgePolygon;
 775         }
 776     } // end of anonymous namespace
 777
 778     namespace utils
 779     {
 780         B2DPolyPolygon createAreaGeometry(
 781             const B2DPolygon& rCandidate,
 782             double fHalfLineWidth,
 783             B2DLineJoin eJoin,
 784             css::drawing::LineCap eCap,
 785             double fMaxAllowedAngle,
 786             double fMaxPartOfEdge,
 787             double fMiterMinimumAngle)
 788         {
 789             if(fMaxAllowedAngle > M_PI_2)
 790             {
 791                 fMaxAllowedAngle = M_PI_2;
 792             }
 793             else if(fMaxAllowedAngle < 0.01 * M_PI_2)
 794             {
 795                 fMaxAllowedAngle = 0.01 * M_PI_2;
 796             }
 797
 798             if(fMaxPartOfEdge > 1.0)
 799             {
 800                 fMaxPartOfEdge = 1.0;
 801             }
 802             else if(fMaxPartOfEdge < 0.01)
 803             {
 804                 fMaxPartOfEdge = 0.01;
 805             }
 806
 807             if(fMiterMinimumAngle > M_PI)
 808             {
 809                 fMiterMinimumAngle = M_PI;
 810             }
 811             else if(fMiterMinimumAngle < 0.01 * M_PI)
 812             {
 813                 fMiterMinimumAngle = 0.01 * M_PI;
 814             }
 815
 816             B2DPolygon aCandidate(rCandidate);
 817             const double fMaxCos(cos(fMaxAllowedAngle));
 818
 819             aCandidate.removeDoublePoints();
 820             aCandidate = subdivideToSimple(aCandidate, fMaxCos * fMaxCos, fMaxPartOfEdge * fMaxPartOfEdge);
 821
 822             const sal_uInt32 nPointCount(aCandidate.count());
 823
 824             if(nPointCount)
 825             {
 826                 B2DPolyPolygon aRetval;
 827                 const bool bIsClosed(aCandidate.isClosed());
 828                 const sal_uInt32 nEdgeCount(bIsClosed ? nPointCount : nPointCount - 1);
 829                 const bool bLineCap(!bIsClosed && eCap != css::drawing::LineCap_BUTT);
 830
 831                 if(nEdgeCount)
 832                 {
 833                     B2DCubicBezier aEdge;
 834                     B2DCubicBezier aPrev;
 835
 836                     const bool bEventuallyCreateLineJoin(eJoin != B2DLineJoin::NONE);
 837                     // prepare edge
 838                     aEdge.setStartPoint(aCandidate.getB2DPoint(0));
 839
 840                     if(bIsClosed && bEventuallyCreateLineJoin)
 841                     {
 842                         // prepare previous edge
 843                         const sal_uInt32 nPrevIndex(nPointCount - 1);
 844                         aPrev.setStartPoint(aCandidate.getB2DPoint(nPrevIndex));
 845                         aPrev.setControlPointA(aCandidate.getNextControlPoint(nPrevIndex));
 846                         aPrev.setControlPointB(aCandidate.getPrevControlPoint(0));
 847                         aPrev.setEndPoint(aEdge.getStartPoint());
 848                     }
 849
 850                     for(sal_uInt32 a(0); a < nEdgeCount; a++)
 851                     {
 852                         // fill current Edge
 853                         const sal_uInt32 nNextIndex((a + 1) % nPointCount);
 854                         aEdge.setControlPointA(aCandidate.getNextControlPoint(a));
 855                         aEdge.setControlPointB(aCandidate.getPrevControlPoint(nNextIndex));
 856                         aEdge.setEndPoint(aCandidate.getB2DPoint(nNextIndex));
 857
 858                         // check and create linejoin
 859                         if(bEventuallyCreateLineJoin && (bIsClosed || a != 0))
 860                         {
 861                             B2DVector aTangentPrev(aPrev.getTangent(1.0)); aTangentPrev.normalize();
 862                             B2DVector aTangentEdge(aEdge.getTangent(0.0)); aTangentEdge.normalize();
 863                             B2VectorOrientation aOrientation(getOrientation(aTangentPrev, aTangentEdge));
 864
 865                             if(aOrientation == B2VectorOrientation::Neutral)
 866                             {
 867                                 // they are parallel or empty; if they are both not zero and point
 868                                 // in opposite direction, a half-circle is needed
 869                                 if(!aTangentPrev.equalZero() && !aTangentEdge.equalZero())
 870                                 {
 871                                     const double fAngle(fabs(aTangentPrev.angle(aTangentEdge)));
 872
 873                                     if(fTools::equal(fAngle, M_PI))
 874                                     {
 875                                         // for half-circle production, fallback to positive
 876                                         // orientation
 877                                         aOrientation = B2VectorOrientation::Positive;
 878                                     }
 879                                 }
 880                             }
 881
 882                             if(aOrientation == B2VectorOrientation::Positive)
 883                             {
 884                                 const B2DVector aPerpendPrev(getPerpendicular(aTangentPrev) * -fHalfLineWidth);
 885                                 const B2DVector aPerpendEdge(getPerpendicular(aTangentEdge) * -fHalfLineWidth);
 886
 887                                 aRetval.append(
 888                                     createAreaGeometryForJoin(
 889                                         aTangentPrev,
 890                                         aTangentEdge,
 891                                         aPerpendPrev,
 892                                         aPerpendEdge,
 893                                         aEdge.getStartPoint(),
 894                                         fHalfLineWidth,
 895                                         eJoin,
 896                                         fMiterMinimumAngle));
 897                             }
 898                             else if(aOrientation == B2VectorOrientation::Negative)
 899                             {
 900                                 const B2DVector aPerpendPrev(getPerpendicular(aTangentPrev) * fHalfLineWidth);
 901                                 const B2DVector aPerpendEdge(getPerpendicular(aTangentEdge) * fHalfLineWidth);
 902
 903                                 aRetval.append(
 904                                     createAreaGeometryForJoin(
 905                                         aTangentEdge,
 906                                         aTangentPrev,
 907                                         aPerpendEdge,
 908                                         aPerpendPrev,
 909                                         aEdge.getStartPoint(),
 910                                         fHalfLineWidth,
 911                                         eJoin,
 912                                         fMiterMinimumAngle));
 913                             }
 914                         }
 915
 916                         // create geometry for edge
 917                         const bool bLast(a + 1 == nEdgeCount);
 918
 919                         if(bLineCap)
 920                         {
 921                             const bool bFirst(!a);
 922
 923                             aRetval.append(
 924                                 createAreaGeometryForEdge(
 925                                     aEdge,
 926                                     fHalfLineWidth,
 927                                     bFirst && eCap == css::drawing::LineCap_ROUND,
 928                                     bLast && eCap == css::drawing::LineCap_ROUND,
 929                                     bFirst && eCap == css::drawing::LineCap_SQUARE,
 930                                     bLast && eCap == css::drawing::LineCap_SQUARE));
 931                         }
 932                         else
 933                         {
 934                             aRetval.append(
 935                                 createAreaGeometryForEdge(
 936                                     aEdge,
 937                                     fHalfLineWidth,
 938                                     false,
 939                                     false,
 940                                     false,
 941                                     false));
 942                         }
 943
 944                         // prepare next step
 945                         if(!bLast)
 946                         {
 947                             if(bEventuallyCreateLineJoin)
 948                             {
 949                                 aPrev = aEdge;
 950                             }
 951
 952                             aEdge.setStartPoint(aEdge.getEndPoint());
 953                         }
 954                     }
 955                 }
 956                 else
 957                 {
 958                     // point count, but no edge count -> single point
 959                     const basegfx::B2DPolygon aCircle(
 960                         createPolygonFromCircle(
 961                             aCandidate.getB2DPoint(0),
 962                             fHalfLineWidth));
 963
 964                     aRetval.append(aCircle);
 965                 }
 966
 967                 return aRetval;
 968             }
 969             else
 970             {
 971                 return B2DPolyPolygon(rCandidate);
 972             }
 973         }
 974     } // end of namespace utils
 975 } // end of namespace basegfx
 976
 977 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */