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