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