1 /*************************************************************************
2  *
3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4  *
5  * Copyright 2000, 2010 Oracle and/or its affiliates.
6  *
7  * OpenOffice.org - a multi-platform office productivity suite
8  *
9  * This file is part of OpenOffice.org.
10  *
11  * OpenOffice.org is free software: you can redistribute it and/or modify
12  * it under the terms of the GNU Lesser General Public License version 3
13  * only, as published by the Free Software Foundation.
14  *
15  * OpenOffice.org is distributed in the hope that it will be useful,
16  * but WITHOUT ANY WARRANTY; without even the implied warranty of
17  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
18  * GNU Lesser General Public License version 3 for more details
19  * (a copy is included in the LICENSE file that accompanied this code).
20  *
21  * You should have received a copy of the GNU Lesser General Public License
22  * version 3 along with OpenOffice.org.  If not, see
23  * <http://www.openoffice.org/license.html>
24  * for a copy of the LGPLv3 License.
25  *
26  ************************************************************************/
27 
28 // MARKER(update_precomp.py): autogen include statement, do not remove
29 #include "precompiled_basegfx.hxx"
30 #include <basegfx/polygon/b2dpolypolygontools.hxx>
31 #include <osl/diagnose.h>
32 #include <basegfx/polygon/b2dpolypolygon.hxx>
33 #include <basegfx/polygon/b2dpolygon.hxx>
34 #include <basegfx/polygon/b2dpolygontools.hxx>
35 #include <basegfx/numeric/ftools.hxx>
36 #include <basegfx/polygon/b2dpolypolygoncutter.hxx>
37 
38 #include <numeric>
39 
40 //////////////////////////////////////////////////////////////////////////////
41 
42 namespace basegfx
43 {
44 	namespace tools
45 	{
46 		B2DPolyPolygon correctOrientations(const B2DPolyPolygon& rCandidate)
47 		{
48 			B2DPolyPolygon aRetval(rCandidate);
49 			const sal_uInt32 nCount(aRetval.count());
50 
51 			for(sal_uInt32 a(0L); a < nCount; a++)
52 			{
53 				const B2DPolygon aCandidate(rCandidate.getB2DPolygon(a));
54 				const B2VectorOrientation aOrientation(tools::getOrientation(aCandidate));
55 				sal_uInt32 nDepth(0L);
56 
57 				for(sal_uInt32 b(0L); b < nCount; b++)
58 				{
59 					if(b != a)
60 					{
61 						const B2DPolygon aCompare(rCandidate.getB2DPolygon(b));
62 
63 						if(tools::isInside(aCompare, aCandidate, true))
64 						{
65 							nDepth++;
66 						}
67 					}
68 				}
69 
70 				const bool bShallBeHole(1L == (nDepth & 0x00000001));
71 				const bool bIsHole(ORIENTATION_NEGATIVE == aOrientation);
72 
73 				if(bShallBeHole != bIsHole && ORIENTATION_NEUTRAL != aOrientation)
74 				{
75 					B2DPolygon aFlipped(aCandidate);
76 					aFlipped.flip();
77 					aRetval.setB2DPolygon(a, aFlipped);
78 				}
79 			}
80 
81 			return aRetval;
82 		}
83 
84 		B2DPolyPolygon correctOutmostPolygon(const B2DPolyPolygon& rCandidate)
85 		{
86 			const sal_uInt32 nCount(rCandidate.count());
87 
88 			if(nCount > 1L)
89 			{
90 				for(sal_uInt32 a(0L); a < nCount; a++)
91 				{
92 					const B2DPolygon aCandidate(rCandidate.getB2DPolygon(a));
93 					sal_uInt32 nDepth(0L);
94 
95 					for(sal_uInt32 b(0L); b < nCount; b++)
96 					{
97 						if(b != a)
98 						{
99 							const B2DPolygon aCompare(rCandidate.getB2DPolygon(b));
100 
101 							if(tools::isInside(aCompare, aCandidate, true))
102 							{
103 								nDepth++;
104 							}
105 						}
106 					}
107 
108 					if(!nDepth)
109 					{
110 						B2DPolyPolygon aRetval(rCandidate);
111 
112 						if(a != 0L)
113 						{
114 							// exchange polygon a and polygon 0L
115 							aRetval.setB2DPolygon(0L, aCandidate);
116 							aRetval.setB2DPolygon(a, rCandidate.getB2DPolygon(0L));
117 						}
118 
119 						// exit
120 						return aRetval;
121 					}
122 				}
123 			}
124 
125 			return rCandidate;
126 		}
127 
128 		B2DPolyPolygon adaptiveSubdivideByDistance(const B2DPolyPolygon& rCandidate, double fDistanceBound)
129 		{
130 			if(rCandidate.areControlPointsUsed())
131 			{
132 				const sal_uInt32 nPolygonCount(rCandidate.count());
133 				B2DPolyPolygon aRetval;
134 
135 				for(sal_uInt32 a(0L); a < nPolygonCount; a++)
136 				{
137 					const B2DPolygon aCandidate(rCandidate.getB2DPolygon(a));
138 
139 					if(aCandidate.areControlPointsUsed())
140 					{
141 						aRetval.append(tools::adaptiveSubdivideByDistance(aCandidate, fDistanceBound));
142 					}
143 					else
144 					{
145 						aRetval.append(aCandidate);
146 					}
147 				}
148 
149 				return aRetval;
150 			}
151 			else
152 			{
153 				return rCandidate;
154 			}
155 		}
156 
157 		B2DPolyPolygon adaptiveSubdivideByAngle(const B2DPolyPolygon& rCandidate, double fAngleBound)
158 		{
159 			if(rCandidate.areControlPointsUsed())
160 			{
161 				const sal_uInt32 nPolygonCount(rCandidate.count());
162 				B2DPolyPolygon aRetval;
163 
164 				for(sal_uInt32 a(0L); a < nPolygonCount; a++)
165 				{
166 					const B2DPolygon aCandidate(rCandidate.getB2DPolygon(a));
167 
168 					if(aCandidate.areControlPointsUsed())
169 					{
170 						aRetval.append(tools::adaptiveSubdivideByAngle(aCandidate, fAngleBound));
171 					}
172 					else
173 					{
174 						aRetval.append(aCandidate);
175 					}
176 				}
177 
178 				return aRetval;
179 			}
180 			else
181 			{
182 				return rCandidate;
183 			}
184 		}
185 
186 		B2DPolyPolygon adaptiveSubdivideByCount(const B2DPolyPolygon& rCandidate, sal_uInt32 nCount)
187 		{
188 			if(rCandidate.areControlPointsUsed())
189 			{
190 				const sal_uInt32 nPolygonCount(rCandidate.count());
191 				B2DPolyPolygon aRetval;
192 
193 				for(sal_uInt32 a(0L); a < nPolygonCount; a++)
194 				{
195 					const B2DPolygon aCandidate(rCandidate.getB2DPolygon(a));
196 
197 					if(aCandidate.areControlPointsUsed())
198 					{
199 						aRetval.append(tools::adaptiveSubdivideByCount(aCandidate, nCount));
200 					}
201 					else
202 					{
203 						aRetval.append(aCandidate);
204 					}
205 				}
206 
207 				return aRetval;
208 			}
209 			else
210 			{
211 				return rCandidate;
212 			}
213 		}
214 
215 		bool isInside(const B2DPolyPolygon& rCandidate, const B2DPoint& rPoint, bool bWithBorder)
216 		{
217 			const sal_uInt32 nPolygonCount(rCandidate.count());
218 
219 			if(1L == nPolygonCount)
220 			{
221 				return isInside(rCandidate.getB2DPolygon(0L), rPoint, bWithBorder);
222 			}
223 			else
224 			{
225 				sal_Int32 nInsideCount(0L);
226 
227 				for(sal_uInt32 a(0L); a < nPolygonCount; a++)
228 				{
229 					const B2DPolygon aPolygon(rCandidate.getB2DPolygon(a));
230 					const bool bInside(isInside(aPolygon, rPoint, bWithBorder));
231 
232 					if(bInside)
233 					{
234 						nInsideCount++;
235 					}
236 				}
237 
238 				return (nInsideCount % 2L);
239 			}
240 		}
241 
242 		B2DRange getRangeWithControlPoints(const B2DPolyPolygon& rCandidate)
243 		{
244 			B2DRange aRetval;
245 			const sal_uInt32 nPolygonCount(rCandidate.count());
246 
247 			for(sal_uInt32 a(0L); a < nPolygonCount; a++)
248 			{
249 				B2DPolygon aCandidate = rCandidate.getB2DPolygon(a);
250 				aRetval.expand(tools::getRangeWithControlPoints(aCandidate));
251 			}
252 
253 			return aRetval;
254 		}
255 
256 		B2DRange getRange(const B2DPolyPolygon& rCandidate)
257 		{
258 			B2DRange aRetval;
259 			const sal_uInt32 nPolygonCount(rCandidate.count());
260 
261 			for(sal_uInt32 a(0L); a < nPolygonCount; a++)
262 			{
263 				B2DPolygon aCandidate = rCandidate.getB2DPolygon(a);
264 				aRetval.expand(tools::getRange(aCandidate));
265 			}
266 
267 			return aRetval;
268 		}
269 
270 		void applyLineDashing(const B2DPolyPolygon& rCandidate, const ::std::vector<double>& rDotDashArray, B2DPolyPolygon* pLineTarget, B2DPolyPolygon* pGapTarget, double fFullDashDotLen)
271 		{
272 			if(0.0 == fFullDashDotLen && rDotDashArray.size())
273 			{
274 				// calculate fFullDashDotLen from rDotDashArray
275 				fFullDashDotLen = ::std::accumulate(rDotDashArray.begin(), rDotDashArray.end(), 0.0);
276 			}
277 
278 			if(rCandidate.count() && fFullDashDotLen > 0.0)
279 			{
280 				B2DPolyPolygon aLineTarget, aGapTarget;
281 
282 				for(sal_uInt32 a(0L); a < rCandidate.count(); a++)
283 				{
284 					const B2DPolygon aCandidate(rCandidate.getB2DPolygon(a));
285 
286 					applyLineDashing(
287 						aCandidate,
288 						rDotDashArray,
289 						pLineTarget ? &aLineTarget : 0,
290 						pGapTarget ? &aGapTarget : 0,
291 						fFullDashDotLen);
292 
293 					if(pLineTarget)
294 					{
295 						pLineTarget->append(aLineTarget);
296 					}
297 
298 					if(pGapTarget)
299 					{
300 						pGapTarget->append(aGapTarget);
301 					}
302 				}
303 			}
304 		}
305 
306 		bool isInEpsilonRange(const B2DPolyPolygon& rCandidate, const B2DPoint& rTestPosition, double fDistance)
307 		{
308 			const sal_uInt32 nPolygonCount(rCandidate.count());
309 
310 			for(sal_uInt32 a(0L); a < nPolygonCount; a++)
311 			{
312 				B2DPolygon aCandidate(rCandidate.getB2DPolygon(a));
313 
314 				if(isInEpsilonRange(aCandidate, rTestPosition, fDistance))
315 				{
316 					return true;
317 				}
318 			}
319 
320 			return false;
321 		}
322 
323 		B3DPolyPolygon createB3DPolyPolygonFromB2DPolyPolygon(const B2DPolyPolygon& rCandidate, double fZCoordinate)
324 		{
325 			const sal_uInt32 nPolygonCount(rCandidate.count());
326 			B3DPolyPolygon aRetval;
327 
328 			for(sal_uInt32 a(0L); a < nPolygonCount; a++)
329 			{
330 				B2DPolygon aCandidate(rCandidate.getB2DPolygon(a));
331 
332 				aRetval.append(createB3DPolygonFromB2DPolygon(aCandidate, fZCoordinate));
333 			}
334 
335 			return aRetval;
336 		}
337 
338 		B2DPolyPolygon createB2DPolyPolygonFromB3DPolyPolygon(const B3DPolyPolygon& rCandidate, const B3DHomMatrix& rMat)
339 		{
340 			const sal_uInt32 nPolygonCount(rCandidate.count());
341 			B2DPolyPolygon aRetval;
342 
343 			for(sal_uInt32 a(0L); a < nPolygonCount; a++)
344 			{
345 				B3DPolygon aCandidate(rCandidate.getB3DPolygon(a));
346 
347 				aRetval.append(createB2DPolygonFromB3DPolygon(aCandidate, rMat));
348 			}
349 
350 			return aRetval;
351 		}
352 
353 		double getSmallestDistancePointToPolyPolygon(const B2DPolyPolygon& rCandidate, const B2DPoint& rTestPoint, sal_uInt32& rPolygonIndex, sal_uInt32& rEdgeIndex, double& rCut)
354 		{
355 			double fRetval(DBL_MAX);
356 			const double fZero(0.0);
357 			const sal_uInt32 nPolygonCount(rCandidate.count());
358 
359 			for(sal_uInt32 a(0L); a < nPolygonCount; a++)
360 			{
361 				const B2DPolygon aCandidate(rCandidate.getB2DPolygon(a));
362 				sal_uInt32 nNewEdgeIndex;
363 				double fNewCut;
364 				const double fNewDistance(getSmallestDistancePointToPolygon(aCandidate, rTestPoint, nNewEdgeIndex, fNewCut));
365 
366 				if(DBL_MAX == fRetval || fNewDistance < fRetval)
367 				{
368 					fRetval = fNewDistance;
369 					rPolygonIndex = a;
370 					rEdgeIndex = nNewEdgeIndex;
371 					rCut = fNewCut;
372 
373 					if(fTools::equal(fRetval, fZero))
374 					{
375 						// already found zero distance, cannot get better. Ensure numerical zero value and end loop.
376 						fRetval = 0.0;
377 						break;
378 					}
379 				}
380 			}
381 
382 			return fRetval;
383 		}
384 
385 		B2DPolyPolygon distort(const B2DPolyPolygon& rCandidate, const B2DRange& rOriginal, const B2DPoint& rTopLeft, const B2DPoint& rTopRight, const B2DPoint& rBottomLeft, const B2DPoint& rBottomRight)
386 		{
387 			const sal_uInt32 nPolygonCount(rCandidate.count());
388 			B2DPolyPolygon aRetval;
389 
390 			for(sal_uInt32 a(0L); a < nPolygonCount; a++)
391 			{
392 				const B2DPolygon aCandidate(rCandidate.getB2DPolygon(a));
393 
394 				aRetval.append(distort(aCandidate, rOriginal, rTopLeft, rTopRight, rBottomLeft, rBottomRight));
395 			}
396 
397 			return aRetval;
398 		}
399 
400 		B2DPolyPolygon rotateAroundPoint(const B2DPolyPolygon& rCandidate, const B2DPoint& rCenter, double fAngle)
401 		{
402 			const sal_uInt32 nPolygonCount(rCandidate.count());
403 			B2DPolyPolygon aRetval;
404 
405 			for(sal_uInt32 a(0L); a < nPolygonCount; a++)
406 			{
407 				const B2DPolygon aCandidate(rCandidate.getB2DPolygon(a));
408 
409 				aRetval.append(rotateAroundPoint(aCandidate, rCenter, fAngle));
410 			}
411 
412 			return aRetval;
413 		}
414 
415 		B2DPolyPolygon expandToCurve(const B2DPolyPolygon& rCandidate)
416 		{
417 			const sal_uInt32 nPolygonCount(rCandidate.count());
418 			B2DPolyPolygon aRetval;
419 
420 			for(sal_uInt32 a(0L); a < nPolygonCount; a++)
421 			{
422 				const B2DPolygon aCandidate(rCandidate.getB2DPolygon(a));
423 
424 				aRetval.append(expandToCurve(aCandidate));
425 			}
426 
427 			return aRetval;
428 		}
429 
430 		B2DPolyPolygon setContinuity(const B2DPolyPolygon& rCandidate, B2VectorContinuity eContinuity)
431 		{
432 			if(rCandidate.areControlPointsUsed())
433 			{
434 				const sal_uInt32 nPolygonCount(rCandidate.count());
435 				B2DPolyPolygon aRetval;
436 
437 				for(sal_uInt32 a(0L); a < nPolygonCount; a++)
438 				{
439 					const B2DPolygon aCandidate(rCandidate.getB2DPolygon(a));
440 
441 					aRetval.append(setContinuity(aCandidate, eContinuity));
442 				}
443 
444 				return aRetval;
445 			}
446 			else
447 			{
448 				return rCandidate;
449 			}
450 		}
451 
452 		B2DPolyPolygon growInNormalDirection(const B2DPolyPolygon& rCandidate, double fValue)
453 		{
454 			if(0.0 != fValue)
455 			{
456 				B2DPolyPolygon aRetval;
457 
458 				for(sal_uInt32 a(0L); a < rCandidate.count(); a++)
459 				{
460 					aRetval.append(growInNormalDirection(rCandidate.getB2DPolygon(a), fValue));
461 				}
462 
463 				return aRetval;
464 			}
465 			else
466 			{
467 				return rCandidate;
468 			}
469 		}
470 
471 		void correctGrowShrinkPolygonPair(B2DPolyPolygon& /*rOriginal*/, B2DPolyPolygon& /*rGrown*/)
472 		{
473 		}
474 
475 		B2DPolyPolygon reSegmentPolyPolygon(const B2DPolyPolygon& rCandidate, sal_uInt32 nSegments)
476 		{
477 			B2DPolyPolygon aRetval;
478 
479 			for(sal_uInt32 a(0L); a < rCandidate.count(); a++)
480 			{
481 				aRetval.append(reSegmentPolygon(rCandidate.getB2DPolygon(a), nSegments));
482 			}
483 
484 			return aRetval;
485 		}
486 
487 		B2DPolyPolygon interpolate(const B2DPolyPolygon& rOld1, const B2DPolyPolygon& rOld2, double t)
488 		{
489 			OSL_ENSURE(rOld1.count() == rOld2.count(), "B2DPolyPolygon interpolate: Different geometry (!)");
490 			B2DPolyPolygon aRetval;
491 
492 			for(sal_uInt32 a(0L); a < rOld1.count(); a++)
493 			{
494 				aRetval.append(interpolate(rOld1.getB2DPolygon(a), rOld2.getB2DPolygon(a), t));
495 			}
496 
497 			return aRetval;
498 		}
499 
500         bool isRectangle( const B2DPolyPolygon& rPoly )
501         {
502             // exclude some cheap cases first
503             if( rPoly.count() != 1 )
504                 return false;
505 
506             return isRectangle( rPoly.getB2DPolygon(0) );
507         }
508 
509 		// #i76891#
510 		B2DPolyPolygon simplifyCurveSegments(const B2DPolyPolygon& rCandidate)
511 		{
512 			if(rCandidate.areControlPointsUsed())
513 			{
514 				B2DPolyPolygon aRetval;
515 
516 				for(sal_uInt32 a(0L); a < rCandidate.count(); a++)
517 				{
518 					aRetval.append(simplifyCurveSegments(rCandidate.getB2DPolygon(a)));
519 				}
520 
521 				return aRetval;
522 			}
523 			else
524 			{
525 				return rCandidate;
526 			}
527 		}
528 
529 		B2DPolyPolygon reSegmentPolyPolygonEdges(const B2DPolyPolygon& rCandidate, sal_uInt32 nSubEdges, bool bHandleCurvedEdges, bool bHandleStraightEdges)
530         {
531 			B2DPolyPolygon aRetval;
532 
533 			for(sal_uInt32 a(0L); a < rCandidate.count(); a++)
534 			{
535 				aRetval.append(reSegmentPolygonEdges(rCandidate.getB2DPolygon(a), nSubEdges, bHandleCurvedEdges, bHandleStraightEdges));
536 			}
537 
538 			return aRetval;
539         }
540 
541         //////////////////////////////////////////////////////////////////////
542 		// comparators with tolerance for 2D PolyPolygons
543 
544 		bool equal(const B2DPolyPolygon& rCandidateA, const B2DPolyPolygon& rCandidateB, const double& rfSmallValue)
545 		{
546 			const sal_uInt32 nPolygonCount(rCandidateA.count());
547 
548 			if(nPolygonCount != rCandidateB.count())
549 				return false;
550 
551 			for(sal_uInt32 a(0); a < nPolygonCount; a++)
552 			{
553 				const B2DPolygon aCandidate(rCandidateA.getB2DPolygon(a));
554 
555 				if(!equal(aCandidate, rCandidateB.getB2DPolygon(a), rfSmallValue))
556 					return false;
557 			}
558 
559 			return true;
560 		}
561 
562 		bool equal(const B2DPolyPolygon& rCandidateA, const B2DPolyPolygon& rCandidateB)
563 		{
564 			const double fSmallValue(fTools::getSmallValue());
565 
566 			return equal(rCandidateA, rCandidateB, fSmallValue);
567 		}
568 
569 		B2DPolyPolygon snapPointsOfHorizontalOrVerticalEdges(const B2DPolyPolygon& rCandidate)
570 		{
571 			B2DPolyPolygon aRetval;
572 
573 			for(sal_uInt32 a(0L); a < rCandidate.count(); a++)
574 			{
575 				aRetval.append(snapPointsOfHorizontalOrVerticalEdges(rCandidate.getB2DPolygon(a)));
576 			}
577 
578 			return aRetval;
579 		}
580 
581 	} // end of namespace tools
582 } // end of namespace basegfx
583 
584 //////////////////////////////////////////////////////////////////////////////
585 // eof
586