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 11010 : 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 1641 : temporaryPoint(const B2DPoint& rNewPoint, sal_uInt32 nIndex, double fCut)
52 : : maPoint(rNewPoint),
53 : mnIndex(nIndex),
54 1641 : mfCut(fCut)
55 : {
56 1641 : }
57 :
58 2066 : bool operator<(const temporaryPoint& rComp) const
59 : {
60 2066 : if(mnIndex == rComp.mnIndex)
61 : {
62 612 : return (mfCut < rComp.mfCut);
63 : }
64 :
65 1454 : return (mnIndex < rComp.mnIndex);
66 : }
67 :
68 1517 : const B2DPoint& getPoint() const { return maPoint; }
69 2926 : sal_uInt32 getIndex() const { return mnIndex; }
70 0 : double getCut() const { return mfCut; }
71 : };
72 :
73 : ////////////////////////////////////////////////////////////////////////////////
74 :
75 : typedef ::std::vector< temporaryPoint > temporaryPointVector;
76 :
77 : ////////////////////////////////////////////////////////////////////////////////
78 :
79 780 : class temporaryPolygonData
80 : {
81 : B2DPolygon maPolygon;
82 : B2DRange maRange;
83 : temporaryPointVector maPoints;
84 :
85 : public:
86 1584 : const B2DPolygon& getPolygon() const { return maPolygon; }
87 390 : void setPolygon(const B2DPolygon& rNew) { maPolygon = rNew; maRange = tools::getRange(maPolygon); }
88 1260 : const B2DRange& getRange() const { return maRange; }
89 1186 : temporaryPointVector& getTemporaryPointVector() { return maPoints; }
90 : };
91 :
92 : ////////////////////////////////////////////////////////////////////////////////
93 :
94 864 : 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 864 : const sal_uInt32 nTempPointCount(rTempPoints.size());
100 :
101 864 : if(nTempPointCount)
102 : {
103 428 : B2DPolygon aRetval;
104 428 : const sal_uInt32 nCount(rCandidate.count());
105 :
106 428 : if(nCount)
107 : {
108 : // sort temp points to assure increasing fCut values and increasing indices
109 428 : ::std::sort(rTempPoints.begin(), rTempPoints.end());
110 :
111 : // prepare loop
112 428 : B2DCubicBezier aEdge;
113 428 : sal_uInt32 nNewInd(0L);
114 :
115 : // add start point
116 428 : aRetval.append(rCandidate.getB2DPoint(0));
117 :
118 2392 : for(sal_uInt32 a(0L); a < nCount; a++)
119 : {
120 : // get edge
121 1964 : rCandidate.getBezierSegment(a, aEdge);
122 :
123 1964 : if(aEdge.isBezier())
124 : {
125 : // control vectors involved for this edge
126 0 : double fLeftStart(0.0);
127 :
128 : // now add all points targeted to be at this index
129 0 : while(nNewInd < nTempPointCount && rTempPoints[nNewInd].getIndex() == a)
130 : {
131 0 : 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 0 : B2DCubicBezier aLeftPart;
137 0 : const double fRelativeSplitPoint((rTempPoint.getCut() - fLeftStart) / (1.0 - fLeftStart));
138 0 : aEdge.split(fRelativeSplitPoint, &aLeftPart, &aEdge);
139 0 : fLeftStart = rTempPoint.getCut();
140 :
141 : // add left bow
142 0 : aRetval.appendBezierSegment(aLeftPart.getControlPointA(), aLeftPart.getControlPointB(), rTempPoint.getPoint());
143 0 : }
144 :
145 : // add remaining bow
146 0 : aRetval.appendBezierSegment(aEdge.getControlPointA(), aEdge.getControlPointB(), aEdge.getEndPoint());
147 : }
148 : else
149 : {
150 : // add all points targeted to be at this index
151 5445 : while(nNewInd < nTempPointCount && rTempPoints[nNewInd].getIndex() == a)
152 : {
153 1517 : const temporaryPoint& rTempPoint = rTempPoints[nNewInd++];
154 1517 : const B2DPoint aNewPoint(rTempPoint.getPoint());
155 :
156 : // do not add points double
157 1517 : if(!aRetval.getB2DPoint(aRetval.count() - 1L).equal(aNewPoint))
158 : {
159 1514 : aRetval.append(aNewPoint);
160 : }
161 1517 : }
162 :
163 : // add edge end point
164 1964 : aRetval.append(aEdge.getEndPoint());
165 : }
166 428 : }
167 : }
168 :
169 428 : if(rCandidate.isClosed())
170 : {
171 : // set closed flag and correct last point (which is added double now).
172 366 : tools::closeWithGeometryChange(aRetval);
173 : }
174 :
175 428 : return aRetval;
176 : }
177 : else
178 : {
179 436 : return rCandidate;
180 : }
181 : }
182 :
183 : ////////////////////////////////////////////////////////////////////////////////
184 :
185 0 : 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 0 : const sal_uInt32 nTempPointCount(rPointVector.size());
194 0 : const sal_uInt32 nEdgeCount(rPolygon.count() ? rPolygon.count() - 1L : 0L);
195 :
196 0 : if(nTempPointCount && nEdgeCount)
197 : {
198 0 : for(sal_uInt32 a(0L); a < nTempPointCount; a++)
199 : {
200 0 : const temporaryPoint& rTempPoint = rPointVector[a];
201 0 : const double fCutPosInPolygon((double)rTempPoint.getIndex() + rTempPoint.getCut());
202 0 : const double fRelativeCutPos(fCutPosInPolygon / (double)nEdgeCount);
203 0 : rTempPoints.push_back(temporaryPoint(rTempPoint.getPoint(), nInd, fRelativeCutPos));
204 : }
205 : }
206 0 : }
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 1346 : 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 1346 : if(!(rCurrA.equal(rNextA) || rCurrB.equal(rNextB)))
236 : {
237 : // no common start/end points, this can be no cuts
238 1319 : if(!(rCurrB.equal(rCurrA) || rCurrB.equal(rNextA) || rNextB.equal(rCurrA) || rNextB.equal(rNextA)))
239 : {
240 880 : const B2DVector aVecA(rNextA - rCurrA);
241 880 : const B2DVector aVecB(rNextB - rCurrB);
242 880 : double fCut(aVecA.cross(aVecB));
243 :
244 880 : if(!fTools::equalZero(fCut))
245 : {
246 879 : const double fZero(0.0);
247 879 : const double fOne(1.0);
248 879 : fCut = (aVecB.getY() * (rCurrB.getX() - rCurrA.getX()) + aVecB.getX() * (rCurrA.getY() - rCurrB.getY())) / fCut;
249 :
250 879 : 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 855 : if(fabs(aVecB.getX()) > fabs(aVecB.getY()))
257 : {
258 464 : fCut2 = (rCurrA.getX() + (fCut * aVecA.getX()) - rCurrB.getX()) / aVecB.getX();
259 : }
260 : else
261 : {
262 391 : fCut2 = (rCurrA.getY() + (fCut * aVecA.getY()) - rCurrB.getY()) / aVecB.getY();
263 : }
264 :
265 855 : 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 803 : const B2DPoint aCutPoint(interpolate(rCurrA, rNextA, fCut));
271 803 : rTempPointsA.push_back(temporaryPoint(aCutPoint, nIndA, fCut));
272 803 : rTempPointsB.push_back(temporaryPoint(aCutPoint, nIndB, fCut2));
273 : }
274 : }
275 880 : }
276 : }
277 : }
278 1346 : }
279 :
280 : ////////////////////////////////////////////////////////////////////////////////
281 :
282 1 : 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 1 : const sal_uInt32 nPointCountA(rCandidateA.count());
299 1 : const sal_uInt32 nPointCountB(rCandidateB.count());
300 :
301 1 : if(nPointCountA > 1 && nPointCountB > 1)
302 : {
303 1 : const sal_uInt32 nEdgeCountA(nPointCountA - 1);
304 1 : const sal_uInt32 nEdgeCountB(nPointCountB - 1);
305 1 : B2DPoint aCurrA(rCandidateA.getB2DPoint(0L));
306 :
307 52 : for(sal_uInt32 a(0L); a < nEdgeCountA; a++)
308 : {
309 51 : const B2DPoint aNextA(rCandidateA.getB2DPoint(a + 1L));
310 51 : const B2DRange aRangeA(aCurrA, aNextA);
311 51 : B2DPoint aCurrB(rCandidateB.getB2DPoint(0L));
312 :
313 2652 : for(sal_uInt32 b(0L); b < nEdgeCountB; b++)
314 : {
315 2601 : const B2DPoint aNextB(rCandidateB.getB2DPoint(b + 1L));
316 2601 : const B2DRange aRangeB(aCurrB, aNextB);
317 :
318 2601 : if(aRangeA.overlaps(aRangeB))
319 : {
320 : // no null length edges
321 151 : if(!(aCurrA.equal(aNextA) || aCurrB.equal(aNextB)))
322 : {
323 151 : const B2DVector aVecA(aNextA - aCurrA);
324 151 : const B2DVector aVecB(aNextB - aCurrB);
325 151 : double fCutA(aVecA.cross(aVecB));
326 :
327 151 : if(!fTools::equalZero(fCutA))
328 : {
329 100 : const double fZero(0.0);
330 100 : const double fOne(1.0);
331 100 : 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 100 : 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 27 : if(fabs(aVecB.getX()) > fabs(aVecB.getY()))
342 : {
343 11 : fCutB = (aCurrA.getX() + (fCutA * aVecA.getX()) - aCurrB.getX()) / aVecB.getX();
344 : }
345 : else
346 : {
347 16 : 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 27 : 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 0 : 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 0 : if(a)
361 : {
362 0 : rTempPointsA.push_back(temporaryPoint(aCurrA, a, 0.0));
363 : }
364 : }
365 : else
366 : {
367 0 : const B2DPoint aCutPoint(interpolate(aCurrA, aNextA, fCutA));
368 0 : rTempPointsA.push_back(temporaryPoint(aCutPoint, a, fCutA));
369 : }
370 :
371 : // #i111715# use fTools::equal instead of fTools::equalZero for better accuracy
372 0 : 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 0 : if(b)
377 : {
378 0 : rTempPointsB.push_back(temporaryPoint(aCurrB, b, 0.0));
379 : }
380 : }
381 : else
382 : {
383 0 : const B2DPoint aCutPoint(interpolate(aCurrB, aNextB, fCutB));
384 0 : rTempPointsB.push_back(temporaryPoint(aCutPoint, b, fCutB));
385 : }
386 : }
387 : }
388 151 : }
389 : }
390 : }
391 :
392 : // prepare next step
393 2601 : aCurrB = aNextB;
394 2601 : }
395 :
396 : // prepare next step
397 51 : aCurrA = aNextA;
398 52 : }
399 : }
400 1 : }
401 :
402 : ////////////////////////////////////////////////////////////////////////////////
403 :
404 0 : 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 0 : B2DPolygon aTempPolygonA;
414 0 : B2DPolygon aTempPolygonEdge;
415 0 : temporaryPointVector aTempPointVectorA;
416 0 : temporaryPointVector aTempPointVectorEdge;
417 :
418 : // create subdivided polygons and find cuts between them
419 : // Keep adaptiveSubdivideByCount due to needed quality
420 0 : aTempPolygonA.reserve(SUBDIVIDE_FOR_CUT_TEST_COUNT + 8);
421 0 : aTempPolygonA.append(rCubicA.getStartPoint());
422 0 : rCubicA.adaptiveSubdivideByCount(aTempPolygonA, SUBDIVIDE_FOR_CUT_TEST_COUNT);
423 0 : aTempPolygonEdge.append(rCurrB);
424 0 : aTempPolygonEdge.append(rNextB);
425 :
426 : // #i76891# using findCuts recursively is not sufficient here
427 0 : findCutsAndTouchesAndCommonForBezier(aTempPolygonA, aTempPolygonEdge, aTempPointVectorA, aTempPointVectorEdge);
428 :
429 0 : if(!aTempPointVectorA.empty())
430 : {
431 : // adapt tempVector entries to segment
432 0 : adaptAndTransferCutsWithBezierSegment(aTempPointVectorA, aTempPolygonA, nIndA, rTempPointsA);
433 : }
434 :
435 : // append remapped tempVector entries for edge to tempPoints for edge
436 0 : for(sal_uInt32 a(0L); a < aTempPointVectorEdge.size(); a++)
437 : {
438 0 : const temporaryPoint& rTempPoint = aTempPointVectorEdge[a];
439 0 : rTempPointsB.push_back(temporaryPoint(rTempPoint.getPoint(), nIndB, rTempPoint.getCut()));
440 0 : }
441 0 : }
442 :
443 : ////////////////////////////////////////////////////////////////////////////////
444 :
445 1 : 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 1 : B2DPolygon aTempPolygonA;
455 1 : B2DPolygon aTempPolygonB;
456 1 : temporaryPointVector aTempPointVectorA;
457 1 : temporaryPointVector aTempPointVectorB;
458 :
459 : // create subdivided polygons and find cuts between them
460 : // Keep adaptiveSubdivideByCount due to needed quality
461 1 : aTempPolygonA.reserve(SUBDIVIDE_FOR_CUT_TEST_COUNT + 8);
462 1 : aTempPolygonA.append(rCubicA.getStartPoint());
463 1 : rCubicA.adaptiveSubdivideByCount(aTempPolygonA, SUBDIVIDE_FOR_CUT_TEST_COUNT);
464 1 : aTempPolygonB.reserve(SUBDIVIDE_FOR_CUT_TEST_COUNT + 8);
465 1 : aTempPolygonB.append(rCubicB.getStartPoint());
466 1 : rCubicB.adaptiveSubdivideByCount(aTempPolygonB, SUBDIVIDE_FOR_CUT_TEST_COUNT);
467 :
468 : // #i76891# using findCuts recursively is not sufficient here
469 1 : findCutsAndTouchesAndCommonForBezier(aTempPolygonA, aTempPolygonB, aTempPointVectorA, aTempPointVectorB);
470 :
471 1 : if(!aTempPointVectorA.empty())
472 : {
473 : // adapt tempVector entries to segment
474 0 : adaptAndTransferCutsWithBezierSegment(aTempPointVectorA, aTempPolygonA, nIndA, rTempPointsA);
475 : }
476 :
477 1 : if(!aTempPointVectorB.empty())
478 : {
479 : // adapt tempVector entries to segment
480 0 : adaptAndTransferCutsWithBezierSegment(aTempPointVectorB, aTempPolygonB, nIndB, rTempPointsB);
481 1 : }
482 1 : }
483 :
484 : ////////////////////////////////////////////////////////////////////////////////
485 :
486 2 : 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 2 : const bool bHasAnyExtremum = rCubicA.getMinimumExtremumPosition( fDummy );
494 2 : if( !bHasAnyExtremum )
495 2 : 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 2 : B2DPolygon aTempPolygon;
501 2 : temporaryPointVector aTempPointVector;
502 :
503 : // create subdivided polygon and find cuts on it
504 : // Keep adaptiveSubdivideByCount due to needed quality
505 2 : aTempPolygon.reserve(SUBDIVIDE_FOR_CUT_TEST_COUNT + 8);
506 2 : aTempPolygon.append(rCubicA.getStartPoint());
507 2 : rCubicA.adaptiveSubdivideByCount(aTempPolygon, SUBDIVIDE_FOR_CUT_TEST_COUNT);
508 2 : findCuts(aTempPolygon, aTempPointVector);
509 :
510 2 : if(!aTempPointVector.empty())
511 : {
512 : // adapt tempVector entries to segment
513 0 : adaptAndTransferCutsWithBezierSegment(aTempPointVector, aTempPolygon, nInd, rTempPoints);
514 2 : }
515 : }
516 :
517 : ////////////////////////////////////////////////////////////////////////////////
518 :
519 406 : 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 406 : const sal_uInt32 nPointCount(rCandidate.count());
524 :
525 406 : if(nPointCount)
526 : {
527 406 : const sal_uInt32 nEdgeCount(rCandidate.isClosed() ? nPointCount : nPointCount - 1L);
528 :
529 406 : if(nEdgeCount)
530 : {
531 406 : const bool bCurvesInvolved(rCandidate.areControlPointsUsed());
532 :
533 406 : if(bCurvesInvolved)
534 : {
535 2 : B2DCubicBezier aCubicA;
536 2 : B2DCubicBezier aCubicB;
537 :
538 14 : for(sal_uInt32 a(0L); a < nEdgeCount - 1L; a++)
539 : {
540 12 : rCandidate.getBezierSegment(a, aCubicA);
541 12 : aCubicA.testAndSolveTrivialBezier();
542 12 : const bool bEdgeAIsCurve(aCubicA.isBezier());
543 12 : const B2DRange aRangeA(aCubicA.getRange());
544 :
545 12 : if(bEdgeAIsCurve)
546 : {
547 : // curved segments may have self-intersections, do not forget those (!)
548 2 : findEdgeCutsOneBezier(aCubicA, a, rTempPoints);
549 : }
550 :
551 55 : for(sal_uInt32 b(a + 1L); b < nEdgeCount; b++)
552 : {
553 43 : rCandidate.getBezierSegment(b, aCubicB);
554 43 : aCubicB.testAndSolveTrivialBezier();
555 43 : const B2DRange aRangeB(aCubicB.getRange());
556 :
557 : // only overlapping segments need to be tested
558 : // consecutive segments touch of course
559 43 : bool bOverlap = false;
560 43 : if( b > a+1)
561 31 : bOverlap = aRangeA.overlaps(aRangeB);
562 : else
563 12 : bOverlap = aRangeA.overlapsMore(aRangeB);
564 43 : if( bOverlap)
565 : {
566 5 : const bool bEdgeBIsCurve(aCubicB.isBezier());
567 5 : if(bEdgeAIsCurve && bEdgeBIsCurve)
568 : {
569 : // test for bezier-bezier cuts
570 0 : findEdgeCutsTwoBeziers(aCubicA, aCubicB, a, b, rTempPoints, rTempPoints);
571 : }
572 5 : else if(bEdgeAIsCurve)
573 : {
574 : // test for bezier-edge cuts
575 0 : findEdgeCutsBezierAndEdge(aCubicA, aCubicB.getStartPoint(), aCubicB.getEndPoint(), a, b, rTempPoints, rTempPoints);
576 : }
577 5 : else if(bEdgeBIsCurve)
578 : {
579 : // test for bezier-edge cuts
580 0 : 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 5 : a, b, rTempPoints, rTempPoints);
587 : }
588 : }
589 : }
590 2 : }
591 : }
592 : else
593 : {
594 404 : B2DPoint aCurrA(rCandidate.getB2DPoint(0L));
595 :
596 2146 : for(sal_uInt32 a(0L); a < nEdgeCount - 1L; a++)
597 : {
598 1742 : const B2DPoint aNextA(rCandidate.getB2DPoint(a + 1L == nPointCount ? 0L : a + 1L));
599 1742 : const B2DRange aRangeA(aCurrA, aNextA);
600 1742 : B2DPoint aCurrB(rCandidate.getB2DPoint(a + 1L));
601 :
602 8980 : for(sal_uInt32 b(a + 1L); b < nEdgeCount; b++)
603 : {
604 7238 : const B2DPoint aNextB(rCandidate.getB2DPoint(b + 1L == nPointCount ? 0L : b + 1L));
605 7238 : const B2DRange aRangeB(aCurrB, aNextB);
606 :
607 : // consecutive segments touch of course
608 7238 : bool bOverlap = false;
609 7238 : if( b > a+1)
610 5496 : bOverlap = aRangeA.overlaps(aRangeB);
611 : else
612 1742 : bOverlap = aRangeA.overlapsMore(aRangeB);
613 7238 : if( bOverlap)
614 : {
615 430 : findEdgeCutsTwoEdges(aCurrA, aNextA, aCurrB, aNextB, a, b, rTempPoints, rTempPoints);
616 : }
617 :
618 : // prepare next step
619 7238 : aCurrB = aNextB;
620 7238 : }
621 :
622 : // prepare next step
623 1742 : aCurrA = aNextA;
624 2146 : }
625 : }
626 : }
627 : }
628 406 : }
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 4242 : 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 4242 : const sal_uInt32 nPointCount(rPointPolygon.count());
650 :
651 4242 : if(nPointCount)
652 : {
653 4242 : const B2DRange aRange(rCurr, rNext);
654 4242 : const B2DVector aEdgeVector(rNext - rCurr);
655 4242 : B2DVector aNormalizedEdgeVector(aEdgeVector);
656 4242 : aNormalizedEdgeVector.normalize();
657 4242 : bool bTestUsingX(fabs(aEdgeVector.getX()) > fabs(aEdgeVector.getY()));
658 :
659 26991 : for(sal_uInt32 a(0L); a < nPointCount; a++)
660 : {
661 22749 : const B2DPoint aTestPoint(rPointPolygon.getB2DPoint(a));
662 :
663 22749 : if(aRange.isInside(aTestPoint))
664 : {
665 4662 : if(!aTestPoint.equal(rCurr) && !aTestPoint.equal(rNext))
666 : {
667 302 : const B2DVector aTestVector(aTestPoint - rCurr);
668 :
669 302 : if(areParallel(aNormalizedEdgeVector, aTestVector))
670 : {
671 : const double fCut((bTestUsingX)
672 13 : ? aTestVector.getX() / aEdgeVector.getX()
673 48 : : aTestVector.getY() / aEdgeVector.getY());
674 35 : const double fZero(0.0);
675 35 : const double fOne(1.0);
676 :
677 35 : if(fTools::more(fCut, fZero) && fTools::less(fCut, fOne))
678 : {
679 35 : rTempPoints.push_back(temporaryPoint(aTestPoint, nInd, fCut));
680 : }
681 302 : }
682 : }
683 : }
684 26991 : }
685 : }
686 4242 : }
687 :
688 : ////////////////////////////////////////////////////////////////////////////////
689 :
690 4 : 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 4 : B2DPolygon aTempPolygon;
698 4 : temporaryPointVector aTempPointVector;
699 :
700 : // create subdivided polygon and find cuts on it
701 : // Keep adaptiveSubdivideByCount due to needed quality
702 4 : aTempPolygon.reserve(SUBDIVIDE_FOR_CUT_TEST_COUNT + 8);
703 4 : aTempPolygon.append(rCubicA.getStartPoint());
704 4 : rCubicA.adaptiveSubdivideByCount(aTempPolygon, SUBDIVIDE_FOR_CUT_TEST_COUNT);
705 4 : findTouches(aTempPolygon, rPointPolygon, aTempPointVector);
706 :
707 4 : if(!aTempPointVector.empty())
708 : {
709 : // adapt tempVector entries to segment
710 0 : adaptAndTransferCutsWithBezierSegment(aTempPointVector, aTempPolygon, nInd, rTempPoints);
711 4 : }
712 4 : }
713 :
714 : ////////////////////////////////////////////////////////////////////////////////
715 :
716 806 : 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 806 : const sal_uInt32 nPointCount(rPointPolygon.count());
721 806 : const sal_uInt32 nEdgePointCount(rEdgePolygon.count());
722 :
723 806 : if(nPointCount && nEdgePointCount)
724 : {
725 806 : const sal_uInt32 nEdgeCount(rEdgePolygon.isClosed() ? nEdgePointCount : nEdgePointCount - 1L);
726 806 : B2DPoint aCurr(rEdgePolygon.getB2DPoint(0));
727 :
728 5085 : for(sal_uInt32 a(0L); a < nEdgeCount; a++)
729 : {
730 4279 : const sal_uInt32 nNextIndex((a + 1) % nEdgePointCount);
731 4279 : const B2DPoint aNext(rEdgePolygon.getB2DPoint(nNextIndex));
732 :
733 4279 : if(!aCurr.equal(aNext))
734 : {
735 4246 : bool bHandleAsSimpleEdge(true);
736 :
737 4246 : if(rEdgePolygon.areControlPointsUsed())
738 : {
739 28 : const B2DPoint aNextControlPoint(rEdgePolygon.getNextControlPoint(a));
740 28 : const B2DPoint aPrevControlPoint(rEdgePolygon.getPrevControlPoint(nNextIndex));
741 28 : const bool bEdgeIsCurve(!aNextControlPoint.equal(aCurr) || !aPrevControlPoint.equal(aNext));
742 :
743 28 : if(bEdgeIsCurve)
744 : {
745 4 : bHandleAsSimpleEdge = false;
746 4 : const B2DCubicBezier aCubicA(aCurr, aNextControlPoint, aPrevControlPoint, aNext);
747 4 : findTouchesOnCurve(aCubicA, rPointPolygon, a, rTempPoints);
748 28 : }
749 : }
750 :
751 4246 : if(bHandleAsSimpleEdge)
752 : {
753 4242 : findTouchesOnEdge(aCurr, aNext, rPointPolygon, a, rTempPoints);
754 : }
755 : }
756 :
757 : // next step
758 4279 : aCurr = aNext;
759 5085 : }
760 : }
761 806 : }
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 199 : 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 199 : const sal_uInt32 nPointCountA(rCandidateA.count());
781 199 : const sal_uInt32 nPointCountB(rCandidateB.count());
782 :
783 199 : if(nPointCountA && nPointCountB)
784 : {
785 199 : const sal_uInt32 nEdgeCountA(rCandidateA.isClosed() ? nPointCountA : nPointCountA - 1L);
786 199 : const sal_uInt32 nEdgeCountB(rCandidateB.isClosed() ? nPointCountB : nPointCountB - 1L);
787 :
788 199 : if(nEdgeCountA && nEdgeCountB)
789 : {
790 199 : const bool bCurvesInvolved(rCandidateA.areControlPointsUsed() || rCandidateB.areControlPointsUsed());
791 :
792 199 : if(bCurvesInvolved)
793 : {
794 1 : B2DCubicBezier aCubicA;
795 1 : B2DCubicBezier aCubicB;
796 :
797 7 : for(sal_uInt32 a(0L); a < nEdgeCountA; a++)
798 : {
799 6 : rCandidateA.getBezierSegment(a, aCubicA);
800 6 : aCubicA.testAndSolveTrivialBezier();
801 6 : const bool bEdgeAIsCurve(aCubicA.isBezier());
802 6 : const B2DRange aRangeA(aCubicA.getRange());
803 :
804 54 : for(sal_uInt32 b(0L); b < nEdgeCountB; b++)
805 : {
806 48 : rCandidateB.getBezierSegment(b, aCubicB);
807 48 : aCubicB.testAndSolveTrivialBezier();
808 48 : const B2DRange aRangeB(aCubicB.getRange());
809 :
810 : // consecutive segments touch of course
811 48 : bool bOverlap = false;
812 48 : if( b > a+1)
813 21 : bOverlap = aRangeA.overlaps(aRangeB);
814 : else
815 27 : bOverlap = aRangeA.overlapsMore(aRangeB);
816 48 : if( bOverlap)
817 : {
818 9 : const bool bEdgeBIsCurve(aCubicB.isBezier());
819 9 : if(bEdgeAIsCurve && bEdgeBIsCurve)
820 : {
821 : // test for bezier-bezier cuts
822 1 : findEdgeCutsTwoBeziers(aCubicA, aCubicB, a, b, rTempPointsA, rTempPointsB);
823 : }
824 8 : else if(bEdgeAIsCurve)
825 : {
826 : // test for bezier-edge cuts
827 0 : findEdgeCutsBezierAndEdge(aCubicA, aCubicB.getStartPoint(), aCubicB.getEndPoint(), a, b, rTempPointsA, rTempPointsB);
828 : }
829 8 : else if(bEdgeBIsCurve)
830 : {
831 : // test for bezier-edge cuts
832 0 : 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 8 : a, b, rTempPointsA, rTempPointsB);
839 : }
840 : }
841 : }
842 1 : }
843 : }
844 : else
845 : {
846 198 : B2DPoint aCurrA(rCandidateA.getB2DPoint(0L));
847 :
848 1372 : for(sal_uInt32 a(0L); a < nEdgeCountA; a++)
849 : {
850 1174 : const B2DPoint aNextA(rCandidateA.getB2DPoint(a + 1L == nPointCountA ? 0L : a + 1L));
851 1174 : const B2DRange aRangeA(aCurrA, aNextA);
852 1174 : B2DPoint aCurrB(rCandidateB.getB2DPoint(0L));
853 :
854 6122 : for(sal_uInt32 b(0L); b < nEdgeCountB; b++)
855 : {
856 4948 : const B2DPoint aNextB(rCandidateB.getB2DPoint(b + 1L == nPointCountB ? 0L : b + 1L));
857 4948 : const B2DRange aRangeB(aCurrB, aNextB);
858 :
859 : // consecutive segments touch of course
860 4948 : bool bOverlap = false;
861 4948 : if( b > a+1)
862 792 : bOverlap = aRangeA.overlaps(aRangeB);
863 : else
864 4156 : bOverlap = aRangeA.overlapsMore(aRangeB);
865 4948 : if( bOverlap)
866 : {
867 : // test for simple edge-edge cuts
868 763 : findEdgeCutsTwoEdges(aCurrA, aNextA, aCurrB, aNextB, a, b, rTempPointsA, rTempPointsB);
869 : }
870 :
871 : // prepare next step
872 4948 : aCurrB = aNextB;
873 4948 : }
874 :
875 : // prepare next step
876 1174 : aCurrA = aNextA;
877 1372 : }
878 : }
879 : }
880 : }
881 199 : }
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 404 : B2DPolygon addPointsAtCutsAndTouches(const B2DPolygon& rCandidate)
897 : {
898 404 : if(rCandidate.count())
899 : {
900 404 : temporaryPointVector aTempPoints;
901 :
902 404 : findTouches(rCandidate, rCandidate, aTempPoints);
903 404 : findCuts(rCandidate, aTempPoints);
904 :
905 404 : return mergeTemporaryPointsAndPolygon(rCandidate, aTempPoints);
906 : }
907 : else
908 : {
909 0 : return rCandidate;
910 : }
911 : }
912 :
913 : ////////////////////////////////////////////////////////////////////////////////
914 :
915 197 : B2DPolyPolygon addPointsAtCutsAndTouches(const B2DPolyPolygon& rCandidate, bool bSelfIntersections)
916 : {
917 197 : const sal_uInt32 nCount(rCandidate.count());
918 :
919 197 : if(nCount)
920 : {
921 197 : B2DPolyPolygon aRetval;
922 :
923 197 : if(1L == nCount)
924 : {
925 6 : if(bSelfIntersections)
926 : {
927 : // remove self intersections
928 6 : 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 191 : temporaryPolygonData *pTempData = new temporaryPolygonData[nCount];
940 : sal_uInt32 a, b;
941 :
942 581 : for(a = 0L; a < nCount; a++)
943 : {
944 390 : if(bSelfIntersections)
945 : {
946 : // use polygons with solved self intersections
947 390 : 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 581 : for(a = 0L; a < nCount; a++)
958 : {
959 1200 : for(b = 0L; b < nCount; b++)
960 : {
961 810 : if(a != b)
962 : {
963 : // look for touches, compare each edge polygon to all other points
964 420 : if(pTempData[a].getRange().overlaps(pTempData[b].getRange()))
965 : {
966 398 : findTouches(pTempData[a].getPolygon(), pTempData[b].getPolygon(), pTempData[a].getTemporaryPointVector());
967 : }
968 : }
969 :
970 810 : if(a < b)
971 : {
972 : // look for cuts, compare each edge polygon to following ones
973 210 : if(pTempData[a].getRange().overlaps(pTempData[b].getRange()))
974 : {
975 199 : findCuts(pTempData[a].getPolygon(), pTempData[b].getPolygon(), pTempData[a].getTemporaryPointVector(), pTempData[b].getTemporaryPointVector());
976 : }
977 : }
978 : }
979 : }
980 :
981 : // consolidate the result
982 581 : for(a = 0L; a < nCount; a++)
983 : {
984 390 : aRetval.append(mergeTemporaryPointsAndPolygon(pTempData[a].getPolygon(), pTempData[a].getTemporaryPointVector()));
985 : }
986 :
987 191 : delete[] pTempData;
988 : }
989 :
990 197 : 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 70 : B2DPolygon addPointsAtCuts(const B2DPolygon& rCandidate, const B2DPolyPolygon& rPolyMask)
1050 : {
1051 70 : const sal_uInt32 nCountA(rCandidate.count());
1052 70 : const sal_uInt32 nCountM(rPolyMask.count());
1053 :
1054 70 : if(nCountA && nCountM)
1055 : {
1056 70 : const B2DRange aRangeA(rCandidate.getB2DRange());
1057 70 : const B2DRange aRangeM(rPolyMask.getB2DRange());
1058 :
1059 70 : if(aRangeA.overlaps(aRangeM))
1060 : {
1061 70 : const sal_uInt32 nEdgeCountA(rCandidate.isClosed() ? nCountA : nCountA - 1);
1062 70 : temporaryPointVector aTempPointsA;
1063 70 : temporaryPointVector aUnusedTempPointsB;
1064 :
1065 140 : for(sal_uInt32 m(0); m < nCountM; m++)
1066 : {
1067 70 : const B2DPolygon aMask(rPolyMask.getB2DPolygon(m));
1068 70 : const sal_uInt32 nCountB(aMask.count());
1069 :
1070 70 : if(nCountB)
1071 : {
1072 70 : B2DCubicBezier aCubicA;
1073 70 : B2DCubicBezier aCubicB;
1074 :
1075 140 : for(sal_uInt32 a(0); a < nEdgeCountA; a++)
1076 : {
1077 70 : rCandidate.getBezierSegment(a, aCubicA);
1078 70 : const bool bCubicAIsCurve(aCubicA.isBezier());
1079 70 : B2DRange aCubicRangeA(aCubicA.getStartPoint(), aCubicA.getEndPoint());
1080 :
1081 70 : if(bCubicAIsCurve)
1082 : {
1083 0 : aCubicRangeA.expand(aCubicA.getControlPointA());
1084 0 : aCubicRangeA.expand(aCubicA.getControlPointB());
1085 : }
1086 :
1087 490 : for(sal_uInt32 b(0); b < nCountB; b++)
1088 : {
1089 420 : aMask.getBezierSegment(b, aCubicB);
1090 420 : const bool bCubicBIsCurve(aCubicB.isBezier());
1091 420 : B2DRange aCubicRangeB(aCubicB.getStartPoint(), aCubicB.getEndPoint());
1092 :
1093 420 : if(bCubicBIsCurve)
1094 : {
1095 0 : aCubicRangeB.expand(aCubicB.getControlPointA());
1096 0 : aCubicRangeB.expand(aCubicB.getControlPointB());
1097 : }
1098 :
1099 420 : if(aCubicRangeA.overlaps(aCubicRangeB))
1100 : {
1101 140 : if(bCubicAIsCurve && bCubicBIsCurve)
1102 : {
1103 0 : findEdgeCutsTwoBeziers(aCubicA, aCubicB, a, b, aTempPointsA, aUnusedTempPointsB);
1104 : }
1105 140 : else if(bCubicAIsCurve)
1106 : {
1107 0 : findEdgeCutsBezierAndEdge(aCubicA, aCubicB.getStartPoint(), aCubicB.getEndPoint(), a, b, aTempPointsA, aUnusedTempPointsB);
1108 : }
1109 140 : else if(bCubicBIsCurve)
1110 : {
1111 0 : findEdgeCutsBezierAndEdge(aCubicB, aCubicA.getStartPoint(), aCubicA.getEndPoint(), b, a, aUnusedTempPointsB, aTempPointsA);
1112 : }
1113 : else
1114 : {
1115 140 : findEdgeCutsTwoEdges(aCubicA.getStartPoint(), aCubicA.getEndPoint(), aCubicB.getStartPoint(), aCubicB.getEndPoint(), a, b, aTempPointsA, aUnusedTempPointsB);
1116 : }
1117 : }
1118 : }
1119 70 : }
1120 : }
1121 70 : }
1122 :
1123 70 : 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: */
|
