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