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