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 <basegfx/polygon/b2dpolygoncutandtouch.hxx>
21 : #include <osl/diagnose.h>
22 : #include <basegfx/numeric/ftools.hxx>
23 : #include <basegfx/point/b2dpoint.hxx>
24 : #include <basegfx/vector/b2dvector.hxx>
25 : #include <basegfx/range/b2drange.hxx>
26 : #include <basegfx/polygon/b2dpolygontools.hxx>
27 : #include <basegfx/polygon/b2dpolypolygontools.hxx>
28 : #include <basegfx/curve/b2dcubicbezier.hxx>
29 :
30 : #include <vector>
31 : #include <algorithm>
32 :
33 :
34 : #define SUBDIVIDE_FOR_CUT_TEST_COUNT (50)
35 :
36 : //////////////////////////////////////////////////////////////////////////////
37 :
38 : namespace basegfx
39 : {
40 : namespace
41 : {
42 : ////////////////////////////////////////////////////////////////////////////////
43 :
44 48492 : class temporaryPoint
45 : {
46 : B2DPoint maPoint; // the new point
47 : sal_uInt32 mnIndex; // index after which to insert
48 : double mfCut; // parametric cut description [0.0 .. 1.0]
49 :
50 : public:
51 7014 : temporaryPoint(const B2DPoint& rNewPoint, sal_uInt32 nIndex, double fCut)
52 : : maPoint(rNewPoint),
53 : mnIndex(nIndex),
54 7014 : mfCut(fCut)
55 : {
56 7014 : }
57 :
58 9403 : bool operator<(const temporaryPoint& rComp) const
59 : {
60 9403 : if(mnIndex == rComp.mnIndex)
61 : {
62 1947 : return (mfCut < rComp.mfCut);
63 : }
64 :
65 7456 : return (mnIndex < rComp.mnIndex);
66 : }
67 :
68 6982 : const B2DPoint& getPoint() const { return maPoint; }
69 14136 : sal_uInt32 getIndex() const { return mnIndex; }
70 883 : double getCut() const { return mfCut; }
71 : };
72 :
73 : ////////////////////////////////////////////////////////////////////////////////
74 :
75 : typedef ::std::vector< temporaryPoint > temporaryPointVector;
76 :
77 : ////////////////////////////////////////////////////////////////////////////////
78 :
79 26074 : class temporaryPolygonData
80 : {
81 : B2DPolygon maPolygon;
82 : B2DRange maRange;
83 : temporaryPointVector maPoints;
84 :
85 : public:
86 70283 : const B2DPolygon& getPolygon() const { return maPolygon; }
87 13037 : void setPolygon(const B2DPolygon& rNew) { maPolygon = rNew; maRange = tools::getRange(maPolygon); }
88 119802 : const B2DRange& getRange() const { return maRange; }
89 51201 : temporaryPointVector& getTemporaryPointVector() { return maPoints; }
90 : };
91 :
92 : ////////////////////////////////////////////////////////////////////////////////
93 :
94 28856 : B2DPolygon mergeTemporaryPointsAndPolygon(const B2DPolygon& rCandidate, temporaryPointVector& rTempPoints)
95 : {
96 : // #i76891# mergeTemporaryPointsAndPolygon redesigned to be able to correctly handle
97 : // single edges with/without control points
98 : // #i101491# added counter for non-changing element count
99 28856 : const sal_uInt32 nTempPointCount(rTempPoints.size());
100 :
101 28856 : if(nTempPointCount)
102 : {
103 1784 : B2DPolygon aRetval;
104 1784 : const sal_uInt32 nCount(rCandidate.count());
105 :
106 1784 : if(nCount)
107 : {
108 : // sort temp points to assure increasing fCut values and increasing indices
109 1784 : ::std::sort(rTempPoints.begin(), rTempPoints.end());
110 :
111 : // prepare loop
112 1784 : B2DCubicBezier aEdge;
113 1784 : sal_uInt32 nNewInd(0L);
114 :
115 : // add start point
116 1784 : aRetval.append(rCandidate.getB2DPoint(0));
117 :
118 11719 : for(sal_uInt32 a(0L); a < nCount; a++)
119 : {
120 : // get edge
121 9935 : rCandidate.getBezierSegment(a, aEdge);
122 :
123 9935 : if(aEdge.isBezier())
124 : {
125 : // control vectors involved for this edge
126 983 : double fLeftStart(0.0);
127 :
128 : // now add all points targeted to be at this index
129 2239 : while(nNewInd < nTempPointCount && rTempPoints[nNewInd].getIndex() == a)
130 : {
131 273 : const temporaryPoint& rTempPoint = rTempPoints[nNewInd++];
132 :
133 : // split curve segment. Splits need to come sorted and need to be < 1.0. Also,
134 : // since original segment is consumed from left to right, the cut values need
135 : // to be scaled to the remaining part
136 273 : B2DCubicBezier aLeftPart;
137 273 : const double fRelativeSplitPoint((rTempPoint.getCut() - fLeftStart) / (1.0 - fLeftStart));
138 273 : aEdge.split(fRelativeSplitPoint, &aLeftPart, &aEdge);
139 273 : fLeftStart = rTempPoint.getCut();
140 :
141 : // add left bow
142 273 : aRetval.appendBezierSegment(aLeftPart.getControlPointA(), aLeftPart.getControlPointB(), rTempPoint.getPoint());
143 273 : }
144 :
145 : // add remaining bow
146 983 : aRetval.appendBezierSegment(aEdge.getControlPointA(), aEdge.getControlPointB(), aEdge.getEndPoint());
147 : }
148 : else
149 : {
150 : // add all points targeted to be at this index
151 24276 : while(nNewInd < nTempPointCount && rTempPoints[nNewInd].getIndex() == a)
152 : {
153 6372 : const temporaryPoint& rTempPoint = rTempPoints[nNewInd++];
154 6372 : const B2DPoint aNewPoint(rTempPoint.getPoint());
155 :
156 : // do not add points double
157 6372 : if(!aRetval.getB2DPoint(aRetval.count() - 1L).equal(aNewPoint))
158 : {
159 6369 : aRetval.append(aNewPoint);
160 : }
161 6372 : }
162 :
163 : // add edge end point
164 8952 : aRetval.append(aEdge.getEndPoint());
165 : }
166 1784 : }
167 : }
168 :
169 1784 : if(rCandidate.isClosed())
170 : {
171 : // set closed flag and correct last point (which is added double now).
172 1766 : tools::closeWithGeometryChange(aRetval);
173 : }
174 :
175 1784 : return aRetval;
176 : }
177 : else
178 : {
179 27072 : return rCandidate;
180 : }
181 : }
182 :
183 : ////////////////////////////////////////////////////////////////////////////////
184 :
185 222 : void adaptAndTransferCutsWithBezierSegment(
186 : const temporaryPointVector& rPointVector, const B2DPolygon& rPolygon,
187 : sal_uInt32 nInd, temporaryPointVector& rTempPoints)
188 : {
189 : // assuming that the subdivision to create rPolygon used aequidistant pieces
190 : // (as in adaptiveSubdivideByCount) it is now possible to calculate back the
191 : // cut positions in the polygon to relative cut positions on the original bezier
192 : // segment.
193 222 : const sal_uInt32 nTempPointCount(rPointVector.size());
194 222 : const sal_uInt32 nEdgeCount(rPolygon.count() ? rPolygon.count() - 1L : 0L);
195 :
196 222 : if(nTempPointCount && nEdgeCount)
197 : {
198 493 : for(sal_uInt32 a(0L); a < nTempPointCount; a++)
199 : {
200 271 : const temporaryPoint& rTempPoint = rPointVector[a];
201 271 : const double fCutPosInPolygon((double)rTempPoint.getIndex() + rTempPoint.getCut());
202 271 : const double fRelativeCutPos(fCutPosInPolygon / (double)nEdgeCount);
203 271 : rTempPoints.push_back(temporaryPoint(rTempPoint.getPoint(), nInd, fRelativeCutPos));
204 : }
205 : }
206 222 : }
207 :
208 : ////////////////////////////////////////////////////////////////////////////////
209 :
210 : } // end of anonymous namespace
211 : } // end of namespace basegfx
212 :
213 : //////////////////////////////////////////////////////////////////////////////
214 :
215 : namespace basegfx
216 : {
217 : namespace
218 : {
219 : ////////////////////////////////////////////////////////////////////////////////
220 : // predefines for calls to this methods before method implementation
221 :
222 : void findCuts(const B2DPolygon& rCandidate, temporaryPointVector& rTempPoints);
223 : void findTouches(const B2DPolygon& rEdgePolygon, const B2DPolygon& rPointPolygon, temporaryPointVector& rTempPoints);
224 : void findCuts(const B2DPolygon& rCandidateA, const B2DPolygon& rCandidateB, temporaryPointVector& rTempPointsA, temporaryPointVector& rTempPointsB);
225 :
226 : ////////////////////////////////////////////////////////////////////////////////
227 :
228 58257 : void findEdgeCutsTwoEdges(
229 : const B2DPoint& rCurrA, const B2DPoint& rNextA,
230 : const B2DPoint& rCurrB, const B2DPoint& rNextB,
231 : sal_uInt32 nIndA, sal_uInt32 nIndB,
232 : temporaryPointVector& rTempPointsA, temporaryPointVector& rTempPointsB)
233 : {
234 : // no null length edges
235 58257 : if(!(rCurrA.equal(rNextA) || rCurrB.equal(rNextB)))
236 : {
237 : // no common start/end points, this can be no cuts
238 57343 : if(!(rCurrB.equal(rCurrA) || rCurrB.equal(rNextA) || rNextB.equal(rCurrA) || rNextB.equal(rNextA)))
239 : {
240 43422 : const B2DVector aVecA(rNextA - rCurrA);
241 86844 : const B2DVector aVecB(rNextB - rCurrB);
242 43422 : double fCut(aVecA.cross(aVecB));
243 :
244 43422 : if(!fTools::equalZero(fCut))
245 : {
246 42204 : const double fZero(0.0);
247 42204 : const double fOne(1.0);
248 42204 : fCut = (aVecB.getY() * (rCurrB.getX() - rCurrA.getX()) + aVecB.getX() * (rCurrA.getY() - rCurrB.getY())) / fCut;
249 :
250 42204 : if(fTools::more(fCut, fZero) && fTools::less(fCut, fOne))
251 : {
252 : // it's a candidate, but also need to test parameter value of cut on line 2
253 : double fCut2;
254 :
255 : // choose the more precise version
256 5766 : if(fabs(aVecB.getX()) > fabs(aVecB.getY()))
257 : {
258 3208 : fCut2 = (rCurrA.getX() + (fCut * aVecA.getX()) - rCurrB.getX()) / aVecB.getX();
259 : }
260 : else
261 : {
262 2558 : fCut2 = (rCurrA.getY() + (fCut * aVecA.getY()) - rCurrB.getY()) / aVecB.getY();
263 : }
264 :
265 5766 : if(fTools::more(fCut2, fZero) && fTools::less(fCut2, fOne))
266 : {
267 : // cut is in range, add point. Two edges can have only one cut, but
268 : // add a cut point to each list. The lists may be the same for
269 : // self intersections.
270 2964 : const B2DPoint aCutPoint(interpolate(rCurrA, rNextA, fCut));
271 2964 : rTempPointsA.push_back(temporaryPoint(aCutPoint, nIndA, fCut));
272 2964 : rTempPointsB.push_back(temporaryPoint(aCutPoint, nIndB, fCut2));
273 : }
274 : }
275 43422 : }
276 : }
277 : }
278 58257 : }
279 :
280 : ////////////////////////////////////////////////////////////////////////////////
281 :
282 12050 : void findCutsAndTouchesAndCommonForBezier(const B2DPolygon& rCandidateA, const B2DPolygon& rCandidateB, temporaryPointVector& rTempPointsA, temporaryPointVector& rTempPointsB)
283 : {
284 : // #i76891#
285 : // This new method is necessary since in findEdgeCutsBezierAndEdge and in findEdgeCutsTwoBeziers
286 : // it is not sufficient to use findCuts() recursively. This will indeed find the cuts between the
287 : // segments of the two temporarily adaptive subdivided bezier segments, but not the touches or
288 : // equal points of them.
289 : // It would be possible to find the toches using findTouches(), but at last with commpn points
290 : // the adding of cut points (temporary points) would fail. But for these temporarily adaptive
291 : // subdivided bezier segments, common points may be not very likely, but the bug shows that it
292 : // happens.
293 : // Touch points are a little bit more likely than common points. All in all it is best to use
294 : // a specialized method here which can profit from knowing that it is working on a special
295 : // family of B2DPolygons: no curve segments included and not closed.
296 : OSL_ENSURE(!rCandidateA.areControlPointsUsed() && !rCandidateB.areControlPointsUsed(), "findCutsAndTouchesAndCommonForBezier only works with subdivided polygons (!)");
297 : OSL_ENSURE(!rCandidateA.isClosed() && !rCandidateB.isClosed(), "findCutsAndTouchesAndCommonForBezier only works with opened polygons (!)");
298 12050 : const sal_uInt32 nPointCountA(rCandidateA.count());
299 12050 : const sal_uInt32 nPointCountB(rCandidateB.count());
300 :
301 12050 : if(nPointCountA > 1 && nPointCountB > 1)
302 : {
303 12050 : const sal_uInt32 nEdgeCountA(nPointCountA - 1);
304 12050 : const sal_uInt32 nEdgeCountB(nPointCountB - 1);
305 12050 : B2DPoint aCurrA(rCandidateA.getB2DPoint(0L));
306 :
307 626600 : for(sal_uInt32 a(0L); a < nEdgeCountA; a++)
308 : {
309 614550 : const B2DPoint aNextA(rCandidateA.getB2DPoint(a + 1L));
310 614550 : const B2DRange aRangeA(aCurrA, aNextA);
311 1229100 : B2DPoint aCurrB(rCandidateB.getB2DPoint(0L));
312 :
313 15414750 : for(sal_uInt32 b(0L); b < nEdgeCountB; b++)
314 : {
315 14800200 : const B2DPoint aNextB(rCandidateB.getB2DPoint(b + 1L));
316 14800200 : const B2DRange aRangeB(aCurrB, aNextB);
317 :
318 14800200 : if(aRangeA.overlaps(aRangeB))
319 : {
320 : // no null length edges
321 157836 : if(!(aCurrA.equal(aNextA) || aCurrB.equal(aNextB)))
322 : {
323 157432 : const B2DVector aVecA(aNextA - aCurrA);
324 314864 : const B2DVector aVecB(aNextB - aCurrB);
325 157432 : double fCutA(aVecA.cross(aVecB));
326 :
327 157432 : if(!fTools::equalZero(fCutA))
328 : {
329 156260 : const double fZero(0.0);
330 156260 : const double fOne(1.0);
331 156260 : fCutA = (aVecB.getY() * (aCurrB.getX() - aCurrA.getX()) + aVecB.getX() * (aCurrA.getY() - aCurrB.getY())) / fCutA;
332 :
333 : // use range [0.0 .. 1.0[, thus in the loop, all direct aCurrA cuts will be registered
334 : // as 0.0 cut. The 1.0 cut will be registered in the next loop step
335 156260 : if(fTools::moreOrEqual(fCutA, fZero) && fTools::less(fCutA, fOne))
336 : {
337 : // it's a candidate, but also need to test parameter value of cut on line 2
338 : double fCutB;
339 :
340 : // choose the more precise version
341 5495 : if(fabs(aVecB.getX()) > fabs(aVecB.getY()))
342 : {
343 2584 : fCutB = (aCurrA.getX() + (fCutA * aVecA.getX()) - aCurrB.getX()) / aVecB.getX();
344 : }
345 : else
346 : {
347 2911 : fCutB = (aCurrA.getY() + (fCutA * aVecA.getY()) - aCurrB.getY()) / aVecB.getY();
348 : }
349 :
350 : // use range [0.0 .. 1.0[, thus in the loop, all direct aCurrA cuts will be registered
351 : // as 0.0 cut. The 1.0 cut will be registered in the next loop step
352 5495 : if(fTools::moreOrEqual(fCutB, fZero) && fTools::less(fCutB, fOne))
353 : {
354 : // cut is in both ranges. Add points for A and B
355 : // #i111715# use fTools::equal instead of fTools::equalZero for better accuracy
356 169 : if(fTools::equal(fCutA, fZero))
357 : {
358 : // ignore for start point in first edge; this is handled
359 : // by outer methods and would just produce a double point
360 26 : if(a)
361 : {
362 23 : rTempPointsA.push_back(temporaryPoint(aCurrA, a, 0.0));
363 : }
364 : }
365 : else
366 : {
367 143 : const B2DPoint aCutPoint(interpolate(aCurrA, aNextA, fCutA));
368 143 : rTempPointsA.push_back(temporaryPoint(aCutPoint, a, fCutA));
369 : }
370 :
371 : // #i111715# use fTools::equal instead of fTools::equalZero for better accuracy
372 169 : if(fTools::equal(fCutB, fZero))
373 : {
374 : // ignore for start point in first edge; this is handled
375 : // by outer methods and would just produce a double point
376 27 : if(b)
377 : {
378 23 : rTempPointsB.push_back(temporaryPoint(aCurrB, b, 0.0));
379 : }
380 : }
381 : else
382 : {
383 142 : const B2DPoint aCutPoint(interpolate(aCurrB, aNextB, fCutB));
384 142 : rTempPointsB.push_back(temporaryPoint(aCutPoint, b, fCutB));
385 : }
386 : }
387 : }
388 157432 : }
389 : }
390 : }
391 :
392 : // prepare next step
393 14800200 : aCurrB = aNextB;
394 14800200 : }
395 :
396 : // prepare next step
397 614550 : aCurrA = aNextA;
398 626600 : }
399 : }
400 12050 : }
401 :
402 : ////////////////////////////////////////////////////////////////////////////////
403 :
404 6487 : void findEdgeCutsBezierAndEdge(
405 : const B2DCubicBezier& rCubicA,
406 : const B2DPoint& rCurrB, const B2DPoint& rNextB,
407 : sal_uInt32 nIndA, sal_uInt32 nIndB,
408 : temporaryPointVector& rTempPointsA, temporaryPointVector& rTempPointsB)
409 : {
410 : // find all cuts between given bezier segment and edge. Add an entry to the tempPoints
411 : // for each common point with the cut value describing the relative position on given
412 : // bezier segment and edge.
413 6487 : B2DPolygon aTempPolygonA;
414 12974 : B2DPolygon aTempPolygonEdge;
415 12974 : temporaryPointVector aTempPointVectorA;
416 12974 : temporaryPointVector aTempPointVectorEdge;
417 :
418 : // create subdivided polygons and find cuts between them
419 : // Keep adaptiveSubdivideByCount due to needed quality
420 6487 : aTempPolygonA.reserve(SUBDIVIDE_FOR_CUT_TEST_COUNT + 8);
421 6487 : aTempPolygonA.append(rCubicA.getStartPoint());
422 6487 : rCubicA.adaptiveSubdivideByCount(aTempPolygonA, SUBDIVIDE_FOR_CUT_TEST_COUNT);
423 6487 : aTempPolygonEdge.append(rCurrB);
424 6487 : aTempPolygonEdge.append(rNextB);
425 :
426 : // #i76891# using findCuts recursively is not sufficient here
427 6487 : findCutsAndTouchesAndCommonForBezier(aTempPolygonA, aTempPolygonEdge, aTempPointVectorA, aTempPointVectorEdge);
428 :
429 6487 : if(!aTempPointVectorA.empty())
430 : {
431 : // adapt tempVector entries to segment
432 66 : adaptAndTransferCutsWithBezierSegment(aTempPointVectorA, aTempPolygonA, nIndA, rTempPointsA);
433 : }
434 :
435 : // append remapped tempVector entries for edge to tempPoints for edge
436 6553 : for(sal_uInt32 a(0L); a < aTempPointVectorEdge.size(); a++)
437 : {
438 66 : const temporaryPoint& rTempPoint = aTempPointVectorEdge[a];
439 66 : rTempPointsB.push_back(temporaryPoint(rTempPoint.getPoint(), nIndB, rTempPoint.getCut()));
440 6487 : }
441 6487 : }
442 :
443 : ////////////////////////////////////////////////////////////////////////////////
444 :
445 5563 : void findEdgeCutsTwoBeziers(
446 : const B2DCubicBezier& rCubicA,
447 : const B2DCubicBezier& rCubicB,
448 : sal_uInt32 nIndA, sal_uInt32 nIndB,
449 : temporaryPointVector& rTempPointsA, temporaryPointVector& rTempPointsB)
450 : {
451 : // find all cuts between the two given bezier segments. Add an entry to the tempPoints
452 : // for each common point with the cut value describing the relative position on given
453 : // bezier segments.
454 5563 : B2DPolygon aTempPolygonA;
455 11126 : B2DPolygon aTempPolygonB;
456 11126 : temporaryPointVector aTempPointVectorA;
457 11126 : temporaryPointVector aTempPointVectorB;
458 :
459 : // create subdivided polygons and find cuts between them
460 : // Keep adaptiveSubdivideByCount due to needed quality
461 5563 : aTempPolygonA.reserve(SUBDIVIDE_FOR_CUT_TEST_COUNT + 8);
462 5563 : aTempPolygonA.append(rCubicA.getStartPoint());
463 5563 : rCubicA.adaptiveSubdivideByCount(aTempPolygonA, SUBDIVIDE_FOR_CUT_TEST_COUNT);
464 5563 : aTempPolygonB.reserve(SUBDIVIDE_FOR_CUT_TEST_COUNT + 8);
465 5563 : aTempPolygonB.append(rCubicB.getStartPoint());
466 5563 : rCubicB.adaptiveSubdivideByCount(aTempPolygonB, SUBDIVIDE_FOR_CUT_TEST_COUNT);
467 :
468 : // #i76891# using findCuts recursively is not sufficient here
469 5563 : findCutsAndTouchesAndCommonForBezier(aTempPolygonA, aTempPolygonB, aTempPointVectorA, aTempPointVectorB);
470 :
471 5563 : if(!aTempPointVectorA.empty())
472 : {
473 : // adapt tempVector entries to segment
474 75 : adaptAndTransferCutsWithBezierSegment(aTempPointVectorA, aTempPolygonA, nIndA, rTempPointsA);
475 : }
476 :
477 5563 : if(!aTempPointVectorB.empty())
478 : {
479 : // adapt tempVector entries to segment
480 75 : adaptAndTransferCutsWithBezierSegment(aTempPointVectorB, aTempPolygonB, nIndB, rTempPointsB);
481 5563 : }
482 5563 : }
483 :
484 : ////////////////////////////////////////////////////////////////////////////////
485 :
486 11928 : void findEdgeCutsOneBezier(
487 : const B2DCubicBezier& rCubicA,
488 : sal_uInt32 nInd, temporaryPointVector& rTempPoints)
489 : {
490 : // avoid expensive part of this method if possible
491 : // TODO: use hasAnyExtremum() method instead when it becomes available
492 : double fDummy;
493 11928 : const bool bHasAnyExtremum = rCubicA.getMinimumExtremumPosition( fDummy );
494 11928 : if( !bHasAnyExtremum )
495 21990 : return;
496 :
497 : // find all self-intersections on the given bezier segment. Add an entry to the tempPoints
498 : // for each self intersection point with the cut value describing the relative position on given
499 : // bezier segment.
500 1866 : B2DPolygon aTempPolygon;
501 3732 : temporaryPointVector aTempPointVector;
502 :
503 : // create subdivided polygon and find cuts on it
504 : // Keep adaptiveSubdivideByCount due to needed quality
505 1866 : aTempPolygon.reserve(SUBDIVIDE_FOR_CUT_TEST_COUNT + 8);
506 1866 : aTempPolygon.append(rCubicA.getStartPoint());
507 1866 : rCubicA.adaptiveSubdivideByCount(aTempPolygon, SUBDIVIDE_FOR_CUT_TEST_COUNT);
508 1866 : findCuts(aTempPolygon, aTempPointVector);
509 :
510 1866 : if(!aTempPointVector.empty())
511 : {
512 : // adapt tempVector entries to segment
513 0 : adaptAndTransferCutsWithBezierSegment(aTempPointVector, aTempPolygon, nInd, rTempPoints);
514 1866 : }
515 : }
516 :
517 : ////////////////////////////////////////////////////////////////////////////////
518 :
519 16929 : void findCuts(const B2DPolygon& rCandidate, temporaryPointVector& rTempPoints)
520 : {
521 : // find out if there are edges with intersections (self-cuts). If yes, add
522 : // entries to rTempPoints accordingly
523 16929 : const sal_uInt32 nPointCount(rCandidate.count());
524 :
525 16929 : if(nPointCount)
526 : {
527 16929 : const sal_uInt32 nEdgeCount(rCandidate.isClosed() ? nPointCount : nPointCount - 1L);
528 :
529 16929 : if(nEdgeCount)
530 : {
531 16929 : const bool bCurvesInvolved(rCandidate.areControlPointsUsed());
532 :
533 16929 : if(bCurvesInvolved)
534 : {
535 2558 : B2DCubicBezier aCubicA;
536 5116 : B2DCubicBezier aCubicB;
537 :
538 28264 : for(sal_uInt32 a(0L); a < nEdgeCount - 1L; a++)
539 : {
540 25706 : rCandidate.getBezierSegment(a, aCubicA);
541 25706 : aCubicA.testAndSolveTrivialBezier();
542 25706 : const bool bEdgeAIsCurve(aCubicA.isBezier());
543 25706 : const B2DRange aRangeA(aCubicA.getRange());
544 :
545 25706 : if(bEdgeAIsCurve)
546 : {
547 : // curved segments may have self-intersections, do not forget those (!)
548 11928 : findEdgeCutsOneBezier(aCubicA, a, rTempPoints);
549 : }
550 :
551 418180 : for(sal_uInt32 b(a + 1L); b < nEdgeCount; b++)
552 : {
553 392474 : rCandidate.getBezierSegment(b, aCubicB);
554 392474 : aCubicB.testAndSolveTrivialBezier();
555 392474 : const B2DRange aRangeB(aCubicB.getRange());
556 :
557 : // only overlapping segments need to be tested
558 : // consecutive segments touch of course
559 392474 : bool bOverlap = false;
560 392474 : if( b > a+1)
561 366768 : bOverlap = aRangeA.overlaps(aRangeB);
562 : else
563 25706 : bOverlap = aRangeA.overlapsMore(aRangeB);
564 392474 : if( bOverlap)
565 : {
566 7728 : const bool bEdgeBIsCurve(aCubicB.isBezier());
567 7728 : if(bEdgeAIsCurve && bEdgeBIsCurve)
568 : {
569 : // test for bezier-bezier cuts
570 2498 : findEdgeCutsTwoBeziers(aCubicA, aCubicB, a, b, rTempPoints, rTempPoints);
571 : }
572 5230 : else if(bEdgeAIsCurve)
573 : {
574 : // test for bezier-edge cuts
575 1543 : findEdgeCutsBezierAndEdge(aCubicA, aCubicB.getStartPoint(), aCubicB.getEndPoint(), a, b, rTempPoints, rTempPoints);
576 : }
577 3687 : else if(bEdgeBIsCurve)
578 : {
579 : // test for bezier-edge cuts
580 1407 : findEdgeCutsBezierAndEdge(aCubicB, aCubicA.getStartPoint(), aCubicA.getEndPoint(), b, a, rTempPoints, rTempPoints);
581 : }
582 : else
583 : {
584 : // test for simple edge-edge cuts
585 : findEdgeCutsTwoEdges(aCubicA.getStartPoint(), aCubicA.getEndPoint(), aCubicB.getStartPoint(), aCubicB.getEndPoint(),
586 2280 : a, b, rTempPoints, rTempPoints);
587 : }
588 : }
589 : }
590 2558 : }
591 : }
592 : else
593 : {
594 14371 : B2DPoint aCurrA(rCandidate.getB2DPoint(0L));
595 :
596 149919 : for(sal_uInt32 a(0L); a < nEdgeCount - 1L; a++)
597 : {
598 135548 : const B2DPoint aNextA(rCandidate.getB2DPoint(a + 1L == nPointCount ? 0L : a + 1L));
599 135548 : const B2DRange aRangeA(aCurrA, aNextA);
600 271096 : B2DPoint aCurrB(rCandidate.getB2DPoint(a + 1L));
601 :
602 2619955 : for(sal_uInt32 b(a + 1L); b < nEdgeCount; b++)
603 : {
604 2484407 : const B2DPoint aNextB(rCandidate.getB2DPoint(b + 1L == nPointCount ? 0L : b + 1L));
605 2484407 : const B2DRange aRangeB(aCurrB, aNextB);
606 :
607 : // consecutive segments touch of course
608 2484407 : bool bOverlap = false;
609 2484407 : if( b > a+1)
610 2348859 : bOverlap = aRangeA.overlaps(aRangeB);
611 : else
612 135548 : bOverlap = aRangeA.overlapsMore(aRangeB);
613 2484407 : if( bOverlap)
614 : {
615 14604 : findEdgeCutsTwoEdges(aCurrA, aNextA, aCurrB, aNextB, a, b, rTempPoints, rTempPoints);
616 : }
617 :
618 : // prepare next step
619 2484407 : aCurrB = aNextB;
620 2484407 : }
621 :
622 : // prepare next step
623 135548 : aCurrA = aNextA;
624 149919 : }
625 : }
626 : }
627 : }
628 16929 : }
629 :
630 : ////////////////////////////////////////////////////////////////////////////////
631 :
632 : } // end of anonymous namespace
633 : } // end of namespace basegfx
634 :
635 : //////////////////////////////////////////////////////////////////////////////
636 :
637 : namespace basegfx
638 : {
639 : namespace
640 : {
641 : ////////////////////////////////////////////////////////////////////////////////
642 :
643 1628561 : void findTouchesOnEdge(
644 : const B2DPoint& rCurr, const B2DPoint& rNext, const B2DPolygon& rPointPolygon,
645 : sal_uInt32 nInd, temporaryPointVector& rTempPoints)
646 : {
647 : // find out if points from rPointPolygon are positioned on given edge. If Yes, add
648 : // points there to represent touches (which may be enter or leave nodes later).
649 1628561 : const sal_uInt32 nPointCount(rPointPolygon.count());
650 :
651 1628561 : if(nPointCount)
652 : {
653 1628561 : const B2DRange aRange(rCurr, rNext);
654 1628561 : const B2DVector aEdgeVector(rNext - rCurr);
655 3257122 : B2DVector aNormalizedEdgeVector(aEdgeVector);
656 1628561 : aNormalizedEdgeVector.normalize();
657 1628561 : bool bTestUsingX(fabs(aEdgeVector.getX()) > fabs(aEdgeVector.getY()));
658 :
659 34592423 : for(sal_uInt32 a(0L); a < nPointCount; a++)
660 : {
661 32963862 : const B2DPoint aTestPoint(rPointPolygon.getB2DPoint(a));
662 :
663 32963862 : if(aRange.isInside(aTestPoint))
664 : {
665 203825 : if(!aTestPoint.equal(rCurr) && !aTestPoint.equal(rNext))
666 : {
667 36905 : const B2DVector aTestVector(aTestPoint - rCurr);
668 :
669 36905 : if(areParallel(aNormalizedEdgeVector, aTestVector))
670 : {
671 : const double fCut((bTestUsingX)
672 73 : ? aTestVector.getX() / aEdgeVector.getX()
673 491 : : aTestVector.getY() / aEdgeVector.getY());
674 418 : const double fZero(0.0);
675 418 : const double fOne(1.0);
676 :
677 418 : if(fTools::more(fCut, fZero) && fTools::less(fCut, fOne))
678 : {
679 418 : rTempPoints.push_back(temporaryPoint(aTestPoint, nInd, fCut));
680 : }
681 36905 : }
682 : }
683 : }
684 34592423 : }
685 : }
686 1628561 : }
687 :
688 : ////////////////////////////////////////////////////////////////////////////////
689 :
690 29042 : void findTouchesOnCurve(
691 : const B2DCubicBezier& rCubicA, const B2DPolygon& rPointPolygon,
692 : sal_uInt32 nInd, temporaryPointVector& rTempPoints)
693 : {
694 : // find all points from rPointPolygon which touch the given bezier segment. Add an entry
695 : // for each touch to the given pointVector. The cut for that entry is the relative position on
696 : // the given bezier segment.
697 29042 : B2DPolygon aTempPolygon;
698 58084 : temporaryPointVector aTempPointVector;
699 :
700 : // create subdivided polygon and find cuts on it
701 : // Keep adaptiveSubdivideByCount due to needed quality
702 29042 : aTempPolygon.reserve(SUBDIVIDE_FOR_CUT_TEST_COUNT + 8);
703 29042 : aTempPolygon.append(rCubicA.getStartPoint());
704 29042 : rCubicA.adaptiveSubdivideByCount(aTempPolygon, SUBDIVIDE_FOR_CUT_TEST_COUNT);
705 29042 : findTouches(aTempPolygon, rPointPolygon, aTempPointVector);
706 :
707 29042 : if(!aTempPointVector.empty())
708 : {
709 : // adapt tempVector entries to segment
710 6 : adaptAndTransferCutsWithBezierSegment(aTempPointVector, aTempPolygon, nInd, rTempPoints);
711 29042 : }
712 29042 : }
713 :
714 : ////////////////////////////////////////////////////////////////////////////////
715 :
716 63187 : void findTouches(const B2DPolygon& rEdgePolygon, const B2DPolygon& rPointPolygon, temporaryPointVector& rTempPoints)
717 : {
718 : // find out if points from rPointPolygon touch edges from rEdgePolygon. If yes,
719 : // add entries to rTempPoints
720 63187 : const sal_uInt32 nPointCount(rPointPolygon.count());
721 63187 : const sal_uInt32 nEdgePointCount(rEdgePolygon.count());
722 :
723 63187 : if(nPointCount && nEdgePointCount)
724 : {
725 63187 : const sal_uInt32 nEdgeCount(rEdgePolygon.isClosed() ? nEdgePointCount : nEdgePointCount - 1L);
726 63187 : B2DPoint aCurr(rEdgePolygon.getB2DPoint(0));
727 :
728 1723936 : for(sal_uInt32 a(0L); a < nEdgeCount; a++)
729 : {
730 1660749 : const sal_uInt32 nNextIndex((a + 1) % nEdgePointCount);
731 1660749 : const B2DPoint aNext(rEdgePolygon.getB2DPoint(nNextIndex));
732 :
733 1660749 : if(!aCurr.equal(aNext))
734 : {
735 1657603 : bool bHandleAsSimpleEdge(true);
736 :
737 1657603 : if(rEdgePolygon.areControlPointsUsed())
738 : {
739 60170 : const B2DPoint aNextControlPoint(rEdgePolygon.getNextControlPoint(a));
740 120340 : const B2DPoint aPrevControlPoint(rEdgePolygon.getPrevControlPoint(nNextIndex));
741 60170 : const bool bEdgeIsCurve(!aNextControlPoint.equal(aCurr) || !aPrevControlPoint.equal(aNext));
742 :
743 60170 : if(bEdgeIsCurve)
744 : {
745 29042 : bHandleAsSimpleEdge = false;
746 29042 : const B2DCubicBezier aCubicA(aCurr, aNextControlPoint, aPrevControlPoint, aNext);
747 29042 : findTouchesOnCurve(aCubicA, rPointPolygon, a, rTempPoints);
748 60170 : }
749 : }
750 :
751 1657603 : if(bHandleAsSimpleEdge)
752 : {
753 1628561 : findTouchesOnEdge(aCurr, aNext, rPointPolygon, a, rTempPoints);
754 : }
755 : }
756 :
757 : // next step
758 1660749 : aCurr = aNext;
759 1723936 : }
760 : }
761 63187 : }
762 :
763 : ////////////////////////////////////////////////////////////////////////////////
764 :
765 : } // end of anonymous namespace
766 : } // end of namespace basegfx
767 :
768 : //////////////////////////////////////////////////////////////////////////////
769 :
770 : namespace basegfx
771 : {
772 : namespace
773 : {
774 : ////////////////////////////////////////////////////////////////////////////////
775 :
776 9541 : void findCuts(const B2DPolygon& rCandidateA, const B2DPolygon& rCandidateB, temporaryPointVector& rTempPointsA, temporaryPointVector& rTempPointsB)
777 : {
778 : // find out if edges from both polygons cut. If so, add entries to rTempPoints which
779 : // should be added to the polygons accordingly
780 9541 : const sal_uInt32 nPointCountA(rCandidateA.count());
781 9541 : const sal_uInt32 nPointCountB(rCandidateB.count());
782 :
783 9541 : if(nPointCountA && nPointCountB)
784 : {
785 9541 : const sal_uInt32 nEdgeCountA(rCandidateA.isClosed() ? nPointCountA : nPointCountA - 1L);
786 9541 : const sal_uInt32 nEdgeCountB(rCandidateB.isClosed() ? nPointCountB : nPointCountB - 1L);
787 :
788 9541 : if(nEdgeCountA && nEdgeCountB)
789 : {
790 9541 : const bool bCurvesInvolved(rCandidateA.areControlPointsUsed() || rCandidateB.areControlPointsUsed());
791 :
792 9541 : if(bCurvesInvolved)
793 : {
794 3934 : B2DCubicBezier aCubicA;
795 7868 : B2DCubicBezier aCubicB;
796 :
797 29822 : for(sal_uInt32 a(0L); a < nEdgeCountA; a++)
798 : {
799 25888 : rCandidateA.getBezierSegment(a, aCubicA);
800 25888 : aCubicA.testAndSolveTrivialBezier();
801 25888 : const bool bEdgeAIsCurve(aCubicA.isBezier());
802 25888 : const B2DRange aRangeA(aCubicA.getRange());
803 :
804 233384 : for(sal_uInt32 b(0L); b < nEdgeCountB; b++)
805 : {
806 207496 : rCandidateB.getBezierSegment(b, aCubicB);
807 207496 : aCubicB.testAndSolveTrivialBezier();
808 207496 : const B2DRange aRangeB(aCubicB.getRange());
809 :
810 : // consecutive segments touch of course
811 207496 : bool bOverlap = false;
812 207496 : if( b > a+1)
813 71770 : bOverlap = aRangeA.overlaps(aRangeB);
814 : else
815 135726 : bOverlap = aRangeA.overlapsMore(aRangeB);
816 207496 : if( bOverlap)
817 : {
818 22384 : const bool bEdgeBIsCurve(aCubicB.isBezier());
819 22384 : if(bEdgeAIsCurve && bEdgeBIsCurve)
820 : {
821 : // test for bezier-bezier cuts
822 3065 : findEdgeCutsTwoBeziers(aCubicA, aCubicB, a, b, rTempPointsA, rTempPointsB);
823 : }
824 19319 : else if(bEdgeAIsCurve)
825 : {
826 : // test for bezier-edge cuts
827 2077 : findEdgeCutsBezierAndEdge(aCubicA, aCubicB.getStartPoint(), aCubicB.getEndPoint(), a, b, rTempPointsA, rTempPointsB);
828 : }
829 17242 : else if(bEdgeBIsCurve)
830 : {
831 : // test for bezier-edge cuts
832 1460 : findEdgeCutsBezierAndEdge(aCubicB, aCubicA.getStartPoint(), aCubicA.getEndPoint(), b, a, rTempPointsB, rTempPointsA);
833 : }
834 : else
835 : {
836 : // test for simple edge-edge cuts
837 : findEdgeCutsTwoEdges(aCubicA.getStartPoint(), aCubicA.getEndPoint(), aCubicB.getStartPoint(), aCubicB.getEndPoint(),
838 15782 : a, b, rTempPointsA, rTempPointsB);
839 : }
840 : }
841 : }
842 3934 : }
843 : }
844 : else
845 : {
846 5607 : B2DPoint aCurrA(rCandidateA.getB2DPoint(0L));
847 :
848 31896 : for(sal_uInt32 a(0L); a < nEdgeCountA; a++)
849 : {
850 26289 : const B2DPoint aNextA(rCandidateA.getB2DPoint(a + 1L == nPointCountA ? 0L : a + 1L));
851 26289 : const B2DRange aRangeA(aCurrA, aNextA);
852 52578 : B2DPoint aCurrB(rCandidateB.getB2DPoint(0L));
853 :
854 141962 : for(sal_uInt32 b(0L); b < nEdgeCountB; b++)
855 : {
856 115673 : const B2DPoint aNextB(rCandidateB.getB2DPoint(b + 1L == nPointCountB ? 0L : b + 1L));
857 115673 : const B2DRange aRangeB(aCurrB, aNextB);
858 :
859 : // consecutive segments touch of course
860 115673 : bool bOverlap = false;
861 115673 : if( b > a+1)
862 22615 : bOverlap = aRangeA.overlaps(aRangeB);
863 : else
864 93058 : bOverlap = aRangeA.overlapsMore(aRangeB);
865 115673 : if( bOverlap)
866 : {
867 : // test for simple edge-edge cuts
868 24079 : findEdgeCutsTwoEdges(aCurrA, aNextA, aCurrB, aNextB, a, b, rTempPointsA, rTempPointsB);
869 : }
870 :
871 : // prepare next step
872 115673 : aCurrB = aNextB;
873 115673 : }
874 :
875 : // prepare next step
876 26289 : aCurrA = aNextA;
877 31896 : }
878 : }
879 : }
880 : }
881 9541 : }
882 :
883 : ////////////////////////////////////////////////////////////////////////////////
884 :
885 : } // end of anonymous namespace
886 : } // end of namespace basegfx
887 :
888 : //////////////////////////////////////////////////////////////////////////////
889 :
890 : namespace basegfx
891 : {
892 : namespace tools
893 : {
894 : ////////////////////////////////////////////////////////////////////////////////
895 :
896 15063 : B2DPolygon addPointsAtCutsAndTouches(const B2DPolygon& rCandidate)
897 : {
898 15063 : if(rCandidate.count())
899 : {
900 15063 : temporaryPointVector aTempPoints;
901 :
902 15063 : findTouches(rCandidate, rCandidate, aTempPoints);
903 15063 : findCuts(rCandidate, aTempPoints);
904 :
905 15063 : return mergeTemporaryPointsAndPolygon(rCandidate, aTempPoints);
906 : }
907 : else
908 : {
909 0 : return rCandidate;
910 : }
911 : }
912 :
913 : ////////////////////////////////////////////////////////////////////////////////
914 :
915 6082 : B2DPolyPolygon addPointsAtCutsAndTouches(const B2DPolyPolygon& rCandidate, bool bSelfIntersections)
916 : {
917 6082 : const sal_uInt32 nCount(rCandidate.count());
918 :
919 6082 : if(nCount)
920 : {
921 6082 : B2DPolyPolygon aRetval;
922 :
923 6082 : if(1L == nCount)
924 : {
925 45 : if(bSelfIntersections)
926 : {
927 : // remove self intersections
928 45 : aRetval.append(addPointsAtCutsAndTouches(rCandidate.getB2DPolygon(0L)));
929 : }
930 : else
931 : {
932 : // copy source
933 0 : aRetval = rCandidate;
934 : }
935 : }
936 : else
937 : {
938 : // first solve self cuts and self touches for all contained single polygons
939 6037 : temporaryPolygonData *pTempData = new temporaryPolygonData[nCount];
940 : sal_uInt32 a, b;
941 :
942 19074 : for(a = 0L; a < nCount; a++)
943 : {
944 13037 : if(bSelfIntersections)
945 : {
946 : // use polygons with solved self intersections
947 13037 : pTempData[a].setPolygon(addPointsAtCutsAndTouches(rCandidate.getB2DPolygon(a)));
948 : }
949 : else
950 : {
951 : // copy given polygons
952 0 : pTempData[a].setPolygon(rCandidate.getB2DPolygon(a));
953 : }
954 : }
955 :
956 : // now cuts and touches between the polygons
957 19074 : for(a = 0L; a < nCount; a++)
958 : {
959 66008 : for(b = 0L; b < nCount; b++)
960 : {
961 52971 : if(a != b)
962 : {
963 : // look for touches, compare each edge polygon to all other points
964 39934 : if(pTempData[a].getRange().overlaps(pTempData[b].getRange()))
965 : {
966 19082 : findTouches(pTempData[a].getPolygon(), pTempData[b].getPolygon(), pTempData[a].getTemporaryPointVector());
967 : }
968 : }
969 :
970 52971 : if(a < b)
971 : {
972 : // look for cuts, compare each edge polygon to following ones
973 19967 : if(pTempData[a].getRange().overlaps(pTempData[b].getRange()))
974 : {
975 9541 : findCuts(pTempData[a].getPolygon(), pTempData[b].getPolygon(), pTempData[a].getTemporaryPointVector(), pTempData[b].getTemporaryPointVector());
976 : }
977 : }
978 : }
979 : }
980 :
981 : // consolidate the result
982 19074 : for(a = 0L; a < nCount; a++)
983 : {
984 13037 : aRetval.append(mergeTemporaryPointsAndPolygon(pTempData[a].getPolygon(), pTempData[a].getTemporaryPointVector()));
985 : }
986 :
987 6037 : delete[] pTempData;
988 : }
989 :
990 6082 : return aRetval;
991 : }
992 : else
993 : {
994 0 : return rCandidate;
995 : }
996 : }
997 :
998 : ////////////////////////////////////////////////////////////////////////////////
999 :
1000 0 : B2DPolygon addPointsAtCuts(const B2DPolygon& rCandidate, const B2DPoint& rStart, const B2DPoint& rEnd)
1001 : {
1002 0 : const sal_uInt32 nCount(rCandidate.count());
1003 :
1004 0 : if(nCount && !rStart.equal(rEnd))
1005 : {
1006 0 : const B2DRange aPolygonRange(rCandidate.getB2DRange());
1007 0 : const B2DRange aEdgeRange(rStart, rEnd);
1008 :
1009 0 : if(aPolygonRange.overlaps(aEdgeRange))
1010 : {
1011 0 : const sal_uInt32 nEdgeCount(rCandidate.isClosed() ? nCount : nCount - 1);
1012 0 : temporaryPointVector aTempPoints;
1013 0 : temporaryPointVector aUnusedTempPoints;
1014 0 : B2DCubicBezier aCubic;
1015 :
1016 0 : for(sal_uInt32 a(0); a < nEdgeCount; a++)
1017 : {
1018 0 : rCandidate.getBezierSegment(a, aCubic);
1019 0 : B2DRange aCubicRange(aCubic.getStartPoint(), aCubic.getEndPoint());
1020 :
1021 0 : if(aCubic.isBezier())
1022 : {
1023 0 : aCubicRange.expand(aCubic.getControlPointA());
1024 0 : aCubicRange.expand(aCubic.getControlPointB());
1025 :
1026 0 : if(aCubicRange.overlaps(aEdgeRange))
1027 : {
1028 0 : findEdgeCutsBezierAndEdge(aCubic, rStart, rEnd, a, 0, aTempPoints, aUnusedTempPoints);
1029 : }
1030 : }
1031 : else
1032 : {
1033 0 : if(aCubicRange.overlaps(aEdgeRange))
1034 : {
1035 0 : findEdgeCutsTwoEdges(aCubic.getStartPoint(), aCubic.getEndPoint(), rStart, rEnd, a, 0, aTempPoints, aUnusedTempPoints);
1036 : }
1037 : }
1038 : }
1039 :
1040 0 : return mergeTemporaryPointsAndPolygon(rCandidate, aTempPoints);
1041 : }
1042 : }
1043 :
1044 0 : return rCandidate;
1045 : }
1046 :
1047 : ////////////////////////////////////////////////////////////////////////////////
1048 :
1049 756 : B2DPolygon addPointsAtCuts(const B2DPolygon& rCandidate, const B2DPolyPolygon& rPolyMask)
1050 : {
1051 756 : const sal_uInt32 nCountA(rCandidate.count());
1052 756 : const sal_uInt32 nCountM(rPolyMask.count());
1053 :
1054 756 : if(nCountA && nCountM)
1055 : {
1056 756 : const B2DRange aRangeA(rCandidate.getB2DRange());
1057 756 : const B2DRange aRangeM(rPolyMask.getB2DRange());
1058 :
1059 756 : if(aRangeA.overlaps(aRangeM))
1060 : {
1061 756 : const sal_uInt32 nEdgeCountA(rCandidate.isClosed() ? nCountA : nCountA - 1);
1062 756 : temporaryPointVector aTempPointsA;
1063 1512 : temporaryPointVector aUnusedTempPointsB;
1064 :
1065 1512 : for(sal_uInt32 m(0); m < nCountM; m++)
1066 : {
1067 756 : const B2DPolygon aMask(rPolyMask.getB2DPolygon(m));
1068 756 : const sal_uInt32 nCountB(aMask.count());
1069 :
1070 756 : if(nCountB)
1071 : {
1072 756 : B2DCubicBezier aCubicA;
1073 1512 : B2DCubicBezier aCubicB;
1074 :
1075 1512 : for(sal_uInt32 a(0); a < nEdgeCountA; a++)
1076 : {
1077 756 : rCandidate.getBezierSegment(a, aCubicA);
1078 756 : const bool bCubicAIsCurve(aCubicA.isBezier());
1079 756 : B2DRange aCubicRangeA(aCubicA.getStartPoint(), aCubicA.getEndPoint());
1080 :
1081 756 : if(bCubicAIsCurve)
1082 : {
1083 0 : aCubicRangeA.expand(aCubicA.getControlPointA());
1084 0 : aCubicRangeA.expand(aCubicA.getControlPointB());
1085 : }
1086 :
1087 3820 : for(sal_uInt32 b(0); b < nCountB; b++)
1088 : {
1089 3064 : aMask.getBezierSegment(b, aCubicB);
1090 3064 : const bool bCubicBIsCurve(aCubicB.isBezier());
1091 3064 : B2DRange aCubicRangeB(aCubicB.getStartPoint(), aCubicB.getEndPoint());
1092 :
1093 3064 : if(bCubicBIsCurve)
1094 : {
1095 0 : aCubicRangeB.expand(aCubicB.getControlPointA());
1096 0 : aCubicRangeB.expand(aCubicB.getControlPointB());
1097 : }
1098 :
1099 3064 : if(aCubicRangeA.overlaps(aCubicRangeB))
1100 : {
1101 1512 : if(bCubicAIsCurve && bCubicBIsCurve)
1102 : {
1103 0 : findEdgeCutsTwoBeziers(aCubicA, aCubicB, a, b, aTempPointsA, aUnusedTempPointsB);
1104 : }
1105 1512 : else if(bCubicAIsCurve)
1106 : {
1107 0 : findEdgeCutsBezierAndEdge(aCubicA, aCubicB.getStartPoint(), aCubicB.getEndPoint(), a, b, aTempPointsA, aUnusedTempPointsB);
1108 : }
1109 1512 : else if(bCubicBIsCurve)
1110 : {
1111 0 : findEdgeCutsBezierAndEdge(aCubicB, aCubicA.getStartPoint(), aCubicA.getEndPoint(), b, a, aUnusedTempPointsB, aTempPointsA);
1112 : }
1113 : else
1114 : {
1115 1512 : findEdgeCutsTwoEdges(aCubicA.getStartPoint(), aCubicA.getEndPoint(), aCubicB.getStartPoint(), aCubicB.getEndPoint(), a, b, aTempPointsA, aUnusedTempPointsB);
1116 : }
1117 : }
1118 : }
1119 756 : }
1120 : }
1121 756 : }
1122 :
1123 1512 : return mergeTemporaryPointsAndPolygon(rCandidate, aTempPointsA);
1124 : }
1125 : }
1126 :
1127 0 : return rCandidate;
1128 : }
1129 :
1130 : ////////////////////////////////////////////////////////////////////////////////
1131 :
1132 : } // end of namespace tools
1133 : } // end of namespace basegfx
1134 :
1135 : /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
|