Version 6.4.0.0.beta1, tag libreoffice-6.4.0.0.beta1
[LibreOffice.git] / basegfx / source / polygon / b2dpolygoncutandtouch.cxx
blob0fd59291604e970051eadfb06db1b13a24e5757f
1 /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
2 /*
3 * This file is part of the LibreOffice project.
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/.
9 * This file incorporates work covered by the following license notice:
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 .
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/curve/b2dcubicbezier.hxx>
29 #include <vector>
30 #include <algorithm>
31 #include <memory>
33 #define SUBDIVIDE_FOR_CUT_TEST_COUNT (50)
35 namespace basegfx
37 namespace
40 class temporaryPoint
42 B2DPoint maPoint; // the new point
43 sal_uInt32 mnIndex; // index after which to insert
44 double mfCut; // parametric cut description [0.0 .. 1.0]
46 public:
47 temporaryPoint(const B2DPoint& rNewPoint, sal_uInt32 nIndex, double fCut)
48 : maPoint(rNewPoint),
49 mnIndex(nIndex),
50 mfCut(fCut)
54 bool operator<(const temporaryPoint& rComp) const
56 if(mnIndex == rComp.mnIndex)
58 return (mfCut < rComp.mfCut);
61 return (mnIndex < rComp.mnIndex);
64 const B2DPoint& getPoint() const { return maPoint; }
65 sal_uInt32 getIndex() const { return mnIndex; }
66 double getCut() const { return mfCut; }
69 typedef std::vector< temporaryPoint > temporaryPointVector;
71 class temporaryPolygonData
73 B2DPolygon maPolygon;
74 B2DRange maRange;
75 temporaryPointVector maPoints;
77 public:
78 const B2DPolygon& getPolygon() const { return maPolygon; }
79 void setPolygon(const B2DPolygon& rNew) { maPolygon = rNew; maRange = utils::getRange(maPolygon); }
80 const B2DRange& getRange() const { return maRange; }
81 temporaryPointVector& getTemporaryPointVector() { return maPoints; }
84 B2DPolygon mergeTemporaryPointsAndPolygon(const B2DPolygon& rCandidate, temporaryPointVector& rTempPoints)
86 // #i76891# mergeTemporaryPointsAndPolygon redesigned to be able to correctly handle
87 // single edges with/without control points
88 // #i101491# added counter for non-changing element count
89 const sal_uInt32 nTempPointCount(rTempPoints.size());
91 if(nTempPointCount)
93 B2DPolygon aRetval;
94 const sal_uInt32 nCount(rCandidate.count());
96 if(nCount)
98 // sort temp points to assure increasing fCut values and increasing indices
99 std::sort(rTempPoints.begin(), rTempPoints.end());
101 // prepare loop
102 B2DCubicBezier aEdge;
103 sal_uInt32 nNewInd(0);
105 // add start point
106 aRetval.append(rCandidate.getB2DPoint(0));
108 for(sal_uInt32 a(0); a < nCount; a++)
110 // get edge
111 rCandidate.getBezierSegment(a, aEdge);
113 if(aEdge.isBezier())
115 // control vectors involved for this edge
116 double fLeftStart(0.0);
118 // now add all points targeted to be at this index
119 while (nNewInd < nTempPointCount && rTempPoints[nNewInd].getIndex() == a && fLeftStart < 1.0)
121 const temporaryPoint& rTempPoint = rTempPoints[nNewInd++];
123 // split curve segment. Splits need to come sorted and need to be < 1.0. Also,
124 // since original segment is consumed from left to right, the cut values need
125 // to be scaled to the remaining part
126 B2DCubicBezier aLeftPart;
127 const double fRelativeSplitPoint((rTempPoint.getCut() - fLeftStart) / (1.0 - fLeftStart));
128 aEdge.split(fRelativeSplitPoint, &aLeftPart, &aEdge);
129 fLeftStart = rTempPoint.getCut();
131 // add left bow
132 aRetval.appendBezierSegment(aLeftPart.getControlPointA(), aLeftPart.getControlPointB(), rTempPoint.getPoint());
135 // add remaining bow
136 aRetval.appendBezierSegment(aEdge.getControlPointA(), aEdge.getControlPointB(), aEdge.getEndPoint());
138 else
140 // add all points targeted to be at this index
141 while(nNewInd < nTempPointCount && rTempPoints[nNewInd].getIndex() == a)
143 const temporaryPoint& rTempPoint = rTempPoints[nNewInd++];
144 const B2DPoint& aNewPoint(rTempPoint.getPoint());
146 // do not add points double
147 if(!aRetval.getB2DPoint(aRetval.count() - 1).equal(aNewPoint))
149 aRetval.append(aNewPoint);
153 // add edge end point
154 aRetval.append(aEdge.getEndPoint());
159 if(rCandidate.isClosed())
161 // set closed flag and correct last point (which is added double now).
162 utils::closeWithGeometryChange(aRetval);
165 return aRetval;
167 else
169 return rCandidate;
173 void adaptAndTransferCutsWithBezierSegment(
174 const temporaryPointVector& rPointVector, const B2DPolygon& rPolygon,
175 sal_uInt32 nInd, temporaryPointVector& rTempPoints)
177 // assuming that the subdivision to create rPolygon used equidistant pieces
178 // (as in adaptiveSubdivideByCount) it is now possible to calculate back the
179 // cut positions in the polygon to relative cut positions on the original bezier
180 // segment.
181 const sal_uInt32 nTempPointCount(rPointVector.size());
182 const sal_uInt32 nEdgeCount(rPolygon.count() ? rPolygon.count() - 1 : 0);
184 if(nTempPointCount && nEdgeCount)
186 for(sal_uInt32 a(0); a < nTempPointCount; a++)
188 const temporaryPoint& rTempPoint = rPointVector[a];
189 const double fCutPosInPolygon(static_cast<double>(rTempPoint.getIndex()) + rTempPoint.getCut());
190 const double fRelativeCutPos(fCutPosInPolygon / static_cast<double>(nEdgeCount));
191 rTempPoints.emplace_back(rTempPoint.getPoint(), nInd, fRelativeCutPos);
196 } // end of anonymous namespace
197 } // end of namespace basegfx
199 namespace basegfx
201 namespace
204 // predefines for calls to this methods before method implementation
206 void findCuts(const B2DPolygon& rCandidate, temporaryPointVector& rTempPoints);
207 void findTouches(const B2DPolygon& rEdgePolygon, const B2DPolygon& rPointPolygon, temporaryPointVector& rTempPoints);
208 void findCuts(const B2DPolygon& rCandidateA, const B2DPolygon& rCandidateB, temporaryPointVector& rTempPointsA, temporaryPointVector& rTempPointsB);
210 void findEdgeCutsTwoEdges(
211 const B2DPoint& rCurrA, const B2DPoint& rNextA,
212 const B2DPoint& rCurrB, const B2DPoint& rNextB,
213 sal_uInt32 nIndA, sal_uInt32 nIndB,
214 temporaryPointVector& rTempPointsA, temporaryPointVector& rTempPointsB)
216 // no null length edges
217 if(!(rCurrA.equal(rNextA) || rCurrB.equal(rNextB)))
219 // no common start/end points, this can be no cuts
220 if(!(rCurrB.equal(rCurrA) || rCurrB.equal(rNextA) || rNextB.equal(rCurrA) || rNextB.equal(rNextA)))
222 const B2DVector aVecA(rNextA - rCurrA);
223 const B2DVector aVecB(rNextB - rCurrB);
224 double fCut(aVecA.cross(aVecB));
226 if(!fTools::equalZero(fCut))
228 const double fZero(0.0);
229 const double fOne(1.0);
230 fCut = (aVecB.getY() * (rCurrB.getX() - rCurrA.getX()) + aVecB.getX() * (rCurrA.getY() - rCurrB.getY())) / fCut;
232 if (fTools::betweenOrEqualEither(fCut, fZero, fOne))
234 // it's a candidate, but also need to test parameter value of cut on line 2
235 double fCut2;
237 // choose the more precise version
238 if(fabs(aVecB.getX()) > fabs(aVecB.getY()))
240 fCut2 = (rCurrA.getX() + (fCut * aVecA.getX()) - rCurrB.getX()) / aVecB.getX();
242 else
244 fCut2 = (rCurrA.getY() + (fCut * aVecA.getY()) - rCurrB.getY()) / aVecB.getY();
247 if (fTools::betweenOrEqualEither(fCut2, fZero, fOne))
249 // cut is in range, add point. Two edges can have only one cut, but
250 // add a cut point to each list. The lists may be the same for
251 // self intersections.
252 const B2DPoint aCutPoint(interpolate(rCurrA, rNextA, fCut));
253 rTempPointsA.emplace_back(aCutPoint, nIndA, fCut);
254 rTempPointsB.emplace_back(aCutPoint, nIndB, fCut2);
262 void findCutsAndTouchesAndCommonForBezier(const B2DPolygon& rCandidateA, const B2DPolygon& rCandidateB, temporaryPointVector& rTempPointsA, temporaryPointVector& rTempPointsB)
264 // #i76891#
265 // This new method is necessary since in findEdgeCutsBezierAndEdge and in findEdgeCutsTwoBeziers
266 // it is not sufficient to use findCuts() recursively. This will indeed find the cuts between the
267 // segments of the two temporarily adaptive subdivided bezier segments, but not the touches or
268 // equal points of them.
269 // It would be possible to find the touches using findTouches(), but at last with common points
270 // the adding of cut points (temporary points) would fail. But for these temporarily adaptive
271 // subdivided bezier segments, common points may be not very likely, but the bug shows that it
272 // happens.
273 // Touch points are a little bit more likely than common points. All in all it is best to use
274 // a specialized method here which can profit from knowing that it is working on a special
275 // family of B2DPolygons: no curve segments included and not closed.
276 OSL_ENSURE(!rCandidateA.areControlPointsUsed() && !rCandidateB.areControlPointsUsed(), "findCutsAndTouchesAndCommonForBezier only works with subdivided polygons (!)");
277 OSL_ENSURE(!rCandidateA.isClosed() && !rCandidateB.isClosed(), "findCutsAndTouchesAndCommonForBezier only works with opened polygons (!)");
278 const sal_uInt32 nPointCountA(rCandidateA.count());
279 const sal_uInt32 nPointCountB(rCandidateB.count());
281 if(nPointCountA > 1 && nPointCountB > 1)
283 const sal_uInt32 nEdgeCountA(nPointCountA - 1);
284 const sal_uInt32 nEdgeCountB(nPointCountB - 1);
285 B2DPoint aCurrA(rCandidateA.getB2DPoint(0));
287 for(sal_uInt32 a(0); a < nEdgeCountA; a++)
289 const B2DPoint aNextA(rCandidateA.getB2DPoint(a + 1));
290 const B2DRange aRangeA(aCurrA, aNextA);
291 B2DPoint aCurrB(rCandidateB.getB2DPoint(0));
293 for(sal_uInt32 b(0); b < nEdgeCountB; b++)
295 const B2DPoint aNextB(rCandidateB.getB2DPoint(b + 1));
296 const B2DRange aRangeB(aCurrB, aNextB);
298 if(aRangeA.overlaps(aRangeB))
300 // no null length edges
301 if(!(aCurrA.equal(aNextA) || aCurrB.equal(aNextB)))
303 const B2DVector aVecA(aNextA - aCurrA);
304 const B2DVector aVecB(aNextB - aCurrB);
305 double fCutA(aVecA.cross(aVecB));
307 if(!fTools::equalZero(fCutA))
309 const double fZero(0.0);
310 const double fOne(1.0);
311 fCutA = (aVecB.getY() * (aCurrB.getX() - aCurrA.getX()) + aVecB.getX() * (aCurrA.getY() - aCurrB.getY())) / fCutA;
313 // use range [0.0 .. 1.0[, thus in the loop, all direct aCurrA cuts will be registered
314 // as 0.0 cut. The 1.0 cut will be registered in the next loop step
315 if(fTools::moreOrEqual(fCutA, fZero) && fTools::less(fCutA, fOne))
317 // it's a candidate, but also need to test parameter value of cut on line 2
318 double fCutB;
320 // choose the more precise version
321 if(fabs(aVecB.getX()) > fabs(aVecB.getY()))
323 fCutB = (aCurrA.getX() + (fCutA * aVecA.getX()) - aCurrB.getX()) / aVecB.getX();
325 else
327 fCutB = (aCurrA.getY() + (fCutA * aVecA.getY()) - aCurrB.getY()) / aVecB.getY();
330 // use range [0.0 .. 1.0[, thus in the loop, all direct aCurrA cuts will be registered
331 // as 0.0 cut. The 1.0 cut will be registered in the next loop step
332 if(fTools::moreOrEqual(fCutB, fZero) && fTools::less(fCutB, fOne))
334 // cut is in both ranges. Add points for A and B
335 // #i111715# use fTools::equal instead of fTools::equalZero for better accuracy
336 if(fTools::equal(fCutA, fZero))
338 // ignore for start point in first edge; this is handled
339 // by outer methods and would just produce a double point
340 if(a)
342 rTempPointsA.emplace_back(aCurrA, a, 0.0);
345 else
347 const B2DPoint aCutPoint(interpolate(aCurrA, aNextA, fCutA));
348 rTempPointsA.emplace_back(aCutPoint, a, fCutA);
351 // #i111715# use fTools::equal instead of fTools::equalZero for better accuracy
352 if(fTools::equal(fCutB, fZero))
354 // ignore for start point in first edge; this is handled
355 // by outer methods and would just produce a double point
356 if(b)
358 rTempPointsB.emplace_back(aCurrB, b, 0.0);
361 else
363 const B2DPoint aCutPoint(interpolate(aCurrB, aNextB, fCutB));
364 rTempPointsB.emplace_back(aCutPoint, b, fCutB);
372 // prepare next step
373 aCurrB = aNextB;
376 // prepare next step
377 aCurrA = aNextA;
382 void findEdgeCutsBezierAndEdge(
383 const B2DCubicBezier& rCubicA,
384 const B2DPoint& rCurrB, const B2DPoint& rNextB,
385 sal_uInt32 nIndA, sal_uInt32 nIndB,
386 temporaryPointVector& rTempPointsA, temporaryPointVector& rTempPointsB)
388 // find all cuts between given bezier segment and edge. Add an entry to the tempPoints
389 // for each common point with the cut value describing the relative position on given
390 // bezier segment and edge.
391 B2DPolygon aTempPolygonA;
392 B2DPolygon aTempPolygonEdge;
393 temporaryPointVector aTempPointVectorA;
394 temporaryPointVector aTempPointVectorEdge;
396 // create subdivided polygons and find cuts between them
397 // Keep adaptiveSubdivideByCount due to needed quality
398 aTempPolygonA.reserve(SUBDIVIDE_FOR_CUT_TEST_COUNT + 8);
399 aTempPolygonA.append(rCubicA.getStartPoint());
400 rCubicA.adaptiveSubdivideByCount(aTempPolygonA, SUBDIVIDE_FOR_CUT_TEST_COUNT);
401 aTempPolygonEdge.append(rCurrB);
402 aTempPolygonEdge.append(rNextB);
404 // #i76891# using findCuts recursively is not sufficient here
405 findCutsAndTouchesAndCommonForBezier(aTempPolygonA, aTempPolygonEdge, aTempPointVectorA, aTempPointVectorEdge);
407 if(!aTempPointVectorA.empty())
409 // adapt tempVector entries to segment
410 adaptAndTransferCutsWithBezierSegment(aTempPointVectorA, aTempPolygonA, nIndA, rTempPointsA);
413 // append remapped tempVector entries for edge to tempPoints for edge
414 for(const temporaryPoint & rTempPoint : aTempPointVectorEdge)
416 rTempPointsB.emplace_back(rTempPoint.getPoint(), nIndB, rTempPoint.getCut());
420 void findEdgeCutsTwoBeziers(
421 const B2DCubicBezier& rCubicA,
422 const B2DCubicBezier& rCubicB,
423 sal_uInt32 nIndA, sal_uInt32 nIndB,
424 temporaryPointVector& rTempPointsA, temporaryPointVector& rTempPointsB)
426 // find all cuts between the two given bezier segments. Add an entry to the tempPoints
427 // for each common point with the cut value describing the relative position on given
428 // bezier segments.
429 B2DPolygon aTempPolygonA;
430 B2DPolygon aTempPolygonB;
431 temporaryPointVector aTempPointVectorA;
432 temporaryPointVector aTempPointVectorB;
434 // create subdivided polygons and find cuts between them
435 // Keep adaptiveSubdivideByCount due to needed quality
436 aTempPolygonA.reserve(SUBDIVIDE_FOR_CUT_TEST_COUNT + 8);
437 aTempPolygonA.append(rCubicA.getStartPoint());
438 rCubicA.adaptiveSubdivideByCount(aTempPolygonA, SUBDIVIDE_FOR_CUT_TEST_COUNT);
439 aTempPolygonB.reserve(SUBDIVIDE_FOR_CUT_TEST_COUNT + 8);
440 aTempPolygonB.append(rCubicB.getStartPoint());
441 rCubicB.adaptiveSubdivideByCount(aTempPolygonB, SUBDIVIDE_FOR_CUT_TEST_COUNT);
443 // #i76891# using findCuts recursively is not sufficient here
444 findCutsAndTouchesAndCommonForBezier(aTempPolygonA, aTempPolygonB, aTempPointVectorA, aTempPointVectorB);
446 if(!aTempPointVectorA.empty())
448 // adapt tempVector entries to segment
449 adaptAndTransferCutsWithBezierSegment(aTempPointVectorA, aTempPolygonA, nIndA, rTempPointsA);
452 if(!aTempPointVectorB.empty())
454 // adapt tempVector entries to segment
455 adaptAndTransferCutsWithBezierSegment(aTempPointVectorB, aTempPolygonB, nIndB, rTempPointsB);
459 void findEdgeCutsOneBezier(
460 const B2DCubicBezier& rCubicA,
461 sal_uInt32 nInd, temporaryPointVector& rTempPoints)
463 // avoid expensive part of this method if possible
464 // TODO: use hasAnyExtremum() method instead when it becomes available
465 double fDummy;
466 const bool bHasAnyExtremum = rCubicA.getMinimumExtremumPosition( fDummy );
467 if( !bHasAnyExtremum )
468 return;
470 // find all self-intersections on the given bezier segment. Add an entry to the tempPoints
471 // for each self intersection point with the cut value describing the relative position on given
472 // bezier segment.
473 B2DPolygon aTempPolygon;
474 temporaryPointVector aTempPointVector;
476 // create subdivided polygon and find cuts on it
477 // Keep adaptiveSubdivideByCount due to needed quality
478 aTempPolygon.reserve(SUBDIVIDE_FOR_CUT_TEST_COUNT + 8);
479 aTempPolygon.append(rCubicA.getStartPoint());
480 rCubicA.adaptiveSubdivideByCount(aTempPolygon, SUBDIVIDE_FOR_CUT_TEST_COUNT);
481 findCuts(aTempPolygon, aTempPointVector);
483 if(!aTempPointVector.empty())
485 // adapt tempVector entries to segment
486 adaptAndTransferCutsWithBezierSegment(aTempPointVector, aTempPolygon, nInd, rTempPoints);
490 void findCuts(const B2DPolygon& rCandidate, temporaryPointVector& rTempPoints)
492 // find out if there are edges with intersections (self-cuts). If yes, add
493 // entries to rTempPoints accordingly
494 const sal_uInt32 nPointCount(rCandidate.count());
496 if(nPointCount)
498 const sal_uInt32 nEdgeCount(rCandidate.isClosed() ? nPointCount : nPointCount - 1);
500 if(nEdgeCount)
502 const bool bCurvesInvolved(rCandidate.areControlPointsUsed());
504 if(bCurvesInvolved)
506 B2DCubicBezier aCubicA;
507 B2DCubicBezier aCubicB;
509 for(sal_uInt32 a(0); a < nEdgeCount - 1; a++)
511 rCandidate.getBezierSegment(a, aCubicA);
512 aCubicA.testAndSolveTrivialBezier();
513 const bool bEdgeAIsCurve(aCubicA.isBezier());
514 const B2DRange aRangeA(aCubicA.getRange());
516 if(bEdgeAIsCurve)
518 // curved segments may have self-intersections, do not forget those (!)
519 findEdgeCutsOneBezier(aCubicA, a, rTempPoints);
522 for(sal_uInt32 b(a + 1); b < nEdgeCount; b++)
524 rCandidate.getBezierSegment(b, aCubicB);
525 aCubicB.testAndSolveTrivialBezier();
526 const B2DRange aRangeB(aCubicB.getRange());
528 // only overlapping segments need to be tested
529 // consecutive segments touch of course
530 bool bOverlap = false;
531 if( b > a+1)
532 bOverlap = aRangeA.overlaps(aRangeB);
533 else
534 bOverlap = aRangeA.overlapsMore(aRangeB);
535 if( bOverlap)
537 const bool bEdgeBIsCurve(aCubicB.isBezier());
538 if(bEdgeAIsCurve && bEdgeBIsCurve)
540 // test for bezier-bezier cuts
541 findEdgeCutsTwoBeziers(aCubicA, aCubicB, a, b, rTempPoints, rTempPoints);
543 else if(bEdgeAIsCurve)
545 // test for bezier-edge cuts
546 findEdgeCutsBezierAndEdge(aCubicA, aCubicB.getStartPoint(), aCubicB.getEndPoint(), a, b, rTempPoints, rTempPoints);
548 else if(bEdgeBIsCurve)
550 // test for bezier-edge cuts
551 findEdgeCutsBezierAndEdge(aCubicB, aCubicA.getStartPoint(), aCubicA.getEndPoint(), b, a, rTempPoints, rTempPoints);
553 else
555 // test for simple edge-edge cuts
556 findEdgeCutsTwoEdges(aCubicA.getStartPoint(), aCubicA.getEndPoint(), aCubicB.getStartPoint(), aCubicB.getEndPoint(),
557 a, b, rTempPoints, rTempPoints);
563 else
565 B2DPoint aCurrA(rCandidate.getB2DPoint(0));
567 for(sal_uInt32 a(0); a < nEdgeCount - 1; a++)
569 const B2DPoint aNextA(rCandidate.getB2DPoint(a + 1 == nPointCount ? 0 : a + 1));
570 const B2DRange aRangeA(aCurrA, aNextA);
571 B2DPoint aCurrB(rCandidate.getB2DPoint(a + 1));
573 for(sal_uInt32 b(a + 1); b < nEdgeCount; b++)
575 const B2DPoint aNextB(rCandidate.getB2DPoint(b + 1 == nPointCount ? 0 : b + 1));
576 const B2DRange aRangeB(aCurrB, aNextB);
578 // consecutive segments touch of course
579 bool bOverlap = false;
580 if( b > a+1)
581 bOverlap = aRangeA.overlaps(aRangeB);
582 else
583 bOverlap = aRangeA.overlapsMore(aRangeB);
584 if( bOverlap)
586 findEdgeCutsTwoEdges(aCurrA, aNextA, aCurrB, aNextB, a, b, rTempPoints, rTempPoints);
589 // prepare next step
590 aCurrB = aNextB;
593 // prepare next step
594 aCurrA = aNextA;
601 } // end of anonymous namespace
602 } // end of namespace basegfx
604 namespace basegfx
606 namespace
609 void findTouchesOnEdge(
610 const B2DPoint& rCurr, const B2DPoint& rNext, const B2DPolygon& rPointPolygon,
611 sal_uInt32 nInd, temporaryPointVector& rTempPoints)
613 // find out if points from rPointPolygon are positioned on given edge. If Yes, add
614 // points there to represent touches (which may be enter or leave nodes later).
615 const sal_uInt32 nPointCount(rPointPolygon.count());
617 if(nPointCount)
619 const B2DRange aRange(rCurr, rNext);
620 const B2DVector aEdgeVector(rNext - rCurr);
621 bool bTestUsingX(fabs(aEdgeVector.getX()) > fabs(aEdgeVector.getY()));
623 for(sal_uInt32 a(0); a < nPointCount; a++)
625 const B2DPoint aTestPoint(rPointPolygon.getB2DPoint(a));
627 if(aRange.isInside(aTestPoint))
629 if(!aTestPoint.equal(rCurr) && !aTestPoint.equal(rNext))
631 const B2DVector aTestVector(aTestPoint - rCurr);
633 if(areParallel(aEdgeVector, aTestVector))
635 const double fCut(bTestUsingX
636 ? aTestVector.getX() / aEdgeVector.getX()
637 : aTestVector.getY() / aEdgeVector.getY());
638 const double fZero(0.0);
639 const double fOne(1.0);
641 if(fTools::more(fCut, fZero) && fTools::less(fCut, fOne))
643 rTempPoints.emplace_back(aTestPoint, nInd, fCut);
652 void findTouchesOnCurve(
653 const B2DCubicBezier& rCubicA, const B2DPolygon& rPointPolygon,
654 sal_uInt32 nInd, temporaryPointVector& rTempPoints)
656 // find all points from rPointPolygon which touch the given bezier segment. Add an entry
657 // for each touch to the given pointVector. The cut for that entry is the relative position on
658 // the given bezier segment.
659 B2DPolygon aTempPolygon;
660 temporaryPointVector aTempPointVector;
662 // create subdivided polygon and find cuts on it
663 // Keep adaptiveSubdivideByCount due to needed quality
664 aTempPolygon.reserve(SUBDIVIDE_FOR_CUT_TEST_COUNT + 8);
665 aTempPolygon.append(rCubicA.getStartPoint());
666 rCubicA.adaptiveSubdivideByCount(aTempPolygon, SUBDIVIDE_FOR_CUT_TEST_COUNT);
667 findTouches(aTempPolygon, rPointPolygon, aTempPointVector);
669 if(!aTempPointVector.empty())
671 // adapt tempVector entries to segment
672 adaptAndTransferCutsWithBezierSegment(aTempPointVector, aTempPolygon, nInd, rTempPoints);
676 void findTouches(const B2DPolygon& rEdgePolygon, const B2DPolygon& rPointPolygon, temporaryPointVector& rTempPoints)
678 // find out if points from rPointPolygon touch edges from rEdgePolygon. If yes,
679 // add entries to rTempPoints
680 const sal_uInt32 nPointCount(rPointPolygon.count());
681 const sal_uInt32 nEdgePointCount(rEdgePolygon.count());
683 if(nPointCount && nEdgePointCount)
685 const sal_uInt32 nEdgeCount(rEdgePolygon.isClosed() ? nEdgePointCount : nEdgePointCount - 1);
686 B2DPoint aCurr(rEdgePolygon.getB2DPoint(0));
688 for(sal_uInt32 a(0); a < nEdgeCount; a++)
690 const sal_uInt32 nNextIndex((a + 1) % nEdgePointCount);
691 const B2DPoint aNext(rEdgePolygon.getB2DPoint(nNextIndex));
693 if(!aCurr.equal(aNext))
695 bool bHandleAsSimpleEdge(true);
697 if(rEdgePolygon.areControlPointsUsed())
699 const B2DPoint aNextControlPoint(rEdgePolygon.getNextControlPoint(a));
700 const B2DPoint aPrevControlPoint(rEdgePolygon.getPrevControlPoint(nNextIndex));
701 const bool bEdgeIsCurve(!aNextControlPoint.equal(aCurr) || !aPrevControlPoint.equal(aNext));
703 if(bEdgeIsCurve)
705 bHandleAsSimpleEdge = false;
706 const B2DCubicBezier aCubicA(aCurr, aNextControlPoint, aPrevControlPoint, aNext);
707 findTouchesOnCurve(aCubicA, rPointPolygon, a, rTempPoints);
711 if(bHandleAsSimpleEdge)
713 findTouchesOnEdge(aCurr, aNext, rPointPolygon, a, rTempPoints);
717 // next step
718 aCurr = aNext;
723 } // end of anonymous namespace
724 } // end of namespace basegfx
726 namespace basegfx
728 namespace
731 void findCuts(const B2DPolygon& rCandidateA, const B2DPolygon& rCandidateB, temporaryPointVector& rTempPointsA, temporaryPointVector& rTempPointsB)
733 // find out if edges from both polygons cut. If so, add entries to rTempPoints which
734 // should be added to the polygons accordingly
735 const sal_uInt32 nPointCountA(rCandidateA.count());
736 const sal_uInt32 nPointCountB(rCandidateB.count());
738 if(nPointCountA && nPointCountB)
740 const sal_uInt32 nEdgeCountA(rCandidateA.isClosed() ? nPointCountA : nPointCountA - 1);
741 const sal_uInt32 nEdgeCountB(rCandidateB.isClosed() ? nPointCountB : nPointCountB - 1);
743 if(nEdgeCountA && nEdgeCountB)
745 const bool bCurvesInvolved(rCandidateA.areControlPointsUsed() || rCandidateB.areControlPointsUsed());
747 if(bCurvesInvolved)
749 B2DCubicBezier aCubicA;
750 B2DCubicBezier aCubicB;
752 for(sal_uInt32 a(0); a < nEdgeCountA; a++)
754 rCandidateA.getBezierSegment(a, aCubicA);
755 aCubicA.testAndSolveTrivialBezier();
756 const bool bEdgeAIsCurve(aCubicA.isBezier());
757 const B2DRange aRangeA(aCubicA.getRange());
759 for(sal_uInt32 b(0); b < nEdgeCountB; b++)
761 rCandidateB.getBezierSegment(b, aCubicB);
762 aCubicB.testAndSolveTrivialBezier();
763 const B2DRange aRangeB(aCubicB.getRange());
765 // consecutive segments touch of course
766 bool bOverlap = false;
767 if( b > a+1)
768 bOverlap = aRangeA.overlaps(aRangeB);
769 else
770 bOverlap = aRangeA.overlapsMore(aRangeB);
771 if( bOverlap)
773 const bool bEdgeBIsCurve(aCubicB.isBezier());
774 if(bEdgeAIsCurve && bEdgeBIsCurve)
776 // test for bezier-bezier cuts
777 findEdgeCutsTwoBeziers(aCubicA, aCubicB, a, b, rTempPointsA, rTempPointsB);
779 else if(bEdgeAIsCurve)
781 // test for bezier-edge cuts
782 findEdgeCutsBezierAndEdge(aCubicA, aCubicB.getStartPoint(), aCubicB.getEndPoint(), a, b, rTempPointsA, rTempPointsB);
784 else if(bEdgeBIsCurve)
786 // test for bezier-edge cuts
787 findEdgeCutsBezierAndEdge(aCubicB, aCubicA.getStartPoint(), aCubicA.getEndPoint(), b, a, rTempPointsB, rTempPointsA);
789 else
791 // test for simple edge-edge cuts
792 findEdgeCutsTwoEdges(aCubicA.getStartPoint(), aCubicA.getEndPoint(), aCubicB.getStartPoint(), aCubicB.getEndPoint(),
793 a, b, rTempPointsA, rTempPointsB);
799 else
801 B2DPoint aCurrA(rCandidateA.getB2DPoint(0));
803 for(sal_uInt32 a(0); a < nEdgeCountA; a++)
805 const B2DPoint aNextA(rCandidateA.getB2DPoint(a + 1 == nPointCountA ? 0 : a + 1));
806 const B2DRange aRangeA(aCurrA, aNextA);
807 B2DPoint aCurrB(rCandidateB.getB2DPoint(0));
809 for(sal_uInt32 b(0); b < nEdgeCountB; b++)
811 const B2DPoint aNextB(rCandidateB.getB2DPoint(b + 1 == nPointCountB ? 0 : b + 1));
812 const B2DRange aRangeB(aCurrB, aNextB);
814 // consecutive segments touch of course
815 bool bOverlap = false;
816 if( b > a+1)
817 bOverlap = aRangeA.overlaps(aRangeB);
818 else
819 bOverlap = aRangeA.overlapsMore(aRangeB);
820 if( bOverlap)
822 // test for simple edge-edge cuts
823 findEdgeCutsTwoEdges(aCurrA, aNextA, aCurrB, aNextB, a, b, rTempPointsA, rTempPointsB);
826 // prepare next step
827 aCurrB = aNextB;
830 // prepare next step
831 aCurrA = aNextA;
838 } // end of anonymous namespace
839 } // end of namespace basegfx
841 namespace basegfx
843 namespace utils
846 B2DPolygon addPointsAtCutsAndTouches(const B2DPolygon& rCandidate)
848 if(rCandidate.count())
850 temporaryPointVector aTempPoints;
852 findTouches(rCandidate, rCandidate, aTempPoints);
853 findCuts(rCandidate, aTempPoints);
855 return mergeTemporaryPointsAndPolygon(rCandidate, aTempPoints);
857 else
859 return rCandidate;
863 B2DPolyPolygon addPointsAtCutsAndTouches(const B2DPolyPolygon& rCandidate)
865 const sal_uInt32 nCount(rCandidate.count());
867 if(nCount)
869 B2DPolyPolygon aRetval;
871 if(nCount == 1)
873 // remove self intersections
874 aRetval.append(addPointsAtCutsAndTouches(rCandidate.getB2DPolygon(0)));
876 else
878 // first solve self cuts and self touches for all contained single polygons
879 std::unique_ptr<temporaryPolygonData[]> pTempData(new temporaryPolygonData[nCount]);
880 sal_uInt32 a, b;
882 for(a = 0; a < nCount; a++)
884 // use polygons with solved self intersections
885 pTempData[a].setPolygon(addPointsAtCutsAndTouches(rCandidate.getB2DPolygon(a)));
888 // now cuts and touches between the polygons
889 for(a = 0; a < nCount; a++)
891 for(b = 0; b < nCount; b++)
893 if(a != b)
895 // look for touches, compare each edge polygon to all other points
896 if(pTempData[a].getRange().overlaps(pTempData[b].getRange()))
898 findTouches(pTempData[a].getPolygon(), pTempData[b].getPolygon(), pTempData[a].getTemporaryPointVector());
902 if(a < b)
904 // look for cuts, compare each edge polygon to following ones
905 if(pTempData[a].getRange().overlaps(pTempData[b].getRange()))
907 findCuts(pTempData[a].getPolygon(), pTempData[b].getPolygon(), pTempData[a].getTemporaryPointVector(), pTempData[b].getTemporaryPointVector());
913 // consolidate the result
914 for(a = 0; a < nCount; a++)
916 aRetval.append(mergeTemporaryPointsAndPolygon(pTempData[a].getPolygon(), pTempData[a].getTemporaryPointVector()));
920 return aRetval;
922 else
924 return rCandidate;
928 B2DPolygon addPointsAtCuts(const B2DPolygon& rCandidate, const B2DPoint& rStart, const B2DPoint& rEnd)
930 const sal_uInt32 nCount(rCandidate.count());
932 if(nCount && !rStart.equal(rEnd))
934 const B2DRange aPolygonRange(rCandidate.getB2DRange());
935 const B2DRange aEdgeRange(rStart, rEnd);
937 if(aPolygonRange.overlaps(aEdgeRange))
939 const sal_uInt32 nEdgeCount(rCandidate.isClosed() ? nCount : nCount - 1);
940 temporaryPointVector aTempPoints;
941 temporaryPointVector aUnusedTempPoints;
942 B2DCubicBezier aCubic;
944 for(sal_uInt32 a(0); a < nEdgeCount; a++)
946 rCandidate.getBezierSegment(a, aCubic);
947 B2DRange aCubicRange(aCubic.getStartPoint(), aCubic.getEndPoint());
949 if(aCubic.isBezier())
951 aCubicRange.expand(aCubic.getControlPointA());
952 aCubicRange.expand(aCubic.getControlPointB());
954 if(aCubicRange.overlaps(aEdgeRange))
956 findEdgeCutsBezierAndEdge(aCubic, rStart, rEnd, a, 0, aTempPoints, aUnusedTempPoints);
959 else
961 if(aCubicRange.overlaps(aEdgeRange))
963 findEdgeCutsTwoEdges(aCubic.getStartPoint(), aCubic.getEndPoint(), rStart, rEnd, a, 0, aTempPoints, aUnusedTempPoints);
968 return mergeTemporaryPointsAndPolygon(rCandidate, aTempPoints);
972 return rCandidate;
975 B2DPolygon addPointsAtCuts(const B2DPolygon& rCandidate, const B2DPolyPolygon& rPolyMask)
977 const sal_uInt32 nCountA(rCandidate.count());
978 const sal_uInt32 nCountM(rPolyMask.count());
980 if(nCountA && nCountM)
982 const B2DRange aRangeA(rCandidate.getB2DRange());
983 const B2DRange aRangeM(rPolyMask.getB2DRange());
985 if(aRangeA.overlaps(aRangeM))
987 const sal_uInt32 nEdgeCountA(rCandidate.isClosed() ? nCountA : nCountA - 1);
988 temporaryPointVector aTempPointsA;
989 temporaryPointVector aUnusedTempPointsB;
991 for(sal_uInt32 m(0); m < nCountM; m++)
993 const B2DPolygon& aMask(rPolyMask.getB2DPolygon(m));
994 const sal_uInt32 nCountB(aMask.count());
996 if(nCountB)
998 B2DCubicBezier aCubicA;
999 B2DCubicBezier aCubicB;
1001 for(sal_uInt32 a(0); a < nEdgeCountA; a++)
1003 rCandidate.getBezierSegment(a, aCubicA);
1004 const bool bCubicAIsCurve(aCubicA.isBezier());
1005 B2DRange aCubicRangeA(aCubicA.getStartPoint(), aCubicA.getEndPoint());
1007 if(bCubicAIsCurve)
1009 aCubicRangeA.expand(aCubicA.getControlPointA());
1010 aCubicRangeA.expand(aCubicA.getControlPointB());
1013 for(sal_uInt32 b(0); b < nCountB; b++)
1015 aMask.getBezierSegment(b, aCubicB);
1016 const bool bCubicBIsCurve(aCubicB.isBezier());
1017 B2DRange aCubicRangeB(aCubicB.getStartPoint(), aCubicB.getEndPoint());
1019 if(bCubicBIsCurve)
1021 aCubicRangeB.expand(aCubicB.getControlPointA());
1022 aCubicRangeB.expand(aCubicB.getControlPointB());
1025 if(aCubicRangeA.overlaps(aCubicRangeB))
1027 if(bCubicAIsCurve && bCubicBIsCurve)
1029 findEdgeCutsTwoBeziers(aCubicA, aCubicB, a, b, aTempPointsA, aUnusedTempPointsB);
1031 else if(bCubicAIsCurve)
1033 findEdgeCutsBezierAndEdge(aCubicA, aCubicB.getStartPoint(), aCubicB.getEndPoint(), a, b, aTempPointsA, aUnusedTempPointsB);
1035 else if(bCubicBIsCurve)
1037 findEdgeCutsBezierAndEdge(aCubicB, aCubicA.getStartPoint(), aCubicA.getEndPoint(), b, a, aUnusedTempPointsB, aTempPointsA);
1039 else
1041 findEdgeCutsTwoEdges(aCubicA.getStartPoint(), aCubicA.getEndPoint(), aCubicB.getStartPoint(), aCubicB.getEndPoint(), a, b, aTempPointsA, aUnusedTempPointsB);
1049 return mergeTemporaryPointsAndPolygon(rCandidate, aTempPointsA);
1053 return rCandidate;
1056 } // end of namespace utils
1057 } // end of namespace basegfx
1059 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */