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