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 30754 : TrDeSimpleEdge(
47 : const B2DPoint* pStart,
48 : const B2DPoint* pEnd)
49 : : mpStart(pStart),
50 30754 : mpEnd(pEnd)
51 : {
52 30754 : }
53 :
54 : // data read access
55 23338639 : const B2DPoint& getStart() const { return *mpStart; }
56 2575564 : 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 341627 : double getDeltaX() const { return mpEnd->getX() - mpStart->getX(); }
79 341627 : 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 51366 : sal_uInt32 getSortValue() const
84 : {
85 51366 : if(0 != mnSortValue)
86 51048 : 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 318 : const double fRadiant(atan2(getDeltaY(), getDeltaX()) * (SAL_MAX_UINT32 / F_PI));
91 :
92 : // convert to sal_uInt32 value
93 318 : const_cast< TrDeEdgeEntry* >(this)->mnSortValue = sal_uInt32(fRadiant);
94 :
95 318 : return mnSortValue;
96 : }
97 :
98 : // constructor. SortValue can be given when known, use zero otherwise
99 30754 : TrDeEdgeEntry(
100 : const B2DPoint* pStart,
101 : const B2DPoint* pEnd,
102 : sal_uInt32 nSortValue = 0)
103 : : TrDeSimpleEdge(pStart, pEnd),
104 30754 : mnSortValue(nSortValue)
105 : {
106 : // force traversal of deltaY downward
107 30754 : if(mpEnd->getY() < mpStart->getY())
108 : {
109 169 : 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 30754 : }
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 30436 : void setEnd( const B2DPoint* pNewEnd)
132 : {
133 : OSL_ENSURE(0 != pNewEnd, "No null pointer allowed here (!)");
134 :
135 30436 : if(mpEnd != pNewEnd)
136 : {
137 30436 : 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 30436 : }
143 :
144 : // operator for sort support. Sort by Y, X and slope (in that order)
145 3636604 : bool operator<(const TrDeEdgeEntry& rComp) const
146 : {
147 3636604 : if(fTools::equal(getStart().getY(), rComp.getStart().getY(), fTools::getSmallValue()))
148 : {
149 28456 : 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 10465 : return (getSortValue() > rComp.getSortValue());
158 : }
159 : else
160 : {
161 17991 : return fTools::less(getStart().getX(), rComp.getStart().getX());
162 : }
163 : }
164 : else
165 : {
166 3608148 : return fTools::less(getStart().getY(), rComp.getStart().getY());
167 : }
168 : }
169 :
170 : // method for cut support
171 143122 : 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 143122 : const double fFactor((fGivenY - getStart().getY()) / getDeltaY());
176 143122 : const double fDeltaXNew(fFactor * getDeltaX());
177 :
178 143122 : 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 1 : PointBlockAllocator() :
209 : nCurPoint( nBlockSize ),
210 1 : mpPointBase( maFirstStackBlock )
211 : {
212 1 : }
213 :
214 1 : ~PointBlockAllocator()
215 33 : {
216 638 : while(maBlocks.size() > 0)
217 : {
218 636 : delete [] maBlocks.back();
219 636 : maBlocks.pop_back();
220 : }
221 33 : }
222 :
223 20335 : B2DPoint *allocatePoint()
224 : {
225 20335 : if(nCurPoint >= nBlockSize)
226 : {
227 636 : mpPointBase = new B2DPoint[nBlockSize];
228 636 : maBlocks.push_back(mpPointBase);
229 636 : nCurPoint = 0;
230 : }
231 20335 : return mpPointBase + nCurPoint++;
232 : }
233 :
234 20335 : B2DPoint *allocatePoint(const B2DTuple &rPoint)
235 : {
236 20335 : B2DPoint *pPoint = allocatePoint();
237 20335 : *pPoint = rPoint;
238 20335 : 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 1 : 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 30436 : void addEdgeSorted(
262 : TrDeEdgeEntries::iterator aCurrent,
263 : const TrDeEdgeEntry& rNewEdge)
264 : {
265 : // Loop while new entry is bigger, use operator<
266 3664758 : while(aCurrent != maTrDeEdgeEntries.end() && (*aCurrent) < rNewEdge)
267 : {
268 3603886 : ++aCurrent;
269 : }
270 :
271 : // Insert before first which is smaller or equal or at end
272 30436 : maTrDeEdgeEntries.insert(aCurrent, rNewEdge);
273 30436 : }
274 :
275 30450 : 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 30450 : if(aEdge.getStart().equal(rCutPoint, fTools::getSmallValue()))
282 : {
283 7 : return false;
284 : }
285 :
286 : // do not create edges without deltaY: do not split when end is identical
287 30443 : if(aEdge.getEnd().equal(rCutPoint, fTools::getSmallValue()))
288 : {
289 7 : return false;
290 : }
291 :
292 30436 : const double fOldDeltaYStart(rCutPoint.getY() - aEdge.getStart().getY());
293 :
294 30436 : 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 30436 : const double fNewDeltaYStart(aEdge.getEnd().getY() - rCutPoint.getY());
303 :
304 30436 : 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 30436 : &aEdge.getEnd(),
316 60872 : aEdge.getSortValue());
317 :
318 : // Correct old entry
319 30436 : aEdge.setEnd(&rCutPoint);
320 :
321 : // Insert sorted (to avoid new sort)
322 30436 : addEdgeSorted(aCurrent, aNewEdge);
323 :
324 30436 : return true;
325 : }
326 :
327 110044 : 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 110044 : if(aEdgeA.getStart().equal(aEdgeB.getStart(), fTools::getSmallValue()))
334 : {
335 0 : return false;
336 : }
337 :
338 110044 : if(aEdgeA.getStart().equal(aEdgeB.getEnd(), fTools::getSmallValue()))
339 : {
340 0 : return false;
341 : }
342 :
343 110044 : if(aEdgeA.getEnd().equal(aEdgeB.getStart(), fTools::getSmallValue()))
344 : {
345 0 : return false;
346 : }
347 :
348 110044 : if(aEdgeA.getEnd().equal(aEdgeB.getEnd(), fTools::getSmallValue()))
349 : {
350 10938 : return false;
351 : }
352 :
353 : // Exclude simple cases: one of the edges has no length anymore
354 99106 : if(aEdgeA.getStart().equal(aEdgeA.getEnd(), fTools::getSmallValue()))
355 : {
356 0 : return false;
357 : }
358 :
359 99106 : 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 99106 : const B2DVector aDeltaB(aEdgeB.getDeltaX(), aEdgeB.getDeltaY());
366 :
367 99106 : if(tools::isPointOnEdge(aEdgeA.getStart(), aEdgeB.getStart(), aDeltaB))
368 : {
369 0 : return splitEdgeAtGivenPoint(aEdgeB, aEdgeA.getStart(), aCurrent);
370 : }
371 :
372 99106 : if(tools::isPointOnEdge(aEdgeA.getEnd(), aEdgeB.getStart(), aDeltaB))
373 : {
374 25 : return splitEdgeAtGivenPoint(aEdgeB, aEdgeA.getEnd(), aCurrent);
375 : }
376 :
377 198162 : const B2DVector aDeltaA(aEdgeA.getDeltaX(), aEdgeA.getDeltaY());
378 :
379 99081 : if(tools::isPointOnEdge(aEdgeB.getStart(), aEdgeA.getStart(), aDeltaA))
380 : {
381 0 : return splitEdgeAtGivenPoint(aEdgeA, aEdgeB.getStart(), aCurrent);
382 : }
383 :
384 99081 : if(tools::isPointOnEdge(aEdgeB.getEnd(), aEdgeA.getStart(), aDeltaA))
385 : {
386 1 : 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 99080 : double fCutA(0.0);
392 99080 : double fCutB(0.0);
393 :
394 99080 : if(tools::findCut(
395 99080 : aEdgeA.getStart(), aDeltaA,
396 99080 : aEdgeB.getStart(), aDeltaB,
397 : CUTFLAG_LINE,
398 : &fCutA,
399 99080 : &fCutB))
400 : {
401 : // use a simple metric (length criteria) for choosing the numerically
402 : // better cut
403 10089 : const double fSimpleLengthA(aDeltaA.getX() + aDeltaA.getY());
404 10089 : const double fSimpleLengthB(aDeltaB.getX() + aDeltaB.getY());
405 10089 : const bool bAIsLonger(fSimpleLengthA > fSimpleLengthB);
406 : B2DPoint* pNewPoint = bAIsLonger
407 29445 : ? maNewPoints.allocatePoint(aEdgeA.getStart() + (fCutA * aDeltaA))
408 26630 : : maNewPoints.allocatePoint(aEdgeB.getStart() + (fCutB * aDeltaB));
409 :
410 : // try to split both edges
411 10089 : bool bRetval = splitEdgeAtGivenPoint(aEdgeA, *pNewPoint, aCurrent);
412 10089 : bRetval |= splitEdgeAtGivenPoint(aEdgeB, *pNewPoint, aCurrent);
413 :
414 10089 : if(!bRetval)
415 0 : maNewPoints.freeIfLast(pNewPoint);
416 :
417 10089 : return bRetval;
418 : }
419 :
420 188097 : return false;
421 : }
422 :
423 1 : void solveHorizontalEdges(TrDeSimpleEdges& rTrDeSimpleEdges)
424 : {
425 1 : 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 1 : }
485 :
486 : public:
487 1 : explicit TrapezoidSubdivider(
488 : const B2DPolyPolygon& rSourcePolyPolygon)
489 : : mnInitialEdgeEntryCount(0),
490 : maTrDeEdgeEntries(),
491 : maPoints(),
492 1 : maNewPoints()
493 : {
494 1 : B2DPolyPolygon aSource(rSourcePolyPolygon);
495 1 : const sal_uInt32 nPolygonCount(rSourcePolyPolygon.count());
496 2 : TrDeSimpleEdges aTrDeSimpleEdges;
497 1 : sal_uInt32 a(0), b(0);
498 1 : sal_uInt32 nAllPointCount(0);
499 :
500 : // ensure there are no curves used
501 1 : if(aSource.areControlPointsUsed())
502 : {
503 0 : aSource = aSource.getDefaultAdaptiveSubdivision();
504 : }
505 :
506 3 : for(a = 0; a < nPolygonCount; a++)
507 : {
508 : // 1st run: count points
509 2 : const B2DPolygon aPolygonCandidate(aSource.getB2DPolygon(a));
510 2 : const sal_uInt32 nCount(aPolygonCandidate.count());
511 :
512 2 : if(nCount > 2)
513 : {
514 1 : nAllPointCount += nCount;
515 : }
516 2 : }
517 :
518 1 : 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 1 : maPoints.reserve(nAllPointCount);
523 :
524 3 : for(a = 0; a < nPolygonCount; a++)
525 : {
526 : // 2nd run: add points
527 2 : const B2DPolygon aPolygonCandidate(aSource.getB2DPolygon(a));
528 2 : const sal_uInt32 nCount(aPolygonCandidate.count());
529 :
530 2 : if(nCount > 2)
531 : {
532 321 : for(b = 0; b < nCount; b++)
533 : {
534 320 : maPoints.push_back(aPolygonCandidate.getB2DPoint(b));
535 : }
536 : }
537 2 : }
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 1 : sal_uInt32 nStartIndex(0);
544 :
545 3 : for(a = 0; a < nPolygonCount; a++)
546 : {
547 2 : const B2DPolygon aPolygonCandidate(aSource.getB2DPolygon(a));
548 2 : const sal_uInt32 nCount(aPolygonCandidate.count());
549 :
550 2 : if(nCount > 2)
551 : {
552 : // get the last point of the current polygon
553 1 : B2DPoint* pPrev(&maPoints[nCount + nStartIndex - 1]);
554 :
555 321 : for(b = 0; b < nCount; b++)
556 : {
557 : // get next point
558 320 : B2DPoint* pCurr(&maPoints[nStartIndex++]);
559 :
560 320 : if(fTools::equal(pPrev->getY(), pCurr->getY(), fTools::getSmallValue()))
561 : {
562 : // horizontal edge, check for single point
563 2 : 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 318 : maTrDeEdgeEntries.push_back(TrDeEdgeEntry(pPrev, pCurr, 0));
578 318 : mnInitialEdgeEntryCount++;
579 : }
580 :
581 : // prepare next step
582 320 : pPrev = pCurr;
583 : }
584 : }
585 2 : }
586 : }
587 :
588 1 : if(!maTrDeEdgeEntries.empty())
589 : {
590 : // single and initial sort of traversing edges
591 1 : maTrDeEdgeEntries.sort();
592 :
593 : // solve horizontal edges if there are any detected
594 1 : solveHorizontalEdges(aTrDeSimpleEdges);
595 1 : }
596 1 : }
597 :
598 1 : 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 1 : B1DRange aLeftRange;
623 1 : B1DRange aRightRange;
624 :
625 1 : 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 1 : ro_Result.reserve(ro_Result.size() + mnInitialEdgeEntryCount);
633 : }
634 :
635 25538 : while(!maTrDeEdgeEntries.empty())
636 : {
637 : // Prepare current operator and get first edge
638 25536 : TrDeEdgeEntries::iterator aCurrent(maTrDeEdgeEntries.begin());
639 25536 : TrDeEdgeEntries::reference aLeft(*aCurrent++);
640 :
641 25536 : 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 10204 : continue;
650 : }
651 :
652 : // get second edge
653 25536 : TrDeEdgeEntries::reference aRight(*aCurrent++);
654 :
655 25536 : 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 25536 : B2DPoint aLeftEnd(aLeft.getEnd());
673 40868 : 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 25536 : const bool bEndOnSameLine(fTools::equal(aLeftEnd.getY(), aRightEnd.getY(), fTools::getSmallValue()));
678 25536 : bool bLeftIsLonger(false);
679 :
680 25536 : if(!bEndOnSameLine)
681 : {
682 : // check which edge is longer and correct accordingly
683 19908 : bLeftIsLonger = fTools::more(aLeftEnd.getY(), aRightEnd.getY());
684 :
685 19908 : if(bLeftIsLonger)
686 : {
687 9198 : aLeftEnd = aLeft.getCutPointForGivenY(aRightEnd.getY());
688 : }
689 : else
690 : {
691 10710 : aRightEnd = aRight.getCutPointForGivenY(aLeftEnd.getY());
692 : }
693 : }
694 :
695 : // check for same start and end points
696 25536 : const bool bSameStartPoint(aLeft.getStart().equal(aRight.getStart(), fTools::getSmallValue()));
697 25536 : const bool bSameEndPoint(aLeftEnd.equal(aRightEnd, fTools::getSmallValue()));
698 :
699 : // check the simple case that the edges form a 'blind' edge (deadend)
700 25536 : if(bSameStartPoint && bSameEndPoint)
701 : {
702 : // correct the longer edge if prepared
703 45 : if(!bEndOnSameLine)
704 : {
705 12 : if(bLeftIsLonger)
706 : {
707 2 : B2DPoint* pNewPoint = maNewPoints.allocatePoint(aLeftEnd);
708 :
709 2 : if(!splitEdgeAtGivenPoint(aLeft, *pNewPoint, aCurrent))
710 : {
711 0 : maNewPoints.freeIfLast(pNewPoint);
712 : }
713 : }
714 : else
715 : {
716 10 : B2DPoint* pNewPoint = maNewPoints.allocatePoint(aRightEnd);
717 :
718 10 : if(!splitEdgeAtGivenPoint(aRight, *pNewPoint, aCurrent))
719 : {
720 0 : maNewPoints.freeIfLast(pNewPoint);
721 : }
722 : }
723 : }
724 :
725 : // consume both edges and start next run
726 45 : maTrDeEdgeEntries.pop_front();
727 45 : maTrDeEdgeEntries.pop_front();
728 :
729 45 : continue;
730 : }
731 :
732 : // check if the edges self-intersect. This can only happen when
733 : // start and end point are different
734 25491 : bool bRangesSet(false);
735 :
736 25491 : if(!(bSameStartPoint || bSameEndPoint))
737 : {
738 : // get XRanges of edges
739 11958 : aLeftRange = B1DRange(aLeft.getStart().getX(), aLeftEnd.getX());
740 11958 : aRightRange = B1DRange(aRight.getStart().getX(), aRightEnd.getX());
741 11958 : bRangesSet = true;
742 :
743 : // use fast range test first
744 11958 : if(aLeftRange.overlaps(aRightRange))
745 : {
746 : // real cut test and correction. If correction was needed,
747 : // start new run
748 5196 : if(testAndCorrectEdgeIntersection(aLeft, aRight, aCurrent))
749 : {
750 2825 : 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 90664 : if(aCurrent != maTrDeEdgeEntries.end()
758 90664 : && fTools::less(aCurrent->getStart().getY(), aLeftEnd.getY()))
759 : {
760 : // get XRanges of edges
761 22120 : if(!bRangesSet)
762 : {
763 13041 : aLeftRange = B1DRange(aLeft.getStart().getX(), aLeftEnd.getX());
764 13041 : aRightRange = B1DRange(aRight.getStart().getX(), aRightEnd.getX());
765 : }
766 :
767 : // build full XRange for fast check
768 22120 : B1DRange aAllRange(aLeftRange);
769 22120 : 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 22120 : TrDeEdgeEntries::iterator aLoop(aCurrent);
774 22120 : bool bDone(false);
775 :
776 3216550 : do
777 : {
778 : // get compare edge and its XRange
779 1604608 : 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 1604608 : if(aCompare.getStart().equal(aRight.getStart(), fTools::getSmallValue()))
785 : {
786 8032 : continue;
787 : }
788 :
789 : // get compare XRange
790 1596576 : const B1DRange aCompareRange(aCompare.getStart().getX(), aCompare.getEnd().getX());
791 :
792 : // use fast range test first
793 1596576 : if(aAllRange.overlaps(aCompareRange))
794 : {
795 : // check for start point inside thought trapezoid
796 64049 : if(fTools::more(aCompare.getStart().getY(), aLeft.getStart().getY()))
797 : {
798 : // calculate the two possible split points at compare's Y
799 61607 : const B2DPoint aSplitLeft(aLeft.getCutPointForGivenY(aCompare.getStart().getY()));
800 123214 : const B2DPoint aSplitRight(aRight.getCutPointForGivenY(aCompare.getStart().getY()));
801 :
802 : // check for start point of aCompare being inside thought
803 : // trapezoid
804 92737 : if(aCompare.getStart().getX() >= aSplitLeft.getX() &&
805 31130 : aCompare.getStart().getX() <= aSplitRight.getX())
806 : {
807 : // is inside, correct and restart loop
808 44 : B2DPoint* pNewLeft = maNewPoints.allocatePoint(aSplitLeft);
809 :
810 44 : if(splitEdgeAtGivenPoint(aLeft, *pNewLeft, aCurrent))
811 : {
812 44 : bDone = true;
813 : }
814 : else
815 : {
816 0 : maNewPoints.freeIfLast(pNewLeft);
817 : }
818 :
819 44 : B2DPoint* pNewRight = maNewPoints.allocatePoint(aSplitRight);
820 :
821 44 : if(splitEdgeAtGivenPoint(aRight, *pNewRight, aCurrent))
822 : {
823 44 : bDone = true;
824 : }
825 : else
826 : {
827 0 : maNewPoints.freeIfLast(pNewRight);
828 : }
829 61607 : }
830 : }
831 :
832 64049 : if(!bDone && aLeftRange.overlaps(aCompareRange))
833 : {
834 : // test for concrete cut of compare edge with left edge
835 54414 : bDone = testAndCorrectEdgeIntersection(aLeft, aCompare, aCurrent);
836 : }
837 :
838 64049 : if(!bDone && aRightRange.overlaps(aCompareRange))
839 : {
840 : // test for concrete cut of compare edge with Right edge
841 50434 : bDone = testAndCorrectEdgeIntersection(aRight, aCompare, aCurrent);
842 : }
843 : }
844 : }
845 1604608 : while(!bDone
846 4799156 : && aLoop != maTrDeEdgeEntries.end()
847 6411093 : && fTools::less(aLoop->getStart().getY(), aLeftEnd.getY()));
848 :
849 22120 : if(bDone)
850 : {
851 : // something needed to be changed; start next loop
852 7334 : 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 15332 : if(!bEndOnSameLine)
860 : {
861 10146 : if(bLeftIsLonger)
862 : {
863 5010 : B2DPoint* pNewPoint = maNewPoints.allocatePoint(aLeftEnd);
864 :
865 5010 : if(!splitEdgeAtGivenPoint(aLeft, *pNewPoint, aCurrent))
866 : {
867 0 : maNewPoints.freeIfLast(pNewPoint);
868 : }
869 : }
870 : else
871 : {
872 5136 : B2DPoint* pNewPoint = maNewPoints.allocatePoint(aRightEnd);
873 :
874 5136 : 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 15332 : aLeft.getStart().getX(),
887 15332 : aRight.getStart().getX(),
888 15332 : aLeft.getStart().getY(),
889 15332 : aLeftEnd.getX(),
890 15332 : aRightEnd.getX(),
891 91992 : aLeftEnd.getY()));
892 :
893 15332 : maTrDeEdgeEntries.pop_front();
894 15332 : maTrDeEdgeEntries.pop_front();
895 15332 : }
896 1 : }
897 : };
898 : } // end of anonymous namespace
899 : } // end of namespace basegfx
900 :
901 :
902 :
903 : namespace basegfx
904 : {
905 15332 : 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 15332 : mfBottomY(rfBottomY)
918 : {
919 : // guarantee mfTopXRight >= mfTopXLeft
920 15332 : if(mfTopXLeft > mfTopXRight)
921 : {
922 4 : std::swap(mfTopXLeft, mfTopXRight);
923 : }
924 :
925 : // guarantee mfBottomXRight >= mfBottomXLeft
926 15332 : if(mfBottomXLeft > mfBottomXRight)
927 : {
928 125 : std::swap(mfBottomXLeft, mfBottomXRight);
929 : }
930 :
931 : // guarantee mfBottomY >= mfTopY
932 15332 : if(mfTopY > mfBottomY)
933 : {
934 0 : std::swap(mfTopY, mfBottomY);
935 0 : std::swap(mfTopXLeft, mfBottomXLeft);
936 0 : std::swap(mfTopXRight, mfBottomXRight);
937 : }
938 15332 : }
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 1 : void trapezoidSubdivide(B2DTrapezoidVector& ro_Result, const B2DPolyPolygon& rSourcePolyPolygon)
962 : {
963 1 : trapezoidhelper::TrapezoidSubdivider aTrapezoidSubdivider(rSourcePolyPolygon);
964 :
965 1 : aTrapezoidSubdivider.Subdivide(ro_Result);
966 1 : }
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: */
|