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