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 <basegfx/numeric/ftools.hxx>
27 #include <basegfx/polygon/b2dpolygontools.hxx>
28 #include <osl/diagnose.h>
29 #include <rtl/math.hxx>
30 #include <basegfx/polygon/b2dpolygon.hxx>
31 #include <basegfx/polygon/b2dpolypolygon.hxx>
32 #include <basegfx/range/b2drange.hxx>
33 #include <basegfx/curve/b2dcubicbezier.hxx>
34 #include <basegfx/polygon/b2dpolypolygoncutter.hxx>
35 #include <basegfx/point/b3dpoint.hxx>
36 #include <basegfx/matrix/b3dhommatrix.hxx>
37 #include <basegfx/matrix/b2dhommatrix.hxx>
38 #include <basegfx/curve/b2dbeziertools.hxx>
39 #include <basegfx/matrix/b2dhommatrixtools.hxx>
40 #include <osl/mutex.hxx>
41 
42 #include <numeric>
43 #include <limits>
44 
45 // #i37443#
46 #define ANGLE_BOUND_START_VALUE		(2.25)
47 #define ANGLE_BOUND_MINIMUM_VALUE	(0.1)
48 #define COUNT_SUBDIVIDE_DEFAULT		(4L)
49 #ifdef DBG_UTIL
50 static double fAngleBoundStartValue = ANGLE_BOUND_START_VALUE;
51 #endif
52 #define STEPSPERQUARTER     (3)
53 
54 //////////////////////////////////////////////////////////////////////////////
55 
56 namespace basegfx
57 {
58 	namespace tools
59 	{
openWithGeometryChange(B2DPolygon & rCandidate)60 		void openWithGeometryChange(B2DPolygon& rCandidate)
61 		{
62 			if(rCandidate.isClosed())
63 			{
64 				if(rCandidate.count())
65 				{
66 					rCandidate.append(rCandidate.getB2DPoint(0));
67 
68 					if(rCandidate.areControlPointsUsed() && rCandidate.isPrevControlPointUsed(0))
69 					{
70 						rCandidate.setPrevControlPoint(rCandidate.count() - 1, rCandidate.getPrevControlPoint(0));
71 						rCandidate.resetPrevControlPoint(0);
72 					}
73 				}
74 
75 				rCandidate.setClosed(false);
76 			}
77 		}
78 
closeWithGeometryChange(B2DPolygon & rCandidate)79 		void closeWithGeometryChange(B2DPolygon& rCandidate)
80 		{
81 			if(!rCandidate.isClosed())
82 			{
83 				while(rCandidate.count() > 1 && rCandidate.getB2DPoint(0) == rCandidate.getB2DPoint(rCandidate.count() - 1))
84 				{
85 					if(rCandidate.areControlPointsUsed() && rCandidate.isPrevControlPointUsed(rCandidate.count() - 1))
86 					{
87 						rCandidate.setPrevControlPoint(0, rCandidate.getPrevControlPoint(rCandidate.count() - 1));
88 					}
89 
90 					rCandidate.remove(rCandidate.count() - 1);
91 				}
92 
93 				rCandidate.setClosed(true);
94 			}
95 		}
96 
checkClosed(B2DPolygon & rCandidate)97 		void checkClosed(B2DPolygon& rCandidate)
98 		{
99 			// #i80172# Removed unnecessary assertion
100 			// OSL_ENSURE(!rCandidate.isClosed(), "checkClosed: already closed (!)");
101 
102 			if(rCandidate.count() > 1 && rCandidate.getB2DPoint(0) == rCandidate.getB2DPoint(rCandidate.count() - 1))
103 			{
104 				closeWithGeometryChange(rCandidate);
105 			}
106 		}
107 
108 		// Get successor and predecessor indices. Returning the same index means there
109 		// is none. Same for successor.
getIndexOfPredecessor(sal_uInt32 nIndex,const B2DPolygon & rCandidate)110 		sal_uInt32 getIndexOfPredecessor(sal_uInt32 nIndex, const B2DPolygon& rCandidate)
111 		{
112 			OSL_ENSURE(nIndex < rCandidate.count(), "getIndexOfPredecessor: Access to polygon out of range (!)");
113 
114 			if(nIndex)
115 			{
116 				return nIndex - 1L;
117 			}
118 			else if(rCandidate.count())
119 			{
120 				return rCandidate.count() - 1L;
121 			}
122 			else
123 			{
124 				return nIndex;
125 			}
126 		}
127 
getIndexOfSuccessor(sal_uInt32 nIndex,const B2DPolygon & rCandidate)128 		sal_uInt32 getIndexOfSuccessor(sal_uInt32 nIndex, const B2DPolygon& rCandidate)
129 		{
130 			OSL_ENSURE(nIndex < rCandidate.count(), "getIndexOfPredecessor: Access to polygon out of range (!)");
131 
132 			if(nIndex + 1L < rCandidate.count())
133 			{
134 				return nIndex + 1L;
135 			}
136 			else if(nIndex + 1L == rCandidate.count())
137 			{
138 				return 0L;
139 			}
140 			else
141 			{
142 				return nIndex;
143 			}
144 		}
145 
getOrientation(const B2DPolygon & rCandidate)146 		B2VectorOrientation getOrientation(const B2DPolygon& rCandidate)
147 		{
148 			B2VectorOrientation eRetval(ORIENTATION_NEUTRAL);
149 
150 			if(rCandidate.count() > 2L || rCandidate.areControlPointsUsed())
151 			{
152 				const double fSignedArea(getSignedArea(rCandidate));
153 
154 				if(fTools::equalZero(fSignedArea))
155 				{
156 					// ORIENTATION_NEUTRAL, already set
157 				}
158 				if(fSignedArea > 0.0)
159 				{
160 					eRetval = ORIENTATION_POSITIVE;
161 				}
162 				else if(fSignedArea < 0.0)
163 				{
164 					eRetval = ORIENTATION_NEGATIVE;
165 				}
166 			}
167 
168 			return eRetval;
169 		}
170 
getContinuityInPoint(const B2DPolygon & rCandidate,sal_uInt32 nIndex)171 		B2VectorContinuity getContinuityInPoint(const B2DPolygon& rCandidate, sal_uInt32 nIndex)
172 		{
173 			return rCandidate.getContinuityInPoint(nIndex);
174 		}
175 
adaptiveSubdivideByDistance(const B2DPolygon & rCandidate,double fDistanceBound)176 		B2DPolygon adaptiveSubdivideByDistance(const B2DPolygon& rCandidate, double fDistanceBound)
177 		{
178 			if(rCandidate.areControlPointsUsed())
179 			{
180 				const sal_uInt32 nPointCount(rCandidate.count());
181 				B2DPolygon aRetval;
182 
183 				if(nPointCount)
184 				{
185 					// prepare edge-oriented loop
186 					const sal_uInt32 nEdgeCount(rCandidate.isClosed() ? nPointCount : nPointCount - 1);
187 					B2DCubicBezier aBezier;
188 					aBezier.setStartPoint(rCandidate.getB2DPoint(0));
189 
190 					// perf: try to avoid too many realloctions by guessing the result's pointcount
191 					aRetval.reserve(nPointCount*4);
192 
193 					// add start point (always)
194 					aRetval.append(aBezier.getStartPoint());
195 
196 					for(sal_uInt32 a(0L); a < nEdgeCount; a++)
197 					{
198 						// get next and control points
199 						const sal_uInt32 nNextIndex((a + 1) % nPointCount);
200 						aBezier.setEndPoint(rCandidate.getB2DPoint(nNextIndex));
201 						aBezier.setControlPointA(rCandidate.getNextControlPoint(a));
202 						aBezier.setControlPointB(rCandidate.getPrevControlPoint(nNextIndex));
203 						aBezier.testAndSolveTrivialBezier();
204 
205 						if(aBezier.isBezier())
206 						{
207 							// add curved edge and generate DistanceBound
208 							double fBound(0.0);
209 
210 							if(0.0 == fDistanceBound)
211 							{
212 								// If not set, use B2DCubicBezier functionality to guess a rough value
213 								const double fRoughLength((aBezier.getEdgeLength() + aBezier.getControlPolygonLength()) / 2.0);
214 
215 								// take 1/100th of the rough curve length
216 								fBound = fRoughLength * 0.01;
217 							}
218 							else
219 							{
220 								// use given bound value
221 								fBound = fDistanceBound;
222 							}
223 
224 							// make sure bound value is not too small. The base units are 1/100th mm, thus
225 							// just make sure it's not smaller then 1/100th of that
226 							if(fBound < 0.01)
227 							{
228 								fBound = 0.01;
229 							}
230 
231 							// call adaptive subdivide which adds edges to aRetval accordingly
232 							aBezier.adaptiveSubdivideByDistance(aRetval, fBound);
233 						}
234 						else
235 						{
236 							// add non-curved edge
237 							aRetval.append(aBezier.getEndPoint());
238 						}
239 
240 						// prepare next step
241 						aBezier.setStartPoint(aBezier.getEndPoint());
242 					}
243 
244 					if(rCandidate.isClosed())
245 					{
246 						// set closed flag and correct last point (which is added double now).
247 						closeWithGeometryChange(aRetval);
248 					}
249 				}
250 
251 				return aRetval;
252 			}
253 			else
254 			{
255 				return rCandidate;
256 			}
257 		}
258 
adaptiveSubdivideByAngle(const B2DPolygon & rCandidate,double fAngleBound)259 		B2DPolygon adaptiveSubdivideByAngle(const B2DPolygon& rCandidate, double fAngleBound)
260 		{
261 			if(rCandidate.areControlPointsUsed())
262 			{
263 				const sal_uInt32 nPointCount(rCandidate.count());
264 				B2DPolygon aRetval;
265 
266 				if(nPointCount)
267 				{
268 					// prepare edge-oriented loop
269 					const sal_uInt32 nEdgeCount(rCandidate.isClosed() ? nPointCount : nPointCount - 1);
270 					B2DCubicBezier aBezier;
271 					aBezier.setStartPoint(rCandidate.getB2DPoint(0));
272 
273 					// perf: try to avoid too many realloctions by guessing the result's pointcount
274 					aRetval.reserve(nPointCount*4);
275 
276 					// add start point (always)
277 					aRetval.append(aBezier.getStartPoint());
278 
279 					// #i37443# prepare convenient AngleBound if none was given
280 					if(0.0 == fAngleBound)
281 					{
282 #ifdef DBG_UTIL
283 						fAngleBound = fAngleBoundStartValue;
284 #else
285 						fAngleBound = ANGLE_BOUND_START_VALUE;
286 #endif
287 					}
288 					else if(fTools::less(fAngleBound, ANGLE_BOUND_MINIMUM_VALUE))
289 					{
290 						fAngleBound = 0.1;
291 					}
292 
293 					for(sal_uInt32 a(0L); a < nEdgeCount; a++)
294 					{
295 						// get next and control points
296 						const sal_uInt32 nNextIndex((a + 1) % nPointCount);
297 						aBezier.setEndPoint(rCandidate.getB2DPoint(nNextIndex));
298 						aBezier.setControlPointA(rCandidate.getNextControlPoint(a));
299 						aBezier.setControlPointB(rCandidate.getPrevControlPoint(nNextIndex));
300 						aBezier.testAndSolveTrivialBezier();
301 
302 						if(aBezier.isBezier())
303 						{
304 							// call adaptive subdivide
305 							aBezier.adaptiveSubdivideByAngle(aRetval, fAngleBound, true);
306 						}
307 						else
308 						{
309 							// add non-curved edge
310 							aRetval.append(aBezier.getEndPoint());
311 						}
312 
313 						// prepare next step
314 						aBezier.setStartPoint(aBezier.getEndPoint());
315 					}
316 
317 					if(rCandidate.isClosed())
318 					{
319 						// set closed flag and correct last point (which is added double now).
320 						closeWithGeometryChange(aRetval);
321 					}
322 				}
323 
324 				return aRetval;
325 			}
326 			else
327 			{
328 				return rCandidate;
329 			}
330 		}
331 
adaptiveSubdivideByCount(const B2DPolygon & rCandidate,sal_uInt32 nCount)332 		B2DPolygon adaptiveSubdivideByCount(const B2DPolygon& rCandidate, sal_uInt32 nCount)
333 		{
334 			if(rCandidate.areControlPointsUsed())
335 			{
336 				const sal_uInt32 nPointCount(rCandidate.count());
337 				B2DPolygon aRetval;
338 
339 				if(nPointCount)
340 				{
341 					// prepare edge-oriented loop
342 					const sal_uInt32 nEdgeCount(rCandidate.isClosed() ? nPointCount : nPointCount - 1);
343 					B2DCubicBezier aBezier;
344 					aBezier.setStartPoint(rCandidate.getB2DPoint(0));
345 
346 					// perf: try to avoid too many realloctions by guessing the result's pointcount
347 					aRetval.reserve(nPointCount*4);
348 
349 					// add start point (always)
350 					aRetval.append(aBezier.getStartPoint());
351 
352 					// #i37443# prepare convenient count if none was given
353 					if(0L == nCount)
354 					{
355 						nCount = COUNT_SUBDIVIDE_DEFAULT;
356 					}
357 
358 					for(sal_uInt32 a(0L); a < nEdgeCount; a++)
359 					{
360 						// get next and control points
361 						const sal_uInt32 nNextIndex((a + 1) % nPointCount);
362 						aBezier.setEndPoint(rCandidate.getB2DPoint(nNextIndex));
363 						aBezier.setControlPointA(rCandidate.getNextControlPoint(a));
364 						aBezier.setControlPointB(rCandidate.getPrevControlPoint(nNextIndex));
365 						aBezier.testAndSolveTrivialBezier();
366 
367 						if(aBezier.isBezier())
368 						{
369 							// call adaptive subdivide
370 							aBezier.adaptiveSubdivideByCount(aRetval, nCount);
371 						}
372 						else
373 						{
374 							// add non-curved edge
375 							aRetval.append(aBezier.getEndPoint());
376 						}
377 
378 						// prepare next step
379 						aBezier.setStartPoint(aBezier.getEndPoint());
380 					}
381 
382 					if(rCandidate.isClosed())
383 					{
384 						// set closed flag and correct last point (which is added double now).
385 						closeWithGeometryChange(aRetval);
386 					}
387 				}
388 
389 				return aRetval;
390 			}
391 			else
392 			{
393 				return rCandidate;
394 			}
395 		}
396 
isInside(const B2DPolygon & rCandidate,const B2DPoint & rPoint,bool bWithBorder)397 		bool isInside(const B2DPolygon& rCandidate, const B2DPoint& rPoint, bool bWithBorder)
398 		{
399 			const B2DPolygon aCandidate(rCandidate.areControlPointsUsed() ? rCandidate.getDefaultAdaptiveSubdivision() : rCandidate);
400 
401 			if(bWithBorder && isPointOnPolygon(aCandidate, rPoint, true))
402 			{
403 				return true;
404 			}
405 			else
406 			{
407 				bool bRetval(false);
408 				const sal_uInt32 nPointCount(aCandidate.count());
409 
410 				if(nPointCount)
411 				{
412 					B2DPoint aCurrentPoint(aCandidate.getB2DPoint(nPointCount - 1L));
413 
414 					for(sal_uInt32 a(0L); a < nPointCount; a++)
415 					{
416 						const B2DPoint aPreviousPoint(aCurrentPoint);
417 						aCurrentPoint = aCandidate.getB2DPoint(a);
418 
419 						// cross-over in Y?
420 						const bool bCompYA(fTools::more(aPreviousPoint.getY(), rPoint.getY()));
421 						const bool bCompYB(fTools::more(aCurrentPoint.getY(), rPoint.getY()));
422 
423 						if(bCompYA != bCompYB)
424 						{
425 							// cross-over in X?
426 							const bool bCompXA(fTools::more(aPreviousPoint.getX(), rPoint.getX()));
427 							const bool bCompXB(fTools::more(aCurrentPoint.getX(), rPoint.getX()));
428 
429 							if(bCompXA == bCompXB)
430 							{
431 								if(bCompXA)
432 								{
433 									bRetval = !bRetval;
434 								}
435 							}
436 							else
437 							{
438 								const double fCompare(
439 									aCurrentPoint.getX() - (aCurrentPoint.getY() - rPoint.getY()) *
440 									(aPreviousPoint.getX() - aCurrentPoint.getX()) /
441 									(aPreviousPoint.getY() - aCurrentPoint.getY()));
442 
443 								if(fTools::more(fCompare, rPoint.getX()))
444 								{
445 									bRetval = !bRetval;
446 								}
447 							}
448 						}
449 					}
450 				}
451 
452 				return bRetval;
453 			}
454 		}
455 
isInside(const B2DPolygon & rCandidate,const B2DPolygon & rPolygon,bool bWithBorder)456 		bool isInside(const B2DPolygon& rCandidate, const B2DPolygon& rPolygon, bool bWithBorder)
457 		{
458 			const B2DPolygon aCandidate(rCandidate.areControlPointsUsed() ? rCandidate.getDefaultAdaptiveSubdivision() : rCandidate);
459 			const B2DPolygon aPolygon(rPolygon.areControlPointsUsed() ? rPolygon.getDefaultAdaptiveSubdivision() : rPolygon);
460 			const sal_uInt32 nPointCount(aPolygon.count());
461 
462 			for(sal_uInt32 a(0L); a < nPointCount; a++)
463 			{
464 				const B2DPoint aTestPoint(aPolygon.getB2DPoint(a));
465 
466 				if(!isInside(aCandidate, aTestPoint, bWithBorder))
467 				{
468 					return false;
469 				}
470 			}
471 
472 			return true;
473 		}
474 
getRangeWithControlPoints(const B2DPolygon & rCandidate)475 		B2DRange getRangeWithControlPoints(const B2DPolygon& rCandidate)
476 		{
477 			const sal_uInt32 nPointCount(rCandidate.count());
478 			B2DRange aRetval;
479 
480 			if(nPointCount)
481 			{
482 				const bool bControlPointsUsed(rCandidate.areControlPointsUsed());
483 
484 				for(sal_uInt32 a(0); a < nPointCount; a++)
485 				{
486 					aRetval.expand(rCandidate.getB2DPoint(a));
487 
488 					if(bControlPointsUsed)
489 					{
490 						aRetval.expand(rCandidate.getNextControlPoint(a));
491 						aRetval.expand(rCandidate.getPrevControlPoint(a));
492 					}
493 				}
494 			}
495 
496 			return aRetval;
497 		}
498 
getRange(const B2DPolygon & rCandidate)499 		B2DRange getRange(const B2DPolygon& rCandidate)
500 		{
501             // changed to use internally buffered version at B2DPolygon
502             return rCandidate.getB2DRange();
503 		}
504 
getSignedArea(const B2DPolygon & rCandidate)505 		double getSignedArea(const B2DPolygon& rCandidate)
506 		{
507 			const B2DPolygon aCandidate(rCandidate.areControlPointsUsed() ? rCandidate.getDefaultAdaptiveSubdivision() : rCandidate);
508 			double fRetval(0.0);
509 			const sal_uInt32 nPointCount(aCandidate.count());
510 
511 			if(nPointCount > 2)
512 			{
513 				for(sal_uInt32 a(0L); a < nPointCount; a++)
514 				{
515 					const B2DPoint aPreviousPoint(aCandidate.getB2DPoint((!a) ? nPointCount - 1L : a - 1L));
516 					const B2DPoint aCurrentPoint(aCandidate.getB2DPoint(a));
517 
518 					fRetval += aPreviousPoint.getX() * aCurrentPoint.getY();
519 					fRetval -= aPreviousPoint.getY() * aCurrentPoint.getX();
520 				}
521 
522 				// correct to zero if small enough. Also test the quadratic
523 				// of the result since the precision is near quadratic due to
524 				// the algorithm
525 				if(fTools::equalZero(fRetval) || fTools::equalZero(fRetval * fRetval))
526 				{
527 					fRetval = 0.0;
528 				}
529 			}
530 
531 			return fRetval;
532 		}
533 
getArea(const B2DPolygon & rCandidate)534 		double getArea(const B2DPolygon& rCandidate)
535 		{
536 			double fRetval(0.0);
537 
538 			if(rCandidate.count() > 2 || rCandidate.areControlPointsUsed())
539 			{
540 				fRetval = getSignedArea(rCandidate);
541 				const double fZero(0.0);
542 
543 				if(fTools::less(fRetval, fZero))
544 				{
545 					fRetval = -fRetval;
546 				}
547 			}
548 
549 			return fRetval;
550 		}
551 
getEdgeLength(const B2DPolygon & rCandidate,sal_uInt32 nIndex)552 		double getEdgeLength(const B2DPolygon& rCandidate, sal_uInt32 nIndex)
553 		{
554 			const sal_uInt32 nPointCount(rCandidate.count());
555 			OSL_ENSURE(nIndex < nPointCount, "getEdgeLength: Access to polygon out of range (!)");
556 			double fRetval(0.0);
557 
558             if(nPointCount)
559             {
560                 const sal_uInt32 nNextIndex((nIndex + 1) % nPointCount);
561 
562                 if(rCandidate.areControlPointsUsed())
563                 {
564                     B2DCubicBezier aEdge;
565 
566                     aEdge.setStartPoint(rCandidate.getB2DPoint(nIndex));
567                     aEdge.setControlPointA(rCandidate.getNextControlPoint(nIndex));
568                     aEdge.setControlPointB(rCandidate.getPrevControlPoint(nNextIndex));
569                     aEdge.setEndPoint(rCandidate.getB2DPoint(nNextIndex));
570 
571                     fRetval = aEdge.getLength();
572                 }
573                 else
574                 {
575 					const B2DPoint aCurrent(rCandidate.getB2DPoint(nIndex));
576 					const B2DPoint aNext(rCandidate.getB2DPoint(nNextIndex));
577 
578                     fRetval = B2DVector(aNext - aCurrent).getLength();
579                 }
580             }
581 
582 			return fRetval;
583 		}
584 
getLength(const B2DPolygon & rCandidate)585 		double getLength(const B2DPolygon& rCandidate)
586 		{
587 			double fRetval(0.0);
588 			const sal_uInt32 nPointCount(rCandidate.count());
589 
590 			if(nPointCount)
591 			{
592                 const sal_uInt32 nEdgeCount(rCandidate.isClosed() ? nPointCount : nPointCount - 1L);
593 
594                 if(rCandidate.areControlPointsUsed())
595                 {
596                     B2DCubicBezier aEdge;
597                     aEdge.setStartPoint(rCandidate.getB2DPoint(0));
598 
599                     for(sal_uInt32 a(0); a < nEdgeCount; a++)
600                     {
601                         const sal_uInt32 nNextIndex((a + 1) % nPointCount);
602                         aEdge.setControlPointA(rCandidate.getNextControlPoint(a));
603                         aEdge.setControlPointB(rCandidate.getPrevControlPoint(nNextIndex));
604                         aEdge.setEndPoint(rCandidate.getB2DPoint(nNextIndex));
605 
606                         fRetval += aEdge.getLength();
607                         aEdge.setStartPoint(aEdge.getEndPoint());
608                     }
609                 }
610                 else
611                 {
612                     B2DPoint aCurrent(rCandidate.getB2DPoint(0));
613 
614                     for(sal_uInt32 a(0); a < nEdgeCount; a++)
615                     {
616                         const sal_uInt32 nNextIndex((a + 1) % nPointCount);
617                         const B2DPoint aNext(rCandidate.getB2DPoint(nNextIndex));
618 
619                         fRetval += B2DVector(aNext - aCurrent).getLength();
620                         aCurrent = aNext;
621                     }
622                 }
623 			}
624 
625 			return fRetval;
626 		}
627 
getPositionAbsolute(const B2DPolygon & rCandidate,double fDistance,double fLength)628 		B2DPoint getPositionAbsolute(const B2DPolygon& rCandidate, double fDistance, double fLength)
629 		{
630 			B2DPoint aRetval;
631 			const sal_uInt32 nPointCount(rCandidate.count());
632 
633 			if( 1L == nPointCount )
634             {
635                 // only one point (i.e. no edge) - simply take that point
636                 aRetval = rCandidate.getB2DPoint(0);
637             }
638 			else if(nPointCount > 1L)
639 			{
640                 const sal_uInt32 nEdgeCount(rCandidate.isClosed() ? nPointCount : nPointCount - 1);
641 				sal_uInt32 nIndex(0L);
642 				bool bIndexDone(false);
643 
644 				// get length if not given
645 				if(fTools::equalZero(fLength))
646 				{
647 					fLength = getLength(rCandidate);
648 				}
649 
650 				if(fTools::less(fDistance, 0.0))
651 				{
652     				// handle fDistance < 0.0
653 					if(rCandidate.isClosed())
654 					{
655 						// if fDistance < 0.0 increment with multiple of fLength
656 						sal_uInt32 nCount(sal_uInt32(-fDistance / fLength));
657 						fDistance += double(nCount + 1L) * fLength;
658 					}
659 					else
660 					{
661 						// crop to polygon start
662 						fDistance = 0.0;
663 						bIndexDone = true;
664 					}
665 				}
666 				else if(fTools::moreOrEqual(fDistance, fLength))
667 				{
668     				// handle fDistance >= fLength
669 					if(rCandidate.isClosed())
670 					{
671 						// if fDistance >= fLength decrement with multiple of fLength
672 						sal_uInt32 nCount(sal_uInt32(fDistance / fLength));
673 						fDistance -= (double)(nCount) * fLength;
674 					}
675 					else
676 					{
677 						// crop to polygon end
678 						fDistance = 0.0;
679 						nIndex = nEdgeCount;
680 						bIndexDone = true;
681 					}
682 				}
683 
684 				// look for correct index. fDistance is now [0.0 .. fLength[
685     			double fEdgeLength(getEdgeLength(rCandidate, nIndex));
686 
687                 while(!bIndexDone)
688                 {
689                     // edge found must be on the half-open range
690                     // [0,fEdgeLength).
691                     // Note that in theory, we cannot move beyond
692                     // the last polygon point, since fDistance>=fLength
693                     // is checked above. Unfortunately, with floating-
694                     // point calculations, this case might happen.
695                     // Handled by nIndex check below
696                     if(nIndex < nEdgeCount && fTools::moreOrEqual(fDistance, fEdgeLength))
697 					{
698 						// go to next edge
699 						fDistance -= fEdgeLength;
700 						fEdgeLength = getEdgeLength(rCandidate, ++nIndex);
701 					}
702 					else
703 					{
704 						// it's on this edge, stop
705 						bIndexDone = true;
706 					}
707                 }
708 
709                 // get the point using nIndex
710 				aRetval = rCandidate.getB2DPoint(nIndex);
711 
712 				// if fDistance != 0.0, move that length on the edge. The edge
713 				// length is in fEdgeLength.
714 				if(!fTools::equalZero(fDistance))
715 				{
716                     if(fTools::moreOrEqual(fDistance, fEdgeLength))
717                     {
718                         // end point of choosen edge
719     			        const sal_uInt32 nNextIndex((nIndex + 1) % nPointCount);
720 				        aRetval = rCandidate.getB2DPoint(nNextIndex);
721                     }
722                     else if(fTools::equalZero(fDistance))
723                     {
724                         // start point of choosen edge
725                         aRetval = aRetval;
726                     }
727                     else
728                     {
729                         // inside edge
730     			        const sal_uInt32 nNextIndex((nIndex + 1) % nPointCount);
731 				        const B2DPoint aNextPoint(rCandidate.getB2DPoint(nNextIndex));
732 						bool bDone(false);
733 
734 					    // add calculated average value to the return value
735                         if(rCandidate.areControlPointsUsed())
736                         {
737                             // get as bezier segment
738                             const B2DCubicBezier aBezierSegment(
739                                 aRetval, rCandidate.getNextControlPoint(nIndex),
740                                 rCandidate.getPrevControlPoint(nNextIndex), aNextPoint);
741 
742                             if(aBezierSegment.isBezier())
743                             {
744                                 // use B2DCubicBezierHelper to bridge the non-linear gap between
745                                 // length and bezier distances
746                                 const B2DCubicBezierHelper aBezierSegmentHelper(aBezierSegment);
747                                 const double fBezierDistance(aBezierSegmentHelper.distanceToRelative(fDistance));
748 
749                                 aRetval = aBezierSegment.interpolatePoint(fBezierDistance);
750 								bDone = true;
751                             }
752                         }
753 
754 						if(!bDone)
755                         {
756 						    const double fRelativeInEdge(fDistance / fEdgeLength);
757     					    aRetval = interpolate(aRetval, aNextPoint, fRelativeInEdge);
758                         }
759                     }
760 				}
761 			}
762 
763 			return aRetval;
764 		}
765 
getPositionRelative(const B2DPolygon & rCandidate,double fDistance,double fLength)766 		B2DPoint getPositionRelative(const B2DPolygon& rCandidate, double fDistance, double fLength)
767 		{
768 			// get length if not given
769 			if(fTools::equalZero(fLength))
770 			{
771 				fLength = getLength(rCandidate);
772 			}
773 
774 			// multiply fDistance with real length to get absolute position and
775 			// use getPositionAbsolute
776 			return getPositionAbsolute(rCandidate, fDistance * fLength, fLength);
777 		}
778 
getSnippetAbsolute(const B2DPolygon & rCandidate,double fFrom,double fTo,double fLength)779 		B2DPolygon getSnippetAbsolute(const B2DPolygon& rCandidate, double fFrom, double fTo, double fLength)
780 		{
781 			const sal_uInt32 nPointCount(rCandidate.count());
782 
783             if(nPointCount)
784             {
785 			    // get length if not given
786 			    if(fTools::equalZero(fLength))
787 			    {
788 				    fLength = getLength(rCandidate);
789 			    }
790 
791 			    // test and correct fFrom
792                 if(fTools::less(fFrom, 0.0))
793 			    {
794 				    fFrom = 0.0;
795 			    }
796 
797 			    // test and correct fTo
798                 if(fTools::more(fTo, fLength))
799 			    {
800 				    fTo = fLength;
801 			    }
802 
803 			    // test and correct relationship of fFrom, fTo
804                 if(fTools::more(fFrom, fTo))
805 			    {
806 				    fFrom = fTo = (fFrom + fTo) / 2.0;
807 			    }
808 
809                 if(fTools::equalZero(fFrom) && fTools::equal(fTo, fLength))
810 			    {
811 				    // no change, result is the whole polygon
812 				    return rCandidate;
813 			    }
814 			    else
815 			    {
816                     B2DPolygon aRetval;
817                     const sal_uInt32 nEdgeCount(rCandidate.isClosed() ? nPointCount : nPointCount - 1);
818 				    double fPositionOfStart(0.0);
819 				    bool bStartDone(false);
820 				    bool bEndDone(false);
821 
822 				    for(sal_uInt32 a(0L); !(bStartDone && bEndDone) && a < nEdgeCount; a++)
823 				    {
824 					    const double fEdgeLength(getEdgeLength(rCandidate, a));
825 
826 					    if(!bStartDone)
827 					    {
828                             if(fTools::equalZero(fFrom))
829 						    {
830 							    aRetval.append(rCandidate.getB2DPoint(a));
831 
832                                 if(rCandidate.areControlPointsUsed())
833                                 {
834                                     aRetval.setNextControlPoint(aRetval.count() - 1, rCandidate.getNextControlPoint(a));
835                                 }
836 
837 							    bStartDone = true;
838 						    }
839                             else if(fTools::moreOrEqual(fFrom, fPositionOfStart) && fTools::less(fFrom, fPositionOfStart + fEdgeLength))
840 						    {
841 							    // calculate and add start point
842                                 if(fTools::equalZero(fEdgeLength))
843 							    {
844 								    aRetval.append(rCandidate.getB2DPoint(a));
845 
846                                     if(rCandidate.areControlPointsUsed())
847                                     {
848                                         aRetval.setNextControlPoint(aRetval.count() - 1, rCandidate.getNextControlPoint(a));
849                                     }
850 							    }
851                                 else
852 							    {
853                                     const sal_uInt32 nNextIndex((a + 1) % nPointCount);
854 					                const B2DPoint aStart(rCandidate.getB2DPoint(a));
855 					                const B2DPoint aEnd(rCandidate.getB2DPoint(nNextIndex));
856 									bool bDone(false);
857 
858                                     if(rCandidate.areControlPointsUsed())
859                                     {
860                                         const B2DCubicBezier aBezierSegment(
861                                             aStart, rCandidate.getNextControlPoint(a),
862                                             rCandidate.getPrevControlPoint(nNextIndex), aEnd);
863 
864                                         if(aBezierSegment.isBezier())
865                                         {
866                                             // use B2DCubicBezierHelper to bridge the non-linear gap between
867                                             // length and bezier distances
868                                             const B2DCubicBezierHelper aBezierSegmentHelper(aBezierSegment);
869                                             const double fBezierDistance(aBezierSegmentHelper.distanceToRelative(fFrom - fPositionOfStart));
870                                             B2DCubicBezier aRight;
871 
872                                             aBezierSegment.split(fBezierDistance, 0, &aRight);
873                                             aRetval.append(aRight.getStartPoint());
874                                             aRetval.setNextControlPoint(aRetval.count() - 1, aRight.getControlPointA());
875 											bDone = true;
876                                         }
877                                     }
878 
879 									if(!bDone)
880                                     {
881 	                                    const double fRelValue((fFrom - fPositionOfStart) / fEdgeLength);
882     								    aRetval.append(interpolate(aStart, aEnd, fRelValue));
883                                     }
884 							    }
885 
886 							    bStartDone = true;
887 
888 							    // if same point, end is done, too.
889 							    if(fFrom == fTo)
890 							    {
891 								    bEndDone = true;
892 							    }
893 						    }
894 					    }
895 
896                         if(!bEndDone && fTools::moreOrEqual(fTo, fPositionOfStart) && fTools::less(fTo, fPositionOfStart + fEdgeLength))
897 					    {
898 						    // calculate and add end point
899                             if(fTools::equalZero(fEdgeLength))
900 						    {
901                                 const sal_uInt32 nNextIndex((a + 1) % nPointCount);
902 							    aRetval.append(rCandidate.getB2DPoint(nNextIndex));
903 
904                                 if(rCandidate.areControlPointsUsed())
905                                 {
906                                     aRetval.setPrevControlPoint(aRetval.count() - 1, rCandidate.getPrevControlPoint(nNextIndex));
907                                 }
908 						    }
909                             else
910                             {
911                                 const sal_uInt32 nNextIndex((a + 1) % nPointCount);
912 				                const B2DPoint aStart(rCandidate.getB2DPoint(a));
913 				                const B2DPoint aEnd(rCandidate.getB2DPoint(nNextIndex));
914 								bool bDone(false);
915 
916                                 if(rCandidate.areControlPointsUsed())
917                                 {
918                                     const B2DCubicBezier aBezierSegment(
919                                         aStart, rCandidate.getNextControlPoint(a),
920                                         rCandidate.getPrevControlPoint(nNextIndex), aEnd);
921 
922                                     if(aBezierSegment.isBezier())
923                                     {
924                                         // use B2DCubicBezierHelper to bridge the non-linear gap between
925                                         // length and bezier distances
926                                         const B2DCubicBezierHelper aBezierSegmentHelper(aBezierSegment);
927                                         const double fBezierDistance(aBezierSegmentHelper.distanceToRelative(fTo - fPositionOfStart));
928                                         B2DCubicBezier aLeft;
929 
930                                         aBezierSegment.split(fBezierDistance, &aLeft, 0);
931                                         aRetval.append(aLeft.getEndPoint());
932                                         aRetval.setPrevControlPoint(aRetval.count() - 1, aLeft.getControlPointB());
933 										bDone = true;
934                                     }
935                                 }
936 
937                                 if(!bDone)
938                                 {
939 	                                const double fRelValue((fTo - fPositionOfStart) / fEdgeLength);
940 								    aRetval.append(interpolate(aStart, aEnd, fRelValue));
941                                 }
942 						    }
943 
944 						    bEndDone = true;
945 					    }
946 
947 					    if(!bEndDone)
948 					    {
949 						    if(bStartDone)
950 						    {
951 							    // add segments end point
952                                 const sal_uInt32 nNextIndex((a + 1) % nPointCount);
953 							    aRetval.append(rCandidate.getB2DPoint(nNextIndex));
954 
955                                 if(rCandidate.areControlPointsUsed())
956                                 {
957                                     aRetval.setPrevControlPoint(aRetval.count() - 1, rCandidate.getPrevControlPoint(nNextIndex));
958                                     aRetval.setNextControlPoint(aRetval.count() - 1, rCandidate.getNextControlPoint(nNextIndex));
959                                 }
960 						    }
961 
962 						    // increment fPositionOfStart
963 						    fPositionOfStart += fEdgeLength;
964 					    }
965 				    }
966     			    return aRetval;
967 			    }
968             }
969             else
970             {
971                 return rCandidate;
972             }
973 		}
974 
getSnippetRelative(const B2DPolygon & rCandidate,double fFrom,double fTo,double fLength)975 		B2DPolygon getSnippetRelative(const B2DPolygon& rCandidate, double fFrom, double fTo, double fLength)
976 		{
977 			// get length if not given
978 			if(fTools::equalZero(fLength))
979 			{
980 				fLength = getLength(rCandidate);
981 			}
982 
983 			// multiply distances with real length to get absolute position and
984 			// use getSnippetAbsolute
985 			return getSnippetAbsolute(rCandidate, fFrom * fLength, fTo * fLength, fLength);
986 		}
987 
findCut(const B2DPolygon & rCandidate,sal_uInt32 nIndex1,sal_uInt32 nIndex2,CutFlagValue aCutFlags,double * pCut1,double * pCut2)988 		CutFlagValue findCut(
989 			const B2DPolygon& rCandidate,
990 			sal_uInt32 nIndex1, sal_uInt32 nIndex2,
991 			CutFlagValue aCutFlags,
992 			double* pCut1, double* pCut2)
993 		{
994 			CutFlagValue aRetval(CUTFLAG_NONE);
995 			const sal_uInt32 nPointCount(rCandidate.count());
996 
997 			if(nIndex1 < nPointCount && nIndex2 < nPointCount && nIndex1 != nIndex2)
998 			{
999 				sal_uInt32 nEnd1(getIndexOfSuccessor(nIndex1, rCandidate));
1000 				sal_uInt32 nEnd2(getIndexOfSuccessor(nIndex2, rCandidate));
1001 
1002 				const B2DPoint aStart1(rCandidate.getB2DPoint(nIndex1));
1003 				const B2DPoint aEnd1(rCandidate.getB2DPoint(nEnd1));
1004 				const B2DVector aVector1(aEnd1 - aStart1);
1005 
1006 				const B2DPoint aStart2(rCandidate.getB2DPoint(nIndex2));
1007 				const B2DPoint aEnd2(rCandidate.getB2DPoint(nEnd2));
1008 				const B2DVector aVector2(aEnd2 - aStart2);
1009 
1010 				aRetval = findCut(
1011 					aStart1, aVector1, aStart2, aVector2,
1012 					aCutFlags, pCut1, pCut2);
1013 			}
1014 
1015 			return aRetval;
1016 		}
1017 
findCut(const B2DPolygon & rCandidate1,sal_uInt32 nIndex1,const B2DPolygon & rCandidate2,sal_uInt32 nIndex2,CutFlagValue aCutFlags,double * pCut1,double * pCut2)1018 		CutFlagValue findCut(
1019 			const B2DPolygon& rCandidate1, sal_uInt32 nIndex1,
1020 			const B2DPolygon& rCandidate2, sal_uInt32 nIndex2,
1021 			CutFlagValue aCutFlags,
1022 			double* pCut1, double* pCut2)
1023 		{
1024 			CutFlagValue aRetval(CUTFLAG_NONE);
1025 			const sal_uInt32 nPointCount1(rCandidate1.count());
1026 			const sal_uInt32 nPointCount2(rCandidate2.count());
1027 
1028 			if(nIndex1 < nPointCount1 && nIndex2 < nPointCount2)
1029 			{
1030 				sal_uInt32 nEnd1(getIndexOfSuccessor(nIndex1, rCandidate1));
1031 				sal_uInt32 nEnd2(getIndexOfSuccessor(nIndex2, rCandidate2));
1032 
1033 				const B2DPoint aStart1(rCandidate1.getB2DPoint(nIndex1));
1034 				const B2DPoint aEnd1(rCandidate1.getB2DPoint(nEnd1));
1035 				const B2DVector aVector1(aEnd1 - aStart1);
1036 
1037 				const B2DPoint aStart2(rCandidate2.getB2DPoint(nIndex2));
1038 				const B2DPoint aEnd2(rCandidate2.getB2DPoint(nEnd2));
1039 				const B2DVector aVector2(aEnd2 - aStart2);
1040 
1041 				aRetval = findCut(
1042 					aStart1, aVector1, aStart2, aVector2,
1043 					aCutFlags, pCut1, pCut2);
1044 			}
1045 
1046 			return aRetval;
1047 		}
1048 
findCut(const B2DPoint & rEdge1Start,const B2DVector & rEdge1Delta,const B2DPoint & rEdge2Start,const B2DVector & rEdge2Delta,CutFlagValue aCutFlags,double * pCut1,double * pCut2)1049 		CutFlagValue findCut(
1050 			const B2DPoint& rEdge1Start, const B2DVector& rEdge1Delta,
1051 			const B2DPoint& rEdge2Start, const B2DVector& rEdge2Delta,
1052 			CutFlagValue aCutFlags,
1053 			double* pCut1, double* pCut2)
1054 		{
1055 			CutFlagValue aRetval(CUTFLAG_NONE);
1056 			double fCut1(0.0);
1057 			double fCut2(0.0);
1058 			bool bFinished(!((bool)(aCutFlags & CUTFLAG_ALL)));
1059 
1060 			// test for same points?
1061 			if(!bFinished
1062 				&& (aCutFlags & (CUTFLAG_START1|CUTFLAG_END1))
1063 				&& (aCutFlags & (CUTFLAG_START2|CUTFLAG_END2)))
1064 			{
1065 				// same startpoint?
1066 				if(!bFinished && (aCutFlags & (CUTFLAG_START1|CUTFLAG_START2)) == (CUTFLAG_START1|CUTFLAG_START2))
1067 				{
1068 					if(rEdge1Start.equal(rEdge2Start))
1069 					{
1070 						bFinished = true;
1071 						aRetval = (CUTFLAG_START1|CUTFLAG_START2);
1072 					}
1073 				}
1074 
1075 				// same endpoint?
1076 				if(!bFinished && (aCutFlags & (CUTFLAG_END1|CUTFLAG_END2)) == (CUTFLAG_END1|CUTFLAG_END2))
1077 				{
1078 					const B2DPoint aEnd1(rEdge1Start + rEdge1Delta);
1079 					const B2DPoint aEnd2(rEdge2Start + rEdge2Delta);
1080 
1081 					if(aEnd1.equal(aEnd2))
1082 					{
1083 						bFinished = true;
1084 						aRetval = (CUTFLAG_END1|CUTFLAG_END2);
1085 						fCut1 = fCut2 = 1.0;
1086 					}
1087 				}
1088 
1089 				// startpoint1 == endpoint2?
1090 				if(!bFinished && (aCutFlags & (CUTFLAG_START1|CUTFLAG_END2)) == (CUTFLAG_START1|CUTFLAG_END2))
1091 				{
1092 					const B2DPoint aEnd2(rEdge2Start + rEdge2Delta);
1093 
1094 					if(rEdge1Start.equal(aEnd2))
1095 					{
1096 						bFinished = true;
1097 						aRetval = (CUTFLAG_START1|CUTFLAG_END2);
1098 						fCut1 = 0.0;
1099 						fCut2 = 1.0;
1100 					}
1101 				}
1102 
1103 				// startpoint2 == endpoint1?
1104 				if(!bFinished&& (aCutFlags & (CUTFLAG_START2|CUTFLAG_END1)) == (CUTFLAG_START2|CUTFLAG_END1))
1105 				{
1106 					const B2DPoint aEnd1(rEdge1Start + rEdge1Delta);
1107 
1108 					if(rEdge2Start.equal(aEnd1))
1109 					{
1110 						bFinished = true;
1111 						aRetval = (CUTFLAG_START2|CUTFLAG_END1);
1112 						fCut1 = 1.0;
1113 						fCut2 = 0.0;
1114 					}
1115 				}
1116 			}
1117 
1118 			if(!bFinished && (aCutFlags & CUTFLAG_LINE))
1119 			{
1120 				if(!bFinished && (aCutFlags & CUTFLAG_START1))
1121 				{
1122 					// start1 on line 2 ?
1123 					if(isPointOnEdge(rEdge1Start, rEdge2Start, rEdge2Delta, &fCut2))
1124 					{
1125 						bFinished = true;
1126 						aRetval = (CUTFLAG_LINE|CUTFLAG_START1);
1127 					}
1128 				}
1129 
1130 				if(!bFinished && (aCutFlags & CUTFLAG_START2))
1131 				{
1132 					// start2 on line 1 ?
1133 					if(isPointOnEdge(rEdge2Start, rEdge1Start, rEdge1Delta, &fCut1))
1134 					{
1135 						bFinished = true;
1136 						aRetval = (CUTFLAG_LINE|CUTFLAG_START2);
1137 					}
1138 				}
1139 
1140 				if(!bFinished && (aCutFlags & CUTFLAG_END1))
1141 				{
1142 					// end1 on line 2 ?
1143 					const B2DPoint aEnd1(rEdge1Start + rEdge1Delta);
1144 
1145 					if(isPointOnEdge(aEnd1, rEdge2Start, rEdge2Delta, &fCut2))
1146 					{
1147 						bFinished = true;
1148 						aRetval = (CUTFLAG_LINE|CUTFLAG_END1);
1149 					}
1150 				}
1151 
1152 				if(!bFinished && (aCutFlags & CUTFLAG_END2))
1153 				{
1154 					// end2 on line 1 ?
1155 					const B2DPoint aEnd2(rEdge2Start + rEdge2Delta);
1156 
1157 					if(isPointOnEdge(aEnd2, rEdge1Start, rEdge1Delta, &fCut1))
1158 					{
1159 						bFinished = true;
1160 						aRetval = (CUTFLAG_LINE|CUTFLAG_END2);
1161 					}
1162 				}
1163 
1164 				if(!bFinished)
1165 				{
1166 					// cut in line1, line2 ?
1167 					fCut1 = (rEdge1Delta.getX() * rEdge2Delta.getY()) - (rEdge1Delta.getY() * rEdge2Delta.getX());
1168 
1169 					if(!fTools::equalZero(fCut1))
1170 					{
1171 						fCut1 = (rEdge2Delta.getY() * (rEdge2Start.getX() - rEdge1Start.getX())
1172 							+ rEdge2Delta.getX() * (rEdge1Start.getY() - rEdge2Start.getY())) / fCut1;
1173 
1174 						const double fZero(0.0);
1175 						const double fOne(1.0);
1176 
1177 						// inside parameter range edge1 AND fCut2 is calcable
1178 						if(fTools::more(fCut1, fZero) && fTools::less(fCut1, fOne)
1179 							&& (!fTools::equalZero(rEdge2Delta.getX()) || !fTools::equalZero(rEdge2Delta.getY())))
1180 						{
1181 							// take the mopre precise calculation of the two possible
1182 							if(fabs(rEdge2Delta.getX()) > fabs(rEdge2Delta.getY()))
1183 							{
1184 								fCut2 = (rEdge1Start.getX() + fCut1
1185 									* rEdge1Delta.getX() - rEdge2Start.getX()) / rEdge2Delta.getX();
1186 							}
1187 							else
1188 							{
1189 								fCut2 = (rEdge1Start.getY() + fCut1
1190 									* rEdge1Delta.getY() - rEdge2Start.getY()) / rEdge2Delta.getY();
1191 							}
1192 
1193 							// inside parameter range edge2, too
1194 							if(fTools::more(fCut2, fZero) && fTools::less(fCut2, fOne))
1195 							{
1196 								bFinished = true;
1197 								aRetval = CUTFLAG_LINE;
1198 							}
1199 						}
1200 					}
1201 				}
1202 			}
1203 
1204 			// copy values if wanted
1205 			if(pCut1)
1206 			{
1207 				*pCut1 = fCut1;
1208 			}
1209 
1210 			if(pCut2)
1211 			{
1212 				*pCut2 = fCut2;
1213 			}
1214 
1215 			return aRetval;
1216 		}
1217 
isPointOnEdge(const B2DPoint & rPoint,const B2DPoint & rEdgeStart,const B2DVector & rEdgeDelta,double * pCut)1218 		bool isPointOnEdge(
1219 			const B2DPoint& rPoint,
1220 			const B2DPoint& rEdgeStart,
1221 			const B2DVector& rEdgeDelta,
1222 			double* pCut)
1223 		{
1224 			bool bDeltaXIsZero(fTools::equalZero(rEdgeDelta.getX()));
1225 			bool bDeltaYIsZero(fTools::equalZero(rEdgeDelta.getY()));
1226 			const double fZero(0.0);
1227 			const double fOne(1.0);
1228 
1229 			if(bDeltaXIsZero && bDeltaYIsZero)
1230 			{
1231 				// no line, just a point
1232 				return false;
1233 			}
1234 			else if(bDeltaXIsZero)
1235 			{
1236 				// vertical line
1237 				if(fTools::equal(rPoint.getX(), rEdgeStart.getX()))
1238 				{
1239 					double fValue = (rPoint.getY() - rEdgeStart.getY()) / rEdgeDelta.getY();
1240 
1241 					if(fTools::more(fValue, fZero) && fTools::less(fValue, fOne))
1242 					{
1243 						if(pCut)
1244 						{
1245 							*pCut = fValue;
1246 						}
1247 
1248 						return true;
1249 					}
1250 				}
1251 			}
1252 			else if(bDeltaYIsZero)
1253 			{
1254 				// horizontal line
1255 				if(fTools::equal(rPoint.getY(), rEdgeStart.getY()))
1256 				{
1257 					double fValue = (rPoint.getX() - rEdgeStart.getX()) / rEdgeDelta.getX();
1258 
1259 					if(fTools::more(fValue, fZero) && fTools::less(fValue, fOne))
1260 					{
1261 						if(pCut)
1262 						{
1263 							*pCut = fValue;
1264 						}
1265 
1266 						return true;
1267 					}
1268 				}
1269 			}
1270 			else
1271 			{
1272 				// any angle line
1273 				double fTOne = (rPoint.getX() - rEdgeStart.getX()) / rEdgeDelta.getX();
1274 				double fTTwo = (rPoint.getY() - rEdgeStart.getY()) / rEdgeDelta.getY();
1275 
1276 				if(fTools::equal(fTOne, fTTwo))
1277 				{
1278 					// same parameter representation, point is on line. Take
1279 					// middle value for better results
1280 					double fValue = (fTOne + fTTwo) / 2.0;
1281 
1282 					if(fTools::more(fValue, fZero) && fTools::less(fValue, fOne))
1283 					{
1284 						// point is inside line bounds, too
1285 						if(pCut)
1286 						{
1287 							*pCut = fValue;
1288 						}
1289 
1290 						return true;
1291 					}
1292 				}
1293 			}
1294 
1295 			return false;
1296 		}
1297 
applyLineDashing(const B2DPolygon & rCandidate,const::std::vector<double> & rDotDashArray,B2DPolyPolygon * pLineTarget,B2DPolyPolygon * pGapTarget,double fDotDashLength)1298 		void applyLineDashing(const B2DPolygon& rCandidate, const ::std::vector<double>& rDotDashArray, B2DPolyPolygon* pLineTarget, B2DPolyPolygon* pGapTarget, double fDotDashLength)
1299         {
1300             const sal_uInt32 nPointCount(rCandidate.count());
1301             const sal_uInt32 nDotDashCount(rDotDashArray.size());
1302 
1303 			if(fTools::lessOrEqual(fDotDashLength, 0.0))
1304             {
1305                 fDotDashLength = ::std::accumulate(rDotDashArray.begin(), rDotDashArray.end(), 0.0);
1306             }
1307 
1308 			if(fTools::more(fDotDashLength, 0.0) && (pLineTarget || pGapTarget) && nPointCount)
1309             {
1310 				// clear targets
1311 				if(pLineTarget)
1312 				{
1313 					pLineTarget->clear();
1314 				}
1315 
1316 				if(pGapTarget)
1317 				{
1318 					pGapTarget->clear();
1319 				}
1320 
1321                 // prepare current edge's start
1322 				B2DCubicBezier aCurrentEdge;
1323                 const sal_uInt32 nEdgeCount(rCandidate.isClosed() ? nPointCount : nPointCount - 1);
1324                 aCurrentEdge.setStartPoint(rCandidate.getB2DPoint(0));
1325 
1326                 // prepare DotDashArray iteration and the line/gap switching bool
1327                 sal_uInt32 nDotDashIndex(0);
1328                 bool bIsLine(true);
1329                 double fDotDashMovingLength(rDotDashArray[0]);
1330 				B2DPolygon aSnippet;
1331 
1332 				// iterate over all edges
1333                 for(sal_uInt32 a(0); a < nEdgeCount; a++)
1334                 {
1335                     // update current edge (fill in C1, C2 and end point)
1336 					double fLastDotDashMovingLength(0.0);
1337                     const sal_uInt32 nNextIndex((a + 1) % nPointCount);
1338                     aCurrentEdge.setControlPointA(rCandidate.getNextControlPoint(a));
1339                     aCurrentEdge.setControlPointB(rCandidate.getPrevControlPoint(nNextIndex));
1340                     aCurrentEdge.setEndPoint(rCandidate.getB2DPoint(nNextIndex));
1341 
1342 					// check if we have a trivial bezier segment -> possible fallback to edge
1343 					aCurrentEdge.testAndSolveTrivialBezier();
1344 
1345 					if(aCurrentEdge.isBezier())
1346 					{
1347 						// bezier segment
1348 						const B2DCubicBezierHelper aCubicBezierHelper(aCurrentEdge);
1349 						const double fEdgeLength(aCubicBezierHelper.getLength());
1350 
1351 						if(!fTools::equalZero(fEdgeLength))
1352 						{
1353 							while(fTools::less(fDotDashMovingLength, fEdgeLength))
1354 							{
1355 								// new split is inside edge, create and append snippet [fLastDotDashMovingLength, fDotDashMovingLength]
1356 								const bool bHandleLine(bIsLine && pLineTarget);
1357 								const bool bHandleGap(!bIsLine && pGapTarget);
1358 
1359 								if(bHandleLine || bHandleGap)
1360 								{
1361 									const double fBezierSplitStart(aCubicBezierHelper.distanceToRelative(fLastDotDashMovingLength));
1362 									const double fBezierSplitEnd(aCubicBezierHelper.distanceToRelative(fDotDashMovingLength));
1363 									B2DCubicBezier aBezierSnippet(aCurrentEdge.snippet(fBezierSplitStart, fBezierSplitEnd));
1364 
1365 									if(!aSnippet.count())
1366 									{
1367 										aSnippet.append(aBezierSnippet.getStartPoint());
1368 									}
1369 
1370 									aSnippet.appendBezierSegment(aBezierSnippet.getControlPointA(), aBezierSnippet.getControlPointB(), aBezierSnippet.getEndPoint());
1371 
1372 									if(bHandleLine)
1373 									{
1374 										pLineTarget->append(aSnippet);
1375 									}
1376 									else
1377 									{
1378 										pGapTarget->append(aSnippet);
1379 									}
1380 
1381 									aSnippet.clear();
1382 								}
1383 
1384 								// prepare next DotDashArray step and flip line/gap flag
1385 								fLastDotDashMovingLength = fDotDashMovingLength;
1386 								fDotDashMovingLength += rDotDashArray[(++nDotDashIndex) % nDotDashCount];
1387 								bIsLine = !bIsLine;
1388 							}
1389 
1390 							// append closing snippet [fLastDotDashMovingLength, fEdgeLength]
1391 							const bool bHandleLine(bIsLine && pLineTarget);
1392 							const bool bHandleGap(!bIsLine && pGapTarget);
1393 
1394 							if(bHandleLine || bHandleGap)
1395 							{
1396 								B2DCubicBezier aRight;
1397 								const double fBezierSplit(aCubicBezierHelper.distanceToRelative(fLastDotDashMovingLength));
1398 
1399 								aCurrentEdge.split(fBezierSplit, 0, &aRight);
1400 
1401 								if(!aSnippet.count())
1402 								{
1403 									aSnippet.append(aRight.getStartPoint());
1404 								}
1405 
1406 								aSnippet.appendBezierSegment(aRight.getControlPointA(), aRight.getControlPointB(), aRight.getEndPoint());
1407 							}
1408 
1409 							// prepare move to next edge
1410 							fDotDashMovingLength -= fEdgeLength;
1411 						}
1412 					}
1413 					else
1414 					{
1415 						// simple edge
1416 						const double fEdgeLength(aCurrentEdge.getEdgeLength());
1417 
1418 						if(!fTools::equalZero(fEdgeLength))
1419 						{
1420 							while(fTools::less(fDotDashMovingLength, fEdgeLength))
1421 							{
1422 								// new split is inside edge, create and append snippet [fLastDotDashMovingLength, fDotDashMovingLength]
1423 								const bool bHandleLine(bIsLine && pLineTarget);
1424 								const bool bHandleGap(!bIsLine && pGapTarget);
1425 
1426 								if(bHandleLine || bHandleGap)
1427 								{
1428 									if(!aSnippet.count())
1429 									{
1430 										aSnippet.append(interpolate(aCurrentEdge.getStartPoint(), aCurrentEdge.getEndPoint(), fLastDotDashMovingLength / fEdgeLength));
1431 									}
1432 
1433 									aSnippet.append(interpolate(aCurrentEdge.getStartPoint(), aCurrentEdge.getEndPoint(), fDotDashMovingLength / fEdgeLength));
1434 
1435 									if(bHandleLine)
1436 									{
1437 										pLineTarget->append(aSnippet);
1438 									}
1439 									else
1440 									{
1441 										pGapTarget->append(aSnippet);
1442 									}
1443 
1444 									aSnippet.clear();
1445 								}
1446 
1447 								// prepare next DotDashArray step and flip line/gap flag
1448 								fLastDotDashMovingLength = fDotDashMovingLength;
1449 								fDotDashMovingLength += rDotDashArray[(++nDotDashIndex) % nDotDashCount];
1450 								bIsLine = !bIsLine;
1451 							}
1452 
1453 							// append snippet [fLastDotDashMovingLength, fEdgeLength]
1454 							const bool bHandleLine(bIsLine && pLineTarget);
1455 							const bool bHandleGap(!bIsLine && pGapTarget);
1456 
1457 							if(bHandleLine || bHandleGap)
1458 							{
1459 								if(!aSnippet.count())
1460 								{
1461 									aSnippet.append(interpolate(aCurrentEdge.getStartPoint(), aCurrentEdge.getEndPoint(), fLastDotDashMovingLength / fEdgeLength));
1462 								}
1463 
1464 								aSnippet.append(aCurrentEdge.getEndPoint());
1465 							}
1466 
1467 							// prepare move to next edge
1468 							fDotDashMovingLength -= fEdgeLength;
1469 						}
1470 					}
1471 
1472 					// prepare next edge step (end point gets new start point)
1473                     aCurrentEdge.setStartPoint(aCurrentEdge.getEndPoint());
1474                 }
1475 
1476                 // append last intermediate results (if exists)
1477                 if(aSnippet.count())
1478                 {
1479                     if(bIsLine && pLineTarget)
1480                     {
1481                         pLineTarget->append(aSnippet);
1482                     }
1483                     else if(!bIsLine && pGapTarget)
1484                     {
1485                         pGapTarget->append(aSnippet);
1486                     }
1487                 }
1488 
1489 				// check if start and end polygon may be merged
1490 				if(pLineTarget)
1491 				{
1492 					const sal_uInt32 nCount(pLineTarget->count());
1493 
1494 					if(nCount > 1)
1495 					{
1496 						// these polygons were created above, there exists none with less than two points,
1497 						// thus dircet point access below is allowed
1498 						const B2DPolygon aFirst(pLineTarget->getB2DPolygon(0));
1499 						B2DPolygon aLast(pLineTarget->getB2DPolygon(nCount - 1));
1500 
1501 						if(aFirst.getB2DPoint(0).equal(aLast.getB2DPoint(aLast.count() - 1)))
1502 						{
1503 							// start of first and end of last are the same -> merge them
1504 							aLast.append(aFirst);
1505 							aLast.removeDoublePoints();
1506 							pLineTarget->setB2DPolygon(0, aLast);
1507 							pLineTarget->remove(nCount - 1);
1508 						}
1509 					}
1510 				}
1511 
1512 				if(pGapTarget)
1513 				{
1514 					const sal_uInt32 nCount(pGapTarget->count());
1515 
1516 					if(nCount > 1)
1517 					{
1518 						// these polygons were created above, there exists none with less than two points,
1519 						// thus dircet point access below is allowed
1520 						const B2DPolygon aFirst(pGapTarget->getB2DPolygon(0));
1521 						B2DPolygon aLast(pGapTarget->getB2DPolygon(nCount - 1));
1522 
1523 						if(aFirst.getB2DPoint(0).equal(aLast.getB2DPoint(aLast.count() - 1)))
1524 						{
1525 							// start of first and end of last are the same -> merge them
1526 							aLast.append(aFirst);
1527 							aLast.removeDoublePoints();
1528 							pGapTarget->setB2DPolygon(0, aLast);
1529 							pGapTarget->remove(nCount - 1);
1530 						}
1531 					}
1532 				}
1533             }
1534             else
1535             {
1536 				// parameters make no sense, just add source to targets
1537                 if(pLineTarget)
1538                 {
1539                     pLineTarget->append(rCandidate);
1540                 }
1541 
1542 				if(pGapTarget)
1543 				{
1544                     pGapTarget->append(rCandidate);
1545 				}
1546             }
1547 		}
1548 
1549 		// test if point is inside epsilon-range around an edge defined
1550 		// by the two given points. Can be used for HitTesting. The epsilon-range
1551 		// is defined to be the rectangle centered to the given edge, using height
1552 		// 2 x fDistance, and the circle around both points with radius fDistance.
isInEpsilonRange(const B2DPoint & rEdgeStart,const B2DPoint & rEdgeEnd,const B2DPoint & rTestPosition,double fDistance)1553 		bool isInEpsilonRange(const B2DPoint& rEdgeStart, const B2DPoint& rEdgeEnd, const B2DPoint& rTestPosition, double fDistance)
1554 		{
1555 			// build edge vector
1556 			const B2DVector aEdge(rEdgeEnd - rEdgeStart);
1557 			bool bDoDistanceTestStart(false);
1558 			bool bDoDistanceTestEnd(false);
1559 
1560 			if(aEdge.equalZero())
1561 			{
1562 				// no edge, just a point. Do one of the distance tests.
1563 				bDoDistanceTestStart = true;
1564 			}
1565 			else
1566 			{
1567 				// edge has a length. Create perpendicular vector.
1568 				const B2DVector aPerpend(getPerpendicular(aEdge));
1569 				double fCut(
1570 					(aPerpend.getY() * (rTestPosition.getX() - rEdgeStart.getX())
1571 					+ aPerpend.getX() * (rEdgeStart.getY() - rTestPosition.getY())) /
1572 					(aEdge.getX() * aEdge.getX() + aEdge.getY() * aEdge.getY()));
1573 				const double fZero(0.0);
1574 				const double fOne(1.0);
1575 
1576 				if(fTools::less(fCut, fZero))
1577 				{
1578 					// left of rEdgeStart
1579 					bDoDistanceTestStart = true;
1580 				}
1581 				else if(fTools::more(fCut, fOne))
1582 				{
1583 					// right of rEdgeEnd
1584 					bDoDistanceTestEnd = true;
1585 				}
1586 				else
1587 				{
1588 					// inside line [0.0 .. 1.0]
1589 					const B2DPoint aCutPoint(interpolate(rEdgeStart, rEdgeEnd, fCut));
1590     			    const B2DVector aDelta(rTestPosition - aCutPoint);
1591 					const double fDistanceSquare(aDelta.scalar(aDelta));
1592 
1593 					if(fDistanceSquare <= fDistance * fDistance)
1594 					{
1595 						return true;
1596 					}
1597 					else
1598 					{
1599 						return false;
1600 					}
1601 				}
1602 			}
1603 
1604 			if(bDoDistanceTestStart)
1605 			{
1606 			    const B2DVector aDelta(rTestPosition - rEdgeStart);
1607 				const double fDistanceSquare(aDelta.scalar(aDelta));
1608 
1609 				if(fDistanceSquare <= fDistance * fDistance)
1610 				{
1611 					return true;
1612 				}
1613 			}
1614 			else if(bDoDistanceTestEnd)
1615 			{
1616 			    const B2DVector aDelta(rTestPosition - rEdgeEnd);
1617 				const double fDistanceSquare(aDelta.scalar(aDelta));
1618 
1619 				if(fDistanceSquare <= fDistance * fDistance)
1620 				{
1621 					return true;
1622 				}
1623 			}
1624 
1625 			return false;
1626 		}
1627 
1628 		// test if point is inside epsilon-range around the given Polygon. Can be used
1629 		// for HitTesting. The epsilon-range is defined to be the tube around the polygon
1630 		// with distance fDistance and rounded edges (start and end point).
isInEpsilonRange(const B2DPolygon & rCandidate,const B2DPoint & rTestPosition,double fDistance)1631 		bool isInEpsilonRange(const B2DPolygon& rCandidate, const B2DPoint& rTestPosition, double fDistance)
1632 		{
1633 			// force to non-bezier polygon
1634 			const B2DPolygon aCandidate(rCandidate.getDefaultAdaptiveSubdivision());
1635 			const sal_uInt32 nPointCount(aCandidate.count());
1636 
1637 			if(nPointCount)
1638 			{
1639                 const sal_uInt32 nEdgeCount(aCandidate.isClosed() ? nPointCount : nPointCount - 1L);
1640 				B2DPoint aCurrent(aCandidate.getB2DPoint(0));
1641 
1642 				if(nEdgeCount)
1643 				{
1644 					// edges
1645 					for(sal_uInt32 a(0); a < nEdgeCount; a++)
1646 					{
1647 						const sal_uInt32 nNextIndex((a + 1) % nPointCount);
1648 						const B2DPoint aNext(aCandidate.getB2DPoint(nNextIndex));
1649 
1650 						if(isInEpsilonRange(aCurrent, aNext, rTestPosition, fDistance))
1651 						{
1652 							return true;
1653 						}
1654 
1655 						// prepare next step
1656 						aCurrent = aNext;
1657 					}
1658 				}
1659 				else
1660 				{
1661 					// no edges, but points -> not closed. Check single point. Just
1662 					// use isInEpsilonRange with twice the same point, it handles those well
1663 					if(isInEpsilonRange(aCurrent, aCurrent, rTestPosition, fDistance))
1664 					{
1665 						return true;
1666 					}
1667 				}
1668 			}
1669 
1670 			return false;
1671 		}
1672 
createPolygonFromRect(const B2DRectangle & rRect,double fRadius)1673         B2DPolygon createPolygonFromRect( const B2DRectangle& rRect, double fRadius )
1674         {
1675 			const double fZero(0.0);
1676 			const double fOne(1.0);
1677 
1678 			if(fTools::lessOrEqual(fRadius, fZero))
1679 			{
1680 				// no radius, use rectangle
1681 				return createPolygonFromRect( rRect );
1682 			}
1683 			else if(fTools::moreOrEqual(fRadius, fOne))
1684 			{
1685 				// full radius, use ellipse
1686 				const B2DPoint aCenter(rRect.getCenter());
1687 				const double fRadiusX(rRect.getWidth() / 2.0);
1688 				const double fRadiusY(rRect.getHeight() / 2.0);
1689 
1690 				return createPolygonFromEllipse( aCenter, fRadiusX, fRadiusY );
1691 			}
1692 			else
1693 			{
1694 				// create rectangle with two radii between ]0.0 .. 1.0[
1695 				return createPolygonFromRect( rRect, fRadius, fRadius );
1696 			}
1697 		}
1698 
createPolygonFromRect(const B2DRectangle & rRect,double fRadiusX,double fRadiusY)1699         B2DPolygon createPolygonFromRect( const B2DRectangle& rRect, double fRadiusX, double fRadiusY )
1700         {
1701 			const double fZero(0.0);
1702 			const double fOne(1.0);
1703 
1704 			// crop to useful values
1705 			if(fTools::less(fRadiusX, fZero))
1706 			{
1707 				fRadiusX = fZero;
1708 			}
1709 			else if(fTools::more(fRadiusX, fOne))
1710 			{
1711 				fRadiusX = fOne;
1712 			}
1713 
1714 			if(fTools::less(fRadiusY, fZero))
1715 			{
1716 				fRadiusY = fZero;
1717 			}
1718 			else if(fTools::more(fRadiusY, fOne))
1719 			{
1720 				fRadiusY = fOne;
1721 			}
1722 
1723 			if(fZero == fRadiusX || fZero == fRadiusY)
1724 			{
1725 				B2DPolygon aRetval;
1726 
1727 				// at least in one direction no radius, use rectangle.
1728 				// Do not use createPolygonFromRect() here since original
1729 				// creator (historical reasons) still creates a start point at the
1730 				// bottom center, so do the same here to get the same line patterns.
1731 				// Due to this the order of points is different, too.
1732 				const B2DPoint aBottomCenter(rRect.getCenter().getX(), rRect.getMaxY());
1733 				aRetval.append(aBottomCenter);
1734 
1735 				aRetval.append( B2DPoint( rRect.getMinX(), rRect.getMaxY() ) );
1736 				aRetval.append( B2DPoint( rRect.getMinX(), rRect.getMinY() ) );
1737 				aRetval.append( B2DPoint( rRect.getMaxX(), rRect.getMinY() ) );
1738 				aRetval.append( B2DPoint( rRect.getMaxX(), rRect.getMaxY() ) );
1739 
1740 				// close
1741 				aRetval.setClosed( true );
1742 
1743 				return aRetval;
1744 			}
1745 			else if(fOne == fRadiusX && fOne == fRadiusY)
1746 			{
1747 				// in both directions full radius, use ellipse
1748 				const B2DPoint aCenter(rRect.getCenter());
1749 				const double fRectRadiusX(rRect.getWidth() / 2.0);
1750 				const double fRectRadiusY(rRect.getHeight() / 2.0);
1751 
1752 				return createPolygonFromEllipse( aCenter, fRectRadiusX, fRectRadiusY );
1753 			}
1754 			else
1755 			{
1756 				B2DPolygon aRetval;
1757 				const double fBowX((rRect.getWidth() / 2.0) * fRadiusX);
1758 				const double fBowY((rRect.getHeight() / 2.0) * fRadiusY);
1759 	            const double fKappa((M_SQRT2 - 1.0) * 4.0 / 3.0);
1760 
1761 				// create start point at bottom center
1762 				if(fOne != fRadiusX)
1763 				{
1764 					const B2DPoint aBottomCenter(rRect.getCenter().getX(), rRect.getMaxY());
1765 					aRetval.append(aBottomCenter);
1766 				}
1767 
1768 				// create first bow
1769 				{
1770 					const B2DPoint aBottomRight(rRect.getMaxX(), rRect.getMaxY());
1771 					const B2DPoint aStart(aBottomRight + B2DPoint(-fBowX, 0.0));
1772 					const B2DPoint aStop(aBottomRight + B2DPoint(0.0, -fBowY));
1773 					aRetval.append(aStart);
1774 					aRetval.appendBezierSegment(interpolate(aStart, aBottomRight, fKappa), interpolate(aStop, aBottomRight, fKappa), aStop);
1775 				}
1776 
1777 				// create second bow
1778 				{
1779 					const B2DPoint aTopRight(rRect.getMaxX(), rRect.getMinY());
1780 					const B2DPoint aStart(aTopRight + B2DPoint(0.0, fBowY));
1781 					const B2DPoint aStop(aTopRight + B2DPoint(-fBowX, 0.0));
1782 					aRetval.append(aStart);
1783 					aRetval.appendBezierSegment(interpolate(aStart, aTopRight, fKappa), interpolate(aStop, aTopRight, fKappa), aStop);
1784 				}
1785 
1786 				// create third bow
1787 				{
1788 					const B2DPoint aTopLeft(rRect.getMinX(), rRect.getMinY());
1789 					const B2DPoint aStart(aTopLeft + B2DPoint(fBowX, 0.0));
1790 					const B2DPoint aStop(aTopLeft + B2DPoint(0.0, fBowY));
1791 					aRetval.append(aStart);
1792 					aRetval.appendBezierSegment(interpolate(aStart, aTopLeft, fKappa), interpolate(aStop, aTopLeft, fKappa), aStop);
1793 				}
1794 
1795 				// create forth bow
1796 				{
1797 					const B2DPoint aBottomLeft(rRect.getMinX(), rRect.getMaxY());
1798 					const B2DPoint aStart(aBottomLeft + B2DPoint(0.0, -fBowY));
1799 					const B2DPoint aStop(aBottomLeft + B2DPoint(fBowX, 0.0));
1800 					aRetval.append(aStart);
1801 					aRetval.appendBezierSegment(interpolate(aStart, aBottomLeft, fKappa), interpolate(aStop, aBottomLeft, fKappa), aStop);
1802 				}
1803 
1804 				// close
1805 	            aRetval.setClosed( true );
1806 
1807 				// remove double created points if there are extreme radii envolved
1808 				if(fOne == fRadiusX || fOne == fRadiusY)
1809 				{
1810 					aRetval.removeDoublePoints();
1811 				}
1812 
1813 				return aRetval;
1814 			}
1815 		}
1816 
createPolygonFromRect(const B2DRectangle & rRect)1817         B2DPolygon createPolygonFromRect( const B2DRectangle& rRect )
1818         {
1819             B2DPolygon aRetval;
1820 
1821             aRetval.append( B2DPoint( rRect.getMinX(), rRect.getMinY() ) );
1822             aRetval.append( B2DPoint( rRect.getMaxX(), rRect.getMinY() ) );
1823             aRetval.append( B2DPoint( rRect.getMaxX(), rRect.getMaxY() ) );
1824             aRetval.append( B2DPoint( rRect.getMinX(), rRect.getMaxY() ) );
1825 
1826 			// close
1827 			aRetval.setClosed( true );
1828 
1829             return aRetval;
1830         }
1831 
createUnitPolygon()1832         B2DPolygon createUnitPolygon()
1833         {
1834             static B2DPolygon aRetval;
1835 
1836             if(!aRetval.count())
1837             {
1838                 aRetval.append( B2DPoint( 0.0, 0.0 ) );
1839                 aRetval.append( B2DPoint( 1.0, 0.0 ) );
1840                 aRetval.append( B2DPoint( 1.0, 1.0 ) );
1841                 aRetval.append( B2DPoint( 0.0, 1.0 ) );
1842 
1843 			    // close
1844 			    aRetval.setClosed( true );
1845             }
1846 
1847             return aRetval;
1848         }
1849 
createPolygonFromCircle(const B2DPoint & rCenter,double fRadius)1850         B2DPolygon createPolygonFromCircle( const B2DPoint& rCenter, double fRadius )
1851         {
1852             return createPolygonFromEllipse( rCenter, fRadius, fRadius );
1853         }
1854 
impCreateUnitCircle(sal_uInt32 nStartQuadrant)1855         B2DPolygon impCreateUnitCircle(sal_uInt32 nStartQuadrant)
1856         {
1857             B2DPolygon aUnitCircle;
1858 	        const double fKappa((M_SQRT2 - 1.0) * 4.0 / 3.0);
1859             const double fScaledKappa(fKappa * (1.0 / STEPSPERQUARTER));
1860             const B2DHomMatrix aRotateMatrix(createRotateB2DHomMatrix(F_PI2 / STEPSPERQUARTER));
1861 
1862             B2DPoint aPoint(1.0, 0.0);
1863             B2DPoint aForward(1.0, fScaledKappa);
1864             B2DPoint aBackward(1.0, -fScaledKappa);
1865 
1866             if(0 != nStartQuadrant)
1867             {
1868                 const B2DHomMatrix aQuadrantMatrix(createRotateB2DHomMatrix(F_PI2 * (nStartQuadrant % 4)));
1869                 aPoint *= aQuadrantMatrix;
1870                 aBackward *= aQuadrantMatrix;
1871                 aForward *= aQuadrantMatrix;
1872             }
1873 
1874             aUnitCircle.append(aPoint);
1875 
1876             for(sal_uInt32 a(0); a < STEPSPERQUARTER * 4; a++)
1877             {
1878                 aPoint *= aRotateMatrix;
1879                 aBackward *= aRotateMatrix;
1880                 aUnitCircle.appendBezierSegment(aForward, aBackward, aPoint);
1881                 aForward *= aRotateMatrix;
1882             }
1883 
1884             aUnitCircle.setClosed(true);
1885 		    aUnitCircle.removeDoublePoints();
1886 
1887             return aUnitCircle;
1888         }
1889 
createHalfUnitCircle()1890         B2DPolygon createHalfUnitCircle()
1891         {
1892             static B2DPolygon aUnitHalfCircle;
1893 
1894             if(!aUnitHalfCircle.count())
1895             {
1896                 const double fKappa((M_SQRT2 - 1.0) * 4.0 / 3.0);
1897                 const double fScaledKappa(fKappa * (1.0 / STEPSPERQUARTER));
1898                 const B2DHomMatrix aRotateMatrix(createRotateB2DHomMatrix(F_PI2 / STEPSPERQUARTER));
1899                 B2DPoint aPoint(1.0, 0.0);
1900                 B2DPoint aForward(1.0, fScaledKappa);
1901                 B2DPoint aBackward(1.0, -fScaledKappa);
1902 
1903                 aUnitHalfCircle.append(aPoint);
1904 
1905                 for(sal_uInt32 a(0); a < STEPSPERQUARTER * 2; a++)
1906                 {
1907                     aPoint *= aRotateMatrix;
1908                     aBackward *= aRotateMatrix;
1909                     aUnitHalfCircle.appendBezierSegment(aForward, aBackward, aPoint);
1910                     aForward *= aRotateMatrix;
1911                 }
1912             }
1913 
1914             return aUnitHalfCircle;
1915         }
1916 
createPolygonFromUnitCircle(sal_uInt32 nStartQuadrant)1917         B2DPolygon createPolygonFromUnitCircle(sal_uInt32 nStartQuadrant)
1918 		{
1919             switch(nStartQuadrant % 4)
1920             {
1921                 case 1 :
1922                 {
1923         			static B2DPolygon aUnitCircleStartQuadrantOne;
1924 
1925                     if(!aUnitCircleStartQuadrantOne.count())
1926                     {
1927     		            ::osl::Mutex m_mutex;
1928                         aUnitCircleStartQuadrantOne = impCreateUnitCircle(1);
1929                     }
1930 
1931                     return aUnitCircleStartQuadrantOne;
1932                 }
1933                 case 2 :
1934                 {
1935         			static B2DPolygon aUnitCircleStartQuadrantTwo;
1936 
1937                     if(!aUnitCircleStartQuadrantTwo.count())
1938                     {
1939     		            ::osl::Mutex m_mutex;
1940                         aUnitCircleStartQuadrantTwo = impCreateUnitCircle(2);
1941                     }
1942 
1943                     return aUnitCircleStartQuadrantTwo;
1944                 }
1945                 case 3 :
1946                 {
1947         			static B2DPolygon aUnitCircleStartQuadrantThree;
1948 
1949                     if(!aUnitCircleStartQuadrantThree.count())
1950                     {
1951     		            ::osl::Mutex m_mutex;
1952                         aUnitCircleStartQuadrantThree = impCreateUnitCircle(3);
1953                     }
1954 
1955                     return aUnitCircleStartQuadrantThree;
1956                 }
1957                 default : // case 0 :
1958                 {
1959         			static B2DPolygon aUnitCircleStartQuadrantZero;
1960 
1961                     if(!aUnitCircleStartQuadrantZero.count())
1962                     {
1963     		            ::osl::Mutex m_mutex;
1964                         aUnitCircleStartQuadrantZero = impCreateUnitCircle(0);
1965                     }
1966 
1967                     return aUnitCircleStartQuadrantZero;
1968                 }
1969             }
1970 		}
1971 
createPolygonFromEllipse(const B2DPoint & rCenter,double fRadiusX,double fRadiusY)1972         B2DPolygon createPolygonFromEllipse( const B2DPoint& rCenter, double fRadiusX, double fRadiusY )
1973         {
1974 			B2DPolygon aRetval(createPolygonFromUnitCircle());
1975 			const B2DHomMatrix aMatrix(createScaleTranslateB2DHomMatrix(fRadiusX, fRadiusY, rCenter.getX(), rCenter.getY()));
1976 
1977 			aRetval.transform(aMatrix);
1978 
1979             return aRetval;
1980         }
1981 
createPolygonFromUnitEllipseSegment(double fStart,double fEnd)1982         B2DPolygon createPolygonFromUnitEllipseSegment( double fStart, double fEnd )
1983 		{
1984 	        B2DPolygon aRetval;
1985 
1986 			// truncate fStart, fEnd to a range of [0.0 .. F_2PI[ where F_2PI
1987 			// falls back to 0.0 to ensure a unique definition
1988 			if(fTools::less(fStart, 0.0))
1989 			{
1990 				fStart = 0.0;
1991 			}
1992 
1993 			if(fTools::moreOrEqual(fStart, F_2PI))
1994 			{
1995 				fStart = 0.0;
1996 			}
1997 
1998 			if(fTools::less(fEnd, 0.0))
1999 			{
2000 				fEnd = 0.0;
2001 			}
2002 
2003 			if(fTools::moreOrEqual(fEnd, F_2PI))
2004 			{
2005 				fEnd = 0.0;
2006 			}
2007 
2008 		    if(fTools::equal(fStart, fEnd))
2009             {
2010                 // same start and end angle, add single point
2011                 aRetval.append(B2DPoint(cos(fStart), sin(fStart)));
2012             }
2013             else
2014             {
2015                 const sal_uInt32 nSegments(STEPSPERQUARTER * 4);
2016                 const double fAnglePerSegment(F_PI2 / STEPSPERQUARTER);
2017                 const sal_uInt32 nStartSegment(sal_uInt32(fStart / fAnglePerSegment) % nSegments);
2018                 const sal_uInt32 nEndSegment(sal_uInt32(fEnd / fAnglePerSegment) % nSegments);
2019     	        const double fKappa((M_SQRT2 - 1.0) * 4.0 / 3.0);
2020                 const double fScaledKappa(fKappa * (1.0 / STEPSPERQUARTER));
2021 
2022                 B2DPoint aSegStart(cos(fStart), sin(fStart));
2023                 aRetval.append(aSegStart);
2024 
2025                 if(nStartSegment == nEndSegment && fTools::more(fEnd, fStart))
2026                 {
2027                     // start and end in one sector and in the right order, create in one segment
2028                     const B2DPoint aSegEnd(cos(fEnd), sin(fEnd));
2029                     const double fFactor(fScaledKappa * ((fEnd - fStart) / fAnglePerSegment));
2030 
2031                     aRetval.appendBezierSegment(
2032                         aSegStart + (B2DPoint(-aSegStart.getY(), aSegStart.getX()) * fFactor),
2033                         aSegEnd - (B2DPoint(-aSegEnd.getY(), aSegEnd.getX()) * fFactor),
2034                         aSegEnd);
2035                 }
2036                 else
2037                 {
2038                     double fSegEndRad((nStartSegment + 1) * fAnglePerSegment);
2039                     double fFactor(fScaledKappa * ((fSegEndRad - fStart) / fAnglePerSegment));
2040                     B2DPoint aSegEnd(cos(fSegEndRad), sin(fSegEndRad));
2041 
2042                     aRetval.appendBezierSegment(
2043                         aSegStart + (B2DPoint(-aSegStart.getY(), aSegStart.getX()) * fFactor),
2044                         aSegEnd - (B2DPoint(-aSegEnd.getY(), aSegEnd.getX()) * fFactor),
2045                         aSegEnd);
2046 
2047                     sal_uInt32 nSegment((nStartSegment + 1) % nSegments);
2048                     aSegStart = aSegEnd;
2049 
2050                     while(nSegment != nEndSegment)
2051                     {
2052                         // No end in this sector, add full sector.
2053                         fSegEndRad = (nSegment + 1) * fAnglePerSegment;
2054                         aSegEnd = B2DPoint(cos(fSegEndRad), sin(fSegEndRad));
2055 
2056 				        aRetval.appendBezierSegment(
2057                             aSegStart + (B2DPoint(-aSegStart.getY(), aSegStart.getX()) * fScaledKappa),
2058                             aSegEnd - (B2DPoint(-aSegEnd.getY(), aSegEnd.getX()) * fScaledKappa),
2059                             aSegEnd);
2060 
2061                         nSegment = (nSegment + 1) % nSegments;
2062                         aSegStart = aSegEnd;
2063                     }
2064 
2065                     // End in this sector
2066                     const double fSegStartRad(nSegment * fAnglePerSegment);
2067                     fFactor = fScaledKappa * ((fEnd - fSegStartRad) / fAnglePerSegment);
2068                     aSegEnd = B2DPoint(cos(fEnd), sin(fEnd));
2069 
2070                     aRetval.appendBezierSegment(
2071                         aSegStart + (B2DPoint(-aSegStart.getY(), aSegStart.getX()) * fFactor),
2072                         aSegEnd - (B2DPoint(-aSegEnd.getY(), aSegEnd.getX()) * fFactor),
2073                         aSegEnd);
2074                 }
2075             }
2076 
2077 			// remove double points between segments created by segmented creation
2078 			aRetval.removeDoublePoints();
2079 
2080 			return aRetval;
2081 		}
2082 
createPolygonFromEllipseSegment(const B2DPoint & rCenter,double fRadiusX,double fRadiusY,double fStart,double fEnd)2083         B2DPolygon createPolygonFromEllipseSegment( const B2DPoint& rCenter, double fRadiusX, double fRadiusY, double fStart, double fEnd )
2084 		{
2085 	        B2DPolygon aRetval(createPolygonFromUnitEllipseSegment(fStart, fEnd));
2086 			const B2DHomMatrix aMatrix(createScaleTranslateB2DHomMatrix(fRadiusX, fRadiusY, rCenter.getX(), rCenter.getY()));
2087 
2088 			aRetval.transform(aMatrix);
2089 
2090 			return aRetval;
2091 		}
2092 
hasNeutralPoints(const B2DPolygon & rCandidate)2093 		bool hasNeutralPoints(const B2DPolygon& rCandidate)
2094 		{
2095 			OSL_ENSURE(!rCandidate.areControlPointsUsed(), "hasNeutralPoints: ATM works not for curves (!)");
2096 			const sal_uInt32 nPointCount(rCandidate.count());
2097 
2098 			if(nPointCount > 2L)
2099 			{
2100 				B2DPoint aPrevPoint(rCandidate.getB2DPoint(nPointCount - 1L));
2101 				B2DPoint aCurrPoint(rCandidate.getB2DPoint(0L));
2102 
2103 				for(sal_uInt32 a(0L); a < nPointCount; a++)
2104 				{
2105 					const B2DPoint aNextPoint(rCandidate.getB2DPoint((a + 1) % nPointCount));
2106 					const B2DVector aPrevVec(aPrevPoint - aCurrPoint);
2107 					const B2DVector aNextVec(aNextPoint - aCurrPoint);
2108 					const B2VectorOrientation aOrientation(getOrientation(aNextVec, aPrevVec));
2109 
2110 					if(ORIENTATION_NEUTRAL == aOrientation)
2111 					{
2112 						// current has neutral orientation
2113 						return true;
2114 					}
2115 					else
2116 					{
2117 						// prepare next
2118 						aPrevPoint = aCurrPoint;
2119 						aCurrPoint = aNextPoint;
2120 					}
2121 				}
2122 			}
2123 
2124 			return false;
2125 		}
2126 
removeNeutralPoints(const B2DPolygon & rCandidate)2127 		B2DPolygon removeNeutralPoints(const B2DPolygon& rCandidate)
2128 		{
2129 			if(hasNeutralPoints(rCandidate))
2130 			{
2131 				const sal_uInt32 nPointCount(rCandidate.count());
2132 				B2DPolygon aRetval;
2133 				B2DPoint aPrevPoint(rCandidate.getB2DPoint(nPointCount - 1L));
2134 				B2DPoint aCurrPoint(rCandidate.getB2DPoint(0L));
2135 
2136 				for(sal_uInt32 a(0L); a < nPointCount; a++)
2137 				{
2138 					const B2DPoint aNextPoint(rCandidate.getB2DPoint((a + 1) % nPointCount));
2139 					const B2DVector aPrevVec(aPrevPoint - aCurrPoint);
2140 					const B2DVector aNextVec(aNextPoint - aCurrPoint);
2141 					const B2VectorOrientation aOrientation(getOrientation(aNextVec, aPrevVec));
2142 
2143 					if(ORIENTATION_NEUTRAL == aOrientation)
2144 					{
2145 						// current has neutral orientation, leave it out and prepare next
2146 						aCurrPoint = aNextPoint;
2147 					}
2148 					else
2149 					{
2150 						// add current point
2151 						aRetval.append(aCurrPoint);
2152 
2153 						// prepare next
2154 						aPrevPoint = aCurrPoint;
2155 						aCurrPoint = aNextPoint;
2156 					}
2157 				}
2158 
2159 				while(aRetval.count() && ORIENTATION_NEUTRAL == getOrientationForIndex(aRetval, 0L))
2160 				{
2161 					aRetval.remove(0L);
2162 				}
2163 
2164 				// copy closed state
2165 				aRetval.setClosed(rCandidate.isClosed());
2166 
2167 				return aRetval;
2168 			}
2169 			else
2170 			{
2171 				return rCandidate;
2172 			}
2173 		}
2174 
isConvex(const B2DPolygon & rCandidate)2175 		bool isConvex(const B2DPolygon& rCandidate)
2176 		{
2177 			OSL_ENSURE(!rCandidate.areControlPointsUsed(), "isConvex: ATM works not for curves (!)");
2178 			const sal_uInt32 nPointCount(rCandidate.count());
2179 
2180 			if(nPointCount > 2L)
2181 			{
2182 				const B2DPoint aPrevPoint(rCandidate.getB2DPoint(nPointCount - 1L));
2183 				B2DPoint aCurrPoint(rCandidate.getB2DPoint(0L));
2184 				B2DVector aCurrVec(aPrevPoint - aCurrPoint);
2185 				B2VectorOrientation aOrientation(ORIENTATION_NEUTRAL);
2186 
2187 				for(sal_uInt32 a(0L); a < nPointCount; a++)
2188 				{
2189 					const B2DPoint aNextPoint(rCandidate.getB2DPoint((a + 1) % nPointCount));
2190 					const B2DVector aNextVec(aNextPoint - aCurrPoint);
2191 					const B2VectorOrientation aCurrentOrientation(getOrientation(aNextVec, aCurrVec));
2192 
2193 					if(ORIENTATION_NEUTRAL == aOrientation)
2194 					{
2195 						// set start value, maybe neutral again
2196 						aOrientation = aCurrentOrientation;
2197 					}
2198 					else
2199 					{
2200 						if(ORIENTATION_NEUTRAL != aCurrentOrientation && aCurrentOrientation != aOrientation)
2201 						{
2202 							// different orientations found, that's it
2203 							return false;
2204 						}
2205 					}
2206 
2207 					// prepare next
2208 					aCurrPoint = aNextPoint;
2209 					aCurrVec = -aNextVec;
2210 				}
2211 			}
2212 
2213 			return true;
2214 		}
2215 
getOrientationForIndex(const B2DPolygon & rCandidate,sal_uInt32 nIndex)2216 		B2VectorOrientation getOrientationForIndex(const B2DPolygon& rCandidate, sal_uInt32 nIndex)
2217 		{
2218 			OSL_ENSURE(nIndex < rCandidate.count(), "getOrientationForIndex: index out of range (!)");
2219 			const B2DPoint aPrev(rCandidate.getB2DPoint(getIndexOfPredecessor(nIndex, rCandidate)));
2220 			const B2DPoint aCurr(rCandidate.getB2DPoint(nIndex));
2221 			const B2DPoint aNext(rCandidate.getB2DPoint(getIndexOfSuccessor(nIndex, rCandidate)));
2222 			const B2DVector aBack(aPrev - aCurr);
2223 			const B2DVector aForw(aNext - aCurr);
2224 
2225 			return getOrientation(aForw, aBack);
2226 		}
2227 
isPointOnLine(const B2DPoint & rStart,const B2DPoint & rEnd,const B2DPoint & rCandidate,bool bWithPoints)2228 		bool isPointOnLine(const B2DPoint& rStart, const B2DPoint& rEnd, const B2DPoint& rCandidate, bool bWithPoints)
2229 		{
2230 			if(rCandidate.equal(rStart) || rCandidate.equal(rEnd))
2231 			{
2232 				// candidate is in epsilon around start or end -> inside
2233 				return bWithPoints;
2234 			}
2235 			else if(rStart.equal(rEnd))
2236 			{
2237 				// start and end are equal, but candidate is outside their epsilon -> outside
2238 				return false;
2239 			}
2240 			else
2241 			{
2242 				const B2DVector aEdgeVector(rEnd - rStart);
2243 				const B2DVector aTestVector(rCandidate - rStart);
2244 
2245 				if(areParallel(aEdgeVector, aTestVector))
2246 				{
2247 					const double fZero(0.0);
2248 					const double fOne(1.0);
2249 					const double fParamTestOnCurr(fabs(aEdgeVector.getX()) > fabs(aEdgeVector.getY())
2250 						? aTestVector.getX() / aEdgeVector.getX()
2251 						: aTestVector.getY() / aEdgeVector.getY());
2252 
2253 					if(fTools::more(fParamTestOnCurr, fZero) && fTools::less(fParamTestOnCurr, fOne))
2254 					{
2255 						return true;
2256 					}
2257 				}
2258 
2259 				return false;
2260 			}
2261 		}
2262 
isPointOnPolygon(const B2DPolygon & rCandidate,const B2DPoint & rPoint,bool bWithPoints)2263 		bool isPointOnPolygon(const B2DPolygon& rCandidate, const B2DPoint& rPoint, bool bWithPoints)
2264 		{
2265 			const B2DPolygon aCandidate(rCandidate.areControlPointsUsed() ? rCandidate.getDefaultAdaptiveSubdivision() : rCandidate);
2266 			const sal_uInt32 nPointCount(aCandidate.count());
2267 
2268 			if(nPointCount > 1L)
2269 			{
2270 				const sal_uInt32 nLoopCount(aCandidate.isClosed() ? nPointCount : nPointCount - 1L);
2271 				B2DPoint aCurrentPoint(aCandidate.getB2DPoint(0L));
2272 
2273 				for(sal_uInt32 a(0L); a < nLoopCount; a++)
2274 				{
2275 					const B2DPoint aNextPoint(aCandidate.getB2DPoint((a + 1L) % nPointCount));
2276 
2277 					if(isPointOnLine(aCurrentPoint, aNextPoint, rPoint, bWithPoints))
2278 					{
2279 						return true;
2280 					}
2281 
2282 					aCurrentPoint = aNextPoint;
2283 				}
2284 			}
2285 			else if(nPointCount && bWithPoints)
2286 			{
2287 				return rPoint.equal(aCandidate.getB2DPoint(0L));
2288 			}
2289 
2290 			return false;
2291 		}
2292 
isPointInTriangle(const B2DPoint & rA,const B2DPoint & rB,const B2DPoint & rC,const B2DPoint & rCandidate,bool bWithBorder)2293 		bool isPointInTriangle(const B2DPoint& rA, const B2DPoint& rB, const B2DPoint& rC, const B2DPoint& rCandidate, bool bWithBorder)
2294 		{
2295 			if(arePointsOnSameSideOfLine(rA, rB, rC, rCandidate, bWithBorder))
2296 			{
2297 				if(arePointsOnSameSideOfLine(rB, rC, rA, rCandidate, bWithBorder))
2298 				{
2299 					if(arePointsOnSameSideOfLine(rC, rA, rB, rCandidate, bWithBorder))
2300 					{
2301 						return true;
2302 					}
2303 				}
2304 			}
2305 
2306 			return false;
2307 		}
2308 
arePointsOnSameSideOfLine(const B2DPoint & rStart,const B2DPoint & rEnd,const B2DPoint & rCandidateA,const B2DPoint & rCandidateB,bool bWithLine)2309 		bool arePointsOnSameSideOfLine(const B2DPoint& rStart, const B2DPoint& rEnd, const B2DPoint& rCandidateA, const B2DPoint& rCandidateB, bool bWithLine)
2310 		{
2311 			const B2DVector aLineVector(rEnd - rStart);
2312 			const B2DVector aVectorToA(rEnd - rCandidateA);
2313 			const double fCrossA(aLineVector.cross(aVectorToA));
2314 
2315 			if(fTools::equalZero(fCrossA))
2316 			{
2317 				// one point on the line
2318 				return bWithLine;
2319 			}
2320 
2321 			const B2DVector aVectorToB(rEnd - rCandidateB);
2322 			const double fCrossB(aLineVector.cross(aVectorToB));
2323 
2324 			if(fTools::equalZero(fCrossB))
2325 			{
2326 				// one point on the line
2327 				return bWithLine;
2328 			}
2329 
2330 			// return true if they both have the same sign
2331 			return ((fCrossA > 0.0) == (fCrossB > 0.0));
2332 		}
2333 
addTriangleFan(const B2DPolygon & rCandidate,B2DPolygon & rTarget)2334 		void addTriangleFan(const B2DPolygon& rCandidate, B2DPolygon& rTarget)
2335 		{
2336 			const sal_uInt32 nCount(rCandidate.count());
2337 
2338 			if(nCount > 2L)
2339 			{
2340 				const B2DPoint aStart(rCandidate.getB2DPoint(0L));
2341 				B2DPoint aLast(rCandidate.getB2DPoint(1L));
2342 
2343 				for(sal_uInt32 a(2L); a < nCount; a++)
2344 				{
2345 					const B2DPoint aCurrent(rCandidate.getB2DPoint(a));
2346 					rTarget.append(aStart);
2347 					rTarget.append(aLast);
2348 					rTarget.append(aCurrent);
2349 
2350 					// prepare next
2351 					aLast = aCurrent;
2352 				}
2353 			}
2354 		}
2355 
2356         namespace
2357         {
2358             /// return 0 for input of 0, -1 for negative and 1 for positive input
lcl_sgn(const double n)2359             inline int lcl_sgn( const double n )
2360             {
2361                 return n == 0.0 ? 0 : 1 - 2*::rtl::math::isSignBitSet(n);
2362             }
2363         }
2364 
isRectangle(const B2DPolygon & rPoly)2365         bool isRectangle( const B2DPolygon& rPoly )
2366         {
2367             // polygon must be closed to resemble a rect, and contain
2368             // at least four points.
2369             if( !rPoly.isClosed() ||
2370                 rPoly.count() < 4 ||
2371                 rPoly.areControlPointsUsed() )
2372             {
2373                 return false;
2374             }
2375 
2376             // number of 90 degree turns the polygon has taken
2377             int nNumTurns(0);
2378 
2379             int  nVerticalEdgeType=0;
2380             int  nHorizontalEdgeType=0;
2381             bool bNullVertex(true);
2382             bool bCWPolygon(false);  // when true, polygon is CW
2383                                      // oriented, when false, CCW
2384             bool bOrientationSet(false); // when false, polygon
2385                                          // orientation has not yet
2386                                          // been determined.
2387 
2388             // scan all _edges_ (which involves coming back to point 0
2389             // for the last edge - thus the modulo operation below)
2390             const sal_Int32 nCount( rPoly.count() );
2391             for( sal_Int32 i=0; i<nCount; ++i )
2392             {
2393                 const B2DPoint& rPoint0( rPoly.getB2DPoint(i % nCount) );
2394                 const B2DPoint& rPoint1( rPoly.getB2DPoint((i+1) % nCount) );
2395 
2396                 // is 0 for zero direction vector, 1 for south edge and -1
2397                 // for north edge (standard screen coordinate system)
2398                 int nCurrVerticalEdgeType( lcl_sgn( rPoint1.getY() - rPoint0.getY() ) );
2399 
2400                 // is 0 for zero direction vector, 1 for east edge and -1
2401                 // for west edge (standard screen coordinate system)
2402                 int nCurrHorizontalEdgeType( lcl_sgn(rPoint1.getX() - rPoint0.getX()) );
2403 
2404                 if( nCurrVerticalEdgeType && nCurrHorizontalEdgeType )
2405                     return false; // oblique edge - for sure no rect
2406 
2407                 const bool bCurrNullVertex( !nCurrVerticalEdgeType && !nCurrHorizontalEdgeType );
2408 
2409                 // current vertex is equal to previous - just skip,
2410                 // until we have a real edge
2411                 if( bCurrNullVertex )
2412                     continue;
2413 
2414                 // if previous edge has two identical points, because
2415                 // no previous edge direction was available, simply
2416                 // take this first non-null edge as the start
2417                 // direction. That's what will happen here, if
2418                 // bNullVertex is false
2419                 if( !bNullVertex )
2420                 {
2421                     // 2D cross product - is 1 for CW and -1 for CCW turns
2422                     const int nCrossProduct( nHorizontalEdgeType*nCurrVerticalEdgeType -
2423                                              nVerticalEdgeType*nCurrHorizontalEdgeType );
2424 
2425                     if( !nCrossProduct )
2426                         continue; // no change in orientation -
2427                                   // collinear edges - just go on
2428 
2429                     // if polygon orientation is not set, we'll
2430                     // determine it now
2431                     if( !bOrientationSet )
2432                     {
2433                         bCWPolygon = nCrossProduct == 1;
2434                         bOrientationSet = true;
2435                     }
2436                     else
2437                     {
2438                         // if current turn orientation is not equal
2439                         // initial orientation, this is not a
2440                         // rectangle (as rectangles have consistent
2441                         // orientation).
2442                         if( (nCrossProduct == 1) != bCWPolygon )
2443                             return false;
2444                     }
2445 
2446                     ++nNumTurns;
2447 
2448                     // More than four 90 degree turns are an
2449                     // indication that this must not be a rectangle.
2450                     if( nNumTurns > 4 )
2451                         return false;
2452                 }
2453 
2454                 // store current state for the next turn
2455                 nVerticalEdgeType	= nCurrVerticalEdgeType;
2456                 nHorizontalEdgeType = nCurrHorizontalEdgeType;
2457                 bNullVertex		    = false; // won't reach this line,
2458                                              // if bCurrNullVertex is
2459                                              // true - see above
2460             }
2461 
2462             return true;
2463         }
2464 
createB3DPolygonFromB2DPolygon(const B2DPolygon & rCandidate,double fZCoordinate)2465 		B3DPolygon createB3DPolygonFromB2DPolygon(const B2DPolygon& rCandidate, double fZCoordinate)
2466 		{
2467 			if(rCandidate.areControlPointsUsed())
2468 			{
2469 				// call myself recursively with subdivided input
2470 				const B2DPolygon aCandidate(adaptiveSubdivideByAngle(rCandidate));
2471 				return createB3DPolygonFromB2DPolygon(aCandidate, fZCoordinate);
2472 			}
2473 			else
2474 			{
2475 				B3DPolygon aRetval;
2476 
2477 				for(sal_uInt32 a(0L); a < rCandidate.count(); a++)
2478 				{
2479 					B2DPoint aPoint(rCandidate.getB2DPoint(a));
2480 					aRetval.append(B3DPoint(aPoint.getX(), aPoint.getY(), fZCoordinate));
2481 				}
2482 
2483 				// copy closed state
2484 				aRetval.setClosed(rCandidate.isClosed());
2485 
2486 				return aRetval;
2487 			}
2488 		}
2489 
createB2DPolygonFromB3DPolygon(const B3DPolygon & rCandidate,const B3DHomMatrix & rMat)2490 		B2DPolygon createB2DPolygonFromB3DPolygon(const B3DPolygon& rCandidate, const B3DHomMatrix& rMat)
2491 		{
2492 			B2DPolygon aRetval;
2493 			const sal_uInt32 nCount(rCandidate.count());
2494 			const bool bIsIdentity(rMat.isIdentity());
2495 
2496 			for(sal_uInt32 a(0L); a < nCount; a++)
2497 			{
2498 				B3DPoint aCandidate(rCandidate.getB3DPoint(a));
2499 
2500 				if(!bIsIdentity)
2501 				{
2502 					aCandidate *= rMat;
2503 				}
2504 
2505 				aRetval.append(B2DPoint(aCandidate.getX(), aCandidate.getY()));
2506 			}
2507 
2508 			// copy closed state
2509 			aRetval.setClosed(rCandidate.isClosed());
2510 
2511 			return aRetval;
2512 		}
2513 
getDistancePointToEndlessRay(const B2DPoint & rPointA,const B2DPoint & rPointB,const B2DPoint & rTestPoint,double & rCut)2514 		double getDistancePointToEndlessRay(const B2DPoint& rPointA, const B2DPoint& rPointB, const B2DPoint& rTestPoint, double& rCut)
2515 		{
2516 			if(rPointA.equal(rPointB))
2517 			{
2518 				rCut = 0.0;
2519 				const B2DVector aVector(rTestPoint - rPointA);
2520 				return aVector.getLength();
2521 			}
2522 			else
2523 			{
2524 				// get the relative cut value on line vector (Vector1) for cut with perpendicular through TestPoint
2525 				const B2DVector aVector1(rPointB - rPointA);
2526 				const B2DVector aVector2(rTestPoint - rPointA);
2527 				const double fDividend((aVector2.getX() * aVector1.getX()) + (aVector2.getY() * aVector1.getY()));
2528 				const double fDivisor((aVector1.getX() * aVector1.getX()) + (aVector1.getY() * aVector1.getY()));
2529 
2530                 rCut = fDividend / fDivisor;
2531 
2532 				const B2DPoint aCutPoint(rPointA + rCut * aVector1);
2533 				const B2DVector aVector(rTestPoint - aCutPoint);
2534 				return aVector.getLength();
2535 			}
2536 		}
2537 
getSmallestDistancePointToEdge(const B2DPoint & rPointA,const B2DPoint & rPointB,const B2DPoint & rTestPoint,double & rCut)2538 		double getSmallestDistancePointToEdge(const B2DPoint& rPointA, const B2DPoint& rPointB, const B2DPoint& rTestPoint, double& rCut)
2539 		{
2540 			if(rPointA.equal(rPointB))
2541 			{
2542 				rCut = 0.0;
2543 				const B2DVector aVector(rTestPoint - rPointA);
2544 				return aVector.getLength();
2545 			}
2546 			else
2547 			{
2548 				// get the relative cut value on line vector (Vector1) for cut with perpendicular through TestPoint
2549 				const B2DVector aVector1(rPointB - rPointA);
2550 				const B2DVector aVector2(rTestPoint - rPointA);
2551 				const double fDividend((aVector2.getX() * aVector1.getX()) + (aVector2.getY() * aVector1.getY()));
2552 				const double fDivisor((aVector1.getX() * aVector1.getX()) + (aVector1.getY() * aVector1.getY()));
2553 				const double fCut(fDividend / fDivisor);
2554 
2555 				if(fCut < 0.0)
2556 				{
2557 					// not in line range, get distance to PointA
2558 					rCut = 0.0;
2559 					return aVector2.getLength();
2560 				}
2561 				else if(fCut > 1.0)
2562 				{
2563 					// not in line range, get distance to PointB
2564 					rCut = 1.0;
2565 					const B2DVector aVector(rTestPoint - rPointB);
2566 					return aVector.getLength();
2567 				}
2568 				else
2569 				{
2570 					// in line range
2571 					const B2DPoint aCutPoint(rPointA + fCut * aVector1);
2572 					const B2DVector aVector(rTestPoint - aCutPoint);
2573 					rCut = fCut;
2574 					return aVector.getLength();
2575 				}
2576 			}
2577 		}
2578 
getSmallestDistancePointToPolygon(const B2DPolygon & rCandidate,const B2DPoint & rTestPoint,sal_uInt32 & rEdgeIndex,double & rCut)2579 		double getSmallestDistancePointToPolygon(const B2DPolygon& rCandidate, const B2DPoint& rTestPoint, sal_uInt32& rEdgeIndex, double& rCut)
2580 		{
2581 			double fRetval(DBL_MAX);
2582 			const sal_uInt32 nPointCount(rCandidate.count());
2583 
2584 			if(nPointCount > 1L)
2585 			{
2586 				const double fZero(0.0);
2587 				const sal_uInt32 nEdgeCount(rCandidate.isClosed() ? nPointCount : nPointCount - 1L);
2588 				B2DCubicBezier aBezier;
2589 				aBezier.setStartPoint(rCandidate.getB2DPoint(0));
2590 
2591 				for(sal_uInt32 a(0L); a < nEdgeCount; a++)
2592 				{
2593 					const sal_uInt32 nNextIndex((a + 1) % nPointCount);
2594 					aBezier.setEndPoint(rCandidate.getB2DPoint(nNextIndex));
2595 					double fEdgeDist;
2596 					double fNewCut;
2597 					bool bEdgeIsCurve(false);
2598 
2599 					if(rCandidate.areControlPointsUsed())
2600 					{
2601 						aBezier.setControlPointA(rCandidate.getNextControlPoint(a));
2602 						aBezier.setControlPointB(rCandidate.getPrevControlPoint(nNextIndex));
2603 						aBezier.testAndSolveTrivialBezier();
2604 						bEdgeIsCurve = aBezier.isBezier();
2605 					}
2606 
2607 					if(bEdgeIsCurve)
2608 					{
2609 						fEdgeDist = aBezier.getSmallestDistancePointToBezierSegment(rTestPoint, fNewCut);
2610 					}
2611 					else
2612 					{
2613 						fEdgeDist = getSmallestDistancePointToEdge(aBezier.getStartPoint(), aBezier.getEndPoint(), rTestPoint, fNewCut);
2614 					}
2615 
2616 					if(DBL_MAX == fRetval || fEdgeDist < fRetval)
2617 					{
2618 						fRetval = fEdgeDist;
2619 						rEdgeIndex = a;
2620 						rCut = fNewCut;
2621 
2622 						if(fTools::equal(fRetval, fZero))
2623 						{
2624 							// already found zero distance, cannot get better. Ensure numerical zero value and end loop.
2625 							fRetval = 0.0;
2626 							break;
2627 						}
2628 					}
2629 
2630 					// prepare next step
2631 					aBezier.setStartPoint(aBezier.getEndPoint());
2632 				}
2633 
2634 				if(1.0 == rCut)
2635 				{
2636 					// correct rEdgeIndex when not last point
2637 					if(rCandidate.isClosed())
2638 					{
2639 						rEdgeIndex = getIndexOfSuccessor(rEdgeIndex, rCandidate);
2640 						rCut = 0.0;
2641 					}
2642 					else
2643 					{
2644 						if(rEdgeIndex != nEdgeCount - 1L)
2645 						{
2646 							rEdgeIndex++;
2647 							rCut = 0.0;
2648 						}
2649 					}
2650 				}
2651 			}
2652 
2653 			return fRetval;
2654 		}
2655 
distort(const B2DPoint & rCandidate,const B2DRange & rOriginal,const B2DPoint & rTopLeft,const B2DPoint & rTopRight,const B2DPoint & rBottomLeft,const B2DPoint & rBottomRight)2656 		B2DPoint distort(const B2DPoint& rCandidate, const B2DRange& rOriginal, const B2DPoint& rTopLeft, const B2DPoint& rTopRight, const B2DPoint& rBottomLeft, const B2DPoint& rBottomRight)
2657 		{
2658 			if(fTools::equalZero(rOriginal.getWidth()) || fTools::equalZero(rOriginal.getHeight()))
2659 			{
2660 				return rCandidate;
2661 			}
2662 			else
2663 			{
2664 				const double fRelativeX((rCandidate.getX() - rOriginal.getMinX()) / rOriginal.getWidth());
2665 				const double fRelativeY((rCandidate.getY() - rOriginal.getMinY()) / rOriginal.getHeight());
2666 				const double fOneMinusRelativeX(1.0 - fRelativeX);
2667 				const double fOneMinusRelativeY(1.0 - fRelativeY);
2668 				const double fNewX((fOneMinusRelativeY) * ((fOneMinusRelativeX) * rTopLeft.getX() + fRelativeX * rTopRight.getX()) +
2669 					fRelativeY * ((fOneMinusRelativeX) * rBottomLeft.getX() + fRelativeX * rBottomRight.getX()));
2670 				const double fNewY((fOneMinusRelativeX) * ((fOneMinusRelativeY) * rTopLeft.getY() + fRelativeY * rBottomLeft.getY()) +
2671 					fRelativeX * ((fOneMinusRelativeY) * rTopRight.getY() + fRelativeY * rBottomRight.getY()));
2672 
2673 				return B2DPoint(fNewX, fNewY);
2674 			}
2675 		}
2676 
distort(const B2DPolygon & rCandidate,const B2DRange & rOriginal,const B2DPoint & rTopLeft,const B2DPoint & rTopRight,const B2DPoint & rBottomLeft,const B2DPoint & rBottomRight)2677 		B2DPolygon distort(const B2DPolygon& rCandidate, const B2DRange& rOriginal, const B2DPoint& rTopLeft, const B2DPoint& rTopRight, const B2DPoint& rBottomLeft, const B2DPoint& rBottomRight)
2678 		{
2679 			const sal_uInt32 nPointCount(rCandidate.count());
2680 
2681 			if(nPointCount && 0.0 != rOriginal.getWidth() && 0.0 != rOriginal.getHeight())
2682 			{
2683 				B2DPolygon aRetval;
2684 
2685 				for(sal_uInt32 a(0L); a < nPointCount; a++)
2686 				{
2687 					aRetval.append(distort(rCandidate.getB2DPoint(a), rOriginal, rTopLeft, rTopRight, rBottomLeft, rBottomRight));
2688 
2689 					if(rCandidate.areControlPointsUsed())
2690 					{
2691 						if(!rCandidate.getPrevControlPoint(a).equalZero())
2692 						{
2693 							aRetval.setPrevControlPoint(a, distort(rCandidate.getPrevControlPoint(a), rOriginal, rTopLeft, rTopRight, rBottomLeft, rBottomRight));
2694 						}
2695 
2696 						if(!rCandidate.getNextControlPoint(a).equalZero())
2697 						{
2698 							aRetval.setNextControlPoint(a, distort(rCandidate.getNextControlPoint(a), rOriginal, rTopLeft, rTopRight, rBottomLeft, rBottomRight));
2699 						}
2700 					}
2701 				}
2702 
2703 				aRetval.setClosed(rCandidate.isClosed());
2704 				return aRetval;
2705 			}
2706 			else
2707 			{
2708 				return rCandidate;
2709 			}
2710 		}
2711 
rotateAroundPoint(const B2DPolygon & rCandidate,const B2DPoint & rCenter,double fAngle)2712 		B2DPolygon rotateAroundPoint(const B2DPolygon& rCandidate, const B2DPoint& rCenter, double fAngle)
2713 		{
2714 			const sal_uInt32 nPointCount(rCandidate.count());
2715 			B2DPolygon aRetval(rCandidate);
2716 
2717 			if(nPointCount)
2718 			{
2719                 const B2DHomMatrix aMatrix(basegfx::tools::createRotateAroundPoint(rCenter, fAngle));
2720 
2721                 aRetval.transform(aMatrix);
2722 			}
2723 
2724 			return aRetval;
2725 		}
2726 
expandToCurve(const B2DPolygon & rCandidate)2727 		B2DPolygon expandToCurve(const B2DPolygon& rCandidate)
2728 		{
2729 			B2DPolygon aRetval(rCandidate);
2730 
2731 			for(sal_uInt32 a(0L); a < rCandidate.count(); a++)
2732 			{
2733 				expandToCurveInPoint(aRetval, a);
2734 			}
2735 
2736 			return aRetval;
2737 		}
2738 
expandToCurveInPoint(B2DPolygon & rCandidate,sal_uInt32 nIndex)2739 		bool expandToCurveInPoint(B2DPolygon& rCandidate, sal_uInt32 nIndex)
2740 		{
2741 			OSL_ENSURE(nIndex < rCandidate.count(), "expandToCurveInPoint: Access to polygon out of range (!)");
2742 			bool bRetval(false);
2743 			const sal_uInt32 nPointCount(rCandidate.count());
2744 
2745 			if(nPointCount)
2746 			{
2747 				// predecessor
2748 				if(!rCandidate.isPrevControlPointUsed(nIndex))
2749 				{
2750 					if(!rCandidate.isClosed() && 0 == nIndex)
2751 					{
2752 						// do not create previous vector for start point of open polygon
2753 					}
2754 					else
2755 					{
2756 						const sal_uInt32 nPrevIndex((nIndex + (nPointCount - 1)) % nPointCount);
2757 						rCandidate.setPrevControlPoint(nIndex, interpolate(rCandidate.getB2DPoint(nIndex), rCandidate.getB2DPoint(nPrevIndex), 1.0 / 3.0));
2758 						bRetval = true;
2759 					}
2760 				}
2761 
2762 				// successor
2763 				if(!rCandidate.isNextControlPointUsed(nIndex))
2764 				{
2765 					if(!rCandidate.isClosed() && nIndex + 1 == nPointCount)
2766 					{
2767 						// do not create next vector for end point of open polygon
2768 					}
2769 					else
2770 					{
2771 						const sal_uInt32 nNextIndex((nIndex + 1) % nPointCount);
2772 						rCandidate.setNextControlPoint(nIndex, interpolate(rCandidate.getB2DPoint(nIndex), rCandidate.getB2DPoint(nNextIndex), 1.0 / 3.0));
2773 						bRetval = true;
2774 					}
2775 				}
2776 			}
2777 
2778 			return bRetval;
2779 		}
2780 
setContinuity(const B2DPolygon & rCandidate,B2VectorContinuity eContinuity)2781 		B2DPolygon setContinuity(const B2DPolygon& rCandidate, B2VectorContinuity eContinuity)
2782 		{
2783 			B2DPolygon aRetval(rCandidate);
2784 
2785 			for(sal_uInt32 a(0L); a < rCandidate.count(); a++)
2786 			{
2787 				setContinuityInPoint(aRetval, a, eContinuity);
2788 			}
2789 
2790 			return aRetval;
2791 		}
2792 
setContinuityInPoint(B2DPolygon & rCandidate,sal_uInt32 nIndex,B2VectorContinuity eContinuity)2793 		bool setContinuityInPoint(B2DPolygon& rCandidate, sal_uInt32 nIndex, B2VectorContinuity eContinuity)
2794 		{
2795 			OSL_ENSURE(nIndex < rCandidate.count(), "setContinuityInPoint: Access to polygon out of range (!)");
2796 			bool bRetval(false);
2797 			const sal_uInt32 nPointCount(rCandidate.count());
2798 
2799 			if(nPointCount)
2800 			{
2801 				const B2DPoint aCurrentPoint(rCandidate.getB2DPoint(nIndex));
2802 
2803 				switch(eContinuity)
2804 				{
2805 					case CONTINUITY_NONE :
2806 					{
2807 						if(rCandidate.isPrevControlPointUsed(nIndex))
2808 						{
2809 							if(!rCandidate.isClosed() && 0 == nIndex)
2810 							{
2811 								// remove existing previous vector for start point of open polygon
2812 								rCandidate.resetPrevControlPoint(nIndex);
2813 							}
2814 							else
2815 							{
2816 								const sal_uInt32 nPrevIndex((nIndex + (nPointCount - 1)) % nPointCount);
2817 								rCandidate.setPrevControlPoint(nIndex, interpolate(aCurrentPoint, rCandidate.getB2DPoint(nPrevIndex), 1.0 / 3.0));
2818 							}
2819 
2820 							bRetval = true;
2821 						}
2822 
2823 						if(rCandidate.isNextControlPointUsed(nIndex))
2824 						{
2825 							if(!rCandidate.isClosed() && nIndex == nPointCount + 1)
2826 							{
2827 								// remove next vector for end point of open polygon
2828 								rCandidate.resetNextControlPoint(nIndex);
2829 							}
2830 							else
2831 							{
2832 								const sal_uInt32 nNextIndex((nIndex + 1) % nPointCount);
2833 								rCandidate.setNextControlPoint(nIndex, interpolate(aCurrentPoint, rCandidate.getB2DPoint(nNextIndex), 1.0 / 3.0));
2834 							}
2835 
2836 							bRetval = true;
2837 						}
2838 
2839 						break;
2840 					}
2841 					case CONTINUITY_C1 :
2842 					{
2843 						if(rCandidate.isPrevControlPointUsed(nIndex) && rCandidate.isNextControlPointUsed(nIndex))
2844 						{
2845 							// lengths both exist since both are used
2846 							B2DVector aVectorPrev(rCandidate.getPrevControlPoint(nIndex) - aCurrentPoint);
2847 							B2DVector aVectorNext(rCandidate.getNextControlPoint(nIndex) - aCurrentPoint);
2848 							const double fLenPrev(aVectorPrev.getLength());
2849 							const double fLenNext(aVectorNext.getLength());
2850 							aVectorPrev.normalize();
2851 							aVectorNext.normalize();
2852 							const B2VectorOrientation aOrientation(getOrientation(aVectorPrev, aVectorNext));
2853 
2854 							if(ORIENTATION_NEUTRAL == aOrientation && aVectorPrev.scalar(aVectorNext) < 0.0)
2855 							{
2856 								// parallel and opposite direction; check length
2857 								if(fTools::equal(fLenPrev, fLenNext))
2858 								{
2859 									// this would be even C2, but we want C1. Use the lengths of the corresponding edges.
2860 									const sal_uInt32 nPrevIndex((nIndex + (nPointCount - 1)) % nPointCount);
2861 									const sal_uInt32 nNextIndex((nIndex + 1) % nPointCount);
2862 									const double fLenPrevEdge(B2DVector(rCandidate.getB2DPoint(nPrevIndex) - aCurrentPoint).getLength() * (1.0 / 3.0));
2863 									const double fLenNextEdge(B2DVector(rCandidate.getB2DPoint(nNextIndex) - aCurrentPoint).getLength() * (1.0 / 3.0));
2864 
2865 									rCandidate.setControlPoints(nIndex,
2866 										aCurrentPoint + (aVectorPrev * fLenPrevEdge),
2867 										aCurrentPoint + (aVectorNext * fLenNextEdge));
2868 									bRetval = true;
2869 								}
2870 							}
2871 							else
2872 							{
2873 								// not parallel or same direction, set vectors and length
2874 								const B2DVector aNormalizedPerpendicular(getNormalizedPerpendicular(aVectorPrev + aVectorNext));
2875 
2876 								if(ORIENTATION_POSITIVE == aOrientation)
2877 								{
2878 									rCandidate.setControlPoints(nIndex,
2879 										aCurrentPoint - (aNormalizedPerpendicular * fLenPrev),
2880 										aCurrentPoint + (aNormalizedPerpendicular * fLenNext));
2881 								}
2882 								else
2883 								{
2884 									rCandidate.setControlPoints(nIndex,
2885 										aCurrentPoint + (aNormalizedPerpendicular * fLenPrev),
2886 										aCurrentPoint - (aNormalizedPerpendicular * fLenNext));
2887 								}
2888 
2889 								bRetval = true;
2890 							}
2891 						}
2892 						break;
2893 					}
2894 					case CONTINUITY_C2 :
2895 					{
2896 						if(rCandidate.isPrevControlPointUsed(nIndex) && rCandidate.isNextControlPointUsed(nIndex))
2897 						{
2898 							// lengths both exist since both are used
2899 							B2DVector aVectorPrev(rCandidate.getPrevControlPoint(nIndex) - aCurrentPoint);
2900 							B2DVector aVectorNext(rCandidate.getNextControlPoint(nIndex) - aCurrentPoint);
2901 							const double fCommonLength((aVectorPrev.getLength() + aVectorNext.getLength()) / 2.0);
2902 							aVectorPrev.normalize();
2903 							aVectorNext.normalize();
2904 							const B2VectorOrientation aOrientation(getOrientation(aVectorPrev, aVectorNext));
2905 
2906 							if(ORIENTATION_NEUTRAL == aOrientation && aVectorPrev.scalar(aVectorNext) < 0.0)
2907 							{
2908 								// parallel and opposite direction; set length. Use one direction for better numerical correctness
2909 								const B2DVector aScaledDirection(aVectorPrev * fCommonLength);
2910 
2911 								rCandidate.setControlPoints(nIndex,
2912 									aCurrentPoint + aScaledDirection,
2913 									aCurrentPoint - aScaledDirection);
2914 							}
2915 							else
2916 							{
2917 								// not parallel or same direction, set vectors and length
2918 								const B2DVector aNormalizedPerpendicular(getNormalizedPerpendicular(aVectorPrev + aVectorNext));
2919 								const B2DVector aPerpendicular(aNormalizedPerpendicular * fCommonLength);
2920 
2921 								if(ORIENTATION_POSITIVE == aOrientation)
2922 								{
2923 									rCandidate.setControlPoints(nIndex,
2924 										aCurrentPoint - aPerpendicular,
2925 										aCurrentPoint + aPerpendicular);
2926 								}
2927 								else
2928 								{
2929 									rCandidate.setControlPoints(nIndex,
2930 										aCurrentPoint + aPerpendicular,
2931 										aCurrentPoint - aPerpendicular);
2932 								}
2933 							}
2934 
2935 							bRetval = true;
2936 						}
2937 						break;
2938 					}
2939 				}
2940 			}
2941 
2942 			return bRetval;
2943 		}
2944 
growInNormalDirection(const B2DPolygon & rCandidate,double fValue)2945 		B2DPolygon growInNormalDirection(const B2DPolygon& rCandidate, double fValue)
2946 		{
2947 			if(0.0 != fValue)
2948 			{
2949 				if(rCandidate.areControlPointsUsed())
2950 				{
2951 					// call myself recursively with subdivided input
2952 					const B2DPolygon aCandidate(adaptiveSubdivideByAngle(rCandidate));
2953 					return growInNormalDirection(aCandidate, fValue);
2954 				}
2955 				else
2956 				{
2957 					B2DPolygon aRetval;
2958 					const sal_uInt32 nPointCount(rCandidate.count());
2959 
2960 					if(nPointCount)
2961 					{
2962 						B2DPoint aPrev(rCandidate.getB2DPoint(nPointCount - 1L));
2963 						B2DPoint aCurrent(rCandidate.getB2DPoint(0L));
2964 
2965 						for(sal_uInt32 a(0L); a < nPointCount; a++)
2966 						{
2967 							const B2DPoint aNext(rCandidate.getB2DPoint(a + 1L == nPointCount ? 0L : a + 1L));
2968 							const B2DVector aBack(aPrev - aCurrent);
2969 							const B2DVector aForw(aNext - aCurrent);
2970 							const B2DVector aPerpBack(getNormalizedPerpendicular(aBack));
2971 							const B2DVector aPerpForw(getNormalizedPerpendicular(aForw));
2972 							B2DVector aDirection(aPerpBack - aPerpForw);
2973 							aDirection.normalize();
2974 							aDirection *= fValue;
2975 							aRetval.append(aCurrent + aDirection);
2976 
2977 							// prepare next step
2978 							aPrev = aCurrent;
2979 							aCurrent = aNext;
2980 						}
2981 					}
2982 
2983 					// copy closed state
2984 					aRetval.setClosed(rCandidate.isClosed());
2985 
2986 					return aRetval;
2987 				}
2988 			}
2989 			else
2990 			{
2991 				return rCandidate;
2992 			}
2993 		}
2994 
reSegmentPolygon(const B2DPolygon & rCandidate,sal_uInt32 nSegments)2995 		B2DPolygon reSegmentPolygon(const B2DPolygon& rCandidate, sal_uInt32 nSegments)
2996 		{
2997 			B2DPolygon aRetval;
2998 			const sal_uInt32 nPointCount(rCandidate.count());
2999 
3000 			if(nPointCount && nSegments)
3001 			{
3002 				// get current segment count
3003 				const sal_uInt32 nSegmentCount(rCandidate.isClosed() ? nPointCount : nPointCount - 1L);
3004 
3005 				if(nSegmentCount == nSegments)
3006 				{
3007 					aRetval = rCandidate;
3008 				}
3009 				else
3010 				{
3011 					const double fLength(getLength(rCandidate));
3012 					const sal_uInt32 nLoopCount(rCandidate.isClosed() ? nSegments : nSegments + 1L);
3013 
3014 					for(sal_uInt32 a(0L); a < nLoopCount; a++)
3015 					{
3016 						const double fRelativePos((double)a / (double)nSegments); // 0.0 .. 1.0
3017 						const B2DPoint aNewPoint(getPositionRelative(rCandidate, fRelativePos, fLength));
3018 						aRetval.append(aNewPoint);
3019 					}
3020 
3021 					// copy closed flag
3022 					aRetval.setClosed(rCandidate.isClosed());
3023 				}
3024 			}
3025 
3026 			return aRetval;
3027 		}
3028 
reSegmentPolygonEdges(const B2DPolygon & rCandidate,sal_uInt32 nSubEdges,bool bHandleCurvedEdges,bool bHandleStraightEdges)3029 		B2DPolygon reSegmentPolygonEdges(const B2DPolygon& rCandidate, sal_uInt32 nSubEdges, bool bHandleCurvedEdges, bool bHandleStraightEdges)
3030 		{
3031 			const sal_uInt32 nPointCount(rCandidate.count());
3032 
3033             if(nPointCount < 2 || nSubEdges < 2 || (!bHandleCurvedEdges && !bHandleStraightEdges))
3034             {
3035                 // nothing to do:
3036                 // - less than two points -> no edge at all
3037                 // - less than two nSubEdges -> no resegment necessary
3038                 // - neither bHandleCurvedEdges nor bHandleStraightEdges -> nothing to do
3039                 return rCandidate;
3040             }
3041             else
3042             {
3043     			B2DPolygon aRetval;
3044                 const sal_uInt32 nEdgeCount(rCandidate.isClosed() ? nPointCount : nPointCount - 1);
3045                 B2DCubicBezier aCurrentEdge;
3046 
3047                 // prepare first edge and add start point to target
3048                 aCurrentEdge.setStartPoint(rCandidate.getB2DPoint(0));
3049                 aRetval.append(aCurrentEdge.getStartPoint());
3050 
3051                 for(sal_uInt32 a(0); a < nEdgeCount; a++)
3052                 {
3053                     // fill edge
3054                     const sal_uInt32 nNextIndex((a + 1) % nPointCount);
3055                     aCurrentEdge.setControlPointA(rCandidate.getNextControlPoint(a));
3056                     aCurrentEdge.setControlPointB(rCandidate.getPrevControlPoint(nNextIndex));
3057                     aCurrentEdge.setEndPoint(rCandidate.getB2DPoint(nNextIndex));
3058 
3059                     if(aCurrentEdge.isBezier())
3060                     {
3061                         if(bHandleCurvedEdges)
3062                         {
3063                             for(sal_uInt32 b(nSubEdges); b > 1; b--)
3064                             {
3065                                 const double fSplitPoint(1.0 / b);
3066                                 B2DCubicBezier aLeftPart;
3067 
3068                                 aCurrentEdge.split(fSplitPoint, &aLeftPart, &aCurrentEdge);
3069                                 aRetval.appendBezierSegment(aLeftPart.getControlPointA(), aLeftPart.getControlPointB(), aLeftPart.getEndPoint());
3070                             }
3071                         }
3072 
3073                         // copy remaining segment to target
3074                         aRetval.appendBezierSegment(aCurrentEdge.getControlPointA(), aCurrentEdge.getControlPointB(), aCurrentEdge.getEndPoint());
3075                     }
3076                     else
3077                     {
3078                         if(bHandleStraightEdges)
3079                         {
3080                             for(sal_uInt32 b(nSubEdges); b > 1; b--)
3081                             {
3082                                 const double fSplitPoint(1.0 / b);
3083                                 const B2DPoint aSplitPoint(interpolate(aCurrentEdge.getStartPoint(), aCurrentEdge.getEndPoint(), fSplitPoint));
3084 
3085                                 aRetval.append(aSplitPoint);
3086                                 aCurrentEdge.setStartPoint(aSplitPoint);
3087                             }
3088                         }
3089 
3090                         // copy remaining segment to target
3091                         aRetval.append(aCurrentEdge.getEndPoint());
3092                     }
3093 
3094                     // prepare next step
3095                     aCurrentEdge.setStartPoint(aCurrentEdge.getEndPoint());
3096                 }
3097 
3098                 // copy closed flag and return
3099                 aRetval.setClosed(rCandidate.isClosed());
3100                 return aRetval;
3101             }
3102         }
3103 
interpolate(const B2DPolygon & rOld1,const B2DPolygon & rOld2,double t)3104 		B2DPolygon interpolate(const B2DPolygon& rOld1, const B2DPolygon& rOld2, double t)
3105 		{
3106 			OSL_ENSURE(rOld1.count() == rOld2.count(), "B2DPolygon interpolate: Different geometry (!)");
3107 
3108 			if(fTools::lessOrEqual(t, 0.0) || rOld1 == rOld2)
3109 			{
3110 				return rOld1;
3111 			}
3112 			else if(fTools::moreOrEqual(t, 1.0))
3113 			{
3114 				return rOld2;
3115 			}
3116 			else
3117 			{
3118 				B2DPolygon aRetval;
3119 				const bool bInterpolateVectors(rOld1.areControlPointsUsed() || rOld2.areControlPointsUsed());
3120 				aRetval.setClosed(rOld1.isClosed() && rOld2.isClosed());
3121 
3122 				for(sal_uInt32 a(0L); a < rOld1.count(); a++)
3123 				{
3124 					aRetval.append(interpolate(rOld1.getB2DPoint(a), rOld2.getB2DPoint(a), t));
3125 
3126 					if(bInterpolateVectors)
3127 					{
3128 						aRetval.setPrevControlPoint(a, interpolate(rOld1.getPrevControlPoint(a), rOld2.getPrevControlPoint(a), t));
3129 						aRetval.setNextControlPoint(a, interpolate(rOld1.getNextControlPoint(a), rOld2.getNextControlPoint(a), t));
3130 					}
3131 				}
3132 
3133 				return aRetval;
3134 			}
3135 		}
3136 
isPolyPolygonEqualRectangle(const B2DPolyPolygon & rPolyPoly,const B2DRange & rRect)3137 		bool isPolyPolygonEqualRectangle( const B2DPolyPolygon& rPolyPoly,
3138 										  const B2DRange&	   rRect )
3139         {
3140             // exclude some cheap cases first
3141             if( rPolyPoly.count() != 1 )
3142                 return false;
3143 
3144             // fill array with rectangle vertices
3145             const B2DPoint aPoints[] =
3146               {
3147 				  B2DPoint(rRect.getMinX(),rRect.getMinY()),
3148 				  B2DPoint(rRect.getMaxX(),rRect.getMinY()),
3149 				  B2DPoint(rRect.getMaxX(),rRect.getMaxY()),
3150 				  B2DPoint(rRect.getMinX(),rRect.getMaxY())
3151               };
3152 
3153 			const B2DPolygon& rPoly( rPolyPoly.getB2DPolygon(0) );
3154 			const sal_uInt32 nCount( rPoly.count() );
3155 			const double epsilon = ::std::numeric_limits<double>::epsilon();
3156 
3157 			for(unsigned int j=0; j<4; ++j)
3158 			{
3159 				const B2DPoint &p1 = aPoints[j];
3160 				const B2DPoint &p2 = aPoints[(j+1)%4];
3161 				bool bPointOnBoundary = false;
3162 				for( sal_uInt32 i=0; i<nCount; ++i )
3163 				{
3164 					const B2DPoint p(rPoly.getB2DPoint(i));
3165 
3166 					//	   1 | x0 y0 1 |
3167 					// A = - | x1 y1 1 |
3168 					//	   2 | x2 y2 1 |
3169 					double fDoubleArea = p2.getX()*p.getY() -
3170 										 p2.getY()*p.getX() -
3171 										 p1.getX()*p.getY() +
3172 										 p1.getY()*p.getX() +
3173 										 p1.getX()*p2.getY() -
3174 										 p1.getY()*p2.getX();
3175 
3176 					if(fDoubleArea < epsilon)
3177 					{
3178 						bPointOnBoundary=true;
3179 						break;
3180 					}
3181 				}
3182 				if(!(bPointOnBoundary))
3183 					return false;
3184 			}
3185 
3186 			return true;
3187         }
3188 
3189 
3190 		// create simplified version of the original polygon by
3191 		// replacing segments with spikes/loops and self intersections
3192 		// by several trivial sub-segments
createSimplifiedPolygon(const B2DPolygon & rCandidate)3193 		B2DPolygon createSimplifiedPolygon( const B2DPolygon& rCandidate )
3194 		{
3195 			const sal_uInt32 nCount(rCandidate.count());
3196 
3197 			if(nCount && rCandidate.areControlPointsUsed())
3198 			{
3199 				const sal_uInt32 nEdgeCount(rCandidate.isClosed() ? nCount : nCount - 1);
3200 				B2DPolygon aRetval;
3201 				B2DCubicBezier aSegment;
3202 
3203 				aSegment.setStartPoint(rCandidate.getB2DPoint(0));
3204 				aRetval.append(aSegment.getStartPoint());
3205 
3206 				for(sal_uInt32 a(0); a < nEdgeCount; a++)
3207 				{
3208 					// fill edge
3209 					const sal_uInt32 nNextIndex((a + 1) % nCount);
3210 					aSegment.setControlPointA(rCandidate.getNextControlPoint(a));
3211 					aSegment.setControlPointB(rCandidate.getPrevControlPoint(nNextIndex));
3212 					aSegment.setEndPoint(rCandidate.getB2DPoint(nNextIndex));
3213 
3214 					if(aSegment.isBezier())
3215 					{
3216 						double fExtremumPos(0.0);
3217 						sal_uInt32 nExtremumCounter(4);
3218 
3219 						while(nExtremumCounter-- && aSegment.isBezier() && aSegment.getMinimumExtremumPosition(fExtremumPos))
3220 						{
3221 							// split off left, now extremum-free part and append
3222 							B2DCubicBezier aLeft;
3223 
3224 							aSegment.split(fExtremumPos, &aLeft, &aSegment);
3225 		                    aLeft.testAndSolveTrivialBezier();
3226 		                    aSegment.testAndSolveTrivialBezier();
3227 
3228 							if(aLeft.isBezier())
3229 							{
3230 								aRetval.appendBezierSegment(aLeft.getControlPointA(), aLeft.getControlPointB(), aLeft.getEndPoint());
3231 							}
3232 							else
3233 							{
3234 								aRetval.append(aLeft.getEndPoint());
3235 							}
3236 						}
3237 
3238 						// append (evtl. reduced) rest of Segment
3239 						if(aSegment.isBezier())
3240 						{
3241 							aRetval.appendBezierSegment(aSegment.getControlPointA(), aSegment.getControlPointB(), aSegment.getEndPoint());
3242 						}
3243 						else
3244 						{
3245 							aRetval.append(aSegment.getEndPoint());
3246 						}
3247 					}
3248 					else
3249 					{
3250 						// simple edge, append end point
3251 						aRetval.append(aSegment.getEndPoint());
3252 					}
3253 
3254 					// prepare next edge
3255 					aSegment.setStartPoint(aSegment.getEndPoint());
3256 				}
3257 
3258 				// copy closed flag and check for double points
3259 				aRetval.setClosed(rCandidate.isClosed());
3260 				aRetval.removeDoublePoints();
3261 
3262 				return aRetval;
3263 			}
3264 			else
3265 			{
3266 				return rCandidate;
3267 			}
3268 		}
3269 
3270 		// #i76891#
simplifyCurveSegments(const B2DPolygon & rCandidate)3271 		B2DPolygon simplifyCurveSegments(const B2DPolygon& rCandidate)
3272 		{
3273 			const sal_uInt32 nPointCount(rCandidate.count());
3274 
3275 			if(nPointCount && rCandidate.areControlPointsUsed())
3276 			{
3277 				// prepare loop
3278 				const sal_uInt32 nEdgeCount(rCandidate.isClosed() ? nPointCount : nPointCount - 1);
3279 				B2DPolygon aRetval;
3280 				B2DCubicBezier aBezier;
3281 				aBezier.setStartPoint(rCandidate.getB2DPoint(0));
3282 
3283 				// try to avoid costly reallocations
3284 				aRetval.reserve( nEdgeCount+1);
3285 
3286 				// add start point
3287 				aRetval.append(aBezier.getStartPoint());
3288 
3289 				for(sal_uInt32 a(0L); a < nEdgeCount; a++)
3290 				{
3291 					// get values for edge
3292 					const sal_uInt32 nNextIndex((a + 1) % nPointCount);
3293 					aBezier.setEndPoint(rCandidate.getB2DPoint(nNextIndex));
3294 					aBezier.setControlPointA(rCandidate.getNextControlPoint(a));
3295 					aBezier.setControlPointB(rCandidate.getPrevControlPoint(nNextIndex));
3296 					aBezier.testAndSolveTrivialBezier();
3297 
3298 					// still bezier?
3299 					if(aBezier.isBezier())
3300 					{
3301 						// add edge with control vectors
3302 						aRetval.appendBezierSegment(aBezier.getControlPointA(), aBezier.getControlPointB(), aBezier.getEndPoint());
3303 					}
3304 					else
3305 					{
3306 						// add edge
3307 						aRetval.append(aBezier.getEndPoint());
3308 					}
3309 
3310 					// next point
3311 					aBezier.setStartPoint(aBezier.getEndPoint());
3312 				}
3313 
3314 				if(rCandidate.isClosed())
3315 				{
3316 					// set closed flag, rescue control point and correct last double point
3317 					closeWithGeometryChange(aRetval);
3318 				}
3319 
3320 				return aRetval;
3321 			}
3322 			else
3323 			{
3324 				return rCandidate;
3325 			}
3326 		}
3327 
3328 		// makes the given indexed point the new polygon start point. To do that, the points in the
3329 		// polygon will be rotated. This is only valid for closed polygons, for non-closed ones
3330 		// an assertion will be triggered
makeStartPoint(const B2DPolygon & rCandidate,sal_uInt32 nIndexOfNewStatPoint)3331 		B2DPolygon makeStartPoint(const B2DPolygon& rCandidate, sal_uInt32 nIndexOfNewStatPoint)
3332 		{
3333 			const sal_uInt32 nPointCount(rCandidate.count());
3334 
3335 			if(nPointCount > 2 && nIndexOfNewStatPoint != 0 && nIndexOfNewStatPoint < nPointCount)
3336 			{
3337 				OSL_ENSURE(rCandidate.isClosed(), "makeStartPoint: only valid for closed polygons (!)");
3338 				B2DPolygon aRetval;
3339 
3340 				for(sal_uInt32 a(0); a < nPointCount; a++)
3341 				{
3342 					const sal_uInt32 nSourceIndex((a + nIndexOfNewStatPoint) % nPointCount);
3343 					aRetval.append(rCandidate.getB2DPoint(nSourceIndex));
3344 
3345 					if(rCandidate.areControlPointsUsed())
3346 					{
3347 						aRetval.setPrevControlPoint(a, rCandidate.getPrevControlPoint(nSourceIndex));
3348 						aRetval.setNextControlPoint(a, rCandidate.getNextControlPoint(nSourceIndex));
3349 					}
3350 				}
3351 
3352 				return aRetval;
3353 			}
3354 
3355 			return rCandidate;
3356 		}
3357 
createEdgesOfGivenLength(const B2DPolygon & rCandidate,double fLength,double fStart,double fEnd)3358 		B2DPolygon createEdgesOfGivenLength(const B2DPolygon& rCandidate, double fLength, double fStart, double fEnd)
3359 		{
3360 			B2DPolygon aRetval;
3361 
3362 			if(fLength < 0.0)
3363 			{
3364 				fLength = 0.0;
3365 			}
3366 
3367 			if(!fTools::equalZero(fLength))
3368 			{
3369 				if(fStart < 0.0)
3370 				{
3371 					fStart = 0.0;
3372 				}
3373 
3374 				if(fEnd < 0.0)
3375 				{
3376 					fEnd = 0.0;
3377 				}
3378 
3379 				if(fEnd < fStart)
3380 				{
3381 					fEnd = fStart;
3382 				}
3383 
3384 				// iterate and consume pieces with fLength. First subdivide to reduce input to line segments
3385 				const B2DPolygon aCandidate(rCandidate.areControlPointsUsed() ? rCandidate.getDefaultAdaptiveSubdivision() : rCandidate);
3386 				const sal_uInt32 nPointCount(aCandidate.count());
3387 
3388 				if(nPointCount > 1)
3389 				{
3390 					const bool bEndActive(!fTools::equalZero(fEnd));
3391 					const sal_uInt32 nEdgeCount(aCandidate.isClosed() ? nPointCount : nPointCount - 1);
3392 					B2DPoint aCurrent(aCandidate.getB2DPoint(0));
3393 					double fPositionInEdge(fStart);
3394 					double fAbsolutePosition(fStart);
3395 
3396 					for(sal_uInt32 a(0); a < nEdgeCount; a++)
3397 					{
3398 						const sal_uInt32 nNextIndex((a + 1) % nPointCount);
3399 						const B2DPoint aNext(aCandidate.getB2DPoint(nNextIndex));
3400 						const B2DVector aEdge(aNext - aCurrent);
3401 						double fEdgeLength(aEdge.getLength());
3402 
3403 						if(!fTools::equalZero(fEdgeLength))
3404 						{
3405 							while(fTools::less(fPositionInEdge, fEdgeLength))
3406 							{
3407 								// move position on edge forward as long as on edge
3408 								const double fScalar(fPositionInEdge / fEdgeLength);
3409 								aRetval.append(aCurrent + (aEdge * fScalar));
3410 								fPositionInEdge += fLength;
3411 
3412 								if(bEndActive)
3413 								{
3414 									fAbsolutePosition += fLength;
3415 
3416 									if(fTools::more(fAbsolutePosition, fEnd))
3417 									{
3418 										break;
3419 									}
3420 								}
3421 							}
3422 
3423 							// substract length of current edge
3424 							fPositionInEdge -= fEdgeLength;
3425 						}
3426 
3427 						if(bEndActive && fTools::more(fAbsolutePosition, fEnd))
3428 						{
3429 							break;
3430 						}
3431 
3432 						// prepare next step
3433 						aCurrent = aNext;
3434 					}
3435 
3436 					// keep closed state
3437 					aRetval.setClosed(aCandidate.isClosed());
3438 				}
3439 				else
3440 				{
3441 					// source polygon has only one point, return unchanged
3442 					aRetval = aCandidate;
3443 				}
3444 			}
3445 
3446 			return aRetval;
3447 		}
3448 
createWaveline(const B2DPolygon & rCandidate,double fWaveWidth,double fWaveHeight)3449 		B2DPolygon createWaveline(const B2DPolygon& rCandidate, double fWaveWidth, double fWaveHeight)
3450 		{
3451 			B2DPolygon aRetval;
3452 
3453 			if(fWaveWidth < 0.0)
3454 			{
3455 				fWaveWidth = 0.0;
3456 			}
3457 
3458 			if(fWaveHeight < 0.0)
3459 			{
3460 				fWaveHeight = 0.0;
3461 			}
3462 
3463 			const bool bHasWidth(!fTools::equalZero(fWaveWidth));
3464 			const bool bHasHeight(!fTools::equalZero(fWaveHeight));
3465 
3466 			if(bHasWidth)
3467 			{
3468 				if(bHasHeight)
3469 				{
3470 					// width and height, create waveline. First subdivide to reduce input to line segments
3471 					// of WaveWidth. Last segment may be missing. If this turns out to be a problem, it
3472 					// may be added here again using the original last point from rCandidate. It may
3473 					// also be the case that rCandidate was closed. To simplify things it is handled here
3474 					// as if it was opened.
3475 					// Result from createEdgesOfGivenLength contains no curved segments, handle as straight
3476 					// edges.
3477 					const B2DPolygon aEqualLenghEdges(createEdgesOfGivenLength(rCandidate, fWaveWidth));
3478 					const sal_uInt32 nPointCount(aEqualLenghEdges.count());
3479 
3480 					if(nPointCount > 1)
3481 					{
3482 						// iterate over straight edges, add start point
3483 						B2DPoint aCurrent(aEqualLenghEdges.getB2DPoint(0));
3484 						aRetval.append(aCurrent);
3485 
3486 						for(sal_uInt32 a(0); a < nPointCount - 1; a++)
3487 						{
3488 							const sal_uInt32 nNextIndex((a + 1) % nPointCount);
3489 							const B2DPoint aNext(aEqualLenghEdges.getB2DPoint(nNextIndex));
3490 							const B2DVector aEdge(aNext - aCurrent);
3491 							const B2DVector aPerpendicular(getNormalizedPerpendicular(aEdge));
3492                             const B2DVector aControlOffset((aEdge * 0.467308) - (aPerpendicular * fWaveHeight));
3493 
3494 							// add curve segment
3495 							aRetval.appendBezierSegment(
3496 								aCurrent + aControlOffset,
3497 								aNext - aControlOffset,
3498 								aNext);
3499 
3500 							// prepare next step
3501 							aCurrent = aNext;
3502 						}
3503 					}
3504 				}
3505 				else
3506 				{
3507 					// width but no height -> return original polygon
3508 					aRetval = rCandidate;
3509 				}
3510 			}
3511 			else
3512 			{
3513 				// no width -> no waveline, stay empty and return
3514 			}
3515 
3516 			return aRetval;
3517 		}
3518 
3519         //////////////////////////////////////////////////////////////////////
3520 		// comparators with tolerance for 2D Polygons
3521 
equal(const B2DPolygon & rCandidateA,const B2DPolygon & rCandidateB,const double & rfSmallValue)3522 		bool equal(const B2DPolygon& rCandidateA, const B2DPolygon& rCandidateB, const double& rfSmallValue)
3523 		{
3524 			const sal_uInt32 nPointCount(rCandidateA.count());
3525 
3526 			if(nPointCount != rCandidateB.count())
3527 				return false;
3528 
3529 			const bool bClosed(rCandidateA.isClosed());
3530 
3531 			if(bClosed != rCandidateB.isClosed())
3532 				return false;
3533 
3534 			const bool bAreControlPointsUsed(rCandidateA.areControlPointsUsed());
3535 
3536 			if(bAreControlPointsUsed != rCandidateB.areControlPointsUsed())
3537 				return false;
3538 
3539 			for(sal_uInt32 a(0); a < nPointCount; a++)
3540 			{
3541 				const B2DPoint aPoint(rCandidateA.getB2DPoint(a));
3542 
3543 				if(!aPoint.equal(rCandidateB.getB2DPoint(a), rfSmallValue))
3544 					return false;
3545 
3546 				if(bAreControlPointsUsed)
3547 				{
3548 					const basegfx::B2DPoint aPrev(rCandidateA.getPrevControlPoint(a));
3549 
3550 					if(!aPrev.equal(rCandidateB.getPrevControlPoint(a), rfSmallValue))
3551 						return false;
3552 
3553 					const basegfx::B2DPoint aNext(rCandidateA.getNextControlPoint(a));
3554 
3555 					if(!aNext.equal(rCandidateB.getNextControlPoint(a), rfSmallValue))
3556 						return false;
3557 				}
3558 			}
3559 
3560 			return true;
3561 		}
3562 
equal(const B2DPolygon & rCandidateA,const B2DPolygon & rCandidateB)3563 		bool equal(const B2DPolygon& rCandidateA, const B2DPolygon& rCandidateB)
3564 		{
3565 			const double fSmallValue(fTools::getSmallValue());
3566 
3567 			return equal(rCandidateA, rCandidateB, fSmallValue);
3568 		}
3569 
3570 		// snap points of horizontal or vertical edges to discrete values
snapPointsOfHorizontalOrVerticalEdges(const B2DPolygon & rCandidate)3571 		B2DPolygon snapPointsOfHorizontalOrVerticalEdges(const B2DPolygon& rCandidate)
3572 		{
3573 			const sal_uInt32 nPointCount(rCandidate.count());
3574 
3575 			if(nPointCount > 1)
3576 			{
3577 				// Start by copying the source polygon to get a writeable copy. The closed state is
3578 				// copied by aRetval's initialisation, too, so no need to copy it in this method
3579 				B2DPolygon aRetval(rCandidate);
3580 
3581 				// prepare geometry data. Get rounded from original
3582                 B2ITuple aPrevTuple(basegfx::fround(rCandidate.getB2DPoint(nPointCount - 1)));
3583 				B2DPoint aCurrPoint(rCandidate.getB2DPoint(0));
3584 				B2ITuple aCurrTuple(basegfx::fround(aCurrPoint));
3585 
3586 				// loop over all points. This will also snap the implicit closing edge
3587 				// even when not closed, but that's no problem here
3588 				for(sal_uInt32 a(0); a < nPointCount; a++)
3589 				{
3590 					// get next point. Get rounded from original
3591                     const bool bLastRun(a + 1 == nPointCount);
3592                     const sal_uInt32 nNextIndex(bLastRun ? 0 : a + 1);
3593 					const B2DPoint aNextPoint(rCandidate.getB2DPoint(nNextIndex));
3594 					const B2ITuple aNextTuple(basegfx::fround(aNextPoint));
3595 
3596 					// get the states
3597 					const bool bPrevVertical(aPrevTuple.getX() == aCurrTuple.getX());
3598 					const bool bNextVertical(aNextTuple.getX() == aCurrTuple.getX());
3599 					const bool bPrevHorizontal(aPrevTuple.getY() == aCurrTuple.getY());
3600 					const bool bNextHorizontal(aNextTuple.getY() == aCurrTuple.getY());
3601 					const bool bSnapX(bPrevVertical || bNextVertical);
3602 					const bool bSnapY(bPrevHorizontal || bNextHorizontal);
3603 
3604 					if(bSnapX || bSnapY)
3605 					{
3606 						const B2DPoint aSnappedPoint(
3607 							bSnapX ? aCurrTuple.getX() : aCurrPoint.getX(),
3608 							bSnapY ? aCurrTuple.getY() : aCurrPoint.getY());
3609 
3610 						aRetval.setB2DPoint(a, aSnappedPoint);
3611 					}
3612 
3613 					// prepare next point
3614                     if(!bLastRun)
3615                     {
3616     					aPrevTuple = aCurrTuple;
3617 	    				aCurrPoint = aNextPoint;
3618 		    			aCurrTuple = aNextTuple;
3619                     }
3620 				}
3621 
3622 				return aRetval;
3623 			}
3624 			else
3625 			{
3626 				return rCandidate;
3627 			}
3628 		}
3629 
containsOnlyHorizontalAndVerticalEdges(const B2DPolygon & rCandidate)3630         bool containsOnlyHorizontalAndVerticalEdges(const B2DPolygon& rCandidate)
3631         {
3632             if(rCandidate.areControlPointsUsed())
3633             {
3634                 return false;
3635             }
3636 
3637             const sal_uInt32 nPointCount(rCandidate.count());
3638 
3639             if(nPointCount < 2)
3640             {
3641                 return true;
3642             }
3643 
3644             const sal_uInt32 nEdgeCount(rCandidate.isClosed() ? nPointCount + 1 : nPointCount);
3645             basegfx::B2DPoint aLast(rCandidate.getB2DPoint(0));
3646 
3647             for(sal_uInt32 a(1); a < nEdgeCount; a++)
3648             {
3649                 const sal_uInt32 nNextIndex(a % nPointCount);
3650                 const basegfx::B2DPoint aCurrent(rCandidate.getB2DPoint(nNextIndex));
3651 
3652                 if(!basegfx::fTools::equal(aLast.getX(), aCurrent.getX()) && !basegfx::fTools::equal(aLast.getY(), aCurrent.getY()))
3653                 {
3654                     return false;
3655                 }
3656 
3657                 aLast = aCurrent;
3658             }
3659 
3660             return true;
3661         }
3662 
getTangentEnteringPoint(const B2DPolygon & rCandidate,sal_uInt32 nIndex)3663         B2DVector getTangentEnteringPoint(const B2DPolygon& rCandidate, sal_uInt32 nIndex)
3664         {
3665             B2DVector aRetval(0.0, 0.0);
3666             const sal_uInt32 nCount(rCandidate.count());
3667 
3668             if(nIndex >= nCount)
3669             {
3670                 // out of range
3671                 return aRetval;
3672             }
3673 
3674             // start immediately at prev point compared to nIndex
3675             const bool bClosed(rCandidate.isClosed());
3676             sal_uInt32 nPrev(bClosed ? (nIndex + nCount - 1) % nCount : nIndex ? nIndex - 1 : nIndex);
3677 
3678             if(nPrev == nIndex)
3679             {
3680                 // no previous, done
3681                 return aRetval;
3682             }
3683 
3684             B2DCubicBezier aSegment;
3685 
3686             // go backward in the polygon; if closed, maximal back to start index (nIndex); if not closed,
3687             // until zero. Use nIndex as stop criteria
3688             while(nPrev != nIndex)
3689             {
3690                 // get BezierSegment and tangent at the *end* of segment
3691                 rCandidate.getBezierSegment(nPrev, aSegment);
3692                 aRetval = aSegment.getTangent(1.0);
3693 
3694                 if(!aRetval.equalZero())
3695                 {
3696                     // if we have a tangent, return it
3697                     return aRetval;
3698                 }
3699 
3700                 // prepare index before checked one
3701                 nPrev = bClosed ? (nPrev + nCount - 1) % nCount : nPrev ? nPrev - 1 : nIndex;
3702             }
3703 
3704             return aRetval;
3705         }
3706 
getTangentLeavingPoint(const B2DPolygon & rCandidate,sal_uInt32 nIndex)3707         B2DVector getTangentLeavingPoint(const B2DPolygon& rCandidate, sal_uInt32 nIndex)
3708         {
3709             B2DVector aRetval(0.0, 0.0);
3710             const sal_uInt32 nCount(rCandidate.count());
3711 
3712             if(nIndex >= nCount)
3713             {
3714                 // out of range
3715                 return aRetval;
3716             }
3717 
3718             // start at nIndex
3719             const bool bClosed(rCandidate.isClosed());
3720             sal_uInt32 nCurrent(nIndex);
3721             B2DCubicBezier aSegment;
3722 
3723             // go forward; if closed, do this until once around and back at start index (nIndex); if not
3724             // closed, until last point (nCount - 1). Use nIndex as stop criteria
3725             do
3726             {
3727                 // get BezierSegment and tangent at the *beginning* of segment
3728                 rCandidate.getBezierSegment(nCurrent, aSegment);
3729                 aRetval = aSegment.getTangent(0.0);
3730 
3731                 if(!aRetval.equalZero())
3732                 {
3733                     // if we have a tangent, return it
3734                     return aRetval;
3735                 }
3736 
3737                 // prepare next index
3738                 nCurrent = bClosed ? (nCurrent + 1) % nCount : nCurrent + 1 < nCount ? nCurrent + 1 : nIndex;
3739             }
3740             while(nCurrent != nIndex);
3741 
3742             return aRetval;
3743         }
3744 
3745         //////////////////////////////////////////////////////////////////////////////
3746         // converters for com::sun::star::drawing::PointSequence
3747 
UnoPointSequenceToB2DPolygon(const com::sun::star::drawing::PointSequence & rPointSequenceSource,bool bCheckClosed)3748         B2DPolygon UnoPointSequenceToB2DPolygon(
3749             const com::sun::star::drawing::PointSequence& rPointSequenceSource,
3750             bool bCheckClosed)
3751         {
3752             B2DPolygon aRetval;
3753             const sal_uInt32 nLength(rPointSequenceSource.getLength());
3754 
3755             if(nLength)
3756             {
3757                 aRetval.reserve(nLength);
3758                 const com::sun::star::awt::Point* pArray = rPointSequenceSource.getConstArray();
3759                 const com::sun::star::awt::Point* pArrayEnd = pArray + rPointSequenceSource.getLength();
3760 
3761                 for(;pArray != pArrayEnd; pArray++)
3762                 {
3763                     aRetval.append(B2DPoint(pArray->X, pArray->Y));
3764                 }
3765 
3766                 if(bCheckClosed)
3767                 {
3768                     // check for closed state flag
3769                     tools::checkClosed(aRetval);
3770                 }
3771             }
3772 
3773             return aRetval;
3774         }
3775 
B2DPolygonToUnoPointSequence(const B2DPolygon & rPolygon,com::sun::star::drawing::PointSequence & rPointSequenceRetval)3776         void B2DPolygonToUnoPointSequence(
3777             const B2DPolygon& rPolygon,
3778             com::sun::star::drawing::PointSequence& rPointSequenceRetval)
3779         {
3780             B2DPolygon aPolygon(rPolygon);
3781 
3782             if(aPolygon.areControlPointsUsed())
3783             {
3784                 OSL_ENSURE(false, "B2DPolygonToUnoPointSequence: Source contains bezier segments, wrong UNO API data type may be used (!)");
3785                 aPolygon = aPolygon.getDefaultAdaptiveSubdivision();
3786             }
3787 
3788             const sal_uInt32 nPointCount(aPolygon.count());
3789 
3790             if(nPointCount)
3791             {
3792                 // Take closed state into account, the API polygon still uses the old closed definition
3793                 // with last/first point are identical (cannot hold information about open polygons with identical
3794                 // first and last point, though)
3795                 const bool bIsClosed(aPolygon.isClosed());
3796 
3797                 rPointSequenceRetval.realloc(bIsClosed ? nPointCount + 1 : nPointCount);
3798                 com::sun::star::awt::Point* pSequence = rPointSequenceRetval.getArray();
3799 
3800                 for(sal_uInt32 b(0); b < nPointCount; b++)
3801                 {
3802                     const B2DPoint aPoint(aPolygon.getB2DPoint(b));
3803                     const com::sun::star::awt::Point aAPIPoint(fround(aPoint.getX()), fround(aPoint.getY()));
3804 
3805                     *pSequence = aAPIPoint;
3806                     pSequence++;
3807                 }
3808 
3809                 // copy first point if closed
3810                 if(bIsClosed)
3811                 {
3812                     *pSequence = *rPointSequenceRetval.getArray();
3813                 }
3814             }
3815             else
3816             {
3817                 rPointSequenceRetval.realloc(0);
3818             }
3819         }
3820 
3821         //////////////////////////////////////////////////////////////////////////////
3822         // converters for com::sun::star::drawing::PointSequence and
3823         // com::sun::star::drawing::FlagSequence to B2DPolygon (curved polygons)
3824 
UnoPolygonBezierCoordsToB2DPolygon(const com::sun::star::drawing::PointSequence & rPointSequenceSource,const com::sun::star::drawing::FlagSequence & rFlagSequenceSource,bool bCheckClosed)3825         B2DPolygon UnoPolygonBezierCoordsToB2DPolygon(
3826             const com::sun::star::drawing::PointSequence& rPointSequenceSource,
3827             const com::sun::star::drawing::FlagSequence& rFlagSequenceSource,
3828             bool bCheckClosed)
3829         {
3830             const sal_uInt32 nCount((sal_uInt32)rPointSequenceSource.getLength());
3831             OSL_ENSURE(nCount == (sal_uInt32)rFlagSequenceSource.getLength(),
3832                 "UnoPolygonBezierCoordsToB2DPolygon: Unequal count of Points and Flags (!)");
3833 
3834             // prepare new polygon
3835             B2DPolygon aRetval;
3836             const com::sun::star::awt::Point* pPointSequence = rPointSequenceSource.getConstArray();
3837             const com::sun::star::drawing::PolygonFlags* pFlagSequence = rFlagSequenceSource.getConstArray();
3838 
3839             // get first point and flag
3840             B2DPoint aNewCoordinatePair(pPointSequence->X, pPointSequence->Y); pPointSequence++;
3841             com::sun::star::drawing::PolygonFlags ePolygonFlag(*pFlagSequence); pFlagSequence++;
3842             B2DPoint aControlA;
3843             B2DPoint aControlB;
3844 
3845             // first point is not allowed to be a control point
3846             OSL_ENSURE(com::sun::star::drawing::PolygonFlags_CONTROL != ePolygonFlag,
3847                 "UnoPolygonBezierCoordsToB2DPolygon: Start point is a control point, illegal input polygon (!)");
3848 
3849             // add first point as start point
3850             aRetval.append(aNewCoordinatePair);
3851 
3852             for(sal_uInt32 b(1); b < nCount;)
3853             {
3854                 // prepare loop
3855                 bool bControlA(false);
3856                 bool bControlB(false);
3857 
3858                 // get next point and flag
3859                 aNewCoordinatePair = B2DPoint(pPointSequence->X, pPointSequence->Y);
3860                 ePolygonFlag = *pFlagSequence;
3861                 pPointSequence++; pFlagSequence++; b++;
3862 
3863                 if(b < nCount && com::sun::star::drawing::PolygonFlags_CONTROL == ePolygonFlag)
3864                 {
3865                     aControlA = aNewCoordinatePair;
3866                     bControlA = true;
3867 
3868                     // get next point and flag
3869                     aNewCoordinatePair = B2DPoint(pPointSequence->X, pPointSequence->Y);
3870                     ePolygonFlag = *pFlagSequence;
3871                     pPointSequence++; pFlagSequence++; b++;
3872                 }
3873 
3874                 if(b < nCount && com::sun::star::drawing::PolygonFlags_CONTROL == ePolygonFlag)
3875                 {
3876                     aControlB = aNewCoordinatePair;
3877                     bControlB = true;
3878 
3879                     // get next point and flag
3880                     aNewCoordinatePair = B2DPoint(pPointSequence->X, pPointSequence->Y);
3881                     ePolygonFlag = *pFlagSequence;
3882                     pPointSequence++; pFlagSequence++; b++;
3883                 }
3884 
3885                 // two or no control points are consumed, another one would be an error.
3886                 // It's also an error if only one control point was read
3887                 OSL_ENSURE(com::sun::star::drawing::PolygonFlags_CONTROL != ePolygonFlag && bControlA == bControlB,
3888                     "UnoPolygonBezierCoordsToB2DPolygon: Illegal source polygon (!)");
3889 
3890                 // the previous writes used the B2DPolyPoygon -> PolyPolygon converter
3891                 // which did not create minimal PolyPolygons, but created all control points
3892                 // as null vectors (identical points). Because of the former P(CA)(CB)-norm of
3893                 // B2DPolygon and it's unused sign of being the zero-vector and CA and CB being
3894                 // relative to P, an empty edge was exported as P == CA == CB. Luckily, the new
3895                 // export format can be read without errors by the old OOo-versions, so we need only
3896                 // to correct here at read and do not need to export a wrong but compatible version
3897                 // for the future.
3898                 if(bControlA
3899                     && aControlA.equal(aControlB)
3900                     && aControlA.equal(aRetval.getB2DPoint(aRetval.count() - 1)))
3901                 {
3902                     bControlA = bControlB = false;
3903                 }
3904 
3905                 if(bControlA)
3906                 {
3907                     // add bezier edge
3908                     aRetval.appendBezierSegment(aControlA, aControlB, aNewCoordinatePair);
3909                 }
3910                 else
3911                 {
3912                     // add edge
3913                     aRetval.append(aNewCoordinatePair);
3914                 }
3915             }
3916 
3917             // #i72807# API import uses old line start/end-equal definition for closed,
3918             // so we need to correct this to closed state here
3919             if(bCheckClosed)
3920             {
3921                 checkClosed(aRetval);
3922             }
3923 
3924             return aRetval;
3925         }
3926 
B2DPolygonToUnoPolygonBezierCoords(const B2DPolygon & rPolygon,com::sun::star::drawing::PointSequence & rPointSequenceRetval,com::sun::star::drawing::FlagSequence & rFlagSequenceRetval)3927         void B2DPolygonToUnoPolygonBezierCoords(
3928             const B2DPolygon& rPolygon,
3929             com::sun::star::drawing::PointSequence& rPointSequenceRetval,
3930             com::sun::star::drawing::FlagSequence& rFlagSequenceRetval)
3931         {
3932             const sal_uInt32 nPointCount(rPolygon.count());
3933 
3934             if(nPointCount)
3935             {
3936                 const bool bCurve(rPolygon.areControlPointsUsed());
3937                 const bool bClosed(rPolygon.isClosed());
3938 
3939                 if(nPointCount)
3940                 {
3941                     if(bCurve)
3942                     {
3943                         // calculate target point count
3944                         const sal_uInt32 nLoopCount(bClosed ? nPointCount : (nPointCount ? nPointCount - 1 : 0));
3945 
3946                         if(nLoopCount)
3947                         {
3948                             // prepare target data. The real needed number of target points (and flags)
3949                             // could only be calculated by using two loops, so use dynamic memory
3950                             std::vector< com::sun::star::awt::Point > aCollectPoints;
3951                             std::vector< com::sun::star::drawing::PolygonFlags > aCollectFlags;
3952 
3953                             // reserve maximum creatable points
3954                             const sal_uInt32 nMaxTargetCount((nLoopCount * 3) + 1);
3955                             aCollectPoints.reserve(nMaxTargetCount);
3956                             aCollectFlags.reserve(nMaxTargetCount);
3957 
3958                             // prepare current bezier segment by setting start point
3959                             B2DCubicBezier aBezierSegment;
3960                             aBezierSegment.setStartPoint(rPolygon.getB2DPoint(0));
3961 
3962                             for(sal_uInt32 a(0); a < nLoopCount; a++)
3963                             {
3964                                 // add current point (always) and remember StartPointIndex for evtl. later corrections
3965                                 const sal_uInt32 nStartPointIndex(aCollectPoints.size());
3966                                 aCollectPoints.push_back(
3967                                     com::sun::star::awt::Point(
3968                                         fround(aBezierSegment.getStartPoint().getX()),
3969                                         fround(aBezierSegment.getStartPoint().getY())));
3970                                 aCollectFlags.push_back(com::sun::star::drawing::PolygonFlags_NORMAL);
3971 
3972                                 // prepare next segment
3973                                 const sal_uInt32 nNextIndex((a + 1) % nPointCount);
3974                                 aBezierSegment.setEndPoint(rPolygon.getB2DPoint(nNextIndex));
3975                                 aBezierSegment.setControlPointA(rPolygon.getNextControlPoint(a));
3976                                 aBezierSegment.setControlPointB(rPolygon.getPrevControlPoint(nNextIndex));
3977 
3978                                 if(aBezierSegment.isBezier())
3979                                 {
3980                                     // if bezier is used, add always two control points due to the old schema
3981                                     aCollectPoints.push_back(
3982                                         com::sun::star::awt::Point(
3983                                             fround(aBezierSegment.getControlPointA().getX()),
3984                                             fround(aBezierSegment.getControlPointA().getY())));
3985                                     aCollectFlags.push_back(com::sun::star::drawing::PolygonFlags_CONTROL);
3986 
3987                                     aCollectPoints.push_back(
3988                                         com::sun::star::awt::Point(
3989                                             fround(aBezierSegment.getControlPointB().getX()),
3990                                             fround(aBezierSegment.getControlPointB().getY())));
3991                                     aCollectFlags.push_back(com::sun::star::drawing::PolygonFlags_CONTROL);
3992                                 }
3993 
3994                                 // test continuity with previous control point to set flag value
3995                                 if(aBezierSegment.getControlPointA() != aBezierSegment.getStartPoint() && (bClosed || a))
3996                                 {
3997                                     const B2VectorContinuity eCont(rPolygon.getContinuityInPoint(a));
3998 
3999                                     if(CONTINUITY_C1 == eCont)
4000                                     {
4001                                         aCollectFlags[nStartPointIndex] = com::sun::star::drawing::PolygonFlags_SMOOTH;
4002                                     }
4003                                     else if(CONTINUITY_C2 == eCont)
4004                                     {
4005                                         aCollectFlags[nStartPointIndex] = com::sun::star::drawing::PolygonFlags_SYMMETRIC;
4006                                     }
4007                                 }
4008 
4009                                 // prepare next loop
4010                                 aBezierSegment.setStartPoint(aBezierSegment.getEndPoint());
4011                             }
4012 
4013                             if(bClosed)
4014                             {
4015                                 // add first point again as closing point due to old definition
4016                                 aCollectPoints.push_back(aCollectPoints[0]);
4017                                 aCollectFlags.push_back(com::sun::star::drawing::PolygonFlags_NORMAL);
4018                             }
4019                             else
4020                             {
4021                                 // add last point as closing point
4022                                 const B2DPoint aClosingPoint(rPolygon.getB2DPoint(nPointCount - 1L));
4023                                 aCollectPoints.push_back(
4024                                     com::sun::star::awt::Point(
4025                                         fround(aClosingPoint.getX()),
4026                                         fround(aClosingPoint.getY())));
4027                                 aCollectFlags.push_back(com::sun::star::drawing::PolygonFlags_NORMAL);
4028                             }
4029 
4030                             // copy collected data to target arrays
4031                             const sal_uInt32 nTargetCount(aCollectPoints.size());
4032                             OSL_ENSURE(nTargetCount == aCollectFlags.size(), "Unequal Point and Flag count (!)");
4033 
4034                             rPointSequenceRetval.realloc((sal_Int32)nTargetCount);
4035                             rFlagSequenceRetval.realloc((sal_Int32)nTargetCount);
4036                             com::sun::star::awt::Point* pPointSequence = rPointSequenceRetval.getArray();
4037                             com::sun::star::drawing::PolygonFlags* pFlagSequence = rFlagSequenceRetval.getArray();
4038 
4039                             for(sal_uInt32 a(0); a < nTargetCount; a++)
4040                             {
4041                                 *pPointSequence = aCollectPoints[a];
4042                                 *pFlagSequence = aCollectFlags[a];
4043                                 pPointSequence++;
4044                                 pFlagSequence++;
4045                             }
4046                         }
4047                     }
4048                     else
4049                     {
4050                         // straightforward point list creation
4051                         const sal_uInt32 nTargetCount(nPointCount + (bClosed ? 1 : 0));
4052 
4053                         rPointSequenceRetval.realloc((sal_Int32)nTargetCount);
4054                         rFlagSequenceRetval.realloc((sal_Int32)nTargetCount);
4055 
4056                         com::sun::star::awt::Point* pPointSequence = rPointSequenceRetval.getArray();
4057                         com::sun::star::drawing::PolygonFlags* pFlagSequence = rFlagSequenceRetval.getArray();
4058 
4059                         for(sal_uInt32 a(0); a < nPointCount; a++)
4060                         {
4061                             const B2DPoint aB2DPoint(rPolygon.getB2DPoint(a));
4062                             const com::sun::star::awt::Point aAPIPoint(
4063                                 fround(aB2DPoint.getX()),
4064                                 fround(aB2DPoint.getY()));
4065 
4066                             *pPointSequence = aAPIPoint;
4067                             *pFlagSequence = com::sun::star::drawing::PolygonFlags_NORMAL;
4068                             pPointSequence++;
4069                             pFlagSequence++;
4070                         }
4071 
4072                         if(bClosed)
4073                         {
4074                             // add first point as closing point
4075                             *pPointSequence = *rPointSequenceRetval.getConstArray();
4076                             *pFlagSequence = com::sun::star::drawing::PolygonFlags_NORMAL;
4077                         }
4078                     }
4079                 }
4080             }
4081             else
4082             {
4083                 rPointSequenceRetval.realloc(0);
4084                 rFlagSequenceRetval.realloc(0);
4085             }
4086         }
4087 
4088     } // end of namespace tools
4089 } // end of namespace basegfx
4090 
4091 //////////////////////////////////////////////////////////////////////////////
4092 // eof
4093