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