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 <osl/diagnose.h>
30 : : #include <basegfx/numeric/ftools.hxx>
31 : : #include <basegfx/polygon/b2dpolypolygoncutter.hxx>
32 : : #include <basegfx/point/b2dpoint.hxx>
33 : : #include <basegfx/vector/b2dvector.hxx>
34 : : #include <basegfx/polygon/b2dpolygon.hxx>
35 : : #include <basegfx/polygon/b2dpolygontools.hxx>
36 : : #include <basegfx/polygon/b2dpolygoncutandtouch.hxx>
37 : : #include <basegfx/range/b2drange.hxx>
38 : : #include <basegfx/polygon/b2dpolypolygontools.hxx>
39 : : #include <basegfx/curve/b2dcubicbezier.hxx>
40 : : #include <vector>
41 : : #include <algorithm>
42 : :
43 : : //////////////////////////////////////////////////////////////////////////////
44 : :
45 : : namespace basegfx
46 : : {
47 : : namespace
48 : : {
49 : : //////////////////////////////////////////////////////////////////////////////
50 : :
51 : 2119 : struct StripHelper
52 : : {
53 : : B2DRange maRange;
54 : : sal_Int32 mnDepth;
55 : : B2VectorOrientation meOrinetation;
56 : : };
57 : :
58 : : //////////////////////////////////////////////////////////////////////////////
59 : :
60 : 36646 : struct PN
61 : : {
62 : : public:
63 : : B2DPoint maPoint;
64 : : sal_uInt32 mnI;
65 : : sal_uInt32 mnIP;
66 : : sal_uInt32 mnIN;
67 : : };
68 : :
69 : : //////////////////////////////////////////////////////////////////////////////
70 : :
71 : 4806 : struct VN
72 : : {
73 : : public:
74 : : B2DVector maPrev;
75 : : B2DVector maNext;
76 : :
77 : : // to have the correct curve segments in the crossover checks,
78 : : // it is necessary to keep the original next vectors, too. Else,
79 : : // it may happen to use a already switched next vector which
80 : : // would interpolate the wrong comparison point
81 : : B2DVector maOriginalNext;
82 : : };
83 : :
84 : : //////////////////////////////////////////////////////////////////////////////
85 : :
86 : : struct SN
87 : : {
88 : : public:
89 : : PN* mpPN;
90 : :
91 : 72293 : bool operator<(const SN& rComp) const
92 : : {
93 [ + + ]: 72293 : if(fTools::equal(mpPN->maPoint.getX(), rComp.mpPN->maPoint.getX()))
94 : : {
95 [ + + ]: 18401 : if(fTools::equal(mpPN->maPoint.getY(), rComp.mpPN->maPoint.getY()))
96 : : {
97 : 4175 : return (mpPN->mnI < rComp.mpPN->mnI);
98 : : }
99 : : else
100 : : {
101 : 14226 : return fTools::less(mpPN->maPoint.getY(), rComp.mpPN->maPoint.getY());
102 : : }
103 : : }
104 : : else
105 : : {
106 : 72293 : return fTools::less(mpPN->maPoint.getX(), rComp.mpPN->maPoint.getX());
107 : : }
108 : : }
109 : : };
110 : :
111 : : //////////////////////////////////////////////////////////////////////////////
112 : :
113 : : typedef ::std::vector< PN > PNV;
114 : : typedef ::std::vector< VN > VNV;
115 : : typedef ::std::vector< SN > SNV;
116 : :
117 : : //////////////////////////////////////////////////////////////////////////////
118 : :
119 : 1156 : class solver
120 : : {
121 : : private:
122 : : const B2DPolyPolygon maOriginal;
123 : : PNV maPNV;
124 : : VNV maVNV;
125 : : SNV maSNV;
126 : :
127 : : unsigned mbIsCurve : 1;
128 : : unsigned mbChanged : 1;
129 : :
130 : 2333 : void impAddPolygon(const sal_uInt32 aPos, const B2DPolygon& rGeometry)
131 : : {
132 [ + - ]: 2333 : const sal_uInt32 nCount(rGeometry.count());
133 : 2333 : PN aNewPN;
134 : 2333 : VN aNewVN;
135 : : SN aNewSN;
136 : :
137 [ + + ]: 18323 : for(sal_uInt32 a(0); a < nCount; a++)
138 : : {
139 [ + - ]: 15990 : const B2DPoint aPoint(rGeometry.getB2DPoint(a));
140 : 15990 : aNewPN.maPoint = aPoint;
141 : 15990 : aNewPN.mnI = aPos + a;
142 [ + + ]: 15990 : aNewPN.mnIP = aPos + ((a != 0) ? a - 1 : nCount - 1);
143 [ + + ]: 15990 : aNewPN.mnIN = aPos + ((a + 1 == nCount) ? 0 : a + 1);
144 [ + - ]: 15990 : maPNV.push_back(aNewPN);
145 : :
146 [ + + ]: 15990 : if(mbIsCurve)
147 : : {
148 [ + - ][ + - ]: 70 : aNewVN.maPrev = rGeometry.getPrevControlPoint(a) - aPoint;
149 [ + - ][ + - ]: 70 : aNewVN.maNext = rGeometry.getNextControlPoint(a) - aPoint;
150 [ + - ]: 70 : aNewVN.maOriginalNext = aNewVN.maNext;
151 [ + - ]: 70 : maVNV.push_back(aNewVN);
152 : : }
153 : :
154 : 15990 : aNewSN.mpPN = &maPNV[maPNV.size() - 1];
155 [ + - ]: 15990 : maSNV.push_back(aNewSN);
156 : 18323 : }
157 : 2333 : }
158 : :
159 : 4714 : bool impLeftOfEdges(const B2DVector& rVecA, const B2DVector& rVecB, const B2DVector& rTest)
160 : : {
161 : : // tests if rTest is left of both directed line segments along the line -rVecA, rVecB. Test is
162 : : // with border.
163 [ + + ]: 4714 : if(rVecA.cross(rVecB) > 0.0)
164 : : {
165 : : // b is left turn seen from a, test if Test is left of both and so inside (left is seeen as inside)
166 [ + - ]: 1410 : const bool bBoolA(fTools::moreOrEqual(rVecA.cross(rTest), 0.0));
167 [ + - ]: 1410 : const bool bBoolB(fTools::lessOrEqual(rVecB.cross(rTest), 0.0));
168 : :
169 [ + + ][ + + ]: 1410 : return (bBoolA && bBoolB);
170 : : }
171 : : else
172 : : {
173 : : // b is right turn seen from a, test if Test is right of both and so outside (left is seeen as inside)
174 [ + - ]: 3304 : const bool bBoolA(fTools::lessOrEqual(rVecA.cross(rTest), 0.0));
175 [ + - ]: 3304 : const bool bBoolB(fTools::moreOrEqual(rVecB.cross(rTest), 0.0));
176 : :
177 [ + + ][ + + ]: 4714 : return (!(bBoolA && bBoolB));
178 : : }
179 : : }
180 : :
181 : 2237 : void impSwitchNext(PN& rPNa, PN& rPNb)
182 : : {
183 : 2237 : ::std::swap(rPNa.mnIN, rPNb.mnIN);
184 : :
185 [ + + ]: 2237 : if(mbIsCurve)
186 : : {
187 : 5 : VN& rVNa = maVNV[rPNa.mnI];
188 : 5 : VN& rVNb = maVNV[rPNb.mnI];
189 : :
190 : 5 : ::std::swap(rVNa.maNext, rVNb.maNext);
191 : : }
192 : :
193 [ + + ]: 2237 : if(!mbChanged)
194 : : {
195 : 641 : mbChanged = true;
196 : : }
197 : 2237 : }
198 : :
199 : 210 : B2DCubicBezier createSegment(const PN& rPN, bool bPrev) const
200 : : {
201 : 210 : const B2DPoint& rStart(rPN.maPoint);
202 [ + + ]: 210 : const B2DPoint& rEnd(maPNV[bPrev ? rPN.mnIP : rPN.mnIN].maPoint);
203 [ + + ]: 210 : const B2DVector& rCPA(bPrev ? maVNV[rPN.mnI].maPrev : maVNV[rPN.mnI].maNext);
204 : : // Use maOriginalNext, not maNext to create the original (yet unchanged)
205 : : // curve segment. Otherwise, this segment would NOT ne correct.
206 [ + + ]: 210 : const B2DVector& rCPB(bPrev ? maVNV[maPNV[rPN.mnIP].mnI].maOriginalNext : maVNV[maPNV[rPN.mnIN].mnI].maPrev);
207 : :
208 [ + - ]: 210 : return B2DCubicBezier(rStart, rStart + rCPA, rEnd + rCPB, rEnd);
209 : : }
210 : :
211 : 3331 : void impHandleCommon(PN& rPNa, PN& rPNb)
212 : : {
213 [ + + ]: 3331 : if(mbIsCurve)
214 : : {
215 [ + - ]: 40 : const B2DCubicBezier aNextA(createSegment(rPNa, false));
216 [ + - ]: 40 : const B2DCubicBezier aPrevA(createSegment(rPNa, true));
217 : :
218 [ + - ][ - + ]: 40 : if(aNextA.equal(aPrevA))
219 : : {
220 : : // deadend on A (identical edge)
221 : : return;
222 : : }
223 : :
224 [ + - ]: 40 : const B2DCubicBezier aNextB(createSegment(rPNb, false));
225 [ + - ]: 40 : const B2DCubicBezier aPrevB(createSegment(rPNb, true));
226 : :
227 [ + - ][ - + ]: 40 : if(aNextB.equal(aPrevB))
228 : : {
229 : : // deadend on B (identical edge)
230 : : return;
231 : : }
232 : :
233 [ + - ][ + + ]: 40 : if(aPrevA.equal(aPrevB))
234 : : {
235 : : // common edge in same direction
236 : : return;
237 : : }
238 [ + - ][ + + ]: 10 : else if(aPrevA.equal(aNextB))
239 : : {
240 : : // common edge in opposite direction
241 [ + - ][ - + ]: 5 : if(aNextA.equal(aPrevB))
242 : : {
243 : : // common edge in opposite direction continues
244 : : return;
245 : : }
246 : : else
247 : : {
248 : : // common edge in opposite direction leave
249 [ + - ]: 5 : impSwitchNext(rPNa, rPNb);
250 : : }
251 : : }
252 [ + - ][ + - ]: 5 : else if(aNextA.equal(aNextB))
253 : : {
254 : : // common edge in same direction enter
255 : : // search leave edge
256 : 5 : PN* pPNa2 = &maPNV[rPNa.mnIN];
257 : 5 : PN* pPNb2 = &maPNV[rPNb.mnIN];
258 : 5 : bool bOnEdge(true);
259 : :
260 [ + - ][ + + ]: 25 : do
[ + - ][ + + ]
261 : : {
262 [ + - ]: 25 : const B2DCubicBezier aNextA2(createSegment(*pPNa2, false));
263 [ + - ]: 25 : const B2DCubicBezier aNextB2(createSegment(*pPNb2, false));
264 : :
265 [ + - ][ + - ]: 25 : if(aNextA2.equal(aNextB2))
266 : : {
267 : 25 : pPNa2 = &maPNV[pPNa2->mnIN];
268 : 25 : pPNb2 = &maPNV[pPNb2->mnIN];
269 : : }
270 : : else
271 : : {
272 : 0 : bOnEdge = false;
273 [ + - ][ + - ]: 25 : }
274 : : }
275 : : while(bOnEdge && pPNa2 != &rPNa && pPNb2 != &rPNb);
276 : :
277 [ + - ]: 5 : if(bOnEdge)
278 : : {
279 : : // loop over two identical polygon paths
280 : : return;
281 : : }
282 : : else
283 : : {
284 : : // enter at rPNa, rPNb; leave at pPNa2, pPNb2. No common edges
285 : : // at enter/leave. Check for crossover.
286 [ # # ]: 0 : const B2DVector aPrevCA(aPrevA.interpolatePoint(0.5) - aPrevA.getStartPoint());
287 [ # # ]: 0 : const B2DVector aNextCA(aNextA.interpolatePoint(0.5) - aNextA.getStartPoint());
288 [ # # ]: 0 : const B2DVector aPrevCB(aPrevB.interpolatePoint(0.5) - aPrevB.getStartPoint());
289 [ # # ]: 0 : const bool bEnter(impLeftOfEdges(aPrevCA, aNextCA, aPrevCB));
290 : :
291 [ # # ]: 0 : const B2DCubicBezier aNextA2(createSegment(*pPNa2, false));
292 [ # # ]: 0 : const B2DCubicBezier aPrevA2(createSegment(*pPNa2, true));
293 [ # # ]: 0 : const B2DCubicBezier aNextB2(createSegment(*pPNb2, false));
294 [ # # ]: 0 : const B2DVector aPrevCA2(aPrevA2.interpolatePoint(0.5) - aPrevA2.getStartPoint());
295 [ # # ]: 0 : const B2DVector aNextCA2(aNextA2.interpolatePoint(0.5) - aNextA2.getStartPoint());
296 [ # # ]: 0 : const B2DVector aNextCB2(aNextB2.interpolatePoint(0.5) - aNextB2.getStartPoint());
297 [ # # ]: 0 : const bool bLeave(impLeftOfEdges(aPrevCA2, aNextCA2, aNextCB2));
298 : :
299 [ # # ]: 0 : if(bEnter != bLeave)
300 : : {
301 : : // crossover
302 [ # # ]: 0 : impSwitchNext(rPNa, rPNb);
303 [ # # ][ # # ]: 0 : }
[ # # ]
304 : : }
305 : : }
306 [ # # ][ # # ]: 0 : else if(aNextA.equal(aPrevB))
307 : : {
308 : : // common edge in opposite direction enter
309 [ # # ]: 0 : impSwitchNext(rPNa, rPNb);
310 : : }
311 : : else
312 : : {
313 : : // no common edges, check for crossover
314 [ # # ]: 0 : const B2DVector aPrevCA(aPrevA.interpolatePoint(0.5) - aPrevA.getStartPoint());
315 [ # # ]: 0 : const B2DVector aNextCA(aNextA.interpolatePoint(0.5) - aNextA.getStartPoint());
316 [ # # ]: 0 : const B2DVector aPrevCB(aPrevB.interpolatePoint(0.5) - aPrevB.getStartPoint());
317 [ # # ]: 0 : const B2DVector aNextCB(aNextB.interpolatePoint(0.5) - aNextB.getStartPoint());
318 : :
319 [ # # ]: 0 : const bool bEnter(impLeftOfEdges(aPrevCA, aNextCA, aPrevCB));
320 [ # # ]: 0 : const bool bLeave(impLeftOfEdges(aPrevCA, aNextCA, aNextCB));
321 : :
322 [ # # ]: 0 : if(bEnter != bLeave)
323 : : {
324 : : // crossover
325 [ # # ]: 0 : impSwitchNext(rPNa, rPNb);
326 : 5 : }
327 [ + - ][ + + ]: 40 : }
[ + - ][ + + ]
[ + - ][ + + ]
[ + - ][ + + ]
328 : : }
329 : : else
330 : : {
331 : 3291 : const B2DPoint& rNextA(maPNV[rPNa.mnIN].maPoint);
332 : 3291 : const B2DPoint& rPrevA(maPNV[rPNa.mnIP].maPoint);
333 : :
334 [ - + ]: 3291 : if(rNextA.equal(rPrevA))
335 : : {
336 : : // deadend on A
337 : 0 : return;
338 : : }
339 : :
340 : 3291 : const B2DPoint& rNextB(maPNV[rPNb.mnIN].maPoint);
341 : 3291 : const B2DPoint& rPrevB(maPNV[rPNb.mnIP].maPoint);
342 : :
343 [ - + ]: 3291 : if(rNextB.equal(rPrevB))
344 : : {
345 : : // deadend on B
346 : 0 : return;
347 : : }
348 : :
349 [ + + ]: 3291 : if(rPrevA.equal(rPrevB))
350 : : {
351 : : // common edge in same direction
352 : 879 : return;
353 : : }
354 [ + + ]: 2412 : else if(rPrevA.equal(rNextB))
355 : : {
356 : : // common edge in opposite direction
357 [ + + ]: 40 : if(rNextA.equal(rPrevB))
358 : : {
359 : : // common edge in opposite direction continues
360 : 25 : return;
361 : : }
362 : : else
363 : : {
364 : : // common edge in opposite direction leave
365 : 15 : impSwitchNext(rPNa, rPNb);
366 : : }
367 : : }
368 [ + + ]: 2372 : else if(rNextA.equal(rNextB))
369 : : {
370 : : // common edge in same direction enter
371 : : // search leave edge
372 : 178 : PN* pPNa2 = &maPNV[rPNa.mnIN];
373 : 178 : PN* pPNb2 = &maPNV[rPNb.mnIN];
374 : 178 : bool bOnEdge(true);
375 : :
376 [ + + ][ + + ]: 262 : do
[ + - ][ + + ]
377 : : {
378 : 262 : const B2DPoint& rNextA2(maPNV[pPNa2->mnIN].maPoint);
379 : 262 : const B2DPoint& rNextB2(maPNV[pPNb2->mnIN].maPoint);
380 : :
381 [ + + ]: 262 : if(rNextA2.equal(rNextB2))
382 : : {
383 : 89 : pPNa2 = &maPNV[pPNa2->mnIN];
384 : 89 : pPNb2 = &maPNV[pPNb2->mnIN];
385 : : }
386 : : else
387 : : {
388 : 173 : bOnEdge = false;
389 : : }
390 : : }
391 : : while(bOnEdge && pPNa2 != &rPNa && pPNb2 != &rPNb);
392 : :
393 [ + + ]: 178 : if(bOnEdge)
394 : : {
395 : : // loop over two identical polygon paths
396 : 5 : return;
397 : : }
398 : : else
399 : : {
400 : : // enter at rPNa, rPNb; leave at pPNa2, pPNb2. No common edges
401 : : // at enter/leave. Check for crossover.
402 : 173 : const B2DPoint& aPointE(rPNa.maPoint);
403 : 173 : const B2DVector aPrevAE(rPrevA - aPointE);
404 : 173 : const B2DVector aNextAE(rNextA - aPointE);
405 : 173 : const B2DVector aPrevBE(rPrevB - aPointE);
406 : :
407 : 173 : const B2DPoint& aPointL(pPNa2->maPoint);
408 : 173 : const B2DVector aPrevAL(maPNV[pPNa2->mnIP].maPoint - aPointL);
409 : 173 : const B2DVector aNextAL(maPNV[pPNa2->mnIN].maPoint - aPointL);
410 : 173 : const B2DVector aNextBL(maPNV[pPNb2->mnIN].maPoint - aPointL);
411 : :
412 [ + - ]: 173 : const bool bEnter(impLeftOfEdges(aPrevAE, aNextAE, aPrevBE));
413 [ + - ]: 173 : const bool bLeave(impLeftOfEdges(aPrevAL, aNextAL, aNextBL));
414 : :
415 [ + + ]: 173 : if(bEnter != bLeave)
416 : : {
417 : : // crossover; switch start or end
418 [ + - ]: 76 : impSwitchNext(rPNa, rPNb);
419 : 173 : }
420 : : }
421 : : }
422 [ + + ]: 2194 : else if(rNextA.equal(rPrevB))
423 : : {
424 : : // common edge in opposite direction enter
425 : 10 : impSwitchNext(rPNa, rPNb);
426 : : }
427 : : else
428 : : {
429 : : // no common edges, check for crossover
430 : 2184 : const B2DPoint& aPoint(rPNa.maPoint);
431 : 2184 : const B2DVector aPrevA(rPrevA - aPoint);
432 : 2184 : const B2DVector aNextA(rNextA - aPoint);
433 : 2184 : const B2DVector aPrevB(rPrevB - aPoint);
434 : 2184 : const B2DVector aNextB(rNextB - aPoint);
435 : :
436 [ + - ]: 2184 : const bool bEnter(impLeftOfEdges(aPrevA, aNextA, aPrevB));
437 [ + - ]: 2184 : const bool bLeave(impLeftOfEdges(aPrevA, aNextA, aNextB));
438 : :
439 [ + + ]: 2184 : if(bEnter != bLeave)
440 : : {
441 : : // crossover
442 [ + - ]: 2131 : impSwitchNext(rPNa, rPNb);
443 : 3331 : }
444 : : }
445 : : }
446 : : }
447 : :
448 : 1156 : void impSolve()
449 : : {
450 : : // sort by point to identify common nodes
451 : 1156 : ::std::sort(maSNV.begin(), maSNV.end());
452 : :
453 : : // handle common nodes
454 : 1156 : const sal_uInt32 nNodeCount(maSNV.size());
455 : :
456 [ + + ]: 15990 : for(sal_uInt32 a(0); a < nNodeCount - 1; a++)
457 : : {
458 : : // test a before using it, not after. Also use nPointCount instead of aSortNodes.size()
459 : 14834 : PN& rPNb = *(maSNV[a].mpPN);
460 : :
461 [ + + ][ + + ]: 18165 : for(sal_uInt32 b(a + 1); b < nNodeCount && rPNb.maPoint.equal(maSNV[b].mpPN->maPoint); b++)
[ + + ]
462 : : {
463 : 3331 : impHandleCommon(rPNb, *maSNV[b].mpPN);
464 : : }
465 : : }
466 : 1156 : }
467 : :
468 : : public:
469 : 40 : explicit solver(const B2DPolygon& rOriginal)
470 : : : maOriginal(B2DPolyPolygon(rOriginal)),
471 : : mbIsCurve(false),
472 [ + - ][ + - ]: 40 : mbChanged(false)
[ + - ]
473 : : {
474 [ + - ]: 40 : const sal_uInt32 nOriginalCount(rOriginal.count());
475 : :
476 [ + - ]: 40 : if(nOriginalCount)
477 : : {
478 [ + - ]: 40 : B2DPolygon aGeometry(tools::addPointsAtCutsAndTouches(rOriginal));
479 [ + - ]: 40 : aGeometry.removeDoublePoints();
480 [ + - ][ + - ]: 40 : aGeometry = tools::simplifyCurveSegments(aGeometry);
[ + - ]
481 [ + - ]: 40 : mbIsCurve = aGeometry.areControlPointsUsed();
482 : :
483 [ + - ]: 40 : const sal_uInt32 nPointCount(aGeometry.count());
484 : :
485 : : // If it's not a pezier polygon, at least four points are needed to create
486 : : // a self-intersection. If it's a bezier polygon, the minimum point number
487 : : // is two, since with a single point You get a curve, but no self-intersection
488 [ - + ][ # # ]: 40 : if(nPointCount > 3 || (nPointCount > 1 && mbIsCurve))
[ # # ]
489 : : {
490 : : // reserve space in point, control and sort vector.
491 [ + - ]: 40 : maSNV.reserve(nPointCount);
492 [ + - ]: 40 : maPNV.reserve(nPointCount);
493 [ - + ][ + - ]: 40 : maVNV.reserve(mbIsCurve ? nPointCount : 0);
494 : :
495 : : // fill data
496 [ + - ]: 40 : impAddPolygon(0, aGeometry);
497 : :
498 : : // solve common nodes
499 [ + - ]: 40 : impSolve();
500 [ + - ]: 40 : }
501 : : }
502 : 40 : }
503 : :
504 : 1116 : explicit solver(const B2DPolyPolygon& rOriginal)
505 : : : maOriginal(rOriginal),
506 : : mbIsCurve(false),
507 [ + - ][ + - ]: 1116 : mbChanged(false)
[ + - ]
508 : : {
509 [ + - ]: 1116 : sal_uInt32 nOriginalCount(maOriginal.count());
510 : :
511 [ + - ]: 1116 : if(nOriginalCount)
512 : : {
513 [ + - ]: 1116 : B2DPolyPolygon aGeometry(tools::addPointsAtCutsAndTouches(maOriginal, true));
514 [ + - ]: 1116 : aGeometry.removeDoublePoints();
515 [ + - ][ + - ]: 1116 : aGeometry = tools::simplifyCurveSegments(aGeometry);
[ + - ]
516 [ + - ]: 1116 : mbIsCurve = aGeometry.areControlPointsUsed();
517 [ + - ]: 1116 : nOriginalCount = aGeometry.count();
518 : :
519 [ + - ]: 1116 : if(nOriginalCount)
520 : : {
521 : 1116 : sal_uInt32 nPointCount(0);
522 : 1116 : sal_uInt32 a(0);
523 : :
524 : : // count points
525 [ + + ]: 3409 : for(a = 0; a < nOriginalCount; a++)
526 : : {
527 [ + - ]: 2293 : const B2DPolygon aCandidate(aGeometry.getB2DPolygon(a));
528 [ + - ]: 2293 : const sal_uInt32 nCandCount(aCandidate.count());
529 : :
530 : : // If it's not a bezier curve, at least three points would be needed to have a
531 : : // topological relevant (not empty) polygon. Since its not known here if trivial
532 : : // edges (dead ends) will be kept or sorted out, add non-bezier polygons with
533 : : // more than one point.
534 : : // For bezier curves, the minimum for defining an area is also one.
535 [ + - ]: 2293 : if(nCandCount)
536 : : {
537 : 2293 : nPointCount += nCandCount;
538 : : }
539 [ + - ]: 2293 : }
540 : :
541 [ + - ]: 1116 : if(nPointCount)
542 : : {
543 : : // reserve space in point, control and sort vector.
544 [ + - ]: 1116 : maSNV.reserve(nPointCount);
545 [ + - ]: 1116 : maPNV.reserve(nPointCount);
546 [ + + ][ + - ]: 1116 : maVNV.reserve(mbIsCurve ? nPointCount : 0);
547 : :
548 : : // fill data
549 : 1116 : sal_uInt32 nInsertIndex(0);
550 : :
551 [ + + ]: 3409 : for(a = 0; a < nOriginalCount; a++)
552 : : {
553 [ + - ]: 2293 : const B2DPolygon aCandidate(aGeometry.getB2DPolygon(a));
554 [ + - ]: 2293 : const sal_uInt32 nCandCount(aCandidate.count());
555 : :
556 : : // use same condition as above, the data vector is
557 : : // pre-allocated
558 [ + - ]: 2293 : if(nCandCount)
559 : : {
560 [ + - ]: 2293 : impAddPolygon(nInsertIndex, aCandidate);
561 : 2293 : nInsertIndex += nCandCount;
562 : : }
563 [ + - ]: 2293 : }
564 : :
565 : : // solve common nodes
566 [ + - ]: 1116 : impSolve();
567 : : }
568 [ + - ]: 1116 : }
569 : : }
570 : 1116 : }
571 : :
572 : 1156 : B2DPolyPolygon getB2DPolyPolygon()
573 : : {
574 [ + + ]: 1156 : if(mbChanged)
575 : : {
576 [ + - ]: 641 : B2DPolyPolygon aRetval;
577 : 641 : const sal_uInt32 nCount(maPNV.size());
578 : 641 : sal_uInt32 nCountdown(nCount);
579 : :
580 [ + + ][ + - ]: 3612 : for(sal_uInt32 a(0); nCountdown && a < nCount; a++)
[ + + ]
581 : : {
582 : 2971 : PN& rPN = maPNV[a];
583 : :
584 [ + + ]: 2971 : if(SAL_MAX_UINT32 != rPN.mnI)
585 : : {
586 : : // unused node, start new part polygon
587 [ + - ]: 1354 : B2DPolygon aNewPart;
588 : 1354 : PN* pPNCurr = &rPN;
589 : :
590 [ + - ][ + + ]: 11068 : do
[ + + ]
591 : : {
592 : 11068 : const B2DPoint& rPoint = pPNCurr->maPoint;
593 [ + - ]: 11068 : aNewPart.append(rPoint);
594 : :
595 [ + + ]: 11068 : if(mbIsCurve)
596 : : {
597 : 70 : const VN& rVNCurr = maVNV[pPNCurr->mnI];
598 : :
599 [ + + ][ + - ]: 70 : if(!rVNCurr.maPrev.equalZero())
600 : : {
601 [ + - ][ + - ]: 10 : aNewPart.setPrevControlPoint(aNewPart.count() - 1, rPoint + rVNCurr.maPrev);
602 : : }
603 : :
604 [ + - ][ + + ]: 70 : if(!rVNCurr.maNext.equalZero())
605 : : {
606 [ + - ][ + - ]: 10 : aNewPart.setNextControlPoint(aNewPart.count() - 1, rPoint + rVNCurr.maNext);
607 : : }
608 : : }
609 : :
610 : 11068 : pPNCurr->mnI = SAL_MAX_UINT32;
611 : 11068 : nCountdown--;
612 : 11068 : pPNCurr = &(maPNV[pPNCurr->mnIN]);
613 : : }
614 : : while(pPNCurr != &rPN && SAL_MAX_UINT32 != pPNCurr->mnI);
615 : :
616 : : // close and add
617 [ + - ]: 1354 : aNewPart.setClosed(true);
618 [ + - ][ + - ]: 1354 : aRetval.append(aNewPart);
619 : : }
620 : : }
621 : :
622 [ + - ][ + - ]: 641 : return aRetval;
623 : : }
624 : : else
625 : : {
626 : : // no change, return original
627 : 1156 : return maOriginal;
628 : : }
629 : : }
630 : : };
631 : :
632 : : //////////////////////////////////////////////////////////////////////////////
633 : :
634 : : } // end of anonymous namespace
635 : : } // end of namespace basegfx
636 : :
637 : : //////////////////////////////////////////////////////////////////////////////
638 : :
639 : : namespace basegfx
640 : : {
641 : : namespace tools
642 : : {
643 : : //////////////////////////////////////////////////////////////////////////////
644 : :
645 : 2968 : B2DPolyPolygon solveCrossovers(const B2DPolyPolygon& rCandidate)
646 : : {
647 [ + + ]: 2968 : if(rCandidate.count() > 1L)
648 : : {
649 [ + - ]: 1085 : solver aSolver(rCandidate);
650 [ + - ][ + - ]: 1085 : return aSolver.getB2DPolyPolygon();
651 : : }
652 : : else
653 : : {
654 : 2968 : return rCandidate;
655 : : }
656 : : }
657 : :
658 : : //////////////////////////////////////////////////////////////////////////////
659 : :
660 : 3274 : B2DPolyPolygon stripNeutralPolygons(const B2DPolyPolygon& rCandidate)
661 : : {
662 : 3274 : B2DPolyPolygon aRetval;
663 : :
664 [ + - ][ + + ]: 8690 : for(sal_uInt32 a(0L); a < rCandidate.count(); a++)
665 : : {
666 [ + - ]: 5416 : const B2DPolygon aCandidate(rCandidate.getB2DPolygon(a));
667 : :
668 [ + - ][ + + ]: 5416 : if(ORIENTATION_NEUTRAL != tools::getOrientation(aCandidate))
669 : : {
670 [ + - ]: 5342 : aRetval.append(aCandidate);
671 : : }
672 [ + - ]: 5416 : }
673 : :
674 : 3274 : return aRetval;
675 : : }
676 : :
677 : : //////////////////////////////////////////////////////////////////////////////
678 : :
679 : 1008 : B2DPolyPolygon stripDispensablePolygons(const B2DPolyPolygon& rCandidate, bool bKeepAboveZero)
680 : : {
681 : 1008 : const sal_uInt32 nCount(rCandidate.count());
682 : 1008 : B2DPolyPolygon aRetval;
683 : :
684 [ + - ]: 1008 : if(nCount)
685 : : {
686 [ + + ]: 1008 : if(nCount == 1L)
687 : : {
688 [ - + ][ # # ]: 7 : if(!bKeepAboveZero && ORIENTATION_POSITIVE == tools::getOrientation(rCandidate.getB2DPolygon(0L)))
[ # # ][ # # ]
[ - + ][ # # ]
[ - + # # ]
689 : : {
690 [ # # ]: 0 : aRetval = rCandidate;
691 : : }
692 : : }
693 : : else
694 : : {
695 : : sal_uInt32 a, b;
696 [ + - ]: 1001 : ::std::vector< StripHelper > aHelpers;
697 [ + - ]: 1001 : aHelpers.resize(nCount);
698 : :
699 [ + + ]: 3120 : for(a = 0L; a < nCount; a++)
700 : : {
701 [ + - ]: 2119 : const B2DPolygon aCandidate(rCandidate.getB2DPolygon(a));
702 : 2119 : StripHelper* pNewHelper = &(aHelpers[a]);
703 [ + - ]: 2119 : pNewHelper->maRange = tools::getRange(aCandidate);
704 [ + - ]: 2119 : pNewHelper->meOrinetation = tools::getOrientation(aCandidate);
705 [ + + ]: 2119 : pNewHelper->mnDepth = (ORIENTATION_NEGATIVE == pNewHelper->meOrinetation ? -1L : 0L);
706 [ + - ]: 2119 : }
707 : :
708 [ + + ]: 2119 : for(a = 0L; a < nCount - 1L; a++)
709 : : {
710 [ + - ]: 1118 : const B2DPolygon aCandA(rCandidate.getB2DPolygon(a));
711 : 1118 : StripHelper& rHelperA = aHelpers[a];
712 : :
713 [ + + ]: 2410 : for(b = a + 1L; b < nCount; b++)
714 : : {
715 [ + - ]: 1292 : const B2DPolygon aCandB(rCandidate.getB2DPolygon(b));
716 : 1292 : StripHelper& rHelperB = aHelpers[b];
717 [ + + ][ + - ]: 1292 : const bool bAInB(rHelperB.maRange.isInside(rHelperA.maRange) && tools::isInside(aCandB, aCandA, true));
[ + - ][ + - ]
718 [ + - ][ + + ]: 1292 : const bool bBInA(rHelperA.maRange.isInside(rHelperB.maRange) && tools::isInside(aCandA, aCandB, true));
[ + - ][ + + ]
719 : :
720 [ + + ][ + + ]: 1292 : if(bAInB && bBInA)
721 : : {
722 : : // congruent
723 [ + - ]: 296 : if(rHelperA.meOrinetation == rHelperB.meOrinetation)
724 : : {
725 : : // two polys or two holes. Lower one of them to get one of them out of the way.
726 : : // Since each will be contained in the other one, both will be increased, too.
727 : : // So, for lowering, increase only one of them
728 : 148 : rHelperA.mnDepth++;
729 : : }
730 : : else
731 : : {
732 : : // poly and hole. They neutralize, so get rid of both. Move securely below zero.
733 : 0 : rHelperA.mnDepth = -((sal_Int32)nCount);
734 : 0 : rHelperB.mnDepth = -((sal_Int32)nCount);
735 : : }
736 : : }
737 : : else
738 : : {
739 [ + + ]: 1144 : if(bAInB)
740 : : {
741 [ - + ]: 79 : if(ORIENTATION_NEGATIVE == rHelperB.meOrinetation)
742 : : {
743 : 0 : rHelperA.mnDepth--;
744 : : }
745 : : else
746 : : {
747 : 79 : rHelperA.mnDepth++;
748 : : }
749 : : }
750 [ + + ]: 1065 : else if(bBInA)
751 : : {
752 [ - + ]: 816 : if(ORIENTATION_NEGATIVE == rHelperA.meOrinetation)
753 : : {
754 : 0 : rHelperB.mnDepth--;
755 : : }
756 : : else
757 : : {
758 : 816 : rHelperB.mnDepth++;
759 : : }
760 : : }
761 : : }
762 [ + - ]: 1292 : }
763 [ + - ]: 1118 : }
764 : :
765 [ + + ]: 3120 : for(a = 0L; a < nCount; a++)
766 : : {
767 : 2119 : const StripHelper& rHelper = aHelpers[a];
768 [ + + ]: 2119 : bool bAcceptEntry(bKeepAboveZero ? 1L <= rHelper.mnDepth : 0L == rHelper.mnDepth);
769 : :
770 [ + + ]: 2119 : if(bAcceptEntry)
771 : : {
772 [ + - ][ + - ]: 1056 : aRetval.append(rCandidate.getB2DPolygon(a));
[ + - ]
773 : : }
774 : 1001 : }
775 : : }
776 : : }
777 : :
778 : 1008 : return aRetval;
779 : : }
780 : :
781 : : //////////////////////////////////////////////////////////////////////////////
782 : :
783 : 40 : B2DPolyPolygon prepareForPolygonOperation(const B2DPolygon& rCandidate)
784 : : {
785 [ + - ]: 40 : solver aSolver(rCandidate);
786 [ + - ][ + - ]: 40 : B2DPolyPolygon aRetval(stripNeutralPolygons(aSolver.getB2DPolyPolygon()));
[ + - ]
787 : :
788 [ + - ][ + - ]: 40 : return correctOrientations(aRetval);
[ + - ]
789 : : }
790 : :
791 : 31 : B2DPolyPolygon prepareForPolygonOperation(const B2DPolyPolygon& rCandidate)
792 : : {
793 [ + - ]: 31 : solver aSolver(rCandidate);
794 [ + - ][ + - ]: 31 : B2DPolyPolygon aRetval(stripNeutralPolygons(aSolver.getB2DPolyPolygon()));
[ + - ]
795 : :
796 [ + - ][ + - ]: 31 : return correctOrientations(aRetval);
[ + - ]
797 : : }
798 : :
799 : 18 : B2DPolyPolygon solvePolygonOperationOr(const B2DPolyPolygon& rCandidateA, const B2DPolyPolygon& rCandidateB)
800 : : {
801 [ - + ]: 18 : if(!rCandidateA.count())
802 : : {
803 : 0 : return rCandidateB;
804 : : }
805 [ - + ]: 18 : else if(!rCandidateB.count())
806 : : {
807 : 0 : return rCandidateA;
808 : : }
809 : : else
810 : : {
811 : : // concatenate polygons, solve crossovers and throw away all sub-polygons
812 : : // which have a depth other than 0.
813 [ + - ]: 18 : B2DPolyPolygon aRetval(rCandidateA);
814 : :
815 [ + - ]: 18 : aRetval.append(rCandidateB);
816 [ + - ][ + - ]: 18 : aRetval = solveCrossovers(aRetval);
[ + - ]
817 [ + - ][ + - ]: 18 : aRetval = stripNeutralPolygons(aRetval);
[ + - ]
818 : :
819 [ + - ][ + - ]: 18 : return stripDispensablePolygons(aRetval, false);
820 : : }
821 : : }
822 : :
823 : 10 : B2DPolyPolygon solvePolygonOperationXor(const B2DPolyPolygon& rCandidateA, const B2DPolyPolygon& rCandidateB)
824 : : {
825 [ - + ]: 10 : if(!rCandidateA.count())
826 : : {
827 : 0 : return rCandidateB;
828 : : }
829 [ - + ]: 10 : else if(!rCandidateB.count())
830 : : {
831 : 0 : return rCandidateA;
832 : : }
833 : : else
834 : : {
835 : : // XOR is pretty simple: By definition it is the simple concatenation of
836 : : // the single polygons since we imply XOR fill rule. Make it intersection-free
837 : : // and correct orientations
838 [ + - ]: 10 : B2DPolyPolygon aRetval(rCandidateA);
839 : :
840 [ + - ]: 10 : aRetval.append(rCandidateB);
841 [ + - ][ + - ]: 10 : aRetval = solveCrossovers(aRetval);
[ + - ]
842 [ + - ][ + - ]: 10 : aRetval = stripNeutralPolygons(aRetval);
[ + - ]
843 : :
844 [ + - ][ + - ]: 10 : return correctOrientations(aRetval);
845 : : }
846 : : }
847 : :
848 : 5 : B2DPolyPolygon solvePolygonOperationAnd(const B2DPolyPolygon& rCandidateA, const B2DPolyPolygon& rCandidateB)
849 : : {
850 [ - + ]: 5 : if(!rCandidateA.count())
851 : : {
852 : 0 : return B2DPolyPolygon();
853 : : }
854 [ - + ]: 5 : else if(!rCandidateB.count())
855 : : {
856 : 0 : return B2DPolyPolygon();
857 : : }
858 : : else
859 : : {
860 : : // concatenate polygons, solve crossovers and throw away all sub-polygons
861 : : // with a depth of < 1. This means to keep all polygons where at least two
862 : : // polygons do overlap.
863 [ + - ]: 5 : B2DPolyPolygon aRetval(rCandidateA);
864 : :
865 [ + - ]: 5 : aRetval.append(rCandidateB);
866 [ + - ][ + - ]: 5 : aRetval = solveCrossovers(aRetval);
[ + - ]
867 [ + - ][ + - ]: 5 : aRetval = stripNeutralPolygons(aRetval);
[ + - ]
868 : :
869 [ + - ][ + - ]: 5 : return stripDispensablePolygons(aRetval, true);
870 : : }
871 : : }
872 : :
873 : 15 : B2DPolyPolygon solvePolygonOperationDiff(const B2DPolyPolygon& rCandidateA, const B2DPolyPolygon& rCandidateB)
874 : : {
875 [ - + ]: 15 : if(!rCandidateA.count())
876 : : {
877 : 0 : return B2DPolyPolygon();
878 : : }
879 [ - + ]: 15 : else if(!rCandidateB.count())
880 : : {
881 : 0 : return rCandidateA;
882 : : }
883 : : else
884 : : {
885 : : // Make B topologically to holes and append to A
886 [ + - ]: 15 : B2DPolyPolygon aRetval(rCandidateB);
887 : :
888 [ + - ]: 15 : aRetval.flip();
889 [ + - ]: 15 : aRetval.append(rCandidateA);
890 : :
891 : : // solve crossovers and throw away all sub-polygons which have a
892 : : // depth other than 0.
893 [ + - ][ + - ]: 15 : aRetval = basegfx::tools::solveCrossovers(aRetval);
[ + - ]
894 [ + - ][ + - ]: 15 : aRetval = basegfx::tools::stripNeutralPolygons(aRetval);
[ + - ]
895 : :
896 [ + - ][ + - ]: 15 : return basegfx::tools::stripDispensablePolygons(aRetval, false);
897 : : }
898 : : }
899 : :
900 : 0 : B2DPolyPolygon mergeToSinglePolyPolygon(const std::vector< basegfx::B2DPolyPolygon >& rInput)
901 : : {
902 [ # # ]: 0 : std::vector< basegfx::B2DPolyPolygon > aInput(rInput);
903 : :
904 : : // first step: prepareForPolygonOperation and simple merge of non-overlapping
905 : : // PolyPolygons for speedup; this is possible for the wanted OR-operation
906 [ # # ]: 0 : if(!aInput.empty())
907 : : {
908 [ # # ]: 0 : std::vector< basegfx::B2DPolyPolygon > aResult;
909 [ # # ]: 0 : aResult.reserve(aInput.size());
910 : :
911 [ # # ]: 0 : for(sal_uInt32 a(0); a < aInput.size(); a++)
912 : : {
913 [ # # ][ # # ]: 0 : const basegfx::B2DPolyPolygon aCandidate(prepareForPolygonOperation(aInput[a]));
914 : :
915 [ # # ]: 0 : if(!aResult.empty())
916 : : {
917 [ # # ]: 0 : const B2DRange aCandidateRange(aCandidate.getB2DRange());
918 : 0 : bool bCouldMergeSimple(false);
919 : :
920 [ # # ][ # # ]: 0 : for(sal_uInt32 b(0); !bCouldMergeSimple && b < aResult.size(); b++)
[ # # ]
921 : : {
922 [ # # ][ # # ]: 0 : basegfx::B2DPolyPolygon aTarget(aResult[b]);
923 [ # # ]: 0 : const B2DRange aTargetRange(aTarget.getB2DRange());
924 : :
925 [ # # ][ # # ]: 0 : if(!aCandidateRange.overlaps(aTargetRange))
926 : : {
927 [ # # ]: 0 : aTarget.append(aCandidate);
928 [ # # ][ # # ]: 0 : aResult[b] = aTarget;
929 : 0 : bCouldMergeSimple = true;
930 : : }
931 [ # # ]: 0 : }
932 : :
933 [ # # ]: 0 : if(!bCouldMergeSimple)
934 : : {
935 [ # # ]: 0 : aResult.push_back(aCandidate);
936 : : }
937 : : }
938 : : else
939 : : {
940 [ # # ]: 0 : aResult.push_back(aCandidate);
941 : : }
942 [ # # ]: 0 : }
943 : :
944 [ # # ]: 0 : aInput = aResult;
945 : : }
946 : :
947 : : // second step: melt pairwise to a single PolyPolygon
948 [ # # ]: 0 : while(aInput.size() > 1)
949 : : {
950 [ # # ]: 0 : std::vector< basegfx::B2DPolyPolygon > aResult;
951 [ # # ]: 0 : aResult.reserve((aInput.size() / 2) + 1);
952 : :
953 [ # # ]: 0 : for(sal_uInt32 a(0); a < aInput.size(); a += 2)
954 : : {
955 [ # # ]: 0 : if(a + 1 < aInput.size())
956 : : {
957 : : // a pair for processing
958 [ # # ][ # # ]: 0 : aResult.push_back(solvePolygonOperationOr(aInput[a], aInput[a + 1]));
[ # # ][ # # ]
[ # # ]
959 : : }
960 : : else
961 : : {
962 : : // last single PolyPolygon; copy to target to not lose it
963 [ # # ][ # # ]: 0 : aResult.push_back(aInput[a]);
964 : : }
965 : : }
966 : :
967 [ # # ]: 0 : aInput = aResult;
968 : 0 : }
969 : :
970 : : // third step: get result
971 [ # # ]: 0 : if(1 == aInput.size())
972 : : {
973 [ # # ][ # # ]: 0 : return aInput[0];
974 : : }
975 : :
976 [ # # ]: 0 : return B2DPolyPolygon();
977 : : }
978 : :
979 : : //////////////////////////////////////////////////////////////////////////////
980 : :
981 : : } // end of namespace tools
982 : : } // end of namespace basegfx
983 : :
984 : : /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
|
