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