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