# Rectification

`LazySets.Rectification`

— Type`Rectification{N, S<:LazySet{N}} <: LazySet{N}`

Type that represents the rectification of a set.

**Fields**

`X`

– set`cache`

– storage of information computed before

**Notes**

Given a vector $v = (v_1, …, v_n)$, its rectification is defined as $\text{rectify}(v) = (v_1', …, v_n')$ such that $v_i' = \max(v_i, 0)$ for each $i = 1, …, n$.

The extension to a set $X$ is defined elementwise:

\[ \text{rectify}(X) = \{\text{rectify}(x) \mid x ∈ X\}\]

The rectification of a convex set $X$ is not necessarily convex.

It can be expressed exactly as the union of the intersection of $X$ with the nonnegative orthant and the projection of the intersection of $X$ with each other orthant. This can be seen as follows.

First we observe that rectification distributes with union.

\[ \text{rectify}(X_1 ∪ … ∪ X_m) = ⋃_j \text{rectify}(X_j)\]

Next we express $X$ as the union of the intersection of $X$ with each orthant $O$.

\[ X = ⋃_j (X ∩ O_j)\]

Thus we have

\[ \text{rectify}(X) = \text{rectify}((X ∩ O_1) ∪ … ∪ (X ∩ O_m)) = ⋃_j \text{rectify}(X ∩ O_j).\]

Clearly, $\text{rectify}(X ∩ O_j) = X$ if $O_j$ is the nonnegative orthant.

For example, consider a two-dimensional case and call the orthants $O_1, …, O_4$ in clockwise fashion, starting with the nonnegative orthant. We conclude that

\[ \text{rectify}(X) = (X ∩ O_1) ∪ \text{rectify}(X ∩ O_2) ∪ \text{rectify}(X ∩ O_3) ∪ \text{rectify}(X ∩ O_4).\]

The rectification of the intersection in the nonpositive orthant, $\text{rectify}(X ∩ O_3)$, is either the empty set or the singleton containing the origin. The rectification of $X ∩ O_2$ and $X ∩ O_4$ both result in flat $1$-dimensional line segments on the corresponding hyperplane of $O_1$.

`LazySets.set`

— Method`set(R::Rectification)`

Return the original set of a rectification.

**Input**

`R`

– rectification

**Output**

The original set of the rectification.

`LazySets.API.dim`

— Method`dim(R::Rectification)`

Return the dimension of a rectification.

**Input**

`R`

– rectification

**Output**

The ambient dimension of the rectification.

`LazySets.API.σ`

— Method`σ(d::AbstractVector, R::Rectification)`

Return a support vector of a rectification.

**Input**

`d`

– direction`R`

– rectification

**Output**

A support vector in the given direction. If the direction has norm zero, the result depends on the wrapped set.

`LazySets.API.σ`

— Method```
σ(d::AbstractVector,
R::Rectification{N, <:AbstractHyperrectangle{N}}) where {N}
```

Return a support vector of the rectification of a hyperrectangular set.

**Input**

`d`

– direction`R`

– rectification of a hyperrectangular set

**Output**

A support vector in the given direction.

**Algorithm**

Let $R(·)$ be the rectification of a vector respectively a set, and let $H$ be a hyperrectangle. Then $σ_{R(H)}(d) = R(σ_{H}(d))$.

`LazySets.API.σ`

— Method`σ(d::AbstractVector, R::Rectification{N, <:CartesianProduct{N}}) where {N}`

Return a support vector of the rectification of a Cartesian product of two sets.

**Input**

`d`

– direction`R`

– rectification of a Cartesian product of two sets

**Output**

A support vector in the given direction.

**Notes**

Note that this implementation creates new `Rectification`

objects that do not get preserved. Hence a second support-vector query does not benefit from the computations in the first query. For this use case another implementation should be added.

**Algorithm**

Rectification distributes with the Cartesian product. Let $R(·)$ be the rectification of a set. We can just query a support vector for $R(X)$ and $R(Y)$ recursively: $σ_{R(X × Y)}(d) = σ_{R(X)}(d_X) × σ_{R(Y)}(d_Y)$, where $x × y$ concatenates vectors $x$ and $y$.

`LazySets.API.σ`

— Method```
σ(d::AbstractVector,
R::Rectification{N, <:CartesianProductArray{N}}) where {N}
```

Return a support vector of the rectification of a Cartesian product of a finite number of sets.

**Input**

`d`

– direction`R`

– rectification of a Cartesian product of a finite number of sets

**Output**

A support vector in the given direction.

**Notes**

Note that this implementation creates new `Rectification`

objects that do not get preserved. Hence a second support-vector query does not benefit from the computations in the first query. For this use case another implementation should be added.

**Algorithm**

Rectification distributes with the Cartesian product. Let $R(·)$ be the rectification of a set. We can just query a support vector for each subspace recursively: $σ_{R(X_1 × ⋯ × X_m)}(d) = σ_{R(X_1)}(d_{X_1}) × ⋯ × σ_{R(X_m)}(d_{X_m})$, where $x × y$ concatenates vectors $x$ and $y$.

