Line data Source code
1 : /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
2 : /*
3 : * This file is part of the LibreOffice project.
4 : *
5 : * This Source Code Form is subject to the terms of the Mozilla Public
6 : * License, v. 2.0. If a copy of the MPL was not distributed with this
7 : * file, You can obtain one at http://mozilla.org/MPL/2.0/.
8 : *
9 : * This file incorporates work covered by the following license notice:
10 : *
11 : * Licensed to the Apache Software Foundation (ASF) under one or more
12 : * contributor license agreements. See the NOTICE file distributed
13 : * with this work for additional information regarding copyright
14 : * ownership. The ASF licenses this file to you under the Apache
15 : * License, Version 2.0 (the "License"); you may not use this file
16 : * except in compliance with the License. You may obtain a copy of
17 : * the License at http://www.apache.org/licenses/LICENSE-2.0 .
18 : */
19 :
20 : #include <basegfx/polygon/b2dtrapezoid.hxx>
21 : #include <basegfx/range/b1drange.hxx>
22 : #include <basegfx/polygon/b2dpolygontools.hxx>
23 : #include <list>
24 :
25 : namespace basegfx
26 : {
27 : namespace trapezoidhelper
28 : {
29 :
30 : // helper class to hold a simple ege. This is only used for horizontal edges
31 : // currently, thus the YPositions will be equal. I did not create a special
32 : // class for this since holdingthe pointers is more effective and also can be
33 : // used as baseclass for the traversing edges
34 :
35 : class TrDeSimpleEdge
36 : {
37 : protected:
38 : // pointers to start and end point
39 : const B2DPoint* mpStart;
40 : const B2DPoint* mpEnd;
41 :
42 : public:
43 : // constructor
44 62465 : TrDeSimpleEdge(
45 : const B2DPoint* pStart,
46 : const B2DPoint* pEnd)
47 : : mpStart(pStart),
48 62465 : mpEnd(pEnd)
49 : {
50 62465 : }
51 :
52 : // data read access
53 47329822 : const B2DPoint& getStart() const { return *mpStart; }
54 5257503 : const B2DPoint& getEnd() const { return *mpEnd; }
55 : };
56 :
57 : // define vector of simple edges
58 :
59 : typedef ::std::vector< TrDeSimpleEdge > TrDeSimpleEdges;
60 :
61 : // helper class for holding a traversing edge. It will always have some
62 : // distance in YPos. The slope (in a numerically useful form, see comments) is
63 : // hold and used in SortValue to allow sorting traversing edges by Y, X and slope
64 : // (in that order)
65 :
66 : class TrDeEdgeEntry : public TrDeSimpleEdge
67 : {
68 : private:
69 : // the slope in a numerical useful form for sorting
70 : sal_uInt32 mnSortValue;
71 :
72 : public:
73 : // convenience data read access
74 708701 : double getDeltaX() const { return mpEnd->getX() - mpStart->getX(); }
75 708701 : double getDeltaY() const { return mpEnd->getY() - mpStart->getY(); }
76 :
77 : // convenience data read access. SortValue is created on demand since
78 : // it is not always used
79 104202 : sal_uInt32 getSortValue() const
80 : {
81 104202 : if(0 != mnSortValue)
82 103568 : return mnSortValue;
83 :
84 : // get radiant; has to be in the range ]0.0 .. pi[, thus scale to full
85 : // sal_uInt32 range for maximum precision
86 634 : const double fRadiant(atan2(getDeltaY(), getDeltaX()) * (SAL_MAX_UINT32 / F_PI));
87 :
88 : // convert to sal_uInt32 value
89 634 : const_cast< TrDeEdgeEntry* >(this)->mnSortValue = sal_uInt32(fRadiant);
90 :
91 634 : return mnSortValue;
92 : }
93 :
94 : // constructor. SortValue can be given when known, use zero otherwise
95 62462 : TrDeEdgeEntry(
96 : const B2DPoint* pStart,
97 : const B2DPoint* pEnd,
98 : sal_uInt32 nSortValue = 0)
99 : : TrDeSimpleEdge(pStart, pEnd),
100 62462 : mnSortValue(nSortValue)
101 : {
102 : // force traversal of deltaY downward
103 62462 : if(mpEnd->getY() < mpStart->getY())
104 : {
105 305 : std::swap(mpStart, mpEnd);
106 : }
107 :
108 : // no horizontal edges allowed, all neeed to traverse vertically
109 : OSL_ENSURE(mpEnd->getY() > mpStart->getY(), "Illegal TrDeEdgeEntry constructed (!)");
110 62462 : }
111 :
112 : // data write access to StartPoint
113 0 : void setStart( const B2DPoint* pNewStart)
114 : {
115 : OSL_ENSURE(0 != pNewStart, "No null pointer allowed here (!)");
116 :
117 0 : if(mpStart != pNewStart)
118 : {
119 0 : mpStart = pNewStart;
120 :
121 : // no horizontal edges allowed, all neeed to traverse vertivally
122 : OSL_ENSURE(mpEnd->getY() > mpStart->getY(), "Illegal TrDeEdgeEntry constructed (!)");
123 : }
124 0 : }
125 :
126 : // data write access to EndPoint
127 61828 : void setEnd( const B2DPoint* pNewEnd)
128 : {
129 : OSL_ENSURE(0 != pNewEnd, "No null pointer allowed here (!)");
130 :
131 61828 : if(mpEnd != pNewEnd)
132 : {
133 61828 : mpEnd = pNewEnd;
134 :
135 : // no horizontal edges allowed, all neeed to traverse vertivally
136 : OSL_ENSURE(mpEnd->getY() > mpStart->getY(), "Illegal TrDeEdgeEntry constructed (!)");
137 : }
138 61828 : }
139 :
140 : // operator for sort support. Sort by Y, X and slope (in that order)
141 7361967 : bool operator<(const TrDeEdgeEntry& rComp) const
142 : {
143 7361967 : if(fTools::equal(getStart().getY(), rComp.getStart().getY(), fTools::getSmallValue()))
144 : {
145 58201 : if(fTools::equal(getStart().getX(), rComp.getStart().getX(), fTools::getSmallValue()))
146 : {
147 : // when start points are equal, use the direction the edge is pointing
148 : // to. That value is created on demand and derived from atan2 in the
149 : // range ]0.0 .. pi[ (without extremas, we always have a deltaY in this
150 : // class) and scaled to sal_uInt32 range for best precision. 0 means no angle,
151 : // while SAL_MAX_UINT32 means pi. Thus, the higher the value, the more left
152 : // the edge traverses.
153 21187 : return (getSortValue() > rComp.getSortValue());
154 : }
155 : else
156 : {
157 37014 : return fTools::less(getStart().getX(), rComp.getStart().getX());
158 : }
159 : }
160 : else
161 : {
162 7303766 : return fTools::less(getStart().getY(), rComp.getStart().getY());
163 : }
164 : }
165 :
166 : // method for cut support
167 295197 : B2DPoint getCutPointForGivenY(double fGivenY)
168 : {
169 : // Calculate cut point locally (do not use interpolate) since it is numerically
170 : // necessary to guarantee the new, equal Y-coordinate
171 295197 : const double fFactor((fGivenY - getStart().getY()) / getDeltaY());
172 295197 : const double fDeltaXNew(fFactor * getDeltaX());
173 :
174 295197 : return B2DPoint(getStart().getX() + fDeltaXNew, fGivenY);
175 : }
176 : };
177 :
178 : // define double linked list of edges (for fast random insert)
179 :
180 : typedef ::std::list< TrDeEdgeEntry > TrDeEdgeEntries;
181 :
182 : } // end of anonymous namespace
183 : } // end of namespace basegfx
184 :
185 : namespace basegfx
186 : {
187 : namespace trapezoidhelper
188 : {
189 : // FIXME: templatize this and use it for TrDeEdgeEntries too ...
190 :
191 : /// Class to allow efficient allocation and release of B2DPoints
192 : class PointBlockAllocator
193 : {
194 : static const size_t nBlockSize = 32;
195 : size_t nCurPoint;
196 : B2DPoint *mpPointBase;
197 : /// Special case the first allocation to avoid it.
198 : B2DPoint maFirstStackBlock[nBlockSize];
199 : std::vector< B2DPoint * > maBlocks;
200 : public:
201 2 : PointBlockAllocator() :
202 : nCurPoint( nBlockSize ),
203 2 : mpPointBase( maFirstStackBlock )
204 : {
205 2 : }
206 :
207 2 : ~PointBlockAllocator()
208 2 : {
209 1297 : while(maBlocks.size() > 0)
210 : {
211 1293 : delete [] maBlocks.back();
212 1293 : maBlocks.pop_back();
213 : }
214 2 : }
215 :
216 41337 : B2DPoint *allocatePoint()
217 : {
218 41337 : if(nCurPoint >= nBlockSize)
219 : {
220 1293 : mpPointBase = new B2DPoint[nBlockSize];
221 1293 : maBlocks.push_back(mpPointBase);
222 1293 : nCurPoint = 0;
223 : }
224 41337 : return mpPointBase + nCurPoint++;
225 : }
226 :
227 41337 : B2DPoint *allocatePoint(const B2DTuple &rPoint)
228 : {
229 41337 : B2DPoint *pPoint = allocatePoint();
230 41337 : *pPoint = rPoint;
231 41337 : return pPoint;
232 : }
233 :
234 : /// This is a very uncommon case but why not ...
235 0 : void freeIfLast(B2DPoint *pPoint)
236 : {
237 : // just re-use the last point if we can.
238 0 : if ( nCurPoint > 0 && pPoint == mpPointBase + nCurPoint - 1 )
239 0 : nCurPoint--;
240 0 : }
241 : };
242 :
243 : // helper class to handle the complete trapezoid subdivision of a PolyPolygon
244 2 : class TrapezoidSubdivider
245 : {
246 : private:
247 : // local data
248 : sal_uInt32 mnInitialEdgeEntryCount;
249 : TrDeEdgeEntries maTrDeEdgeEntries;
250 : ::std::vector< B2DPoint > maPoints;
251 : /// new points allocated for cuts
252 : PointBlockAllocator maNewPoints;
253 :
254 61828 : void addEdgeSorted(
255 : TrDeEdgeEntries::iterator aCurrent,
256 : const TrDeEdgeEntry& rNewEdge)
257 : {
258 : // Loop while new entry is bigger, use operator<
259 7419249 : while(aCurrent != maTrDeEdgeEntries.end() && (*aCurrent) < rNewEdge)
260 : {
261 7295593 : ++aCurrent;
262 : }
263 :
264 : // Insert before first which is smaller or equal or at end
265 61828 : maTrDeEdgeEntries.insert(aCurrent, rNewEdge);
266 61828 : }
267 :
268 61864 : bool splitEdgeAtGivenPoint(
269 : TrDeEdgeEntries::reference aEdge,
270 : const B2DPoint& rCutPoint,
271 : TrDeEdgeEntries::iterator aCurrent)
272 : {
273 : // do not create edges without deltaY: do not split when start is identical
274 61864 : if(aEdge.getStart().equal(rCutPoint, fTools::getSmallValue()))
275 : {
276 5 : return false;
277 : }
278 :
279 : // do not create edges without deltaY: do not split when end is identical
280 61859 : if(aEdge.getEnd().equal(rCutPoint, fTools::getSmallValue()))
281 : {
282 31 : return false;
283 : }
284 :
285 61828 : const double fOldDeltaYStart(rCutPoint.getY() - aEdge.getStart().getY());
286 :
287 61828 : if(fTools::lessOrEqual(fOldDeltaYStart, 0.0))
288 : {
289 : // do not split: the resulting edge would be horizontal
290 : // correct it to new start point
291 0 : aEdge.setStart(&rCutPoint);
292 0 : return false;
293 : }
294 :
295 61828 : const double fNewDeltaYStart(aEdge.getEnd().getY() - rCutPoint.getY());
296 :
297 61828 : if(fTools::lessOrEqual(fNewDeltaYStart, 0.0))
298 : {
299 : // do not split: the resulting edge would be horizontal
300 : // correct it to new end point
301 0 : aEdge.setEnd(&rCutPoint);
302 0 : return false;
303 : }
304 :
305 : // Create new entry
306 : const TrDeEdgeEntry aNewEdge(
307 : &rCutPoint,
308 61828 : &aEdge.getEnd(),
309 123656 : aEdge.getSortValue());
310 :
311 : // Correct old entry
312 61828 : aEdge.setEnd(&rCutPoint);
313 :
314 : // Insert sorted (to avoid new sort)
315 61828 : addEdgeSorted(aCurrent, aNewEdge);
316 :
317 61828 : return true;
318 : }
319 :
320 228076 : bool testAndCorrectEdgeIntersection(
321 : TrDeEdgeEntries::reference aEdgeA,
322 : TrDeEdgeEntries::reference aEdgeB,
323 : TrDeEdgeEntries::iterator aCurrent)
324 : {
325 : // Exclude simple cases: same start or end point
326 228076 : if(aEdgeA.getStart().equal(aEdgeB.getStart(), fTools::getSmallValue()))
327 : {
328 0 : return false;
329 : }
330 :
331 228076 : if(aEdgeA.getStart().equal(aEdgeB.getEnd(), fTools::getSmallValue()))
332 : {
333 0 : return false;
334 : }
335 :
336 228076 : if(aEdgeA.getEnd().equal(aEdgeB.getStart(), fTools::getSmallValue()))
337 : {
338 0 : return false;
339 : }
340 :
341 228076 : if(aEdgeA.getEnd().equal(aEdgeB.getEnd(), fTools::getSmallValue()))
342 : {
343 21624 : return false;
344 : }
345 :
346 : // Exclude simple cases: one of the edges has no length anymore
347 206452 : if(aEdgeA.getStart().equal(aEdgeA.getEnd(), fTools::getSmallValue()))
348 : {
349 0 : return false;
350 : }
351 :
352 206452 : if(aEdgeB.getStart().equal(aEdgeB.getEnd(), fTools::getSmallValue()))
353 : {
354 0 : return false;
355 : }
356 :
357 : // check if one point is on the other edge (a touch, not a cut)
358 206452 : const B2DVector aDeltaB(aEdgeB.getDeltaX(), aEdgeB.getDeltaY());
359 :
360 206452 : if(tools::isPointOnEdge(aEdgeA.getStart(), aEdgeB.getStart(), aDeltaB))
361 : {
362 0 : return splitEdgeAtGivenPoint(aEdgeB, aEdgeA.getStart(), aCurrent);
363 : }
364 :
365 206452 : if(tools::isPointOnEdge(aEdgeA.getEnd(), aEdgeB.getStart(), aDeltaB))
366 : {
367 34 : return splitEdgeAtGivenPoint(aEdgeB, aEdgeA.getEnd(), aCurrent);
368 : }
369 :
370 412836 : const B2DVector aDeltaA(aEdgeA.getDeltaX(), aEdgeA.getDeltaY());
371 :
372 206418 : if(tools::isPointOnEdge(aEdgeB.getStart(), aEdgeA.getStart(), aDeltaA))
373 : {
374 1 : return splitEdgeAtGivenPoint(aEdgeA, aEdgeB.getStart(), aCurrent);
375 : }
376 :
377 206417 : if(tools::isPointOnEdge(aEdgeB.getEnd(), aEdgeA.getStart(), aDeltaA))
378 : {
379 3 : return splitEdgeAtGivenPoint(aEdgeA, aEdgeB.getEnd(), aCurrent);
380 : }
381 :
382 : // check for cut inside edges. Use both t-values to choose the more precise
383 : // one later
384 206414 : double fCutA(0.0);
385 206414 : double fCutB(0.0);
386 :
387 206414 : if(tools::findCut(
388 206414 : aEdgeA.getStart(), aDeltaA,
389 206414 : aEdgeB.getStart(), aDeltaB,
390 : CUTFLAG_LINE,
391 : &fCutA,
392 206414 : &fCutB))
393 : {
394 : // use a simple metric (length criteria) for choosing the numerically
395 : // better cut
396 20489 : const double fSimpleLengthA(aDeltaA.getX() + aDeltaA.getY());
397 20489 : const double fSimpleLengthB(aDeltaB.getX() + aDeltaB.getY());
398 20489 : const bool bAIsLonger(fSimpleLengthA > fSimpleLengthB);
399 : B2DPoint* pNewPoint = bAIsLonger
400 58520 : ? maNewPoints.allocatePoint(aEdgeA.getStart() + (fCutA * aDeltaA))
401 53655 : : maNewPoints.allocatePoint(aEdgeB.getStart() + (fCutB * aDeltaB));
402 :
403 : // try to split both edges
404 20489 : bool bRetval = splitEdgeAtGivenPoint(aEdgeA, *pNewPoint, aCurrent);
405 20489 : bRetval |= splitEdgeAtGivenPoint(aEdgeB, *pNewPoint, aCurrent);
406 :
407 20489 : if(!bRetval)
408 0 : maNewPoints.freeIfLast(pNewPoint);
409 :
410 20489 : return bRetval;
411 : }
412 :
413 392377 : return false;
414 : }
415 :
416 2 : void solveHorizontalEdges(TrDeSimpleEdges& rTrDeSimpleEdges)
417 : {
418 2 : if(!rTrDeSimpleEdges.empty() && !maTrDeEdgeEntries.empty())
419 : {
420 : // there were horizontal edges. These can be excluded, but
421 : // cuts with other edges need to be solved and added before
422 : // ignoring them
423 4 : for(sal_uInt32 a = 0; a < rTrDeSimpleEdges.size(); a++)
424 : {
425 : // get horizontal edge as candidate; prepare its range and fixed Y
426 3 : const TrDeSimpleEdge& rHorEdge = rTrDeSimpleEdges[a];
427 3 : const B1DRange aRange(rHorEdge.getStart().getX(), rHorEdge.getEnd().getX());
428 3 : const double fFixedY(rHorEdge.getStart().getY());
429 :
430 : // loop over traversing edges
431 3 : TrDeEdgeEntries::iterator aCurrent(maTrDeEdgeEntries.begin());
432 :
433 554 : do
434 : {
435 : // get compare edge
436 277 : TrDeEdgeEntries::reference aCompare(*aCurrent++);
437 :
438 277 : if(fTools::lessOrEqual(aCompare.getEnd().getY(), fFixedY))
439 : {
440 : // edge ends above horizontal edge, continue
441 89 : continue;
442 : }
443 :
444 233 : if(fTools::moreOrEqual(aCompare.getStart().getY(), fFixedY))
445 : {
446 : // edge starts below horizontal edge, continue
447 1 : continue;
448 : }
449 :
450 : // vertical overlap, get horizontal range
451 232 : const B1DRange aCompareRange(aCompare.getStart().getX(), aCompare.getEnd().getX());
452 :
453 232 : if(aRange.overlaps(aCompareRange))
454 : {
455 : // possible cut, get cut point
456 148 : const B2DPoint aSplit(aCompare.getCutPointForGivenY(fFixedY));
457 :
458 740 : if(fTools::more(aSplit.getX(), aRange.getMinimum())
459 740 : && fTools::less(aSplit.getX(), aRange.getMaximum()))
460 : {
461 : // cut is in XRange of horizontal edge, potentially needed cut
462 57 : B2DPoint* pNewPoint = maNewPoints.allocatePoint(aSplit);
463 :
464 57 : if(!splitEdgeAtGivenPoint(aCompare, *pNewPoint, aCurrent))
465 : {
466 0 : maNewPoints.freeIfLast(pNewPoint);
467 : }
468 148 : }
469 : }
470 : }
471 1108 : while(aCurrent != maTrDeEdgeEntries.end()
472 1108 : && fTools::less(aCurrent->getStart().getY(), fFixedY));
473 : }
474 : }
475 2 : }
476 :
477 : public:
478 2 : explicit TrapezoidSubdivider(
479 : const B2DPolyPolygon& rSourcePolyPolygon)
480 : : mnInitialEdgeEntryCount(0),
481 : maTrDeEdgeEntries(),
482 : maPoints(),
483 2 : maNewPoints()
484 : {
485 2 : B2DPolyPolygon aSource(rSourcePolyPolygon);
486 2 : const sal_uInt32 nPolygonCount(rSourcePolyPolygon.count());
487 4 : TrDeSimpleEdges aTrDeSimpleEdges;
488 2 : sal_uInt32 a(0), b(0);
489 2 : sal_uInt32 nAllPointCount(0);
490 :
491 : // ensure there are no curves used
492 2 : if(aSource.areControlPointsUsed())
493 : {
494 0 : aSource = aSource.getDefaultAdaptiveSubdivision();
495 : }
496 :
497 6 : for(a = 0; a < nPolygonCount; a++)
498 : {
499 : // 1st run: count points
500 4 : const B2DPolygon aPolygonCandidate(aSource.getB2DPolygon(a));
501 4 : const sal_uInt32 nCount(aPolygonCandidate.count());
502 :
503 4 : if(nCount > 2)
504 : {
505 2 : nAllPointCount += nCount;
506 : }
507 4 : }
508 :
509 2 : if(nAllPointCount)
510 : {
511 : // reserve needed points. CAUTION: maPoints size is NOT to be changed anymore
512 : // after 2nd loop since pointers to it are used in the edges
513 2 : maPoints.reserve(nAllPointCount);
514 :
515 6 : for(a = 0; a < nPolygonCount; a++)
516 : {
517 : // 2nd run: add points
518 4 : const B2DPolygon aPolygonCandidate(aSource.getB2DPolygon(a));
519 4 : const sal_uInt32 nCount(aPolygonCandidate.count());
520 :
521 4 : if(nCount > 2)
522 : {
523 642 : for(b = 0; b < nCount; b++)
524 : {
525 640 : maPoints.push_back(aPolygonCandidate.getB2DPoint(b));
526 : }
527 : }
528 4 : }
529 :
530 : // Moved the edge construction to a 3rd run: doing it in the 2nd run is
531 : // possible(and i used it), but requires a working vector::reserve()
532 : // implementation, else the vector will be reallocated and the pointers
533 : // in the edges may be wrong. Security first here.
534 2 : sal_uInt32 nStartIndex(0);
535 :
536 6 : for(a = 0; a < nPolygonCount; a++)
537 : {
538 4 : const B2DPolygon aPolygonCandidate(aSource.getB2DPolygon(a));
539 4 : const sal_uInt32 nCount(aPolygonCandidate.count());
540 :
541 4 : if(nCount > 2)
542 : {
543 : // get the last point of the current polygon
544 2 : B2DPoint* pPrev(&maPoints[nCount + nStartIndex - 1]);
545 :
546 642 : for(b = 0; b < nCount; b++)
547 : {
548 : // get next point
549 640 : B2DPoint* pCurr(&maPoints[nStartIndex++]);
550 :
551 640 : if(fTools::equal(pPrev->getY(), pCurr->getY(), fTools::getSmallValue()))
552 : {
553 : // horizontal edge, check for single point
554 6 : if(!fTools::equal(pPrev->getX(), pCurr->getX(), fTools::getSmallValue()))
555 : {
556 : // X-order not needed, just add
557 3 : aTrDeSimpleEdges.push_back(TrDeSimpleEdge(pPrev, pCurr));
558 :
559 3 : const double fMiddle((pPrev->getY() + pCurr->getY()) * 0.5);
560 3 : pPrev->setY(fMiddle);
561 3 : pCurr->setY(fMiddle);
562 : }
563 : }
564 : else
565 : {
566 : // vertical edge. Positive Y-direction is guaranteed by the
567 : // TrDeEdgeEntry constructor
568 634 : maTrDeEdgeEntries.push_back(TrDeEdgeEntry(pPrev, pCurr, 0));
569 634 : mnInitialEdgeEntryCount++;
570 : }
571 :
572 : // prepare next step
573 640 : pPrev = pCurr;
574 : }
575 : }
576 4 : }
577 : }
578 :
579 2 : if(!maTrDeEdgeEntries.empty())
580 : {
581 : // single and initial sort of traversing edges
582 2 : maTrDeEdgeEntries.sort();
583 :
584 : // solve horizontal edges if there are any detected
585 2 : solveHorizontalEdges(aTrDeSimpleEdges);
586 2 : }
587 2 : }
588 :
589 2 : void Subdivide(B2DTrapezoidVector& ro_Result)
590 : {
591 : // This is the central subdivider. The strategy is to use the first two entries
592 : // from the traversing edges as a potential trapezoid and do the needed corrections
593 : // and adaptions on the way.
594 :
595 : // There always must be two edges with the same YStart value: When adding the polygons
596 : // in the constructor, there is always a topmost point from which two edges start; when
597 : // the topmost is an edge, there is a start and end of this edge from which two edges
598 : // start. All cases have two edges with same StartY (QED).
599 :
600 : // Based on this these edges get corrected when:
601 : // - one is longer than the other
602 : // - they intersect
603 : // - they intersect with other edges
604 : // - another edge starts inside the thought trapezoid
605 :
606 : // All this cases again produce a valid state so that the first two edges have a common
607 : // Ystart again. Some cases lead to a restart of the process, some allow consuming the
608 : // edges and create the intended trapezoid.
609 :
610 : // Be careful when doing chages here: It is essential to keep all possible paths
611 : // in valid states and to be numerically correct. This is especially needed e.g.
612 : // by using fTools::equal(..) in the more robust small-value incarnation.
613 2 : B1DRange aLeftRange;
614 2 : B1DRange aRightRange;
615 :
616 2 : if(!maTrDeEdgeEntries.empty())
617 : {
618 : // measuring shows that the relation between edges and created trapezoids is
619 : // mostly in the 1:1 range, thus reserve as much trapezoids as edges exist. Do
620 : // not use maTrDeEdgeEntries.size() since that may be a non-constant time
621 : // operation for Lists. Instead, use mnInitialEdgeEntryCount which will contain
622 : // the roughly counted adds to the List
623 2 : ro_Result.reserve(ro_Result.size() + mnInitialEdgeEntryCount);
624 : }
625 :
626 51835 : while(!maTrDeEdgeEntries.empty())
627 : {
628 : // Prepare current operator and get first edge
629 51831 : TrDeEdgeEntries::iterator aCurrent(maTrDeEdgeEntries.begin());
630 51831 : TrDeEdgeEntries::reference aLeft(*aCurrent++);
631 :
632 51831 : if(aCurrent == maTrDeEdgeEntries.end())
633 : {
634 : // Should not happen: No 2nd edge; consume the single edge
635 : // to not have an endless loop and start next. During development
636 : // i constantly had breakpoints here, so i am sure enough to add an
637 : // assertion here
638 : OSL_FAIL("Trapeziod decomposer in illegal state (!)");
639 0 : maTrDeEdgeEntries.pop_front();
640 0 : continue;
641 : }
642 :
643 : // get second edge
644 51831 : TrDeEdgeEntries::reference aRight(*aCurrent++);
645 :
646 51831 : if(!fTools::equal(aLeft.getStart().getY(), aRight.getStart().getY(), fTools::getSmallValue()))
647 : {
648 : // Should not happen: We have a 2nd edge, but YStart is on another
649 : // line; consume the single edge to not have an endless loop and start
650 : // next. During development i constantly had breakpoints here, so i am
651 : // sure enough to add an assertion here
652 : OSL_FAIL("Trapeziod decomposer in illegal state (!)");
653 0 : maTrDeEdgeEntries.pop_front();
654 0 : continue;
655 : }
656 :
657 : // aLeft and aRight build a thought trapezoid now. They have a common
658 : // start line (same Y for start points). Potentially, one of the edges
659 : // is longer than the other. It is only needed to look at the shorter
660 : // length which build the potential trapezoid. To do so, get the end points
661 : // locally and adapt the evtl. longer one. Use only aLeftEnd and aRightEnd
662 : // from here on, not the aLeft.getEnd() or aRight.getEnd() accesses.
663 51831 : B2DPoint aLeftEnd(aLeft.getEnd());
664 82952 : B2DPoint aRightEnd(aRight.getEnd());
665 :
666 : // check if end points are on the same line. If yes, no adaption
667 : // needs to be prepared. Also remember which one actually is longer.
668 51831 : const bool bEndOnSameLine(fTools::equal(aLeftEnd.getY(), aRightEnd.getY(), fTools::getSmallValue()));
669 51831 : bool bLeftIsLonger(false);
670 :
671 51831 : if(!bEndOnSameLine)
672 : {
673 : // check which edge is longer and correct accordingly
674 40331 : bLeftIsLonger = fTools::more(aLeftEnd.getY(), aRightEnd.getY());
675 :
676 40331 : if(bLeftIsLonger)
677 : {
678 18494 : aLeftEnd = aLeft.getCutPointForGivenY(aRightEnd.getY());
679 : }
680 : else
681 : {
682 21837 : aRightEnd = aRight.getCutPointForGivenY(aLeftEnd.getY());
683 : }
684 : }
685 :
686 : // check for same start and end points
687 51831 : const bool bSameStartPoint(aLeft.getStart().equal(aRight.getStart(), fTools::getSmallValue()));
688 51831 : const bool bSameEndPoint(aLeftEnd.equal(aRightEnd, fTools::getSmallValue()));
689 :
690 : // check the simple case that the edges form a 'blind' edge (deadend)
691 51831 : if(bSameStartPoint && bSameEndPoint)
692 : {
693 : // correct the longer edge if prepared
694 110 : if(!bEndOnSameLine)
695 : {
696 51 : if(bLeftIsLonger)
697 : {
698 12 : B2DPoint* pNewPoint = maNewPoints.allocatePoint(aLeftEnd);
699 :
700 12 : if(!splitEdgeAtGivenPoint(aLeft, *pNewPoint, aCurrent))
701 : {
702 0 : maNewPoints.freeIfLast(pNewPoint);
703 : }
704 : }
705 : else
706 : {
707 39 : B2DPoint* pNewPoint = maNewPoints.allocatePoint(aRightEnd);
708 :
709 39 : if(!splitEdgeAtGivenPoint(aRight, *pNewPoint, aCurrent))
710 : {
711 0 : maNewPoints.freeIfLast(pNewPoint);
712 : }
713 : }
714 : }
715 :
716 : // consume both edges and start next run
717 110 : maTrDeEdgeEntries.pop_front();
718 110 : maTrDeEdgeEntries.pop_front();
719 :
720 110 : continue;
721 : }
722 :
723 : // check if the edges self-intersect. This can only happen when
724 : // start and end point are different
725 51721 : bool bRangesSet(false);
726 :
727 51721 : if(!(bSameStartPoint || bSameEndPoint))
728 : {
729 : // get XRanges of edges
730 24297 : aLeftRange = B1DRange(aLeft.getStart().getX(), aLeftEnd.getX());
731 24297 : aRightRange = B1DRange(aRight.getStart().getX(), aRightEnd.getX());
732 24297 : bRangesSet = true;
733 :
734 : // use fast range test first
735 24297 : if(aLeftRange.overlaps(aRightRange))
736 : {
737 : // real cut test and correction. If correction was needed,
738 : // start new run
739 10818 : if(testAndCorrectEdgeIntersection(aLeft, aRight, aCurrent))
740 : {
741 5825 : continue;
742 : }
743 : }
744 : }
745 :
746 : // now we need to check if there are intersections with other edges
747 : // or if other edges start inside the candidate trapezoid
748 183584 : if(aCurrent != maTrDeEdgeEntries.end()
749 183584 : && fTools::less(aCurrent->getStart().getY(), aLeftEnd.getY()))
750 : {
751 : // get XRanges of edges
752 44691 : if(!bRangesSet)
753 : {
754 26309 : aLeftRange = B1DRange(aLeft.getStart().getX(), aLeftEnd.getX());
755 26309 : aRightRange = B1DRange(aRight.getStart().getX(), aRightEnd.getX());
756 : }
757 :
758 : // build full XRange for fast check
759 44691 : B1DRange aAllRange(aLeftRange);
760 44691 : aAllRange.expand(aRightRange);
761 :
762 : // prepare loop iterator; aCurrent needs to stay unchanged for
763 : // eventual sorted insertions of new EdgeNodes. Also prepare stop flag
764 44691 : TrDeEdgeEntries::iterator aLoop(aCurrent);
765 44691 : bool bDone(false);
766 :
767 6506279 : do
768 : {
769 : // get compare edge and its XRange
770 3245752 : TrDeEdgeEntries::reference aCompare(*aLoop++);
771 :
772 : // avoid edges using the same start point as one of
773 : // the edges. These can neither have their start point
774 : // in the thought trapezoid nor cut with one of the edges
775 3245752 : if(aCompare.getStart().equal(aRight.getStart(), fTools::getSmallValue()))
776 : {
777 16052 : continue;
778 : }
779 :
780 : // get compare XRange
781 3229700 : const B1DRange aCompareRange(aCompare.getStart().getX(), aCompare.getEnd().getX());
782 :
783 : // use fast range test first
784 3229700 : if(aAllRange.overlaps(aCompareRange))
785 : {
786 : // check for start point inside thought trapezoid
787 132358 : if(fTools::more(aCompare.getStart().getY(), aLeft.getStart().getY()))
788 : {
789 : // calculate the two possible split points at compare's Y
790 127359 : const B2DPoint aSplitLeft(aLeft.getCutPointForGivenY(aCompare.getStart().getY()));
791 254718 : const B2DPoint aSplitRight(aRight.getCutPointForGivenY(aCompare.getStart().getY()));
792 :
793 : // check for start point of aCompare being inside thought
794 : // trapezoid
795 176570 : if(aCompare.getStart().getX() >= aSplitLeft.getX() &&
796 49211 : aCompare.getStart().getX() <= aSplitRight.getX())
797 : {
798 : // is inside, correct and restart loop
799 73 : B2DPoint* pNewLeft = maNewPoints.allocatePoint(aSplitLeft);
800 :
801 73 : if(splitEdgeAtGivenPoint(aLeft, *pNewLeft, aCurrent))
802 : {
803 73 : bDone = true;
804 : }
805 : else
806 : {
807 0 : maNewPoints.freeIfLast(pNewLeft);
808 : }
809 :
810 73 : B2DPoint* pNewRight = maNewPoints.allocatePoint(aSplitRight);
811 :
812 73 : if(splitEdgeAtGivenPoint(aRight, *pNewRight, aCurrent))
813 : {
814 73 : bDone = true;
815 : }
816 : else
817 : {
818 0 : maNewPoints.freeIfLast(pNewRight);
819 : }
820 127359 : }
821 : }
822 :
823 132358 : if(!bDone && aLeftRange.overlaps(aCompareRange))
824 : {
825 : // test for concrete cut of compare edge with left edge
826 112331 : bDone = testAndCorrectEdgeIntersection(aLeft, aCompare, aCurrent);
827 : }
828 :
829 132358 : if(!bDone && aRightRange.overlaps(aCompareRange))
830 : {
831 : // test for concrete cut of compare edge with Right edge
832 104927 : bDone = testAndCorrectEdgeIntersection(aRight, aCompare, aCurrent);
833 : }
834 : }
835 : }
836 3245752 : while(!bDone
837 9707706 : && aLoop != maTrDeEdgeEntries.end()
838 12968212 : && fTools::less(aLoop->getStart().getY(), aLeftEnd.getY()));
839 :
840 44691 : if(bDone)
841 : {
842 : // something needed to be changed; start next loop
843 14775 : continue;
844 : }
845 : }
846 :
847 : // when we get here, the intended trapezoid can be used. It needs to
848 : // be corrected, eventually (if prepared); but this is no reason not to
849 : // use it in the same loop iteration
850 31121 : if(!bEndOnSameLine)
851 : {
852 20594 : if(bLeftIsLonger)
853 : {
854 10171 : B2DPoint* pNewPoint = maNewPoints.allocatePoint(aLeftEnd);
855 :
856 10171 : if(!splitEdgeAtGivenPoint(aLeft, *pNewPoint, aCurrent))
857 : {
858 0 : maNewPoints.freeIfLast(pNewPoint);
859 : }
860 : }
861 : else
862 : {
863 10423 : B2DPoint* pNewPoint = maNewPoints.allocatePoint(aRightEnd);
864 :
865 10423 : if(!splitEdgeAtGivenPoint(aRight, *pNewPoint, aCurrent))
866 : {
867 0 : maNewPoints.freeIfLast(pNewPoint);
868 : }
869 : }
870 : }
871 :
872 : // the two edges start at the same Y, they use the same DeltaY, they
873 : // do not cut themselves and not any other edge in range. Create a
874 : // B2DTrapezoid and consume both edges
875 : ro_Result.push_back(
876 : B2DTrapezoid(
877 31121 : aLeft.getStart().getX(),
878 31121 : aRight.getStart().getX(),
879 31121 : aLeft.getStart().getY(),
880 31121 : aLeftEnd.getX(),
881 31121 : aRightEnd.getX(),
882 186726 : aLeftEnd.getY()));
883 :
884 31121 : maTrDeEdgeEntries.pop_front();
885 31121 : maTrDeEdgeEntries.pop_front();
886 31121 : }
887 2 : }
888 : };
889 : } // end of anonymous namespace
890 : } // end of namespace basegfx
891 :
892 : namespace basegfx
893 : {
894 31121 : B2DTrapezoid::B2DTrapezoid(
895 : const double& rfTopXLeft,
896 : const double& rfTopXRight,
897 : const double& rfTopY,
898 : const double& rfBottomXLeft,
899 : const double& rfBottomXRight,
900 : const double& rfBottomY)
901 : : mfTopXLeft(rfTopXLeft),
902 : mfTopXRight(rfTopXRight),
903 : mfTopY(rfTopY),
904 : mfBottomXLeft(rfBottomXLeft),
905 : mfBottomXRight(rfBottomXRight),
906 31121 : mfBottomY(rfBottomY)
907 : {
908 : // guarantee mfTopXRight >= mfTopXLeft
909 31121 : if(mfTopXLeft > mfTopXRight)
910 : {
911 30 : std::swap(mfTopXLeft, mfTopXRight);
912 : }
913 :
914 : // guarantee mfBottomXRight >= mfBottomXLeft
915 31121 : if(mfBottomXLeft > mfBottomXRight)
916 : {
917 333 : std::swap(mfBottomXLeft, mfBottomXRight);
918 : }
919 :
920 : // guarantee mfBottomY >= mfTopY
921 31121 : if(mfTopY > mfBottomY)
922 : {
923 0 : std::swap(mfTopY, mfBottomY);
924 0 : std::swap(mfTopXLeft, mfBottomXLeft);
925 0 : std::swap(mfTopXRight, mfBottomXRight);
926 : }
927 31121 : }
928 :
929 0 : B2DPolygon B2DTrapezoid::getB2DPolygon() const
930 : {
931 0 : B2DPolygon aRetval;
932 :
933 0 : aRetval.append(B2DPoint(getTopXLeft(), getTopY()));
934 0 : aRetval.append(B2DPoint(getTopXRight(), getTopY()));
935 0 : aRetval.append(B2DPoint(getBottomXRight(), getBottomY()));
936 0 : aRetval.append(B2DPoint(getBottomXLeft(), getBottomY()));
937 0 : aRetval.setClosed(true);
938 :
939 0 : return aRetval;
940 : }
941 : } // end of namespace basegfx
942 :
943 : namespace basegfx
944 : {
945 : namespace tools
946 : {
947 : // convert Source tools::PolyPolygon to trapezoids
948 2 : void trapezoidSubdivide(B2DTrapezoidVector& ro_Result, const B2DPolyPolygon& rSourcePolyPolygon)
949 : {
950 2 : trapezoidhelper::TrapezoidSubdivider aTrapezoidSubdivider(rSourcePolyPolygon);
951 :
952 2 : aTrapezoidSubdivider.Subdivide(ro_Result);
953 2 : }
954 :
955 0 : void createLineTrapezoidFromEdge(
956 : B2DTrapezoidVector& ro_Result,
957 : const B2DPoint& rPointA,
958 : const B2DPoint& rPointB,
959 : double fLineWidth)
960 : {
961 0 : if(fTools::lessOrEqual(fLineWidth, 0.0))
962 : {
963 : // no line witdh
964 0 : return;
965 : }
966 :
967 0 : if(rPointA.equal(rPointB, fTools::getSmallValue()))
968 : {
969 : // points are equal, no edge
970 0 : return;
971 : }
972 :
973 0 : const double fHalfLineWidth(0.5 * fLineWidth);
974 :
975 0 : if(fTools::equal(rPointA.getX(), rPointB.getX(), fTools::getSmallValue()))
976 : {
977 : // vertical line
978 0 : const double fLeftX(rPointA.getX() - fHalfLineWidth);
979 0 : const double fRightX(rPointA.getX() + fHalfLineWidth);
980 :
981 : ro_Result.push_back(
982 : B2DTrapezoid(
983 : fLeftX,
984 : fRightX,
985 0 : std::min(rPointA.getY(), rPointB.getY()),
986 : fLeftX,
987 : fRightX,
988 0 : std::max(rPointA.getY(), rPointB.getY())));
989 : }
990 0 : else if(fTools::equal(rPointA.getY(), rPointB.getY(), fTools::getSmallValue()))
991 : {
992 : // horizontal line
993 0 : const double fLeftX(std::min(rPointA.getX(), rPointB.getX()));
994 0 : const double fRightX(std::max(rPointA.getX(), rPointB.getX()));
995 :
996 : ro_Result.push_back(
997 : B2DTrapezoid(
998 : fLeftX,
999 : fRightX,
1000 0 : rPointA.getY() - fHalfLineWidth,
1001 : fLeftX,
1002 : fRightX,
1003 0 : rPointA.getY() + fHalfLineWidth));
1004 : }
1005 : else
1006 : {
1007 : // diagonal line
1008 : // create perpendicular vector
1009 0 : const B2DVector aDelta(rPointB - rPointA);
1010 0 : B2DVector aPerpendicular(-aDelta.getY(), aDelta.getX());
1011 0 : aPerpendicular.setLength(fHalfLineWidth);
1012 :
1013 : // create StartLow, StartHigh, EndLow and EndHigh
1014 0 : const B2DPoint aStartLow(rPointA + aPerpendicular);
1015 0 : const B2DPoint aStartHigh(rPointA - aPerpendicular);
1016 0 : const B2DPoint aEndHigh(rPointB - aPerpendicular);
1017 0 : const B2DPoint aEndLow(rPointB + aPerpendicular);
1018 :
1019 : // create EdgeEntries
1020 0 : basegfx::trapezoidhelper::TrDeEdgeEntries aTrDeEdgeEntries;
1021 :
1022 0 : aTrDeEdgeEntries.push_back(basegfx::trapezoidhelper::TrDeEdgeEntry(&aStartLow, &aStartHigh, 0));
1023 0 : aTrDeEdgeEntries.push_back(basegfx::trapezoidhelper::TrDeEdgeEntry(&aStartHigh, &aEndHigh, 0));
1024 0 : aTrDeEdgeEntries.push_back(basegfx::trapezoidhelper::TrDeEdgeEntry(&aEndHigh, &aEndLow, 0));
1025 0 : aTrDeEdgeEntries.push_back(basegfx::trapezoidhelper::TrDeEdgeEntry(&aEndLow, &aStartLow, 0));
1026 0 : aTrDeEdgeEntries.sort();
1027 :
1028 : // here we know we have exactly four edges, and they do not cut, touch or
1029 : // intersect. This makes processing much easier. Get the first two as start
1030 : // edges for the thought trapezoid
1031 0 : basegfx::trapezoidhelper::TrDeEdgeEntries::iterator aCurrent(aTrDeEdgeEntries.begin());
1032 0 : basegfx::trapezoidhelper::TrDeEdgeEntries::reference aLeft(*aCurrent++);
1033 0 : basegfx::trapezoidhelper::TrDeEdgeEntries::reference aRight(*aCurrent++);
1034 0 : const bool bEndOnSameLine(fTools::equal(aLeft.getEnd().getY(), aRight.getEnd().getY(), fTools::getSmallValue()));
1035 :
1036 0 : if(bEndOnSameLine)
1037 : {
1038 : // create two triangle trapezoids
1039 : ro_Result.push_back(
1040 : B2DTrapezoid(
1041 0 : aLeft.getStart().getX(),
1042 0 : aRight.getStart().getX(),
1043 0 : aLeft.getStart().getY(),
1044 0 : aLeft.getEnd().getX(),
1045 0 : aRight.getEnd().getX(),
1046 0 : aLeft.getEnd().getY()));
1047 :
1048 0 : basegfx::trapezoidhelper::TrDeEdgeEntries::reference aLeft2(*aCurrent++);
1049 0 : basegfx::trapezoidhelper::TrDeEdgeEntries::reference aRight2(*aCurrent++);
1050 :
1051 : ro_Result.push_back(
1052 : B2DTrapezoid(
1053 0 : aLeft2.getStart().getX(),
1054 0 : aRight2.getStart().getX(),
1055 0 : aLeft2.getStart().getY(),
1056 0 : aLeft2.getEnd().getX(),
1057 0 : aRight2.getEnd().getX(),
1058 0 : aLeft2.getEnd().getY()));
1059 : }
1060 : else
1061 : {
1062 : // create three trapezoids. Check which edge is longer and
1063 : // correct accordingly
1064 0 : const bool bLeftIsLonger(fTools::more(aLeft.getEnd().getY(), aRight.getEnd().getY()));
1065 :
1066 0 : if(bLeftIsLonger)
1067 : {
1068 0 : basegfx::trapezoidhelper::TrDeEdgeEntries::reference aRight2(*aCurrent++);
1069 0 : basegfx::trapezoidhelper::TrDeEdgeEntries::reference aLeft2(*aCurrent++);
1070 0 : const B2DPoint aSplitLeft(aLeft.getCutPointForGivenY(aRight.getEnd().getY()));
1071 0 : const B2DPoint aSplitRight(aRight2.getCutPointForGivenY(aLeft.getEnd().getY()));
1072 :
1073 : ro_Result.push_back(
1074 : B2DTrapezoid(
1075 0 : aLeft.getStart().getX(),
1076 0 : aRight.getStart().getX(),
1077 0 : aLeft.getStart().getY(),
1078 0 : aSplitLeft.getX(),
1079 0 : aRight.getEnd().getX(),
1080 0 : aRight.getEnd().getY()));
1081 :
1082 : ro_Result.push_back(
1083 : B2DTrapezoid(
1084 0 : aSplitLeft.getX(),
1085 0 : aRight.getEnd().getX(),
1086 0 : aRight.getEnd().getY(),
1087 0 : aLeft2.getStart().getX(),
1088 0 : aSplitRight.getX(),
1089 0 : aLeft2.getStart().getY()));
1090 :
1091 : ro_Result.push_back(
1092 : B2DTrapezoid(
1093 0 : aLeft2.getStart().getX(),
1094 0 : aSplitRight.getX(),
1095 0 : aLeft2.getStart().getY(),
1096 0 : aLeft2.getEnd().getX(),
1097 0 : aRight2.getEnd().getX(),
1098 0 : aLeft2.getEnd().getY()));
1099 : }
1100 : else
1101 : {
1102 0 : basegfx::trapezoidhelper::TrDeEdgeEntries::reference aLeft2(*aCurrent++);
1103 0 : basegfx::trapezoidhelper::TrDeEdgeEntries::reference aRight2(*aCurrent++);
1104 0 : const B2DPoint aSplitRight(aRight.getCutPointForGivenY(aLeft.getEnd().getY()));
1105 0 : const B2DPoint aSplitLeft(aLeft2.getCutPointForGivenY(aRight.getEnd().getY()));
1106 :
1107 : ro_Result.push_back(
1108 : B2DTrapezoid(
1109 0 : aLeft.getStart().getX(),
1110 0 : aRight.getStart().getX(),
1111 0 : aLeft.getStart().getY(),
1112 0 : aLeft.getEnd().getX(),
1113 0 : aSplitRight.getX(),
1114 0 : aLeft.getEnd().getY()));
1115 :
1116 : ro_Result.push_back(
1117 : B2DTrapezoid(
1118 0 : aLeft.getEnd().getX(),
1119 0 : aSplitRight.getX(),
1120 0 : aLeft.getEnd().getY(),
1121 0 : aSplitLeft.getX(),
1122 0 : aRight.getEnd().getX(),
1123 0 : aRight2.getStart().getY()));
1124 :
1125 : ro_Result.push_back(
1126 : B2DTrapezoid(
1127 0 : aSplitLeft.getX(),
1128 0 : aRight.getEnd().getX(),
1129 0 : aRight2.getStart().getY(),
1130 0 : aLeft2.getEnd().getX(),
1131 0 : aRight2.getEnd().getX(),
1132 0 : aLeft2.getEnd().getY()));
1133 : }
1134 0 : }
1135 : }
1136 : }
1137 :
1138 0 : void createLineTrapezoidFromB2DPolygon(
1139 : B2DTrapezoidVector& ro_Result,
1140 : const B2DPolygon& rPolygon,
1141 : double fLineWidth)
1142 : {
1143 0 : if(fTools::lessOrEqual(fLineWidth, 0.0))
1144 : {
1145 0 : return;
1146 : }
1147 :
1148 : // ensure there are no curves used
1149 0 : B2DPolygon aSource(rPolygon);
1150 :
1151 0 : if(aSource.areControlPointsUsed())
1152 : {
1153 0 : const double fPrecisionFactor = 0.25;
1154 0 : aSource = adaptiveSubdivideByDistance( aSource, fLineWidth * fPrecisionFactor );
1155 : }
1156 :
1157 0 : const sal_uInt32 nPointCount(aSource.count());
1158 :
1159 0 : if(!nPointCount)
1160 : {
1161 0 : return;
1162 : }
1163 :
1164 0 : const sal_uInt32 nEdgeCount(aSource.isClosed() ? nPointCount : nPointCount - 1);
1165 0 : B2DPoint aCurrent(aSource.getB2DPoint(0));
1166 :
1167 0 : ro_Result.reserve(ro_Result.size() + (3 * nEdgeCount));
1168 :
1169 0 : for(sal_uInt32 a(0); a < nEdgeCount; a++)
1170 : {
1171 0 : const sal_uInt32 nNextIndex((a + 1) % nPointCount);
1172 0 : const B2DPoint aNext(aSource.getB2DPoint(nNextIndex));
1173 :
1174 0 : createLineTrapezoidFromEdge(ro_Result, aCurrent, aNext, fLineWidth);
1175 0 : aCurrent = aNext;
1176 0 : }
1177 : }
1178 :
1179 0 : void createLineTrapezoidFromB2DPolyPolygon(
1180 : B2DTrapezoidVector& ro_Result,
1181 : const B2DPolyPolygon& rPolyPolygon,
1182 : double fLineWidth)
1183 : {
1184 0 : if(fTools::lessOrEqual(fLineWidth, 0.0))
1185 : {
1186 0 : return;
1187 : }
1188 :
1189 : // ensure there are no curves used
1190 0 : B2DPolyPolygon aSource(rPolyPolygon);
1191 :
1192 0 : if(aSource.areControlPointsUsed())
1193 : {
1194 0 : aSource = aSource.getDefaultAdaptiveSubdivision();
1195 : }
1196 :
1197 0 : const sal_uInt32 nCount(aSource.count());
1198 :
1199 0 : if(!nCount)
1200 : {
1201 0 : return;
1202 : }
1203 :
1204 0 : for(sal_uInt32 a(0); a < nCount; a++)
1205 : {
1206 : createLineTrapezoidFromB2DPolygon(
1207 : ro_Result,
1208 : aSource.getB2DPolygon(a),
1209 0 : fLineWidth);
1210 0 : }
1211 : }
1212 :
1213 : } // end of namespace tools
1214 : } // end of namespace basegfx
1215 :
1216 : /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
|
