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