-
Notifications
You must be signed in to change notification settings - Fork 32
/
IntersectionArray.jl
228 lines (163 loc) · 5.09 KB
/
IntersectionArray.jl
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
export IntersectionArray,
array
"""
IntersectionArray{N, S<:LazySet{N}} <: LazySet{N}
Type that represents the intersection of a finite number of sets.
### Fields
- `array` -- array of sets
### Notes
This type assumes that the dimensions of all elements match.
The `EmptySet` is the absorbing element for `IntersectionArray`.
The intersection preserves convexity: if the set arguments are convex, then
their intersection is convex as well.
"""
struct IntersectionArray{N,S<:LazySet{N}} <: LazySet{N}
array::Vector{S}
end
"""
∩(X::LazySet, Xs::LazySet...)
∩(Xs::Vector{<:LazySet})
Alias for the n-ary lazy intersection.
"""
∩(X::LazySet, Xs::LazySet...) = IntersectionArray(vcat(X, Xs...))
∩(X::LazySet) = X
∩(Xs::Vector{<:LazySet}) = IntersectionArray(Xs)
isoperationtype(::Type{<:IntersectionArray}) = true
isconvextype(::Type{IntersectionArray{N,S}}) where {N,S} = isconvextype(S)
# constructor for an empty sum with optional size hint and numeric type
function IntersectionArray(n::Int=0, N::Type=Float64)
arr = Vector{LazySet{N}}()
sizehint!(arr, n)
return IntersectionArray(arr)
end
# Universe is the neutral element for IntersectionArray
@neutral(IntersectionArray, Universe)
# EmptySet is the absorbing element for IntersectionArray
@absorbing(IntersectionArray, EmptySet)
# add functions connecting Intersection and IntersectionArray
@declare_array_version(Intersection, IntersectionArray)
"""
array(ia::IntersectionArray)
Return the array of an intersection of a finite number of sets.
### Input
- `ia` -- intersection of a finite number of sets
### Output
The array of an intersection of a finite number of sets.
"""
function array(ia::IntersectionArray)
return ia.array
end
"""
dim(ia::IntersectionArray)
Return the dimension of an intersection of a finite number of sets.
### Input
- `ia` -- intersection of a finite number of sets
### Output
The ambient dimension of the intersection of a finite number of sets, or `0` if
there is no set in the array.
"""
function dim(ia::IntersectionArray)
return length(ia.array) == 0 ? 0 : dim(ia.array[1])
end
"""
σ(d::AbstractVector, ia::IntersectionArray)
Return a support vector of an intersection of a finite number of sets in a given
direction.
### Input
- `d` -- direction
- `ia` -- intersection of a finite number of sets
### Output
A support vector in the given direction.
If the direction has norm zero, the result depends on the individual sets.
### Algorithm
This implementation computes the concrete intersection, which can be expensive.
"""
function σ(d::AbstractVector, ia::IntersectionArray)
X = concretize(ia)
return σ(d, X)
end
"""
isbounded(ia::IntersectionArray)
Check whether an intersection of a finite number of sets is bounded.
### Input
- `ia` -- intersection of a finite number of sets
### Output
`true` iff the intersection is bounded.
### Algorithm
We first check if any of the wrapped sets is bounded.
Otherwise we check boundedness via
[`LazySets._isbounded_unit_dimensions`](@ref).
"""
function isbounded(ia::IntersectionArray)
if any(isbounded, ia.array)
return true
end
return _isbounded_unit_dimensions(ia)
end
function isboundedtype(::Type{<:IntersectionArray{N,S}}) where {N,S}
return isboundedtype(S)
end
function is_polyhedral(ia::IntersectionArray)
return all(is_polyhedral, array(ia))
end
"""
∈(x::AbstractVector, ia::IntersectionArray)
Check whether a given point is contained in an intersection of a finite number
of sets.
### Input
- `x` -- point/vector
- `ia` -- intersection of a finite number of sets
### Output
`true` iff ``x ∈ ia``.
### Algorithm
A point ``x`` is in the intersection iff it is in each set.
"""
function ∈(x::AbstractVector, ia::IntersectionArray)
for S in ia.array
if x ∉ S
return false
end
end
return true
end
"""
constraints_list(ia::IntersectionArray)
Return the list of constraints of an intersection of a finite number of
(polyhedral) sets.
### Input
- `ia` -- intersection of a finite number of (polyhedral) sets
### Output
The list of constraints of the intersection.
### Notes
We assume that the underlying sets are polyhedral, i.e., offer a method
`constraints_list`.
### Algorithm
We create the polyhedron from the `constraints_list`s of the sets and remove
redundant constraints.
"""
function constraints_list(ia::IntersectionArray)
N = eltype(ia)
constraints = Vector{HalfSpace{N,Vector{N}}}() # TODO: use vector type of ia
for X in ia
clist_X = _normal_Vector(X)
append!(constraints, clist_X)
end
remove_redundant_constraints!(constraints)
return constraints
end
function concretize(ia::IntersectionArray)
a = array(ia)
@assert !isempty(a) "an empty intersection is not allowed"
X = ia
@inbounds for (i, Y) in enumerate(a)
if i == 1
X = concretize(Y)
else
X = intersection(X, concretize(Y))
end
end
return X
end
function translate(ia::IntersectionArray, x::AbstractVector)
return IntersectionArray([translate(X, x) for X in array(ia)])
end