1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
|
/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
/*
* This file is part of the LibreOffice project.
*
* This Source Code Form is subject to the terms of the Mozilla Public
* License, v. 2.0. If a copy of the MPL was not distributed with this
* file, You can obtain one at http://mozilla.org/MPL/2.0/.
*
* This file incorporates work covered by the following license notice:
*
* Licensed to the Apache Software Foundation (ASF) under one or more
* contributor license agreements. See the NOTICE file distributed
* with this work for additional information regarding copyright
* ownership. The ASF licenses this file to you under the Apache
* License, Version 2.0 (the "License"); you may not use this file
* except in compliance with the License. You may obtain a copy of
* the License at http://www.apache.org/licenses/LICENSE-2.0 .
*/
#pragma once
#include <osl/diagnose.h>
#include <basegfx/range/b2drange.hxx>
#include <list>
#include <utility>
#include <algorithm>
namespace basegfx
{
/** Calculate connected ranges from input ranges.
This template constructs a list of connected ranges from the
given input ranges. That is, the output will contain a set of
ranges, itself containing a number of input ranges, which will
be mutually non-intersecting.
Example:
<code>
-------------------
| -------|
| | ||
| --- | ||
| | | -------| --------
| | +--------- | | |
| --+ | | | |
| | | | --------
| ---------- |
-------------------
</code
Here, the outer rectangles represent the output
ranges. Contained are the input rectangles that comprise these
output ranges.
@tpl UserData
User data to be stored along with the range, to later identify
which range went into which connected component. Must be
assignable, default- and copy-constructible.
*/
template< typename UserData > class B2DConnectedRanges
{
public:
/// Type of the basic entity (rect + user data)
typedef ::std::pair< B2DRange, UserData > ComponentType;
typedef ::std::list< ComponentType > ComponentListType;
/// List of (intersecting) components, plus overall bounds
struct ConnectedComponents
{
ComponentListType maComponentList;
B2DRange maTotalBounds;
};
typedef ::std::list< ConnectedComponents > ConnectedComponentsType;
/// Create the range calculator
B2DConnectedRanges() :
maDisjunctAggregatesList(),
maTotalBounds()
{
}
/** Add an additional range.
This method integrates a new range into the connected
ranges lists. The method has a worst-case time complexity
of O(n^2), with n denoting the number of already added
ranges (typically, for well-behaved input, it is O(n)
though).
*/
void addRange( const B2DRange& rRange,
const UserData& rUserData )
{
// check whether fast path is possible: if new range is
// outside accumulated total range, can add it as a
// separate component right away.
const bool bNotOutsideEverything(
maTotalBounds.overlaps( rRange ) );
// update own global bounds range
maTotalBounds.expand( rRange );
// assemble anything intersecting with rRange into
// this new connected component
ConnectedComponents aNewConnectedComponent;
// as at least rRange will be a member of
// aNewConnectedComponent (will be added below), can
// preset the overall bounds here.
aNewConnectedComponent.maTotalBounds = rRange;
// STAGE 1: Search for intersecting maDisjunctAggregatesList entries
// if rRange is empty, it will intersect with no
// maDisjunctAggregatesList member. Thus, we can safe us
// the check.
// if rRange is outside all other rectangle, skip here,
// too
if( bNotOutsideEverything &&
!rRange.isEmpty() )
{
typename ConnectedComponentsType::iterator aCurrAggregate;
typename ConnectedComponentsType::iterator aLastAggregate;
// flag, determining whether we touched one or more of
// the maDisjunctAggregatesList entries. _If_ we did,
// we have to repeat the intersection process, because
// these changes might have generated new
// intersections.
bool bSomeAggregatesChanged;
// loop, until bSomeAggregatesChanged stays false
do
{
// only continue loop if 'intersects' branch below was hit
bSomeAggregatesChanged = false;
// iterate over all current members of maDisjunctAggregatesList
for( aCurrAggregate=maDisjunctAggregatesList.begin(),
aLastAggregate=maDisjunctAggregatesList.end();
aCurrAggregate != aLastAggregate; )
{
// first check if current component's bounds
// are empty. This ensures that distinct empty
// components are not merged into one
// aggregate. As a matter of fact, they have
// no position and size.
if( !aCurrAggregate->maTotalBounds.isEmpty() &&
aCurrAggregate->maTotalBounds.overlaps(
aNewConnectedComponent.maTotalBounds ) )
{
// union the intersecting
// maDisjunctAggregatesList element into
// aNewConnectedComponent
// calc union bounding box
aNewConnectedComponent.maTotalBounds.expand( aCurrAggregate->maTotalBounds );
// extract all aCurrAggregate components
// to aNewConnectedComponent
aNewConnectedComponent.maComponentList.splice(
aNewConnectedComponent.maComponentList.end(),
aCurrAggregate->maComponentList );
// remove and delete aCurrAggregate entry
// from list (we've gutted it's content
// above). list::erase() will update our
// iterator with the predecessor here.
aCurrAggregate = maDisjunctAggregatesList.erase( aCurrAggregate );
// at least one aggregate changed, need to rescan everything
bSomeAggregatesChanged = true;
}
else
{
++aCurrAggregate;
}
}
}
while( bSomeAggregatesChanged );
}
// STAGE 2: Add newly generated connected component list element
// add new component to the end of the component list
aNewConnectedComponent.maComponentList.push_back(
ComponentType( rRange, rUserData ) );
// do some consistency checks (aka post conditions)
OSL_ENSURE( !aNewConnectedComponent.maComponentList.empty(),
"B2DConnectedRanges::addRange(): empty aggregate list" );
OSL_ENSURE( !aNewConnectedComponent.maTotalBounds.isEmpty() ||
aNewConnectedComponent.maComponentList.size() == 1,
"B2DConnectedRanges::addRange(): empty ranges must be solitary");
// add aNewConnectedComponent as a new entry to
// maDisjunctAggregatesList
maDisjunctAggregatesList.push_back( aNewConnectedComponent );
}
/** Apply a functor to each of the disjunct component
aggregates.
@param aFunctor
Functor to apply. Must provide an operator( const ConnectedComponents& ).
@return a copy of the functor, as applied to all aggregates.
*/
template< typename UnaryFunctor > UnaryFunctor forEachAggregate( UnaryFunctor aFunctor ) const
{
return ::std::for_each( maDisjunctAggregatesList.begin(),
maDisjunctAggregatesList.end(),
aFunctor );
}
private:
B2DConnectedRanges(const B2DConnectedRanges&) = delete;
B2DConnectedRanges& operator=( const B2DConnectedRanges& ) = delete;
/** Current list of disjunct sets of connected components
Each entry corresponds to one of the top-level rectangles
in the drawing above.
*/
ConnectedComponentsType maDisjunctAggregatesList;
/** Global bound rect over all added ranges.
*/
B2DRange maTotalBounds;
};
}
/* vim:set shiftwidth=4 softtabstop=4 expandtab: */
|
