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