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