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 2239 : struct StripHelper
40 : {
41 : B2DRange maRange;
42 : sal_Int32 mnDepth;
43 : B2VectorOrientation meOrinetation;
44 : };
45 :
46 84054 : struct PN
47 : {
48 : public:
49 : B2DPoint maPoint;
50 : sal_uInt32 mnI;
51 : sal_uInt32 mnIP;
52 : sal_uInt32 mnIN;
53 : };
54 :
55 67748 : 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 187535 : bool operator<(const SN& rComp) const
74 : {
75 187535 : if(fTools::equal(mpPN->maPoint.getX(), rComp.mpPN->maPoint.getX()))
76 : {
77 19894 : if(fTools::equal(mpPN->maPoint.getY(), rComp.mpPN->maPoint.getY()))
78 : {
79 924 : return (mpPN->mnI < rComp.mpPN->mnI);
80 : }
81 : else
82 : {
83 18970 : return fTools::less(mpPN->maPoint.getY(), rComp.mpPN->maPoint.getY());
84 : }
85 : }
86 : else
87 : {
88 167641 : 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 2886 : 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 4441 : void impAddPolygon(const sal_uInt32 aPos, const B2DPolygon& rGeometry)
112 : {
113 4441 : const sal_uInt32 nCount(rGeometry.count());
114 4441 : PN aNewPN;
115 8882 : VN aNewVN;
116 : SN aNewSN;
117 :
118 42027 : for(sal_uInt32 a(0); a < nCount; a++)
119 : {
120 37586 : const B2DPoint aPoint(rGeometry.getB2DPoint(a));
121 37586 : aNewPN.maPoint = aPoint;
122 37586 : aNewPN.mnI = aPos + a;
123 37586 : aNewPN.mnIP = aPos + ((a != 0) ? a - 1 : nCount - 1);
124 37586 : aNewPN.mnIN = aPos + ((a + 1 == nCount) ? 0 : a + 1);
125 37586 : maPNV.push_back(aNewPN);
126 :
127 37586 : if(mbIsCurve)
128 : {
129 29433 : aNewVN.maPrev = rGeometry.getPrevControlPoint(a) - aPoint;
130 29433 : aNewVN.maNext = rGeometry.getNextControlPoint(a) - aPoint;
131 29433 : aNewVN.maOriginalNext = aNewVN.maNext;
132 29433 : maVNV.push_back(aNewVN);
133 : }
134 :
135 37586 : aNewSN.mpPN = &maPNV[maPNV.size() - 1];
136 37586 : maSNV.push_back(aNewSN);
137 42027 : }
138 4441 : }
139 :
140 706 : static 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 706 : 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 264 : const bool bBoolA(fTools::moreOrEqual(rVecA.cross(rTest), 0.0));
148 264 : const bool bBoolB(fTools::lessOrEqual(rVecB.cross(rTest), 0.0));
149 :
150 264 : 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 442 : const bool bBoolA(fTools::lessOrEqual(rVecA.cross(rTest), 0.0));
156 442 : const bool bBoolB(fTools::moreOrEqual(rVecB.cross(rTest), 0.0));
157 :
158 442 : return (!(bBoolA && bBoolB));
159 : }
160 : }
161 :
162 625 : void impSwitchNext(PN& rPNa, PN& rPNb)
163 : {
164 625 : ::std::swap(rPNa.mnIN, rPNb.mnIN);
165 :
166 625 : if(mbIsCurve)
167 : {
168 411 : VN& rVNa = maVNV[rPNa.mnI];
169 411 : VN& rVNb = maVNV[rPNb.mnI];
170 :
171 411 : ::std::swap(rVNa.maNext, rVNb.maNext);
172 : }
173 :
174 625 : if(!mbChanged)
175 : {
176 335 : mbChanged = true;
177 : }
178 625 : }
179 :
180 2014 : B2DCubicBezier createSegment(const PN& rPN, bool bPrev) const
181 : {
182 2014 : const B2DPoint& rStart(rPN.maPoint);
183 2014 : const B2DPoint& rEnd(maPNV[bPrev ? rPN.mnIP : rPN.mnIN].maPoint);
184 2014 : 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 2014 : const B2DVector& rCPB(bPrev ? maVNV[maPNV[rPN.mnIP].mnI].maOriginalNext : maVNV[maPNV[rPN.mnIN].mnI].maPrev);
188 :
189 2014 : return B2DCubicBezier(rStart, rStart + rCPA, rEnd + rCPB, rEnd);
190 : }
191 :
192 766 : void impHandleCommon(PN& rPNa, PN& rPNb)
193 : {
194 766 : if(mbIsCurve)
195 : {
196 504 : const B2DCubicBezier aNextA(createSegment(rPNa, false));
197 969 : const B2DCubicBezier aPrevA(createSegment(rPNa, true));
198 :
199 504 : if(aNextA.equal(aPrevA))
200 : {
201 : // deadend on A (identical edge)
202 6 : return;
203 : }
204 :
205 963 : const B2DCubicBezier aNextB(createSegment(rPNb, false));
206 963 : const B2DCubicBezier aPrevB(createSegment(rPNb, true));
207 :
208 498 : if(aNextB.equal(aPrevB))
209 : {
210 : // deadend on B (identical edge)
211 2 : return;
212 : }
213 :
214 496 : if(aPrevA.equal(aPrevB))
215 : {
216 : // common edge in same direction
217 6 : return;
218 : }
219 490 : else if(aPrevA.equal(aNextB))
220 : {
221 : // common edge in opposite direction
222 317 : 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 293 : impSwitchNext(rPNa, rPNb);
231 : }
232 : }
233 173 : else if(aNextA.equal(aNextB))
234 : {
235 : // common edge in same direction enter
236 : // search leave edge
237 1 : PN* pPNa2 = &maPNV[rPNa.mnIN];
238 1 : PN* pPNb2 = &maPNV[rPNb.mnIN];
239 1 : bool bOnEdge(true);
240 :
241 5 : do
242 : {
243 5 : const B2DCubicBezier aNextA2(createSegment(*pPNa2, false));
244 10 : const B2DCubicBezier aNextB2(createSegment(*pPNb2, false));
245 :
246 5 : if(aNextA2.equal(aNextB2))
247 : {
248 5 : pPNa2 = &maPNV[pPNa2->mnIN];
249 5 : pPNb2 = &maPNV[pPNb2->mnIN];
250 : }
251 : else
252 : {
253 0 : bOnEdge = false;
254 5 : }
255 : }
256 5 : while(bOnEdge && pPNa2 != &rPNa && pPNb2 != &rPNb);
257 :
258 1 : if(bOnEdge)
259 : {
260 : // loop over two identical polygon paths
261 1 : 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 172 : 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 160 : const B2DVector aPrevCA(aPrevA.interpolatePoint(0.5) - aPrevA.getStartPoint());
296 320 : const B2DVector aNextCA(aNextA.interpolatePoint(0.5) - aNextA.getStartPoint());
297 320 : const B2DVector aPrevCB(aPrevB.interpolatePoint(0.5) - aPrevB.getStartPoint());
298 320 : const B2DVector aNextCB(aNextB.interpolatePoint(0.5) - aNextB.getStartPoint());
299 :
300 160 : const bool bEnter(impLeftOfEdges(aPrevCA, aNextCA, aPrevCB));
301 160 : const bool bLeave(impLeftOfEdges(aPrevCA, aNextCA, aNextCB));
302 :
303 160 : if(bEnter != bLeave)
304 : {
305 : // crossover
306 106 : impSwitchNext(rPNa, rPNb);
307 160 : }
308 465 : }
309 : }
310 : else
311 : {
312 262 : const B2DPoint& rNextA(maPNV[rPNa.mnIN].maPoint);
313 262 : const B2DPoint& rPrevA(maPNV[rPNa.mnIP].maPoint);
314 :
315 262 : if(rNextA.equal(rPrevA))
316 : {
317 : // deadend on A
318 0 : return;
319 : }
320 :
321 262 : const B2DPoint& rNextB(maPNV[rPNb.mnIN].maPoint);
322 262 : const B2DPoint& rPrevB(maPNV[rPNb.mnIP].maPoint);
323 :
324 262 : if(rNextB.equal(rPrevB))
325 : {
326 : // deadend on B
327 0 : return;
328 : }
329 :
330 262 : if(rPrevA.equal(rPrevB))
331 : {
332 : // common edge in same direction
333 37 : return;
334 : }
335 225 : else if(rPrevA.equal(rNextB))
336 : {
337 : // common edge in opposite direction
338 29 : if(rNextA.equal(rPrevB))
339 : {
340 : // common edge in opposite direction continues
341 5 : return;
342 : }
343 : else
344 : {
345 : // common edge in opposite direction leave
346 24 : impSwitchNext(rPNa, rPNb);
347 : }
348 : }
349 196 : else if(rNextA.equal(rNextB))
350 : {
351 : // common edge in same direction enter
352 : // search leave edge
353 13 : PN* pPNa2 = &maPNV[rPNa.mnIN];
354 13 : PN* pPNb2 = &maPNV[rPNb.mnIN];
355 13 : bool bOnEdge(true);
356 :
357 20 : do
358 : {
359 20 : const B2DPoint& rNextA2(maPNV[pPNa2->mnIN].maPoint);
360 20 : const B2DPoint& rNextB2(maPNV[pPNb2->mnIN].maPoint);
361 :
362 20 : if(rNextA2.equal(rNextB2))
363 : {
364 8 : pPNa2 = &maPNV[pPNa2->mnIN];
365 8 : pPNb2 = &maPNV[pPNb2->mnIN];
366 : }
367 : else
368 : {
369 12 : bOnEdge = false;
370 : }
371 : }
372 8 : while(bOnEdge && pPNa2 != &rPNa && pPNb2 != &rPNb);
373 :
374 13 : if(bOnEdge)
375 : {
376 : // loop over two identical polygon paths
377 1 : 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 12 : const B2DPoint& aPointE(rPNa.maPoint);
384 12 : const B2DVector aPrevAE(rPrevA - aPointE);
385 24 : const B2DVector aNextAE(rNextA - aPointE);
386 24 : const B2DVector aPrevBE(rPrevB - aPointE);
387 :
388 12 : const B2DPoint& aPointL(pPNa2->maPoint);
389 24 : const B2DVector aPrevAL(maPNV[pPNa2->mnIP].maPoint - aPointL);
390 24 : const B2DVector aNextAL(maPNV[pPNa2->mnIN].maPoint - aPointL);
391 24 : const B2DVector aNextBL(maPNV[pPNb2->mnIN].maPoint - aPointL);
392 :
393 12 : const bool bEnter(impLeftOfEdges(aPrevAE, aNextAE, aPrevBE));
394 12 : const bool bLeave(impLeftOfEdges(aPrevAL, aNextAL, aNextBL));
395 :
396 12 : if(bEnter != bLeave)
397 : {
398 : // crossover; switch start or end
399 11 : impSwitchNext(rPNa, rPNb);
400 12 : }
401 : }
402 : }
403 183 : else if(rNextA.equal(rPrevB))
404 : {
405 : // common edge in opposite direction enter
406 2 : impSwitchNext(rPNa, rPNb);
407 : }
408 : else
409 : {
410 : // no common edges, check for crossover
411 181 : const B2DPoint& aPoint(rPNa.maPoint);
412 181 : const B2DVector aPrevA(rPrevA - aPoint);
413 362 : const B2DVector aNextA(rNextA - aPoint);
414 362 : const B2DVector aPrevB(rPrevB - aPoint);
415 362 : const B2DVector aNextB(rNextB - aPoint);
416 :
417 181 : const bool bEnter(impLeftOfEdges(aPrevA, aNextA, aPrevB));
418 181 : const bool bLeave(impLeftOfEdges(aPrevA, aNextA, aNextB));
419 :
420 181 : if(bEnter != bLeave)
421 : {
422 : // crossover
423 177 : impSwitchNext(rPNa, rPNb);
424 181 : }
425 : }
426 : }
427 : }
428 :
429 2847 : void impSolve()
430 : {
431 : // sort by point to identify common nodes easier
432 2847 : ::std::sort(maSNV.begin(), maSNV.end());
433 :
434 : // handle common nodes
435 2847 : const sal_uInt32 nNodeCount(maSNV.size());
436 2847 : sal_uInt32 a(0);
437 :
438 : // snap unsharp-equal points
439 2847 : if(nNodeCount)
440 : {
441 2847 : basegfx::B2DPoint* pLast(&maSNV[0].mpPN->maPoint);
442 :
443 37586 : for(a = 1; a < nNodeCount; a++)
444 : {
445 34739 : basegfx::B2DPoint* pCurrent(&maSNV[a].mpPN->maPoint);
446 :
447 34739 : if(pLast->equal(*pCurrent) && (pLast->getX() != pCurrent->getX() || pLast->getY() != pCurrent->getY()))
448 : {
449 325 : const basegfx::B2DPoint aMiddle((*pLast + *pCurrent) * 0.5);
450 :
451 325 : if(pLast->getX() != aMiddle.getX() || pLast->getY() != aMiddle.getY())
452 : {
453 252 : maCorrectionTable.push_back(CorrectionPair(*pLast, aMiddle));
454 252 : *pLast = aMiddle;
455 : }
456 :
457 325 : if(pCurrent->getX() != aMiddle.getX() || pCurrent->getY() != aMiddle.getY())
458 : {
459 163 : maCorrectionTable.push_back(CorrectionPair(*pCurrent, aMiddle));
460 163 : *pCurrent = aMiddle;
461 325 : }
462 : }
463 :
464 34739 : pLast = pCurrent;
465 : }
466 : }
467 :
468 37586 : for(a = 0; a < nNodeCount - 1; a++)
469 : {
470 : // test a before using it, not after. Also use nPointCount instead of aSortNodes.size()
471 34739 : PN& rPNb = *(maSNV[a].mpPN);
472 :
473 35505 : for(sal_uInt32 b(a + 1); b < nNodeCount && rPNb.maPoint.equal(maSNV[b].mpPN->maPoint); b++)
474 : {
475 766 : impHandleCommon(rPNb, *maSNV[b].mpPN);
476 : }
477 : }
478 2847 : }
479 :
480 : public:
481 1929 : explicit solver(const B2DPolygon& rOriginal)
482 : : maOriginal(B2DPolyPolygon(rOriginal)),
483 : mbIsCurve(false),
484 1929 : mbChanged(false)
485 : {
486 1929 : const sal_uInt32 nOriginalCount(rOriginal.count());
487 :
488 1929 : if(nOriginalCount)
489 : {
490 1929 : B2DPolygon aGeometry(tools::addPointsAtCutsAndTouches(rOriginal));
491 1929 : aGeometry.removeDoublePoints();
492 1929 : aGeometry = tools::simplifyCurveSegments(aGeometry);
493 1929 : mbIsCurve = aGeometry.areControlPointsUsed();
494 :
495 1929 : 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 1929 : if(nPointCount > 3 || (nPointCount > 1 && mbIsCurve))
501 : {
502 : // reserve space in point, control and sort vector.
503 1890 : maSNV.reserve(nPointCount);
504 1890 : maPNV.reserve(nPointCount);
505 1890 : maVNV.reserve(mbIsCurve ? nPointCount : 0);
506 :
507 : // fill data
508 1890 : impAddPolygon(0, aGeometry);
509 :
510 : // solve common nodes
511 1890 : impSolve();
512 1929 : }
513 : }
514 1929 : }
515 :
516 957 : explicit solver(const B2DPolyPolygon& rOriginal)
517 : : maOriginal(rOriginal),
518 : mbIsCurve(false),
519 957 : mbChanged(false)
520 : {
521 957 : sal_uInt32 nOriginalCount(maOriginal.count());
522 :
523 957 : if(nOriginalCount)
524 : {
525 957 : B2DPolyPolygon aGeometry(tools::addPointsAtCutsAndTouches(maOriginal, true));
526 957 : aGeometry.removeDoublePoints();
527 957 : aGeometry = tools::simplifyCurveSegments(aGeometry);
528 957 : mbIsCurve = aGeometry.areControlPointsUsed();
529 957 : nOriginalCount = aGeometry.count();
530 :
531 957 : if(nOriginalCount)
532 : {
533 957 : sal_uInt32 nPointCount(0);
534 957 : sal_uInt32 a(0);
535 :
536 : // count points
537 3508 : for(a = 0; a < nOriginalCount; a++)
538 : {
539 2551 : const B2DPolygon aCandidate(aGeometry.getB2DPolygon(a));
540 2551 : 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 2551 : if(nCandCount)
548 : {
549 2551 : nPointCount += nCandCount;
550 : }
551 2551 : }
552 :
553 957 : if(nPointCount)
554 : {
555 : // reserve space in point, control and sort vector.
556 957 : maSNV.reserve(nPointCount);
557 957 : maPNV.reserve(nPointCount);
558 957 : maVNV.reserve(mbIsCurve ? nPointCount : 0);
559 :
560 : // fill data
561 957 : sal_uInt32 nInsertIndex(0);
562 :
563 3508 : for(a = 0; a < nOriginalCount; a++)
564 : {
565 2551 : const B2DPolygon aCandidate(aGeometry.getB2DPolygon(a));
566 2551 : const sal_uInt32 nCandCount(aCandidate.count());
567 :
568 : // use same condition as above, the data vector is
569 : // pre-allocated
570 2551 : if(nCandCount)
571 : {
572 2551 : impAddPolygon(nInsertIndex, aCandidate);
573 2551 : nInsertIndex += nCandCount;
574 : }
575 2551 : }
576 :
577 : // solve common nodes
578 957 : impSolve();
579 : }
580 957 : }
581 : }
582 957 : }
583 :
584 2886 : B2DPolyPolygon getB2DPolyPolygon()
585 : {
586 2886 : if(mbChanged)
587 : {
588 335 : B2DPolyPolygon aRetval;
589 335 : const sal_uInt32 nCount(maPNV.size());
590 335 : sal_uInt32 nCountdown(nCount);
591 :
592 6549 : for(sal_uInt32 a(0); nCountdown && a < nCount; a++)
593 : {
594 6214 : PN& rPN = maPNV[a];
595 :
596 6214 : if(SAL_MAX_UINT32 != rPN.mnI)
597 : {
598 : // unused node, start new part polygon
599 1670 : B2DPolygon aNewPart;
600 1670 : PN* pPNCurr = &rPN;
601 :
602 8902 : do
603 : {
604 8902 : const B2DPoint& rPoint = pPNCurr->maPoint;
605 8902 : aNewPart.append(rPoint);
606 :
607 8902 : if(mbIsCurve)
608 : {
609 7211 : const VN& rVNCurr = maVNV[pPNCurr->mnI];
610 :
611 7211 : if(!rVNCurr.maPrev.equalZero())
612 : {
613 2321 : aNewPart.setPrevControlPoint(aNewPart.count() - 1, rPoint + rVNCurr.maPrev);
614 : }
615 :
616 7211 : if(!rVNCurr.maNext.equalZero())
617 : {
618 2315 : aNewPart.setNextControlPoint(aNewPart.count() - 1, rPoint + rVNCurr.maNext);
619 : }
620 : }
621 :
622 8902 : pPNCurr->mnI = SAL_MAX_UINT32;
623 8902 : nCountdown--;
624 8902 : pPNCurr = &(maPNV[pPNCurr->mnIN]);
625 : }
626 7232 : while(pPNCurr != &rPN && SAL_MAX_UINT32 != pPNCurr->mnI);
627 :
628 : // close and add
629 1670 : aNewPart.setClosed(true);
630 1670 : aRetval.append(aNewPart);
631 : }
632 : }
633 :
634 335 : return aRetval;
635 : }
636 : else
637 : {
638 2551 : const sal_uInt32 nCorrectionSize(maCorrectionTable.size());
639 :
640 : // no change, return original
641 2551 : if(!nCorrectionSize)
642 : {
643 2548 : 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 939 : B2DPolyPolygon solveCrossovers(const B2DPolyPolygon& rCandidate)
690 : {
691 939 : if(rCandidate.count() > 0L)
692 : {
693 939 : solver aSolver(rCandidate);
694 939 : return aSolver.getB2DPolyPolygon();
695 : }
696 : else
697 : {
698 0 : return rCandidate;
699 : }
700 : }
701 :
702 1921 : B2DPolyPolygon solveCrossovers(const B2DPolygon& rCandidate)
703 : {
704 1921 : solver aSolver(rCandidate);
705 1921 : return aSolver.getB2DPolyPolygon();
706 : }
707 :
708 3111 : B2DPolyPolygon stripNeutralPolygons(const B2DPolyPolygon& rCandidate)
709 : {
710 3111 : B2DPolyPolygon aRetval;
711 :
712 8413 : for(sal_uInt32 a(0L); a < rCandidate.count(); a++)
713 : {
714 5302 : const B2DPolygon aCandidate(rCandidate.getB2DPolygon(a));
715 :
716 5302 : if(B2VectorOrientation::Neutral != tools::getOrientation(aCandidate))
717 : {
718 4856 : aRetval.append(aCandidate);
719 : }
720 5302 : }
721 :
722 3111 : return aRetval;
723 : }
724 :
725 2434 : B2DPolyPolygon createNonzeroConform(const B2DPolyPolygon& rCandidate)
726 : {
727 2434 : B2DPolyPolygon aCandidate;
728 :
729 : // remove all self-intersections and intersections
730 2434 : if(rCandidate.count() == 1)
731 : {
732 1921 : aCandidate = basegfx::tools::solveCrossovers(rCandidate.getB2DPolygon(0));
733 : }
734 : else
735 : {
736 513 : aCandidate = basegfx::tools::solveCrossovers(rCandidate);
737 : }
738 :
739 : // cleanup evtl. neutral polygons
740 2434 : aCandidate = basegfx::tools::stripNeutralPolygons(aCandidate);
741 :
742 : // remove all polygons which have the same orientation as the polygon they are directly contained in
743 2434 : const sal_uInt32 nCount(aCandidate.count());
744 :
745 2434 : if(nCount > 1)
746 : {
747 : sal_uInt32 a, b;
748 531 : ::std::vector< StripHelper > aHelpers;
749 531 : aHelpers.resize(nCount);
750 :
751 2458 : for(a = 0; a < nCount; a++)
752 : {
753 1927 : const B2DPolygon aCand(aCandidate.getB2DPolygon(a));
754 1927 : StripHelper* pNewHelper = &(aHelpers[a]);
755 1927 : pNewHelper->maRange = tools::getRange(aCand);
756 1927 : pNewHelper->meOrinetation = tools::getOrientation(aCand);
757 :
758 : // initialize with own orientation
759 1927 : pNewHelper->mnDepth = (B2VectorOrientation::Negative == pNewHelper->meOrinetation ? -1 : 1);
760 1927 : }
761 :
762 1927 : for(a = 0; a < nCount - 1; a++)
763 : {
764 1396 : const B2DPolygon aCandA(aCandidate.getB2DPolygon(a));
765 1396 : StripHelper& rHelperA = aHelpers[a];
766 :
767 15609 : for(b = a + 1; b < nCount; b++)
768 : {
769 14213 : const B2DPolygon aCandB(aCandidate.getB2DPolygon(b));
770 14213 : StripHelper& rHelperB = aHelpers[b];
771 14213 : const bool bAInB(rHelperB.maRange.isInside(rHelperA.maRange) && tools::isInside(aCandB, aCandA, true));
772 :
773 14213 : if(bAInB)
774 : {
775 : // A is inside B, add orientation of B to A
776 0 : rHelperA.mnDepth += (B2VectorOrientation::Negative == rHelperB.meOrinetation ? -1 : 1);
777 : }
778 :
779 14213 : const bool bBInA(rHelperA.maRange.isInside(rHelperB.maRange) && tools::isInside(aCandA, aCandB, true));
780 :
781 14213 : if(bBInA)
782 : {
783 : // B is inside A, add orientation of A to B
784 544 : rHelperB.mnDepth += (B2VectorOrientation::Negative == rHelperA.meOrinetation ? -1 : 1);
785 : }
786 14213 : }
787 1396 : }
788 :
789 1062 : const B2DPolyPolygon aSource(aCandidate);
790 531 : aCandidate.clear();
791 :
792 2458 : for(a = 0L; a < nCount; a++)
793 : {
794 1927 : 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 1927 : bool bAcceptEntry(rHelper.mnDepth >= -1 && rHelper.mnDepth <= 1);
800 :
801 1927 : if(bAcceptEntry)
802 : {
803 1923 : aCandidate.append(aSource.getB2DPolygon(a));
804 : }
805 531 : }
806 : }
807 :
808 2434 : return aCandidate;
809 : }
810 :
811 148 : B2DPolyPolygon stripDispensablePolygons(const B2DPolyPolygon& rCandidate, bool bKeepAboveZero)
812 : {
813 148 : const sal_uInt32 nCount(rCandidate.count());
814 148 : B2DPolyPolygon aRetval;
815 :
816 148 : if(nCount)
817 : {
818 148 : if(nCount == 1L)
819 : {
820 0 : if(!bKeepAboveZero && B2VectorOrientation::Positive == tools::getOrientation(rCandidate.getB2DPolygon(0L)))
821 : {
822 0 : aRetval = rCandidate;
823 : }
824 : }
825 : else
826 : {
827 : sal_uInt32 a, b;
828 148 : ::std::vector< StripHelper > aHelpers;
829 148 : aHelpers.resize(nCount);
830 :
831 460 : for(a = 0L; a < nCount; a++)
832 : {
833 312 : const B2DPolygon aCandidate(rCandidate.getB2DPolygon(a));
834 312 : StripHelper* pNewHelper = &(aHelpers[a]);
835 312 : pNewHelper->maRange = tools::getRange(aCandidate);
836 312 : pNewHelper->meOrinetation = tools::getOrientation(aCandidate);
837 312 : pNewHelper->mnDepth = (B2VectorOrientation::Negative == pNewHelper->meOrinetation ? -1L : 0L);
838 312 : }
839 :
840 312 : for(a = 0L; a < nCount - 1L; a++)
841 : {
842 164 : const B2DPolygon aCandA(rCandidate.getB2DPolygon(a));
843 164 : StripHelper& rHelperA = aHelpers[a];
844 :
845 355 : for(b = a + 1L; b < nCount; b++)
846 : {
847 191 : const B2DPolygon aCandB(rCandidate.getB2DPolygon(b));
848 191 : StripHelper& rHelperB = aHelpers[b];
849 191 : const bool bAInB(rHelperB.maRange.isInside(rHelperA.maRange) && tools::isInside(aCandB, aCandA, true));
850 191 : const bool bBInA(rHelperA.maRange.isInside(rHelperB.maRange) && tools::isInside(aCandA, aCandB, true));
851 :
852 191 : if(bAInB && bBInA)
853 : {
854 : // congruent
855 10 : 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 5 : 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 186 : if(bAInB)
872 : {
873 9 : if(B2VectorOrientation::Negative == rHelperB.meOrinetation)
874 : {
875 0 : rHelperA.mnDepth--;
876 : }
877 : else
878 : {
879 9 : rHelperA.mnDepth++;
880 : }
881 : }
882 177 : else if(bBInA)
883 : {
884 51 : if(B2VectorOrientation::Negative == rHelperA.meOrinetation)
885 : {
886 0 : rHelperB.mnDepth--;
887 : }
888 : else
889 : {
890 51 : rHelperB.mnDepth++;
891 : }
892 : }
893 : }
894 191 : }
895 164 : }
896 :
897 460 : for(a = 0L; a < nCount; a++)
898 : {
899 312 : const StripHelper& rHelper = aHelpers[a];
900 312 : bool bAcceptEntry(bKeepAboveZero ? 1L <= rHelper.mnDepth : 0L == rHelper.mnDepth);
901 :
902 312 : if(bAcceptEntry)
903 : {
904 97 : aRetval.append(rCandidate.getB2DPolygon(a));
905 : }
906 148 : }
907 : }
908 : }
909 :
910 148 : return aRetval;
911 : }
912 :
913 8 : B2DPolyPolygon prepareForPolygonOperation(const B2DPolygon& rCandidate)
914 : {
915 8 : solver aSolver(rCandidate);
916 16 : B2DPolyPolygon aRetval(stripNeutralPolygons(aSolver.getB2DPolyPolygon()));
917 :
918 16 : return correctOrientations(aRetval);
919 : }
920 :
921 18 : B2DPolyPolygon prepareForPolygonOperation(const B2DPolyPolygon& rCandidate)
922 : {
923 18 : solver aSolver(rCandidate);
924 36 : B2DPolyPolygon aRetval(stripNeutralPolygons(aSolver.getB2DPolyPolygon()));
925 :
926 36 : return correctOrientations(aRetval);
927 : }
928 :
929 1 : B2DPolyPolygon solvePolygonOperationOr(const B2DPolyPolygon& rCandidateA, const B2DPolyPolygon& rCandidateB)
930 : {
931 1 : if(!rCandidateA.count())
932 : {
933 0 : return rCandidateB;
934 : }
935 1 : 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 1 : B2DPolyPolygon aRetval(rCandidateA);
944 :
945 1 : aRetval.append(rCandidateB);
946 1 : aRetval = solveCrossovers(aRetval);
947 1 : aRetval = stripNeutralPolygons(aRetval);
948 :
949 1 : return stripDispensablePolygons(aRetval, false);
950 : }
951 : }
952 :
953 2 : B2DPolyPolygon solvePolygonOperationXor(const B2DPolyPolygon& rCandidateA, const B2DPolyPolygon& rCandidateB)
954 : {
955 2 : if(!rCandidateA.count())
956 : {
957 0 : return rCandidateB;
958 : }
959 2 : 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 2 : B2DPolyPolygon aRetval(rCandidateA);
969 :
970 2 : aRetval.append(rCandidateB);
971 2 : aRetval = solveCrossovers(aRetval);
972 2 : aRetval = stripNeutralPolygons(aRetval);
973 :
974 2 : return correctOrientations(aRetval);
975 : }
976 : }
977 :
978 4 : B2DPolyPolygon solvePolygonOperationAnd(const B2DPolyPolygon& rCandidateA, const B2DPolyPolygon& rCandidateB)
979 : {
980 4 : if(!rCandidateA.count())
981 : {
982 0 : return B2DPolyPolygon();
983 : }
984 4 : 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 4 : B2DPolyPolygon aRetval(rCandidateA);
994 :
995 4 : aRetval.append(rCandidateB);
996 4 : aRetval = solveCrossovers(aRetval);
997 4 : aRetval = stripNeutralPolygons(aRetval);
998 :
999 4 : return stripDispensablePolygons(aRetval, true);
1000 : }
1001 : }
1002 :
1003 3 : B2DPolyPolygon solvePolygonOperationDiff(const B2DPolyPolygon& rCandidateA, const B2DPolyPolygon& rCandidateB)
1004 : {
1005 3 : if(!rCandidateA.count())
1006 : {
1007 0 : return B2DPolyPolygon();
1008 : }
1009 3 : else if(!rCandidateB.count())
1010 : {
1011 0 : return rCandidateA;
1012 : }
1013 : else
1014 : {
1015 : // Make B topologically to holes and append to A
1016 3 : B2DPolyPolygon aRetval(rCandidateB);
1017 :
1018 3 : aRetval.flip();
1019 3 : aRetval.append(rCandidateA);
1020 :
1021 : // solve crossovers and throw away all sub-polygons which have a
1022 : // depth other than 0.
1023 3 : aRetval = basegfx::tools::solveCrossovers(aRetval);
1024 3 : aRetval = basegfx::tools::stripNeutralPolygons(aRetval);
1025 :
1026 3 : 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(size_t 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(size_t 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: */
|
