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 <rtl/math.hxx>
21 : #include <osl/diagnose.h>
22 :
23 : #include <basegfx/tuple/b2dtuple.hxx>
24 : #include <basegfx/range/b2drange.hxx>
25 : #include <basegfx/range/b2drangeclipper.hxx>
26 : #include <basegfx/range/b2dpolyrange.hxx>
27 : #include <basegfx/polygon/b2dpolypolygon.hxx>
28 : #include <basegfx/polygon/b2dpolygontools.hxx>
29 : #include <basegfx/polygon/b2dpolypolygontools.hxx>
30 :
31 : #include <o3tl/vector_pool.hxx>
32 : #include <boost/bind.hpp>
33 : #include <boost/utility.hpp>
34 :
35 : #include <algorithm>
36 : #include <deque>
37 : #include <list>
38 :
39 : namespace basegfx
40 : {
41 : namespace
42 : {
43 : // Generating a poly-polygon from a bunch of rectangles
44 :
45 : // Helper functionality for sweep-line algorithm
46 : // ====================================================
47 :
48 : typedef std::vector<B2DRange> VectorOfRanges;
49 :
50 : class ImplPolygon;
51 : typedef o3tl::vector_pool<ImplPolygon> VectorOfPolygons;
52 :
53 : /** This class represents an active edge
54 :
55 : As the sweep line traverses across the overall area,
56 : rectangle edges parallel to it generate events, and
57 : rectangle edges orthogonal to it generate active
58 : edges. This class represents the latter.
59 : */
60 : class ActiveEdge
61 : {
62 : public:
63 : /** The two possible active rectangle edges differ by one
64 : coordinate value - the upper edge has the lower, the
65 : lower edge the higher value.
66 : */
67 : enum EdgeType {
68 : /// edge with lower coordinate value
69 : UPPER=0,
70 : /// edge with higher coordinate value
71 : LOWER=1
72 : };
73 :
74 : enum EdgeDirection {
75 : /// edge proceeds to the left
76 : PROCEED_LEFT=0,
77 : /// edge proceeds to the right
78 : PROCEED_RIGHT=1
79 : };
80 :
81 : /** Create active edge
82 :
83 : @param rRect
84 : Rectangle this edge is part of
85 :
86 : @param fInvariantCoord
87 : The invariant coordinate value of this edge
88 :
89 : @param eEdgeType
90 : Is fInvariantCoord the lower or the higher value, for
91 : this rect?
92 : */
93 826 : ActiveEdge( const B2DRectangle& rRect,
94 : const double& fInvariantCoord,
95 : std::ptrdiff_t nPolyIdx,
96 : EdgeType eEdgeType,
97 : EdgeDirection eEdgeDirection ) :
98 : mfInvariantCoord(fInvariantCoord),
99 : mpAssociatedRect( &rRect ),
100 : mnPolygonIdx( nPolyIdx ),
101 : meEdgeType( eEdgeType ),
102 826 : meEdgeDirection( eEdgeDirection )
103 826 : {}
104 :
105 4016 : double getInvariantCoord() const { return mfInvariantCoord; }
106 6454 : const B2DRectangle& getRect() const { return *mpAssociatedRect; }
107 1834 : std::ptrdiff_t getTargetPolygonIndex() const { return mnPolygonIdx; }
108 1008 : void setTargetPolygonIndex( std::ptrdiff_t nIdx ) { mnPolygonIdx = nIdx; }
109 1232 : EdgeDirection getEdgeDirection() const { return meEdgeDirection; }
110 :
111 : private:
112 : /** The invariant coordinate value of this edge (e.g. the
113 : common y value, for a horizontal edge)
114 : */
115 : double mfInvariantCoord;
116 :
117 : /** Associated rectangle
118 :
119 : This on the one hand saves some storage space (the
120 : vector of rectangles is persistent, anyway), and on
121 : the other hand provides an identifier to match active
122 : edges and x events (see below)
123 :
124 : Ptr because class needs to be assignable
125 : */
126 : const B2DRectangle* mpAssociatedRect;
127 :
128 : /** Index of the polygon this edge is currently involved
129 : with.
130 :
131 : Note that this can change for some kinds of edge
132 : intersection, as the algorithm tends to swap
133 : associated polygons there.
134 :
135 : -1 denotes no assigned polygon
136 : */
137 : std::ptrdiff_t mnPolygonIdx;
138 :
139 : /// 'upper' or 'lower' edge of original rectangle.
140 : EdgeType meEdgeType;
141 :
142 : /// 'left' or 'right'
143 : EdgeDirection meEdgeDirection;
144 : };
145 :
146 : // Needs to be list - various places hold ptrs to elements
147 : typedef std::list< ActiveEdge > ListOfEdges;
148 :
149 : /** Element of the sweep line event list
150 :
151 : As the sweep line traverses across the overall area,
152 : rectangle edges parallel to it generate events, and
153 : rectangle edges orthogonal to it generate active
154 : edges. This class represents the former.
155 :
156 : The class defines an element of the sweep line list. The
157 : sweep line's position jumps in steps defined by the
158 : coordinates of the sorted SweepLineEvent entries.
159 : */
160 : class SweepLineEvent
161 : {
162 : public:
163 : /** The two possible sweep line rectangle edges differ by
164 : one coordinate value - the starting edge has the
165 : lower, the finishing edge the higher value.
166 : */
167 : enum EdgeType {
168 : /// edge with lower coordinate value
169 : STARTING_EDGE=0,
170 : /// edge with higher coordinate value
171 : FINISHING_EDGE=1
172 : };
173 :
174 : /** The two possible sweep line directions
175 : */
176 : enum EdgeDirection {
177 : PROCEED_UP=0,
178 : PROCEED_DOWN=1
179 : };
180 :
181 : /** Create sweep line event
182 :
183 : @param fPos
184 : Coordinate position of the event
185 :
186 : @param rRect
187 : Rectangle this event is generated for.
188 :
189 : @param eEdgeType
190 : Is fPos the lower or the higher value, for the
191 : rectangle this event is generated for?
192 : */
193 826 : SweepLineEvent( double fPos,
194 : const B2DRectangle& rRect,
195 : EdgeType eEdgeType,
196 : EdgeDirection eDirection) :
197 : mfPos( fPos ),
198 : mpAssociatedRect( &rRect ),
199 : meEdgeType( eEdgeType ),
200 826 : meEdgeDirection( eDirection )
201 826 : {}
202 :
203 2058 : double getPos() const { return mfPos; }
204 2471 : const B2DRectangle& getRect() const { return *mpAssociatedRect; }
205 2478 : EdgeType getEdgeType() const { return meEdgeType; }
206 1239 : EdgeDirection getEdgeDirection() const { return meEdgeDirection; }
207 :
208 : /// For STL sort
209 1937 : bool operator<( const SweepLineEvent& rRHS ) const { return mfPos < rRHS.mfPos; }
210 :
211 : private:
212 : /// position of the event, in the direction of the line sweep
213 : double mfPos;
214 :
215 : /** Rectangle this event is generated for
216 :
217 : This on the one hand saves some storage space (the
218 : vector of rectangles is persistent, anyway), and on
219 : the other hand provides an identifier to match active
220 : edges and events (see below)
221 :
222 : Ptr because class needs to be assignable
223 : */
224 : const B2DRectangle* mpAssociatedRect;
225 :
226 : /// 'upper' or 'lower' edge of original rectangle.
227 : EdgeType meEdgeType;
228 :
229 : /// 'up' or 'down'
230 : EdgeDirection meEdgeDirection;
231 : };
232 :
233 : typedef std::vector< SweepLineEvent > VectorOfEvents;
234 :
235 : /** Smart point container for B2DMultiRange::getPolyPolygon()
236 :
237 : This class provides methods needed only here, and is used
238 : as a place to store some additional information per
239 : polygon. Also, most of the intersection logic is
240 : implemented here.
241 : */
242 2655 : class ImplPolygon
243 : {
244 : public:
245 : /** Create polygon
246 : */
247 488 : ImplPolygon() :
248 : mpLeadingRightEdge(NULL),
249 : mnIdx(-1),
250 : maPoints(),
251 488 : mbIsFinished(false)
252 : {
253 : // completely ad-hoc. but what the hell.
254 488 : maPoints.reserve(11);
255 488 : }
256 :
257 488 : void setPolygonPoolIndex( std::ptrdiff_t nIdx ) { mnIdx = nIdx; }
258 :
259 : /// Add point to the end of the existing points
260 2464 : void append( const B2DPoint& rPoint )
261 : {
262 : OSL_PRECOND( maPoints.empty() ||
263 : maPoints.back().getX() == rPoint.getX() ||
264 : maPoints.back().getY() == rPoint.getY(),
265 : "ImplPolygon::append(): added point violates 90 degree line angle constraint!" );
266 :
267 4318 : if( maPoints.empty() ||
268 1854 : maPoints.back() != rPoint )
269 : {
270 : // avoid duplicate points
271 2190 : maPoints.push_back( rPoint );
272 : }
273 2464 : }
274 :
275 : /** Perform the intersection of this polygon with an
276 : active edge.
277 :
278 : @param rEvent
279 : The vertical line event that generated the
280 : intersection
281 :
282 : @param rActiveEdge
283 : The active edge that generated the intersection
284 :
285 : @param rPolygonPool
286 : Polygon pool, we sometimes need to allocate a new one
287 :
288 : @param bIsFinishingEdge
289 : True, when this is hitting the last edge of the
290 : vertical sweep - every vertical sweep starts and ends
291 : with upper and lower edge of the _same_ rectangle.
292 :
293 : @return the new current polygon (that's the one
294 : processing must proceed with, when going through the
295 : list of upcoming active edges).
296 : */
297 2058 : std::ptrdiff_t intersect( SweepLineEvent& rEvent,
298 : ActiveEdge& rActiveEdge,
299 : VectorOfPolygons& rPolygonPool,
300 : B2DPolyPolygon& rRes,
301 : bool isFinishingEdge )
302 : {
303 : OSL_PRECOND( !mbIsFinished,
304 : "ImplPolygon::intersect(): called on already finished polygon!" );
305 : OSL_PRECOND( !isFinishingEdge
306 : || (isFinishingEdge && &rEvent.getRect() == &rActiveEdge.getRect()),
307 : "ImplPolygon::intersect(): inconsistent ending!" );
308 :
309 : const B2DPoint aIntersectionPoint( rEvent.getPos(),
310 2058 : rActiveEdge.getInvariantCoord() );
311 :
312 : // intersection point, goes to our polygon
313 : // unconditionally
314 2058 : append(aIntersectionPoint);
315 :
316 2058 : if( isFinishingEdge )
317 : {
318 : // isSweepLineEnteringRect ?
319 826 : if( rEvent.getEdgeType() == SweepLineEvent::STARTING_EDGE)
320 413 : handleFinalOwnRightEdge(rActiveEdge);
321 : else
322 : handleFinalOwnLeftEdge(rActiveEdge,
323 : rPolygonPool,
324 413 : rRes);
325 :
326 : // we're done with this rect & sweep line
327 826 : return -1;
328 : }
329 1232 : else if( metOwnEdge(rEvent,rActiveEdge) )
330 : {
331 826 : handleInitialOwnEdge(rEvent, rActiveEdge);
332 :
333 : // point already added, all init done, continue
334 : // with same poly
335 826 : return mnIdx;
336 : }
337 : else
338 : {
339 : OSL_ENSURE( rActiveEdge.getTargetPolygonIndex() != -1,
340 : "ImplPolygon::intersect(): non-trivial intersection hit empty polygon!" );
341 :
342 : const bool isHittingLeftEdge(
343 406 : rActiveEdge.getEdgeDirection() == ActiveEdge::PROCEED_LEFT);
344 :
345 406 : if( isHittingLeftEdge )
346 : return handleComplexLeftEdge(rActiveEdge,
347 : aIntersectionPoint,
348 : rPolygonPool,
349 197 : rRes);
350 : else
351 : return handleComplexRightEdge(rActiveEdge,
352 : aIntersectionPoint,
353 209 : rPolygonPool);
354 2058 : }
355 : }
356 :
357 : private:
358 826 : void handleInitialOwnEdge(SweepLineEvent& rEvent,
359 : ActiveEdge& rActiveEdge)
360 : {
361 : const bool isActiveEdgeProceedLeft(
362 826 : rActiveEdge.getEdgeDirection() == ActiveEdge::PROCEED_LEFT);
363 : const bool isSweepLineEnteringRect(
364 826 : rEvent.getEdgeType() == SweepLineEvent::STARTING_EDGE);
365 : (void)isActiveEdgeProceedLeft;
366 : (void)isSweepLineEnteringRect;
367 :
368 : OSL_ENSURE( isSweepLineEnteringRect == isActiveEdgeProceedLeft,
369 : "ImplPolygon::intersect(): sweep initial own edge hit: wrong polygon order" );
370 :
371 : OSL_ENSURE( isSweepLineEnteringRect ||
372 : mpLeadingRightEdge == &rActiveEdge,
373 : "ImplPolygon::intersect(): sweep initial own edge hit: wrong leading edge" );
374 826 : }
375 :
376 413 : void handleFinalOwnRightEdge(ActiveEdge& rActiveEdge)
377 : {
378 : OSL_ENSURE( rActiveEdge.getEdgeDirection() == ActiveEdge::PROCEED_RIGHT,
379 : "ImplPolygon::handleInitialOwnRightEdge(): start edge wrong polygon order" );
380 :
381 413 : rActiveEdge.setTargetPolygonIndex(mnIdx);
382 413 : mpLeadingRightEdge = &rActiveEdge;
383 413 : }
384 :
385 413 : void handleFinalOwnLeftEdge(ActiveEdge& rActiveEdge,
386 : VectorOfPolygons& rPolygonPool,
387 : B2DPolyPolygon& rRes)
388 : {
389 : OSL_ENSURE( rActiveEdge.getEdgeDirection() == ActiveEdge::PROCEED_LEFT,
390 : "ImplPolygon::handleFinalOwnLeftEdge(): end edge wrong polygon order" );
391 :
392 : const bool isHittingOurTail(
393 413 : rActiveEdge.getTargetPolygonIndex() == mnIdx);
394 :
395 413 : if( isHittingOurTail )
396 346 : finish(rRes); // just finish. no fuss.
397 : else
398 : {
399 : // temp poly hits final left edge
400 67 : const std::ptrdiff_t nTmpIdx=rActiveEdge.getTargetPolygonIndex();
401 67 : ImplPolygon& rTmp=rPolygonPool.get(nTmpIdx);
402 :
403 : // active edge's polygon has points
404 : // already. ours need to go in front of them.
405 : maPoints.insert(maPoints.end(),
406 : rTmp.maPoints.begin(),
407 67 : rTmp.maPoints.end());
408 :
409 : // adjust leading edges, we're switching the polygon
410 67 : ActiveEdge* const pFarEdge=rTmp.mpLeadingRightEdge;
411 :
412 67 : mpLeadingRightEdge = pFarEdge;
413 67 : pFarEdge->setTargetPolygonIndex(mnIdx);
414 :
415 : // nTmpIdx is an empty shell, get rid of it
416 67 : rPolygonPool.free(nTmpIdx);
417 : }
418 413 : }
419 :
420 197 : std::ptrdiff_t handleComplexLeftEdge(ActiveEdge& rActiveEdge,
421 : const B2DPoint& rIntersectionPoint,
422 : VectorOfPolygons& rPolygonPool,
423 : B2DPolyPolygon& rRes)
424 : {
425 : const bool isHittingOurTail(
426 197 : rActiveEdge.getTargetPolygonIndex() == mnIdx);
427 197 : if( isHittingOurTail )
428 : {
429 75 : finish(rRes);
430 :
431 : // so "this" is done - need new polygon to collect
432 : // further points
433 75 : const std::ptrdiff_t nIdxNewPolygon=rPolygonPool.alloc();
434 75 : rPolygonPool.get(nIdxNewPolygon).setPolygonPoolIndex(nIdxNewPolygon);
435 75 : rPolygonPool.get(nIdxNewPolygon).append(rIntersectionPoint);
436 :
437 75 : rActiveEdge.setTargetPolygonIndex(nIdxNewPolygon);
438 :
439 75 : return nIdxNewPolygon;
440 : }
441 : else
442 : {
443 122 : const std::ptrdiff_t nTmpIdx=rActiveEdge.getTargetPolygonIndex();
444 122 : ImplPolygon& rTmp=rPolygonPool.get(nTmpIdx);
445 :
446 : // active edge's polygon has points
447 : // already. ours need to go in front of them.
448 : maPoints.insert(maPoints.end(),
449 : rTmp.maPoints.begin(),
450 122 : rTmp.maPoints.end());
451 :
452 122 : rTmp.maPoints.clear();
453 122 : rTmp.append(rIntersectionPoint);
454 :
455 : // adjust leading edges, we're switching the polygon
456 122 : ActiveEdge* const pFarEdge=rTmp.mpLeadingRightEdge;
457 122 : ActiveEdge* const pNearEdge=&rActiveEdge;
458 :
459 122 : rTmp.mpLeadingRightEdge = NULL;
460 122 : pNearEdge->setTargetPolygonIndex(nTmpIdx);
461 :
462 122 : mpLeadingRightEdge = pFarEdge;
463 122 : pFarEdge->setTargetPolygonIndex(mnIdx);
464 :
465 122 : return nTmpIdx;
466 : }
467 : }
468 :
469 209 : std::ptrdiff_t handleComplexRightEdge(ActiveEdge& rActiveEdge,
470 : const B2DPoint& rIntersectionPoint,
471 : VectorOfPolygons& rPolygonPool)
472 : {
473 209 : const std::ptrdiff_t nTmpIdx=rActiveEdge.getTargetPolygonIndex();
474 209 : ImplPolygon& rTmp=rPolygonPool.get(nTmpIdx);
475 :
476 209 : rTmp.append(rIntersectionPoint);
477 :
478 209 : rActiveEdge.setTargetPolygonIndex(mnIdx);
479 209 : mpLeadingRightEdge = &rActiveEdge;
480 :
481 209 : rTmp.mpLeadingRightEdge = NULL;
482 :
483 209 : return nTmpIdx;
484 : }
485 :
486 : /// True when sweep line hits our own active edge
487 1232 : static bool metOwnEdge(const SweepLineEvent& rEvent,
488 : ActiveEdge& rActiveEdge)
489 : {
490 1232 : const bool bHitOwnEdge=&rEvent.getRect() == &rActiveEdge.getRect();
491 1232 : return bHitOwnEdge;
492 : }
493 :
494 : /// Retrieve B2DPolygon from this object
495 421 : B2DPolygon getPolygon() const
496 : {
497 421 : B2DPolygon aRes;
498 : std::for_each( maPoints.begin(),
499 : maPoints.end(),
500 : boost::bind(
501 : &B2DPolygon::append,
502 : boost::ref(aRes),
503 : _1,
504 421 : 1 ) );
505 421 : aRes.setClosed( true );
506 421 : return aRes;
507 : }
508 :
509 : /** Finish this polygon, push to result set.
510 : */
511 421 : void finish(B2DPolyPolygon& rRes)
512 : {
513 : OSL_PRECOND( maPoints.empty() ||
514 : maPoints.front().getX() == maPoints.back().getX() ||
515 : maPoints.front().getY() == maPoints.back().getY(),
516 : "ImplPolygon::finish(): first and last point violate 90 degree line angle constraint!" );
517 :
518 421 : mbIsFinished = true;
519 421 : mpLeadingRightEdge = NULL;
520 :
521 421 : rRes.append(getPolygon());
522 421 : }
523 :
524 : /** Refers to the current leading edge element of this
525 : polygon, or NULL. The leading edge denotes the 'front'
526 : of the polygon vertex sequence, i.e. the coordinates
527 : at the polygon's leading edge are returned from
528 : maPoints.front()
529 : */
530 : ActiveEdge* mpLeadingRightEdge;
531 :
532 : /// current index into vector pool
533 : std::ptrdiff_t mnIdx;
534 :
535 : /// Container for the actual polygon points
536 : std::vector<B2DPoint> maPoints;
537 :
538 : /// When true, this polygon is 'done', i.e. nothing must be added anymore.
539 : bool mbIsFinished;
540 : };
541 :
542 : /** Init sweep line event list
543 :
544 : This method fills the event list with the sweep line
545 : events generated from the input rectangles, and sorts them
546 : with increasing x.
547 : */
548 229 : void setupSweepLineEventListFromRanges( VectorOfEvents& o_rEventVector,
549 : const std::vector<B2DRange>& rRanges,
550 : const std::vector<B2VectorOrientation>& rOrientations )
551 : {
552 : // we need exactly 2*rectVec.size() events: one for the
553 : // left, and one for the right edge of each rectangle
554 229 : o_rEventVector.clear();
555 229 : o_rEventVector.reserve( 2*rRanges.size() );
556 :
557 : // generate events
558 : // ===============
559 :
560 : // first pass: add all left edges in increasing order
561 229 : std::vector<B2DRange>::const_iterator aCurrRect=rRanges.begin();
562 229 : std::vector<B2VectorOrientation>::const_iterator aCurrOrientation=rOrientations.begin();
563 229 : const std::vector<B2DRange>::const_iterator aEnd=rRanges.end();
564 229 : const std::vector<B2VectorOrientation>::const_iterator aEndOrientation=rOrientations.end();
565 871 : while( aCurrRect != aEnd && aCurrOrientation != aEndOrientation )
566 : {
567 413 : const B2DRectangle& rCurrRect( *aCurrRect++ );
568 :
569 : o_rEventVector.push_back(
570 : SweepLineEvent( rCurrRect.getMinX(),
571 : rCurrRect,
572 : SweepLineEvent::STARTING_EDGE,
573 826 : (*aCurrOrientation++) == B2VectorOrientation::Positive ?
574 413 : SweepLineEvent::PROCEED_UP : SweepLineEvent::PROCEED_DOWN) );
575 : }
576 :
577 : // second pass: add all right edges in reversed order
578 229 : std::vector<B2DRange>::const_reverse_iterator aCurrRectR=rRanges.rbegin();
579 229 : std::vector<B2VectorOrientation>::const_reverse_iterator aCurrOrientationR=rOrientations.rbegin();
580 229 : const std::vector<B2DRange>::const_reverse_iterator aEndR=rRanges.rend();
581 871 : while( aCurrRectR != aEndR )
582 : {
583 413 : const B2DRectangle& rCurrRect( *aCurrRectR++ );
584 :
585 : o_rEventVector.push_back(
586 : SweepLineEvent( rCurrRect.getMaxX(),
587 : rCurrRect,
588 : SweepLineEvent::FINISHING_EDGE,
589 826 : (*aCurrOrientationR++) == B2VectorOrientation::Positive ?
590 413 : SweepLineEvent::PROCEED_DOWN : SweepLineEvent::PROCEED_UP ) );
591 : }
592 :
593 : // sort events
594 : // ===========
595 :
596 : // since we use stable_sort, the order of events with the
597 : // same x value will not change. The elaborate two-pass
598 : // add above thus ensures, that for each two rectangles
599 : // with similar left and right x coordinates, the
600 : // rectangle whose left event comes first will have its
601 : // right event come last. This is advantageous for the
602 : // clip algorithm below, see handleRightEdgeCrossing().
603 :
604 : std::stable_sort( o_rEventVector.begin(),
605 229 : o_rEventVector.end() );
606 229 : }
607 :
608 : /** Insert two active edge segments for the given rectangle.
609 :
610 : This method creates two active edge segments from the
611 : given rect, and inserts them into the active edge list,
612 : such that this stays sorted (if it was before).
613 :
614 : @param io_rEdgeList
615 : Active edge list to insert into
616 :
617 : @param io_rPolygons
618 : Vector of polygons. Each rectangle added creates one
619 : tentative result polygon in this vector, and the edge list
620 : entries holds a reference to that polygon (this _requires_
621 : that the polygon vector does not reallocate, i.e. it must
622 : have at least the maximal number of rectangles reserved)
623 :
624 : @param o_CurrentPolygon
625 : The then-current polygon when processing this sweep line
626 : event
627 :
628 : @param rCurrEvent
629 : The actual event that caused this call
630 : */
631 413 : void createActiveEdgesFromStartEvent( ListOfEdges& io_rEdgeList,
632 : VectorOfPolygons& io_rPolygonPool,
633 : SweepLineEvent& rCurrEvent )
634 : {
635 413 : ListOfEdges aNewEdges;
636 413 : const B2DRectangle& rRect=rCurrEvent.getRect();
637 413 : const bool bGoesDown=rCurrEvent.getEdgeDirection() == SweepLineEvent::PROCEED_DOWN;
638 :
639 : // start event - new rect starts here, needs polygon to
640 : // collect points into
641 413 : const std::ptrdiff_t nIdxPolygon=io_rPolygonPool.alloc();
642 413 : io_rPolygonPool.get(nIdxPolygon).setPolygonPoolIndex(nIdxPolygon);
643 :
644 : // upper edge
645 : aNewEdges.push_back(
646 : ActiveEdge(
647 : rRect,
648 413 : rRect.getMinY(),
649 : bGoesDown ? nIdxPolygon : -1,
650 : ActiveEdge::UPPER,
651 826 : bGoesDown ? ActiveEdge::PROCEED_LEFT : ActiveEdge::PROCEED_RIGHT) );
652 : // lower edge
653 : aNewEdges.push_back(
654 : ActiveEdge(
655 : rRect,
656 413 : rRect.getMaxY(),
657 : bGoesDown ? -1 : nIdxPolygon,
658 : ActiveEdge::LOWER,
659 826 : bGoesDown ? ActiveEdge::PROCEED_RIGHT : ActiveEdge::PROCEED_LEFT ) );
660 :
661 : // furthermore, have to respect a special tie-breaking
662 : // rule here, for edges which share the same y value:
663 : // newly added upper edges must be inserted _before_ any
664 : // other edge with the same y value, and newly added lower
665 : // edges must be _after_ all other edges with the same
666 : // y. This ensures that the left vertical edge processing
667 : // below encounters the upper edge of the current rect
668 : // first, and the lower edge last, which automatically
669 : // starts and finishes this rect correctly (as only then,
670 : // the polygon will have their associated active edges
671 : // set).
672 413 : const double nMinY( rRect.getMinY() );
673 413 : const double nMaxY( rRect.getMaxY() );
674 413 : ListOfEdges::iterator aCurr( io_rEdgeList.begin() );
675 413 : const ListOfEdges::iterator aEnd ( io_rEdgeList.end() );
676 2650 : while( aCurr != aEnd )
677 : {
678 1958 : const double nCurrY( aCurr->getInvariantCoord() );
679 :
680 2325 : if( nCurrY >= nMinY &&
681 367 : aNewEdges.size() == 2 ) // only add, if not yet done.
682 : {
683 : // insert upper edge _before_ aCurr. Thus, it will
684 : // be the first entry for a range of equal y
685 : // values. Using splice here, since we hold
686 : // references to the moved list element!
687 : io_rEdgeList.splice( aCurr,
688 : aNewEdges,
689 170 : aNewEdges.begin() );
690 : }
691 :
692 1958 : if( nCurrY > nMaxY )
693 : {
694 : // insert lower edge _before_ aCurr. Thus, it will
695 : // be the last entry for a range of equal y values
696 : // (aCurr is the first entry strictly larger than
697 : // nMaxY). Using splice here, since we hold
698 : // references to the moved list element!
699 : io_rEdgeList.splice( aCurr,
700 : aNewEdges,
701 134 : aNewEdges.begin() );
702 : // done with insertion, can early-exit here.
703 547 : return;
704 : }
705 :
706 1824 : ++aCurr;
707 : }
708 :
709 : // append remainder of aNewList (might still contain 2 or
710 : // 1 elements, depending of the contents of io_rEdgeList).
711 : io_rEdgeList.splice( aCurr,
712 279 : aNewEdges );
713 : }
714 :
715 5222 : inline bool isSameRect(ActiveEdge& rEdge,
716 : const basegfx::B2DRange& rRect)
717 : {
718 5222 : return &rEdge.getRect() == &rRect;
719 : }
720 :
721 : // wow what a hack. necessary because stl's list::erase does
722 : // not eat reverse_iterator
723 : template<typename Cont, typename Iter> Iter eraseFromList(Cont&, Iter);
724 414 : template<> inline ListOfEdges::iterator eraseFromList(
725 : ListOfEdges& rList, ListOfEdges::iterator aIter)
726 : {
727 414 : return rList.erase(aIter);
728 : }
729 412 : template<> inline ListOfEdges::reverse_iterator eraseFromList(
730 : ListOfEdges& rList, ListOfEdges::reverse_iterator aIter)
731 : {
732 : return ListOfEdges::reverse_iterator(
733 412 : rList.erase(boost::prior(aIter.base())));
734 : }
735 :
736 : template<int bPerformErase,
737 826 : typename Iterator> inline void processActiveEdges(
738 : Iterator first,
739 : Iterator last,
740 : ListOfEdges& rActiveEdgeList,
741 : SweepLineEvent& rCurrEvent,
742 : VectorOfPolygons& rPolygonPool,
743 : B2DPolyPolygon& rRes )
744 : {
745 826 : const basegfx::B2DRange& rCurrRect=rCurrEvent.getRect();
746 :
747 : // fast-forward to rCurrEvent's first active edge (holds
748 : // for both starting and finishing sweep line events, a
749 : // rect is regarded _outside_ any rects whose events have
750 : // started earlier
751 826 : first = std::find_if(first, last,
752 : boost::bind(
753 : &isSameRect,
754 : _1,
755 413 : boost::cref(rCurrRect)));
756 :
757 826 : if(first == last)
758 0 : return;
759 :
760 826 : int nCount=0;
761 826 : std::ptrdiff_t nCurrPolyIdx=-1;
762 2884 : while(first != last)
763 : {
764 2058 : if( nCurrPolyIdx == -1 )
765 826 : nCurrPolyIdx=first->getTargetPolygonIndex();
766 :
767 : OSL_ASSERT(nCurrPolyIdx != -1);
768 :
769 : // second encounter of my rect -> second edge
770 : // encountered, done
771 : const bool bExit=
772 : nCount &&
773 1232 : isSameRect(*first,
774 3290 : rCurrRect);
775 :
776 : // deal with current active edge
777 4116 : nCurrPolyIdx =
778 2058 : rPolygonPool.get(nCurrPolyIdx).intersect(
779 : rCurrEvent,
780 2058 : *first,
781 : rPolygonPool,
782 : rRes,
783 : bExit);
784 :
785 : // prune upper & lower active edges, if requested
786 999 : if( bPerformErase && (bExit || !nCount) )
787 826 : first = eraseFromList(rActiveEdgeList,first);
788 : else
789 1232 : ++first;
790 :
791 : // delayed exit, had to prune first
792 2058 : if( bExit )
793 826 : return;
794 :
795 1232 : ++nCount;
796 : }
797 : }
798 :
799 413 : template<int bPerformErase> inline void processActiveEdgesTopDown(
800 : SweepLineEvent& rCurrEvent,
801 : ListOfEdges& rActiveEdgeList,
802 : VectorOfPolygons& rPolygonPool,
803 : B2DPolyPolygon& rRes )
804 : {
805 413 : processActiveEdges<bPerformErase>(
806 : rActiveEdgeList. begin(),
807 : rActiveEdgeList. end(),
808 : rActiveEdgeList,
809 : rCurrEvent,
810 : rPolygonPool,
811 413 : rRes);
812 413 : }
813 :
814 413 : template<int bPerformErase> inline void processActiveEdgesBottomUp(
815 : SweepLineEvent& rCurrEvent,
816 : ListOfEdges& rActiveEdgeList,
817 : VectorOfPolygons& rPolygonPool,
818 : B2DPolyPolygon& rRes )
819 : {
820 413 : processActiveEdges<bPerformErase>(
821 : rActiveEdgeList. rbegin(),
822 : rActiveEdgeList. rend(),
823 : rActiveEdgeList,
824 : rCurrEvent,
825 : rPolygonPool,
826 826 : rRes);
827 413 : }
828 :
829 : enum{ NoErase=0, PerformErase=1 };
830 :
831 413 : void handleStartingEdge( SweepLineEvent& rCurrEvent,
832 : ListOfEdges& rActiveEdgeList,
833 : VectorOfPolygons& rPolygonPool,
834 : B2DPolyPolygon& rRes)
835 : {
836 : // inject two new active edges for rect
837 : createActiveEdgesFromStartEvent( rActiveEdgeList,
838 : rPolygonPool,
839 413 : rCurrEvent );
840 :
841 413 : if( SweepLineEvent::PROCEED_DOWN == rCurrEvent.getEdgeDirection() )
842 : processActiveEdgesTopDown<NoErase>(
843 206 : rCurrEvent, rActiveEdgeList, rPolygonPool, rRes);
844 : else
845 : processActiveEdgesBottomUp<NoErase>(
846 207 : rCurrEvent, rActiveEdgeList, rPolygonPool, rRes);
847 413 : }
848 :
849 413 : void handleFinishingEdge( SweepLineEvent& rCurrEvent,
850 : ListOfEdges& rActiveEdgeList,
851 : VectorOfPolygons& rPolygonPool,
852 : B2DPolyPolygon& rRes)
853 : {
854 413 : if( SweepLineEvent::PROCEED_DOWN == rCurrEvent.getEdgeDirection() )
855 : processActiveEdgesTopDown<PerformErase>(
856 207 : rCurrEvent, rActiveEdgeList, rPolygonPool, rRes);
857 : else
858 : processActiveEdgesBottomUp<PerformErase>(
859 206 : rCurrEvent, rActiveEdgeList, rPolygonPool, rRes);
860 413 : }
861 :
862 826 : inline void handleSweepLineEvent( SweepLineEvent& rCurrEvent,
863 : ListOfEdges& rActiveEdgeList,
864 : VectorOfPolygons& rPolygonPool,
865 : B2DPolyPolygon& rRes)
866 : {
867 826 : if( SweepLineEvent::STARTING_EDGE == rCurrEvent.getEdgeType() )
868 413 : handleStartingEdge(rCurrEvent,rActiveEdgeList,rPolygonPool,rRes);
869 : else
870 413 : handleFinishingEdge(rCurrEvent,rActiveEdgeList,rPolygonPool,rRes);
871 826 : }
872 : }
873 :
874 : namespace tools
875 : {
876 229 : B2DPolyPolygon solveCrossovers(const std::vector<B2DRange>& rRanges,
877 : const std::vector<B2VectorOrientation>& rOrientations)
878 : {
879 : // sweep-line algorithm to generate a poly-polygon
880 : // from a bunch of rectangles
881 : // ===============================================
882 :
883 : // This algorithm uses the well-known sweep line
884 : // concept, explained in every good text book about
885 : // computational geometry.
886 :
887 : // We start with creating two structures for every
888 : // rectangle, one representing the left x coordinate,
889 : // one representing the right x coordinate (and both
890 : // referencing the original rect). These structs are
891 : // sorted with increasing x coordinates.
892 :
893 : // Then, we start processing the resulting list from
894 : // the beginning. Every entry in the list defines a
895 : // point in time of the line sweeping from left to
896 : // right across all rectangles.
897 229 : VectorOfEvents aSweepLineEvents;
898 : setupSweepLineEventListFromRanges( aSweepLineEvents,
899 : rRanges,
900 229 : rOrientations );
901 :
902 229 : B2DPolyPolygon aRes;
903 458 : VectorOfPolygons aPolygonPool;
904 458 : ListOfEdges aActiveEdgeList;
905 :
906 : // sometimes not enough, but a usable compromise
907 229 : aPolygonPool.reserve( rRanges.size() );
908 :
909 : std::for_each( aSweepLineEvents.begin(),
910 : aSweepLineEvents.end(),
911 : boost::bind(
912 : &handleSweepLineEvent,
913 : _1,
914 : boost::ref(aActiveEdgeList),
915 : boost::ref(aPolygonPool),
916 229 : boost::ref(aRes)) );
917 :
918 458 : return aRes;
919 : }
920 : }
921 2106 : }
922 :
923 : /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
|
