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