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