1 /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
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>
33 #define SUBDIVIDE_FOR_CUT_TEST_COUNT (50)
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]
47 temporaryPoint(const B2DPoint
& rNewPoint
, sal_uInt32 nIndex
, double 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
75 temporaryPointVector maPoints
;
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());
94 const sal_uInt32
nCount(rCandidate
.count());
98 // sort temp points to assure increasing fCut values and increasing indices
99 std::sort(rTempPoints
.begin(), rTempPoints
.end());
102 B2DCubicBezier aEdge
;
103 sal_uInt32
nNewInd(0);
106 aRetval
.append(rCandidate
.getB2DPoint(0));
108 for(sal_uInt32
a(0); a
< nCount
; a
++)
111 rCandidate
.getBezierSegment(a
, aEdge
);
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();
132 aRetval
.appendBezierSegment(aLeftPart
.getControlPointA(), aLeftPart
.getControlPointB(), rTempPoint
.getPoint());
136 aRetval
.appendBezierSegment(aEdge
.getControlPointA(), aEdge
.getControlPointB(), aEdge
.getEndPoint());
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
);
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
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
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
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();
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
)
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
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
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();
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
342 rTempPointsA
.emplace_back(aCurrA
, a
, 0.0);
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
358 rTempPointsB
.emplace_back(aCurrB
, b
, 0.0);
363 const B2DPoint
aCutPoint(interpolate(aCurrB
, aNextB
, fCutB
));
364 rTempPointsB
.emplace_back(aCutPoint
, b
, fCutB
);
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
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
466 const bool bHasAnyExtremum
= rCubicA
.getMinimumExtremumPosition( fDummy
);
467 if( !bHasAnyExtremum
)
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
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());
498 const sal_uInt32
nEdgeCount(rCandidate
.isClosed() ? nPointCount
: nPointCount
- 1);
502 const bool bCurvesInvolved(rCandidate
.areControlPointsUsed());
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());
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;
532 bOverlap
= aRangeA
.overlaps(aRangeB
);
534 bOverlap
= aRangeA
.overlapsMore(aRangeB
);
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
);
555 // test for simple edge-edge cuts
556 findEdgeCutsTwoEdges(aCubicA
.getStartPoint(), aCubicA
.getEndPoint(), aCubicB
.getStartPoint(), aCubicB
.getEndPoint(),
557 a
, b
, rTempPoints
, rTempPoints
);
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;
581 bOverlap
= aRangeA
.overlaps(aRangeB
);
583 bOverlap
= aRangeA
.overlapsMore(aRangeB
);
586 findEdgeCutsTwoEdges(aCurrA
, aNextA
, aCurrB
, aNextB
, a
, b
, rTempPoints
, rTempPoints
);
601 } // end of anonymous namespace
602 } // end of namespace basegfx
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());
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
));
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
);
723 } // end of anonymous namespace
724 } // end of namespace basegfx
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());
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;
768 bOverlap
= aRangeA
.overlaps(aRangeB
);
770 bOverlap
= aRangeA
.overlapsMore(aRangeB
);
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
);
791 // test for simple edge-edge cuts
792 findEdgeCutsTwoEdges(aCubicA
.getStartPoint(), aCubicA
.getEndPoint(), aCubicB
.getStartPoint(), aCubicB
.getEndPoint(),
793 a
, b
, rTempPointsA
, rTempPointsB
);
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;
817 bOverlap
= aRangeA
.overlaps(aRangeB
);
819 bOverlap
= aRangeA
.overlapsMore(aRangeB
);
822 // test for simple edge-edge cuts
823 findEdgeCutsTwoEdges(aCurrA
, aNextA
, aCurrB
, aNextB
, a
, b
, rTempPointsA
, rTempPointsB
);
838 } // end of anonymous namespace
839 } // end of namespace basegfx
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
);
863 B2DPolyPolygon
addPointsAtCutsAndTouches(const B2DPolyPolygon
& rCandidate
)
865 const sal_uInt32
nCount(rCandidate
.count());
869 B2DPolyPolygon aRetval
;
873 // remove self intersections
874 aRetval
.append(addPointsAtCutsAndTouches(rCandidate
.getB2DPolygon(0)));
878 // first solve self cuts and self touches for all contained single polygons
879 std::unique_ptr
<temporaryPolygonData
[]> pTempData(new temporaryPolygonData
[nCount
]);
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
++)
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());
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()));
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
);
961 if(aCubicRange
.overlaps(aEdgeRange
))
963 findEdgeCutsTwoEdges(aCubic
.getStartPoint(), aCubic
.getEndPoint(), rStart
, rEnd
, a
, 0, aTempPoints
, aUnusedTempPoints
);
968 return mergeTemporaryPointsAndPolygon(rCandidate
, aTempPoints
);
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());
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());
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());
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
);
1041 findEdgeCutsTwoEdges(aCubicA
.getStartPoint(), aCubicA
.getEndPoint(), aCubicB
.getStartPoint(), aCubicB
.getEndPoint(), a
, b
, aTempPointsA
, aUnusedTempPointsB
);
1049 return mergeTemporaryPointsAndPolygon(rCandidate
, aTempPointsA
);
1056 } // end of namespace utils
1057 } // end of namespace basegfx
1059 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */