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