/
overapproximate_interval.jl
95 lines (70 loc) · 2.47 KB
/
overapproximate_interval.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
"""
overapproximate(S::LazySet, ::Type{<:Interval})
Return the overapproximation of a set with an interval.
### Input
- `S` -- one-dimensional set
- `Interval` -- target type
### Output
An interval.
### Algorithm
We use the `extrema` function.
"""
function overapproximate(S::LazySet, ::Type{<:Interval})
@assert dim(S) == 1 "cannot overapproximate a $(dim(S))-dimensional set " *
"with an `Interval`"
l, h = extrema(S, 1)
return Interval(l, h)
end
"""
overapproximate(cap::Intersection, ::Type{<:Interval})
Return the overapproximation of a lazy intersection with an interval.
### Input
- `cap` -- one-dimensional intersection
- `Interval` -- target type
### Output
An interval.
### Algorithm
The algorithm recursively overapproximates the two intersected sets with
intervals and then intersects these. (Note that this fails if the sets are
unbounded.)
For convex sets this algorithm is precise.
"""
function overapproximate(cap::Intersection, ::Type{<:Interval})
@assert dim(cap) == 1 "cannot overapproximate a $(dim(cap))-dimensional " *
"intersection with an `Interval`"
# TODO this does not work for unbounded sets; better define extrema and
# then copy the default implementation except if result is empty
X = overapproximate(first(cap), Interval)
Y = overapproximate(second(cap), Interval)
return intersection(X, Y)
end
"""
overapproximate(cap::IntersectionArray, ::Type{<:Interval})
Return the overapproximation of an intersection array with an interval.
### Input
- `cap` -- one-dimensional intersection array
- `Interval` -- target type
### Output
An interval.
### Algorithm
The algorithm recursively overapproximates the intersected sets with intervals
and then intersects these. (Note that this fails if the sets are
unbounded.)
For convex sets this algorithm is precise.
"""
function overapproximate(cap::IntersectionArray, ::Type{<:Interval})
@assert dim(cap) == 1 "cannot overapproximate a $(dim(cap))-dimensional " *
"intersection with an `Interval`"
a = array(cap)
# TODO this does not work for unbounded sets; better define extrema and
# then copy the default implementation except if result is empty
X = overapproximate(a[1], Interval)
@inbounds for i in 2:length(a)
Y = overapproximate(a[i], Interval)
X = intersection(X, Y)
if isempty(X)
return X
end
end
return X
end