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