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