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 		void applyLineDashing(const B2DPolyPolygon& rCandidate, const ::std::vector<double>& rDotDashArray, B2DPolyPolygon* pLineTarget, B2DPolyPolygon* pGapTarget, double fFullDashDotLen)
267 		{
268 			if(0.0 == fFullDashDotLen && rDotDashArray.size())
269 			{
270 				// calculate fFullDashDotLen from rDotDashArray
271 				fFullDashDotLen = ::std::accumulate(rDotDashArray.begin(), rDotDashArray.end(), 0.0);
272 			}
273 
274 			if(rCandidate.count() && fFullDashDotLen > 0.0)
275 			{
276 				B2DPolyPolygon aLineTarget, aGapTarget;
277 
278 				for(sal_uInt32 a(0L); a < rCandidate.count(); a++)
279 				{
280 					const B2DPolygon aCandidate(rCandidate.getB2DPolygon(a));
281 
282 					applyLineDashing(
283 						aCandidate,
284 						rDotDashArray,
285 						pLineTarget ? &aLineTarget : 0,
286 						pGapTarget ? &aGapTarget : 0,
287 						fFullDashDotLen);
288 
289 					if(pLineTarget)
290 					{
291 						pLineTarget->append(aLineTarget);
292 					}
293 
294 					if(pGapTarget)
295 					{
296 						pGapTarget->append(aGapTarget);
297 					}
298 				}
299 			}
300 		}
301 
302 		bool isInEpsilonRange(const B2DPolyPolygon& rCandidate, const B2DPoint& rTestPosition, double fDistance)
303 		{
304 			const sal_uInt32 nPolygonCount(rCandidate.count());
305 
306 			for(sal_uInt32 a(0L); a < nPolygonCount; a++)
307 			{
308 				B2DPolygon aCandidate(rCandidate.getB2DPolygon(a));
309 
310 				if(isInEpsilonRange(aCandidate, rTestPosition, fDistance))
311 				{
312 					return true;
313 				}
314 			}
315 
316 			return false;
317 		}
318 
319 		B3DPolyPolygon createB3DPolyPolygonFromB2DPolyPolygon(const B2DPolyPolygon& rCandidate, double fZCoordinate)
320 		{
321 			const sal_uInt32 nPolygonCount(rCandidate.count());
322 			B3DPolyPolygon aRetval;
323 
324 			for(sal_uInt32 a(0L); a < nPolygonCount; a++)
325 			{
326 				B2DPolygon aCandidate(rCandidate.getB2DPolygon(a));
327 
328 				aRetval.append(createB3DPolygonFromB2DPolygon(aCandidate, fZCoordinate));
329 			}
330 
331 			return aRetval;
332 		}
333 
334 		B2DPolyPolygon createB2DPolyPolygonFromB3DPolyPolygon(const B3DPolyPolygon& rCandidate, const B3DHomMatrix& rMat)
335 		{
336 			const sal_uInt32 nPolygonCount(rCandidate.count());
337 			B2DPolyPolygon aRetval;
338 
339 			for(sal_uInt32 a(0L); a < nPolygonCount; a++)
340 			{
341 				B3DPolygon aCandidate(rCandidate.getB3DPolygon(a));
342 
343 				aRetval.append(createB2DPolygonFromB3DPolygon(aCandidate, rMat));
344 			}
345 
346 			return aRetval;
347 		}
348 
349 		double getSmallestDistancePointToPolyPolygon(const B2DPolyPolygon& rCandidate, const B2DPoint& rTestPoint, sal_uInt32& rPolygonIndex, sal_uInt32& rEdgeIndex, double& rCut)
350 		{
351 			double fRetval(DBL_MAX);
352 			const double fZero(0.0);
353 			const sal_uInt32 nPolygonCount(rCandidate.count());
354 
355 			for(sal_uInt32 a(0L); a < nPolygonCount; a++)
356 			{
357 				const B2DPolygon aCandidate(rCandidate.getB2DPolygon(a));
358 				sal_uInt32 nNewEdgeIndex;
359 				double fNewCut;
360 				const double fNewDistance(getSmallestDistancePointToPolygon(aCandidate, rTestPoint, nNewEdgeIndex, fNewCut));
361 
362 				if(DBL_MAX == fRetval || fNewDistance < fRetval)
363 				{
364 					fRetval = fNewDistance;
365 					rPolygonIndex = a;
366 					rEdgeIndex = nNewEdgeIndex;
367 					rCut = fNewCut;
368 
369 					if(fTools::equal(fRetval, fZero))
370 					{
371 						// already found zero distance, cannot get better. Ensure numerical zero value and end loop.
372 						fRetval = 0.0;
373 						break;
374 					}
375 				}
376 			}
377 
378 			return fRetval;
379 		}
380 
381 		B2DPolyPolygon distort(const B2DPolyPolygon& rCandidate, const B2DRange& rOriginal, const B2DPoint& rTopLeft, const B2DPoint& rTopRight, const B2DPoint& rBottomLeft, const B2DPoint& rBottomRight)
382 		{
383 			const sal_uInt32 nPolygonCount(rCandidate.count());
384 			B2DPolyPolygon aRetval;
385 
386 			for(sal_uInt32 a(0L); a < nPolygonCount; a++)
387 			{
388 				const B2DPolygon aCandidate(rCandidate.getB2DPolygon(a));
389 
390 				aRetval.append(distort(aCandidate, rOriginal, rTopLeft, rTopRight, rBottomLeft, rBottomRight));
391 			}
392 
393 			return aRetval;
394 		}
395 
396 		B2DPolyPolygon rotateAroundPoint(const B2DPolyPolygon& rCandidate, const B2DPoint& rCenter, double fAngle)
397 		{
398 			const sal_uInt32 nPolygonCount(rCandidate.count());
399 			B2DPolyPolygon aRetval;
400 
401 			for(sal_uInt32 a(0L); a < nPolygonCount; a++)
402 			{
403 				const B2DPolygon aCandidate(rCandidate.getB2DPolygon(a));
404 
405 				aRetval.append(rotateAroundPoint(aCandidate, rCenter, fAngle));
406 			}
407 
408 			return aRetval;
409 		}
410 
411 		B2DPolyPolygon expandToCurve(const B2DPolyPolygon& rCandidate)
412 		{
413 			const sal_uInt32 nPolygonCount(rCandidate.count());
414 			B2DPolyPolygon aRetval;
415 
416 			for(sal_uInt32 a(0L); a < nPolygonCount; a++)
417 			{
418 				const B2DPolygon aCandidate(rCandidate.getB2DPolygon(a));
419 
420 				aRetval.append(expandToCurve(aCandidate));
421 			}
422 
423 			return aRetval;
424 		}
425 
426 		B2DPolyPolygon setContinuity(const B2DPolyPolygon& rCandidate, B2VectorContinuity eContinuity)
427 		{
428 			if(rCandidate.areControlPointsUsed())
429 			{
430 				const sal_uInt32 nPolygonCount(rCandidate.count());
431 				B2DPolyPolygon aRetval;
432 
433 				for(sal_uInt32 a(0L); a < nPolygonCount; a++)
434 				{
435 					const B2DPolygon aCandidate(rCandidate.getB2DPolygon(a));
436 
437 					aRetval.append(setContinuity(aCandidate, eContinuity));
438 				}
439 
440 				return aRetval;
441 			}
442 			else
443 			{
444 				return rCandidate;
445 			}
446 		}
447 
448 		B2DPolyPolygon growInNormalDirection(const B2DPolyPolygon& rCandidate, double fValue)
449 		{
450 			if(0.0 != fValue)
451 			{
452 				B2DPolyPolygon aRetval;
453 
454 				for(sal_uInt32 a(0L); a < rCandidate.count(); a++)
455 				{
456 					aRetval.append(growInNormalDirection(rCandidate.getB2DPolygon(a), fValue));
457 				}
458 
459 				return aRetval;
460 			}
461 			else
462 			{
463 				return rCandidate;
464 			}
465 		}
466 
467 		void correctGrowShrinkPolygonPair(B2DPolyPolygon& /*rOriginal*/, B2DPolyPolygon& /*rGrown*/)
468 		{
469 		}
470 
471 		B2DPolyPolygon reSegmentPolyPolygon(const B2DPolyPolygon& rCandidate, sal_uInt32 nSegments)
472 		{
473 			B2DPolyPolygon aRetval;
474 
475 			for(sal_uInt32 a(0L); a < rCandidate.count(); a++)
476 			{
477 				aRetval.append(reSegmentPolygon(rCandidate.getB2DPolygon(a), nSegments));
478 			}
479 
480 			return aRetval;
481 		}
482 
483 		B2DPolyPolygon interpolate(const B2DPolyPolygon& rOld1, const B2DPolyPolygon& rOld2, double t)
484 		{
485 			OSL_ENSURE(rOld1.count() == rOld2.count(), "B2DPolyPolygon interpolate: Different geometry (!)");
486 			B2DPolyPolygon aRetval;
487 
488 			for(sal_uInt32 a(0L); a < rOld1.count(); a++)
489 			{
490 				aRetval.append(interpolate(rOld1.getB2DPolygon(a), rOld2.getB2DPolygon(a), t));
491 			}
492 
493 			return aRetval;
494 		}
495 
496         bool isRectangle( const B2DPolyPolygon& rPoly )
497         {
498             // exclude some cheap cases first
499             if( rPoly.count() != 1 )
500                 return false;
501 
502             return isRectangle( rPoly.getB2DPolygon(0) );
503         }
504 
505 		// #i76891#
506 		B2DPolyPolygon simplifyCurveSegments(const B2DPolyPolygon& rCandidate)
507 		{
508 			if(rCandidate.areControlPointsUsed())
509 			{
510 				B2DPolyPolygon aRetval;
511 
512 				for(sal_uInt32 a(0L); a < rCandidate.count(); a++)
513 				{
514 					aRetval.append(simplifyCurveSegments(rCandidate.getB2DPolygon(a)));
515 				}
516 
517 				return aRetval;
518 			}
519 			else
520 			{
521 				return rCandidate;
522 			}
523 		}
524 
525 		B2DPolyPolygon reSegmentPolyPolygonEdges(const B2DPolyPolygon& rCandidate, sal_uInt32 nSubEdges, bool bHandleCurvedEdges, bool bHandleStraightEdges)
526         {
527 			B2DPolyPolygon aRetval;
528 
529 			for(sal_uInt32 a(0L); a < rCandidate.count(); a++)
530 			{
531 				aRetval.append(reSegmentPolygonEdges(rCandidate.getB2DPolygon(a), nSubEdges, bHandleCurvedEdges, bHandleStraightEdges));
532 			}
533 
534 			return aRetval;
535         }
536 
537         //////////////////////////////////////////////////////////////////////
538 		// comparators with tolerance for 2D PolyPolygons
539 
540 		bool equal(const B2DPolyPolygon& rCandidateA, const B2DPolyPolygon& rCandidateB, const double& rfSmallValue)
541 		{
542 			const sal_uInt32 nPolygonCount(rCandidateA.count());
543 
544 			if(nPolygonCount != rCandidateB.count())
545 				return false;
546 
547 			for(sal_uInt32 a(0); a < nPolygonCount; a++)
548 			{
549 				const B2DPolygon aCandidate(rCandidateA.getB2DPolygon(a));
550 
551 				if(!equal(aCandidate, rCandidateB.getB2DPolygon(a), rfSmallValue))
552 					return false;
553 			}
554 
555 			return true;
556 		}
557 
558 		bool equal(const B2DPolyPolygon& rCandidateA, const B2DPolyPolygon& rCandidateB)
559 		{
560 			const double fSmallValue(fTools::getSmallValue());
561 
562 			return equal(rCandidateA, rCandidateB, fSmallValue);
563 		}
564 
565 		B2DPolyPolygon snapPointsOfHorizontalOrVerticalEdges(const B2DPolyPolygon& rCandidate)
566 		{
567 			B2DPolyPolygon aRetval;
568 
569 			for(sal_uInt32 a(0L); a < rCandidate.count(); a++)
570 			{
571 				aRetval.append(snapPointsOfHorizontalOrVerticalEdges(rCandidate.getB2DPolygon(a)));
572 			}
573 
574 			return aRetval;
575 		}
576 
577 	} // end of namespace tools
578 } // end of namespace basegfx
579 
580 //////////////////////////////////////////////////////////////////////////////
581 // eof
582