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