Line data Source code
1 : /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
2 : /*
3 : * This file is part of the LibreOffice project.
4 : *
5 : * This Source Code Form is subject to the terms of the Mozilla Public
6 : * License, v. 2.0. If a copy of the MPL was not distributed with this
7 : * file, You can obtain one at http://mozilla.org/MPL/2.0/.
8 : *
9 : * This file incorporates work covered by the following license notice:
10 : *
11 : * Licensed to the Apache Software Foundation (ASF) under one or more
12 : * contributor license agreements. See the NOTICE file distributed
13 : * with this work for additional information regarding copyright
14 : * ownership. The ASF licenses this file to you under the Apache
15 : * License, Version 2.0 (the "License"); you may not use this file
16 : * except in compliance with the License. You may obtain a copy of
17 : * the License at http://www.apache.org/licenses/LICENSE-2.0 .
18 : */
19 :
20 : #include <basegfx/polygon/b2dpolypolygontools.hxx>
21 : #include <osl/diagnose.h>
22 : #include <basegfx/polygon/b2dpolypolygon.hxx>
23 : #include <basegfx/polygon/b2dpolygon.hxx>
24 : #include <basegfx/polygon/b2dpolygontools.hxx>
25 : #include <basegfx/numeric/ftools.hxx>
26 : #include <basegfx/polygon/b2dpolypolygoncutter.hxx>
27 :
28 : #include <numeric>
29 :
30 : //////////////////////////////////////////////////////////////////////////////
31 :
32 : namespace basegfx
33 : {
34 : namespace tools
35 : {
36 12644 : B2DPolyPolygon correctOrientations(const B2DPolyPolygon& rCandidate)
37 : {
38 12644 : B2DPolyPolygon aRetval(rCandidate);
39 12644 : const sal_uInt32 nCount(aRetval.count());
40 :
41 25330 : for(sal_uInt32 a(0L); a < nCount; a++)
42 : {
43 12686 : const B2DPolygon aCandidate(rCandidate.getB2DPolygon(a));
44 12686 : const B2VectorOrientation aOrientation(tools::getOrientation(aCandidate));
45 12686 : sal_uInt32 nDepth(0L);
46 :
47 25492 : for(sal_uInt32 b(0L); b < nCount; b++)
48 : {
49 12806 : if(b != a)
50 : {
51 120 : const B2DPolygon aCompare(rCandidate.getB2DPolygon(b));
52 :
53 120 : if(tools::isInside(aCompare, aCandidate, true))
54 : {
55 12 : nDepth++;
56 120 : }
57 : }
58 : }
59 :
60 12686 : const bool bShallBeHole(1L == (nDepth & 0x00000001));
61 12686 : const bool bIsHole(ORIENTATION_NEGATIVE == aOrientation);
62 :
63 12686 : if(bShallBeHole != bIsHole && ORIENTATION_NEUTRAL != aOrientation)
64 : {
65 3234 : B2DPolygon aFlipped(aCandidate);
66 3234 : aFlipped.flip();
67 3234 : aRetval.setB2DPolygon(a, aFlipped);
68 : }
69 12686 : }
70 :
71 12644 : return aRetval;
72 : }
73 :
74 1684 : B2DPolyPolygon correctOutmostPolygon(const B2DPolyPolygon& rCandidate)
75 : {
76 1684 : const sal_uInt32 nCount(rCandidate.count());
77 :
78 1684 : if(nCount > 1L)
79 : {
80 0 : for(sal_uInt32 a(0L); a < nCount; a++)
81 : {
82 0 : const B2DPolygon aCandidate(rCandidate.getB2DPolygon(a));
83 0 : sal_uInt32 nDepth(0L);
84 :
85 0 : for(sal_uInt32 b(0L); b < nCount; b++)
86 : {
87 0 : if(b != a)
88 : {
89 0 : const B2DPolygon aCompare(rCandidate.getB2DPolygon(b));
90 :
91 0 : if(tools::isInside(aCompare, aCandidate, true))
92 : {
93 0 : nDepth++;
94 0 : }
95 : }
96 : }
97 :
98 0 : if(!nDepth)
99 : {
100 0 : B2DPolyPolygon aRetval(rCandidate);
101 :
102 0 : if(a != 0L)
103 : {
104 : // exchange polygon a and polygon 0L
105 0 : aRetval.setB2DPolygon(0L, aCandidate);
106 0 : aRetval.setB2DPolygon(a, rCandidate.getB2DPolygon(0L));
107 : }
108 :
109 : // exit
110 0 : return aRetval;
111 : }
112 0 : }
113 : }
114 :
115 1684 : return rCandidate;
116 : }
117 :
118 0 : B2DPolyPolygon adaptiveSubdivideByDistance(const B2DPolyPolygon& rCandidate, double fDistanceBound)
119 : {
120 0 : if(rCandidate.areControlPointsUsed())
121 : {
122 0 : const sal_uInt32 nPolygonCount(rCandidate.count());
123 0 : B2DPolyPolygon aRetval;
124 :
125 0 : for(sal_uInt32 a(0L); a < nPolygonCount; a++)
126 : {
127 0 : const B2DPolygon aCandidate(rCandidate.getB2DPolygon(a));
128 :
129 0 : if(aCandidate.areControlPointsUsed())
130 : {
131 0 : aRetval.append(tools::adaptiveSubdivideByDistance(aCandidate, fDistanceBound));
132 : }
133 : else
134 : {
135 0 : aRetval.append(aCandidate);
136 : }
137 0 : }
138 :
139 0 : return aRetval;
140 : }
141 : else
142 : {
143 0 : return rCandidate;
144 : }
145 : }
146 :
147 1689 : B2DPolyPolygon adaptiveSubdivideByAngle(const B2DPolyPolygon& rCandidate, double fAngleBound)
148 : {
149 1689 : if(rCandidate.areControlPointsUsed())
150 : {
151 5 : const sal_uInt32 nPolygonCount(rCandidate.count());
152 5 : B2DPolyPolygon aRetval;
153 :
154 10 : for(sal_uInt32 a(0L); a < nPolygonCount; a++)
155 : {
156 5 : const B2DPolygon aCandidate(rCandidate.getB2DPolygon(a));
157 :
158 5 : if(aCandidate.areControlPointsUsed())
159 : {
160 5 : aRetval.append(tools::adaptiveSubdivideByAngle(aCandidate, fAngleBound));
161 : }
162 : else
163 : {
164 0 : aRetval.append(aCandidate);
165 : }
166 5 : }
167 :
168 5 : return aRetval;
169 : }
170 : else
171 : {
172 1684 : return rCandidate;
173 : }
174 : }
175 :
176 0 : B2DPolyPolygon adaptiveSubdivideByCount(const B2DPolyPolygon& rCandidate, sal_uInt32 nCount)
177 : {
178 0 : if(rCandidate.areControlPointsUsed())
179 : {
180 0 : const sal_uInt32 nPolygonCount(rCandidate.count());
181 0 : B2DPolyPolygon aRetval;
182 :
183 0 : for(sal_uInt32 a(0L); a < nPolygonCount; a++)
184 : {
185 0 : const B2DPolygon aCandidate(rCandidate.getB2DPolygon(a));
186 :
187 0 : if(aCandidate.areControlPointsUsed())
188 : {
189 0 : aRetval.append(tools::adaptiveSubdivideByCount(aCandidate, nCount));
190 : }
191 : else
192 : {
193 0 : aRetval.append(aCandidate);
194 : }
195 0 : }
196 :
197 0 : return aRetval;
198 : }
199 : else
200 : {
201 0 : return rCandidate;
202 : }
203 : }
204 :
205 805 : bool isInside(const B2DPolyPolygon& rCandidate, const B2DPoint& rPoint, bool bWithBorder)
206 : {
207 805 : const sal_uInt32 nPolygonCount(rCandidate.count());
208 :
209 805 : if(1L == nPolygonCount)
210 : {
211 805 : return isInside(rCandidate.getB2DPolygon(0L), rPoint, bWithBorder);
212 : }
213 : else
214 : {
215 0 : sal_Int32 nInsideCount(0L);
216 :
217 0 : for(sal_uInt32 a(0L); a < nPolygonCount; a++)
218 : {
219 0 : const B2DPolygon aPolygon(rCandidate.getB2DPolygon(a));
220 0 : const bool bInside(isInside(aPolygon, rPoint, bWithBorder));
221 :
222 0 : if(bInside)
223 : {
224 0 : nInsideCount++;
225 : }
226 0 : }
227 :
228 0 : return (nInsideCount % 2L);
229 : }
230 : }
231 :
232 2384151 : B2DRange getRange(const B2DPolyPolygon& rCandidate)
233 : {
234 2384151 : B2DRange aRetval;
235 2384151 : const sal_uInt32 nPolygonCount(rCandidate.count());
236 :
237 4826328 : for(sal_uInt32 a(0L); a < nPolygonCount; a++)
238 : {
239 2442177 : B2DPolygon aCandidate = rCandidate.getB2DPolygon(a);
240 2442177 : aRetval.expand(tools::getRange(aCandidate));
241 2442177 : }
242 :
243 2384151 : return aRetval;
244 : }
245 :
246 0 : double getSignedArea(const B2DPolyPolygon& rCandidate)
247 : {
248 0 : double fRetval(0.0);
249 0 : const sal_uInt32 nPolygonCount(rCandidate.count());
250 :
251 0 : for(sal_uInt32 a(0L); a < nPolygonCount; a++)
252 : {
253 0 : const B2DPolygon aCandidate(rCandidate.getB2DPolygon(a));
254 :
255 0 : fRetval += tools::getSignedArea(aCandidate);
256 0 : }
257 :
258 0 : return fRetval;
259 : }
260 :
261 0 : double getArea(const B2DPolyPolygon& rCandidate)
262 : {
263 0 : return fabs(getSignedArea(rCandidate));
264 : }
265 :
266 0 : void applyLineDashing(const B2DPolyPolygon& rCandidate, const ::std::vector<double>& rDotDashArray, B2DPolyPolygon* pLineTarget, B2DPolyPolygon* pGapTarget, double fFullDashDotLen)
267 : {
268 0 : if(0.0 == fFullDashDotLen && rDotDashArray.size())
269 : {
270 : // calculate fFullDashDotLen from rDotDashArray
271 0 : fFullDashDotLen = ::std::accumulate(rDotDashArray.begin(), rDotDashArray.end(), 0.0);
272 : }
273 :
274 0 : if(rCandidate.count() && fFullDashDotLen > 0.0)
275 : {
276 0 : B2DPolyPolygon aLineTarget, aGapTarget;
277 :
278 0 : for(sal_uInt32 a(0L); a < rCandidate.count(); a++)
279 : {
280 0 : const B2DPolygon aCandidate(rCandidate.getB2DPolygon(a));
281 :
282 : applyLineDashing(
283 : aCandidate,
284 : rDotDashArray,
285 : pLineTarget ? &aLineTarget : 0,
286 : pGapTarget ? &aGapTarget : 0,
287 0 : fFullDashDotLen);
288 :
289 0 : if(pLineTarget)
290 : {
291 0 : pLineTarget->append(aLineTarget);
292 : }
293 :
294 0 : if(pGapTarget)
295 : {
296 0 : pGapTarget->append(aGapTarget);
297 : }
298 0 : }
299 : }
300 0 : }
301 :
302 1 : bool isInEpsilonRange(const B2DPolyPolygon& rCandidate, const B2DPoint& rTestPosition, double fDistance)
303 : {
304 1 : const sal_uInt32 nPolygonCount(rCandidate.count());
305 :
306 2 : for(sal_uInt32 a(0L); a < nPolygonCount; a++)
307 : {
308 1 : B2DPolygon aCandidate(rCandidate.getB2DPolygon(a));
309 :
310 1 : if(isInEpsilonRange(aCandidate, rTestPosition, fDistance))
311 : {
312 0 : return true;
313 : }
314 1 : }
315 :
316 1 : return false;
317 : }
318 :
319 6752 : B3DPolyPolygon createB3DPolyPolygonFromB2DPolyPolygon(const B2DPolyPolygon& rCandidate, double fZCoordinate)
320 : {
321 6752 : const sal_uInt32 nPolygonCount(rCandidate.count());
322 6752 : B3DPolyPolygon aRetval;
323 :
324 14224 : for(sal_uInt32 a(0L); a < nPolygonCount; a++)
325 : {
326 7472 : B2DPolygon aCandidate(rCandidate.getB2DPolygon(a));
327 :
328 7472 : aRetval.append(createB3DPolygonFromB2DPolygon(aCandidate, fZCoordinate));
329 7472 : }
330 :
331 6752 : return aRetval;
332 : }
333 :
334 1082 : B2DPolyPolygon createB2DPolyPolygonFromB3DPolyPolygon(const B3DPolyPolygon& rCandidate, const B3DHomMatrix& rMat)
335 : {
336 1082 : const sal_uInt32 nPolygonCount(rCandidate.count());
337 1082 : B2DPolyPolygon aRetval;
338 :
339 2164 : for(sal_uInt32 a(0L); a < nPolygonCount; a++)
340 : {
341 1082 : B3DPolygon aCandidate(rCandidate.getB3DPolygon(a));
342 :
343 1082 : aRetval.append(createB2DPolygonFromB3DPolygon(aCandidate, rMat));
344 1082 : }
345 :
346 1082 : return aRetval;
347 : }
348 :
349 0 : double getSmallestDistancePointToPolyPolygon(const B2DPolyPolygon& rCandidate, const B2DPoint& rTestPoint, sal_uInt32& rPolygonIndex, sal_uInt32& rEdgeIndex, double& rCut)
350 : {
351 0 : double fRetval(DBL_MAX);
352 0 : const double fZero(0.0);
353 0 : const sal_uInt32 nPolygonCount(rCandidate.count());
354 :
355 0 : for(sal_uInt32 a(0L); a < nPolygonCount; a++)
356 : {
357 0 : const B2DPolygon aCandidate(rCandidate.getB2DPolygon(a));
358 : sal_uInt32 nNewEdgeIndex;
359 : double fNewCut;
360 0 : const double fNewDistance(getSmallestDistancePointToPolygon(aCandidate, rTestPoint, nNewEdgeIndex, fNewCut));
361 :
362 0 : if(DBL_MAX == fRetval || fNewDistance < fRetval)
363 : {
364 0 : fRetval = fNewDistance;
365 0 : rPolygonIndex = a;
366 0 : rEdgeIndex = nNewEdgeIndex;
367 0 : rCut = fNewCut;
368 :
369 0 : if(fTools::equal(fRetval, fZero))
370 : {
371 : // already found zero distance, cannot get better. Ensure numerical zero value and end loop.
372 0 : fRetval = 0.0;
373 0 : break;
374 : }
375 : }
376 0 : }
377 :
378 0 : return fRetval;
379 : }
380 :
381 0 : B2DPolyPolygon distort(const B2DPolyPolygon& rCandidate, const B2DRange& rOriginal, const B2DPoint& rTopLeft, const B2DPoint& rTopRight, const B2DPoint& rBottomLeft, const B2DPoint& rBottomRight)
382 : {
383 0 : const sal_uInt32 nPolygonCount(rCandidate.count());
384 0 : B2DPolyPolygon aRetval;
385 :
386 0 : for(sal_uInt32 a(0L); a < nPolygonCount; a++)
387 : {
388 0 : const B2DPolygon aCandidate(rCandidate.getB2DPolygon(a));
389 :
390 0 : aRetval.append(distort(aCandidate, rOriginal, rTopLeft, rTopRight, rBottomLeft, rBottomRight));
391 0 : }
392 :
393 0 : return aRetval;
394 : }
395 :
396 20 : B2DPolyPolygon expandToCurve(const B2DPolyPolygon& rCandidate)
397 : {
398 20 : const sal_uInt32 nPolygonCount(rCandidate.count());
399 20 : B2DPolyPolygon aRetval;
400 :
401 40 : for(sal_uInt32 a(0L); a < nPolygonCount; a++)
402 : {
403 20 : const B2DPolygon aCandidate(rCandidate.getB2DPolygon(a));
404 :
405 20 : aRetval.append(expandToCurve(aCandidate));
406 20 : }
407 :
408 20 : return aRetval;
409 : }
410 :
411 1684 : B2DPolyPolygon growInNormalDirection(const B2DPolyPolygon& rCandidate, double fValue)
412 : {
413 1684 : if(0.0 != fValue)
414 : {
415 1684 : B2DPolyPolygon aRetval;
416 :
417 3368 : for(sal_uInt32 a(0L); a < rCandidate.count(); a++)
418 : {
419 1684 : aRetval.append(growInNormalDirection(rCandidate.getB2DPolygon(a), fValue));
420 : }
421 :
422 1684 : return aRetval;
423 : }
424 : else
425 : {
426 0 : return rCandidate;
427 : }
428 : }
429 :
430 0 : void correctGrowShrinkPolygonPair(SAL_UNUSED_PARAMETER B2DPolyPolygon& /*rOriginal*/, SAL_UNUSED_PARAMETER B2DPolyPolygon& /*rGrown*/)
431 : {
432 : //TODO!
433 0 : }
434 :
435 0 : B2DPolyPolygon reSegmentPolyPolygon(const B2DPolyPolygon& rCandidate, sal_uInt32 nSegments)
436 : {
437 0 : B2DPolyPolygon aRetval;
438 :
439 0 : for(sal_uInt32 a(0L); a < rCandidate.count(); a++)
440 : {
441 0 : aRetval.append(reSegmentPolygon(rCandidate.getB2DPolygon(a), nSegments));
442 : }
443 :
444 0 : return aRetval;
445 : }
446 :
447 0 : B2DPolyPolygon interpolate(const B2DPolyPolygon& rOld1, const B2DPolyPolygon& rOld2, double t)
448 : {
449 : OSL_ENSURE(rOld1.count() == rOld2.count(), "B2DPolyPolygon interpolate: Different geometry (!)");
450 0 : B2DPolyPolygon aRetval;
451 :
452 0 : for(sal_uInt32 a(0L); a < rOld1.count(); a++)
453 : {
454 0 : aRetval.append(interpolate(rOld1.getB2DPolygon(a), rOld2.getB2DPolygon(a), t));
455 : }
456 :
457 0 : return aRetval;
458 : }
459 :
460 20 : bool isRectangle( const B2DPolyPolygon& rPoly )
461 : {
462 : // exclude some cheap cases first
463 20 : if( rPoly.count() != 1 )
464 0 : return false;
465 :
466 20 : return isRectangle( rPoly.getB2DPolygon(0) );
467 : }
468 :
469 : // #i76891#
470 6102 : B2DPolyPolygon simplifyCurveSegments(const B2DPolyPolygon& rCandidate)
471 : {
472 6102 : if(rCandidate.areControlPointsUsed())
473 : {
474 478 : B2DPolyPolygon aRetval;
475 :
476 2303 : for(sal_uInt32 a(0L); a < rCandidate.count(); a++)
477 : {
478 1825 : aRetval.append(simplifyCurveSegments(rCandidate.getB2DPolygon(a)));
479 : }
480 :
481 478 : return aRetval;
482 : }
483 : else
484 : {
485 5624 : return rCandidate;
486 : }
487 : }
488 :
489 0 : B2DPolyPolygon snapPointsOfHorizontalOrVerticalEdges(const B2DPolyPolygon& rCandidate)
490 : {
491 0 : B2DPolyPolygon aRetval;
492 :
493 0 : for(sal_uInt32 a(0L); a < rCandidate.count(); a++)
494 : {
495 0 : aRetval.append(snapPointsOfHorizontalOrVerticalEdges(rCandidate.getB2DPolygon(a)));
496 : }
497 :
498 0 : return aRetval;
499 : }
500 :
501 : } // end of namespace tools
502 : } // end of namespace basegfx
503 :
504 : /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
|
