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