`LazySets.API.ρ`

— Method`ρ(d::AbstractVector, R::Rectification)`

Evaluate the support function of a rectification in a given direction.

**Input**

`d`

– direction`R`

– rectification

**Output**

The support value of the rectification in the given direction.

**Algorithm**

We use different procedures for different types of input sets. If the wrapped set has a suitable structure for which we can efficiently compute the support vector, we fall back to the evaluation of the support function by means of the support vector. Otherwise we compute the union of projections to obtain a precise result (see `to_union_of_projections`

), and then compute the support function for this union. (The union is cached internally, so subsequent queries are more efficient.)

`LazySets.API.an_element`

— Method`an_element(R::Rectification)`

Return some element of a rectification.

**Input**

`R`

– rectification

**Output**

An element in the rectification. The implementation relies on the `an_element`

function of the wrapped set.

`Base.:∈`

— Method`∈(x::AbstractVector, R::Rectification)`

Check whether a given point is contained in a rectification.

**Input**

`x`

– point/vector`R`

– rectification

**Output**

`true`

iff $x ∈ R$.

**Algorithm**

We first scan for negative entries in the vector. If there are any, the vector is not contained in the rectification.

Next we ask a membership query in the wrapped set. If the answer is positive, the vector is contained in the rectification. (This holds because negative entries have been ruled out before.)

Otherwise, we scan for zero entries in the vector. If there are none, membership reduces to membership in the wrapped set, and so the answer is negative.

Finally, if there are zero entries in the vector and the vector is not contained in the wrapped set, we give up and throw an error.

`Base.isempty`

— Method`isempty(R::Rectification)`

Check whether a rectification is empty.

**Input**

`R`

– rectification

**Output**

`true`

iff the wrapped set is empty.

`LazySets.API.isbounded`

— Method`isbounded(R::Rectification)`

Check whether a rectification is bounded.

**Input**

`R`

– rectification

**Output**

`true`

iff the rectification is bounded.

**Algorithm**

Let $X$ be the set wrapped by rectification $R$. We first check whether $X$ is bounded (because then $R$ is bounded). Otherwise, we check unboundedness of $X$ in direction $(1, 1, …, 1)$, which is sufficient for unboundedness of $R$; this step is not necessary but rather a heuristics. Otherwise, we check boundedness of $X$ in every positive unit direction, which is sufficient and necessary for boundedness of $R$.

`LazySets.to_union_of_projections`

— Function```
to_union_of_projections(R::Rectification{N},
[concrete_intersection]::Bool=false) where {N}
```

Compute an equivalent union of projections from a rectification.

**Input**

`R`

– rectification`concrete_intersection`

– (optional, default:`false`

) option to compute all intersections concretely or lazily`filter_empty_sets`

– (optional, default:`true`

) option to filter out empty sets in the union

**Algorithm**

Let $X$ be the set wrapped by the rectification $R$. We compute a union of sets that represents the rectification of $X$ precisely. The sets are lazy projections, potentially of intersections.

We first identify those dimensions where $X$ is negative, using one call to `low`

per dimension, and collect the dimensions in the index set $I_\text{neg}$. For each element in $I_\text{neg}$ we will later apply a projection to zero.

Next we identify those dimensions from $I_\text{neg}$ where $X$ is also positive, using another `high`

query in each dimension, and collect the dimensions in the index set $I_\text{mix}$. Let us call the remaining dimensions ($I_\text{neg} ∖ I_\text{mix}$) $I_\text{nonpos}$. For each dimension in $j ∈ I_\text{mix}$ we will apply an intersection with axis-aligned polyhedra. In particular, we distinguish two cases using half-spaces $x_j ≤ 0$ and $x_j ≥ 0$, and then compute all possible combinations to intersect, using one half-space per dimension $j ∈ I_\text{mix}$.

Next we project the intersections in all dimensions from $i ∈ I_\text{mix}$ such that we used the half-space $x_i ≤ 0$ in their computation, and in all dimensions $j ∈ I_\text{nonpos}$ irrespective of the half-space used.

Finally, we take the union of the resulting sets.

**Output**

The result can be one of three cases depending on the wrapped set $X$, namely

- the set $X$ if $X$ is contained in the positive quadrant,
- a
`LinearMap`

(projection) of $X$ if for each dimension, $X$ is only either positive or negative, or - a
`UnionSetArray`

of`LinearMap`

s (projections) otherwise.

Inherited from `LazySet`

:

## Rectification cache

`LazySets.RectificationCache`

— Type`RectificationCache{N}`

Struct that is used as a cache for `Rectification`

s.

**Fields**

`set`

– set represented by the rectification (can be`nothing`

if not computed yet)`use_support_vector`

– flag indicating whether to use support-vector computations for the cached set