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 352 : B2DPolyPolygon correctOrientations(const B2DPolyPolygon& rCandidate)
37 : {
38 352 : B2DPolyPolygon aRetval(rCandidate);
39 352 : const sal_uInt32 nCount(aRetval.count());
40 :
41 716 : for(sal_uInt32 a(0L); a < nCount; a++)
42 : {
43 364 : const B2DPolygon aCandidate(rCandidate.getB2DPolygon(a));
44 364 : const B2VectorOrientation aOrientation(tools::getOrientation(aCandidate));
45 364 : sal_uInt32 nDepth(0L);
46 :
47 768 : for(sal_uInt32 b(0L); b < nCount; b++)
48 : {
49 404 : if(b != a)
50 : {
51 40 : const B2DPolygon aCompare(rCandidate.getB2DPolygon(b));
52 :
53 40 : if(tools::isInside(aCompare, aCandidate, true))
54 : {
55 12 : nDepth++;
56 40 : }
57 : }
58 : }
59 :
60 364 : const bool bShallBeHole(1L == (nDepth & 0x00000001));
61 364 : const bool bIsHole(ORIENTATION_NEGATIVE == aOrientation);
62 :
63 364 : if(bShallBeHole != bIsHole && ORIENTATION_NEUTRAL != aOrientation)
64 : {
65 343 : B2DPolygon aFlipped(aCandidate);
66 343 : aFlipped.flip();
67 343 : aRetval.setB2DPolygon(a, aFlipped);
68 : }
69 364 : }
70 :
71 352 : return aRetval;
72 : }
73 :
74 0 : B2DPolyPolygon correctOutmostPolygon(const B2DPolyPolygon& rCandidate)
75 : {
76 0 : const sal_uInt32 nCount(rCandidate.count());
77 :
78 0 : 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 0 : 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 5 : B2DPolyPolygon adaptiveSubdivideByAngle(const B2DPolyPolygon& rCandidate, double fAngleBound)
148 : {
149 5 : 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 0 : 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 256 : bool isInside(const B2DPolyPolygon& rCandidate, const B2DPoint& rPoint, bool bWithBorder)
206 : {
207 256 : const sal_uInt32 nPolygonCount(rCandidate.count());
208 :
209 256 : if(1L == nPolygonCount)
210 : {
211 256 : 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 80811 : B2DRange getRange(const B2DPolyPolygon& rCandidate)
233 : {
234 80811 : B2DRange aRetval;
235 80811 : const sal_uInt32 nPolygonCount(rCandidate.count());
236 :
237 162801 : for(sal_uInt32 a(0L); a < nPolygonCount; a++)
238 : {
239 81990 : B2DPolygon aCandidate = rCandidate.getB2DPolygon(a);
240 81990 : aRetval.expand(tools::getRange(aCandidate));
241 81990 : }
242 :
243 80811 : return aRetval;
244 : }
245 :
246 0 : void applyLineDashing(const B2DPolyPolygon& rCandidate, const ::std::vector<double>& rDotDashArray, B2DPolyPolygon* pLineTarget, B2DPolyPolygon* pGapTarget, double fFullDashDotLen)
247 : {
248 0 : if(0.0 == fFullDashDotLen && rDotDashArray.size())
249 : {
250 : // calculate fFullDashDotLen from rDotDashArray
251 0 : fFullDashDotLen = ::std::accumulate(rDotDashArray.begin(), rDotDashArray.end(), 0.0);
252 : }
253 :
254 0 : if(rCandidate.count() && fFullDashDotLen > 0.0)
255 : {
256 0 : B2DPolyPolygon aLineTarget, aGapTarget;
257 :
258 0 : for(sal_uInt32 a(0L); a < rCandidate.count(); a++)
259 : {
260 0 : const B2DPolygon aCandidate(rCandidate.getB2DPolygon(a));
261 :
262 : applyLineDashing(
263 : aCandidate,
264 : rDotDashArray,
265 : pLineTarget ? &aLineTarget : 0,
266 : pGapTarget ? &aGapTarget : 0,
267 0 : fFullDashDotLen);
268 :
269 0 : if(pLineTarget)
270 : {
271 0 : pLineTarget->append(aLineTarget);
272 : }
273 :
274 0 : if(pGapTarget)
275 : {
276 0 : pGapTarget->append(aGapTarget);
277 : }
278 0 : }
279 : }
280 0 : }
281 :
282 0 : bool isInEpsilonRange(const B2DPolyPolygon& rCandidate, const B2DPoint& rTestPosition, double fDistance)
283 : {
284 0 : const sal_uInt32 nPolygonCount(rCandidate.count());
285 :
286 0 : for(sal_uInt32 a(0L); a < nPolygonCount; a++)
287 : {
288 0 : B2DPolygon aCandidate(rCandidate.getB2DPolygon(a));
289 :
290 0 : if(isInEpsilonRange(aCandidate, rTestPosition, fDistance))
291 : {
292 0 : return true;
293 : }
294 0 : }
295 :
296 0 : return false;
297 : }
298 :
299 0 : B3DPolyPolygon createB3DPolyPolygonFromB2DPolyPolygon(const B2DPolyPolygon& rCandidate, double fZCoordinate)
300 : {
301 0 : const sal_uInt32 nPolygonCount(rCandidate.count());
302 0 : B3DPolyPolygon aRetval;
303 :
304 0 : for(sal_uInt32 a(0L); a < nPolygonCount; a++)
305 : {
306 0 : B2DPolygon aCandidate(rCandidate.getB2DPolygon(a));
307 :
308 0 : aRetval.append(createB3DPolygonFromB2DPolygon(aCandidate, fZCoordinate));
309 0 : }
310 :
311 0 : return aRetval;
312 : }
313 :
314 0 : B2DPolyPolygon createB2DPolyPolygonFromB3DPolyPolygon(const B3DPolyPolygon& rCandidate, const B3DHomMatrix& rMat)
315 : {
316 0 : const sal_uInt32 nPolygonCount(rCandidate.count());
317 0 : B2DPolyPolygon aRetval;
318 :
319 0 : for(sal_uInt32 a(0L); a < nPolygonCount; a++)
320 : {
321 0 : B3DPolygon aCandidate(rCandidate.getB3DPolygon(a));
322 :
323 0 : aRetval.append(createB2DPolygonFromB3DPolygon(aCandidate, rMat));
324 0 : }
325 :
326 0 : return aRetval;
327 : }
328 :
329 0 : double getSmallestDistancePointToPolyPolygon(const B2DPolyPolygon& rCandidate, const B2DPoint& rTestPoint, sal_uInt32& rPolygonIndex, sal_uInt32& rEdgeIndex, double& rCut)
330 : {
331 0 : double fRetval(DBL_MAX);
332 0 : const double fZero(0.0);
333 0 : const sal_uInt32 nPolygonCount(rCandidate.count());
334 :
335 0 : for(sal_uInt32 a(0L); a < nPolygonCount; a++)
336 : {
337 0 : const B2DPolygon aCandidate(rCandidate.getB2DPolygon(a));
338 : sal_uInt32 nNewEdgeIndex;
339 : double fNewCut;
340 0 : const double fNewDistance(getSmallestDistancePointToPolygon(aCandidate, rTestPoint, nNewEdgeIndex, fNewCut));
341 :
342 0 : if(DBL_MAX == fRetval || fNewDistance < fRetval)
343 : {
344 0 : fRetval = fNewDistance;
345 0 : rPolygonIndex = a;
346 0 : rEdgeIndex = nNewEdgeIndex;
347 0 : rCut = fNewCut;
348 :
349 0 : if(fTools::equal(fRetval, fZero))
350 : {
351 : // already found zero distance, cannot get better. Ensure numerical zero value and end loop.
352 0 : fRetval = 0.0;
353 : break;
354 : }
355 : }
356 0 : }
357 :
358 0 : return fRetval;
359 : }
360 :
361 0 : B2DPolyPolygon distort(const B2DPolyPolygon& rCandidate, const B2DRange& rOriginal, const B2DPoint& rTopLeft, const B2DPoint& rTopRight, const B2DPoint& rBottomLeft, const B2DPoint& rBottomRight)
362 : {
363 0 : const sal_uInt32 nPolygonCount(rCandidate.count());
364 0 : B2DPolyPolygon aRetval;
365 :
366 0 : for(sal_uInt32 a(0L); a < nPolygonCount; a++)
367 : {
368 0 : const B2DPolygon aCandidate(rCandidate.getB2DPolygon(a));
369 :
370 0 : aRetval.append(distort(aCandidate, rOriginal, rTopLeft, rTopRight, rBottomLeft, rBottomRight));
371 0 : }
372 :
373 0 : return aRetval;
374 : }
375 :
376 0 : B2DPolyPolygon expandToCurve(const B2DPolyPolygon& rCandidate)
377 : {
378 0 : const sal_uInt32 nPolygonCount(rCandidate.count());
379 0 : B2DPolyPolygon aRetval;
380 :
381 0 : for(sal_uInt32 a(0L); a < nPolygonCount; a++)
382 : {
383 0 : const B2DPolygon aCandidate(rCandidate.getB2DPolygon(a));
384 :
385 0 : aRetval.append(expandToCurve(aCandidate));
386 0 : }
387 :
388 0 : return aRetval;
389 : }
390 :
391 0 : B2DPolyPolygon growInNormalDirection(const B2DPolyPolygon& rCandidate, double fValue)
392 : {
393 0 : if(0.0 != fValue)
394 : {
395 0 : B2DPolyPolygon aRetval;
396 :
397 0 : for(sal_uInt32 a(0L); a < rCandidate.count(); a++)
398 : {
399 0 : aRetval.append(growInNormalDirection(rCandidate.getB2DPolygon(a), fValue));
400 : }
401 :
402 0 : return aRetval;
403 : }
404 : else
405 : {
406 0 : return rCandidate;
407 : }
408 : }
409 :
410 0 : void correctGrowShrinkPolygonPair(SAL_UNUSED_PARAMETER B2DPolyPolygon& /*rOriginal*/, SAL_UNUSED_PARAMETER B2DPolyPolygon& /*rGrown*/)
411 : {
412 : //TODO!
413 0 : }
414 :
415 0 : B2DPolyPolygon reSegmentPolyPolygon(const B2DPolyPolygon& rCandidate, sal_uInt32 nSegments)
416 : {
417 0 : B2DPolyPolygon aRetval;
418 :
419 0 : for(sal_uInt32 a(0L); a < rCandidate.count(); a++)
420 : {
421 0 : aRetval.append(reSegmentPolygon(rCandidate.getB2DPolygon(a), nSegments));
422 : }
423 :
424 0 : return aRetval;
425 : }
426 :
427 0 : B2DPolyPolygon interpolate(const B2DPolyPolygon& rOld1, const B2DPolyPolygon& rOld2, double t)
428 : {
429 : OSL_ENSURE(rOld1.count() == rOld2.count(), "B2DPolyPolygon interpolate: Different geometry (!)");
430 0 : B2DPolyPolygon aRetval;
431 :
432 0 : for(sal_uInt32 a(0L); a < rOld1.count(); a++)
433 : {
434 0 : aRetval.append(interpolate(rOld1.getB2DPolygon(a), rOld2.getB2DPolygon(a), t));
435 : }
436 :
437 0 : return aRetval;
438 : }
439 :
440 8 : bool isRectangle( const B2DPolyPolygon& rPoly )
441 : {
442 : // exclude some cheap cases first
443 8 : if( rPoly.count() != 1 )
444 0 : return false;
445 :
446 8 : return isRectangle( rPoly.getB2DPolygon(0) );
447 : }
448 :
449 : // #i76891#
450 197 : B2DPolyPolygon simplifyCurveSegments(const B2DPolyPolygon& rCandidate)
451 : {
452 197 : if(rCandidate.areControlPointsUsed())
453 : {
454 1 : B2DPolyPolygon aRetval;
455 :
456 3 : for(sal_uInt32 a(0L); a < rCandidate.count(); a++)
457 : {
458 2 : aRetval.append(simplifyCurveSegments(rCandidate.getB2DPolygon(a)));
459 : }
460 :
461 1 : return aRetval;
462 : }
463 : else
464 : {
465 196 : return rCandidate;
466 : }
467 : }
468 :
469 0 : B2DPolyPolygon snapPointsOfHorizontalOrVerticalEdges(const B2DPolyPolygon& rCandidate)
470 : {
471 0 : B2DPolyPolygon aRetval;
472 :
473 0 : for(sal_uInt32 a(0L); a < rCandidate.count(); a++)
474 : {
475 0 : aRetval.append(snapPointsOfHorizontalOrVerticalEdges(rCandidate.getB2DPolygon(a)));
476 : }
477 :
478 0 : return aRetval;
479 : }
480 :
481 : } // end of namespace tools
482 : } // end of namespace basegfx
483 :
484 : /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
|
