Chapter 1

General Definitions

In the later, an obstacle ε j is defined as a closed subset of R n .

Visibility relations between two points

Definition 1.1.1 Let x 1 ∈ R n and x 2 ∈ R n be two points, and ε j be an obstacle . The visibility relation between the two points regards to the obstacle is defined as

(x 1 Vx 2 ) εj ⇔ Seg(x 1 , x 2 ) ∩ ε j = ∅,
(1.1)

with Seg(x 1 , x 2 ) the segment defined by the two edges x 1 and x 2 . The complement of this relation, the non-visibility relation, is denoted

(x 1 Vx 2 ) c εj = (x 1 Vx 2 ) εj .
(1.2)

Remark 1.1.1 Some remarks about this relation:

-the visibility relation is reflexive (x 1 Vx 2 ) εj ⇔ (x 2 Vx 1 ) εj .

(1.3)

-the visibility relation is symmetric (x 1 Vx 1 ) εj .

(1.4)

-the visibility relation is not transitive (Figure 1.1)

(x 1 Vx 2 ) εj ∧ (x 2 Vx 3 ) εj ⇒ (x 1 Vx 3 ) εj .
(1.5)

-the non-visibility relation can be noted

(x 1 Vx 2 ) εj ⇔ Seg(x 1 , x 2 ) ∩ ε j = ∅.
(1.6)

Figure 1.1 presents visibility and non-visibility examples between two points regards to an obstacle.

x 1

x 2

x 1

x 2

x 3 ε j

Figure 1.1: In this example: (x 1 Vx 2 ) εj , (x 2 Vx 3 ) εj and (x 1 Vx 3 ) εj .

x

x 1

x 2 E εj (x) ε j (a) Visible space example.

x

x 1

x 2 Û E εj (x) ε j (b) Non-visible space example. 1.2 Visible and non-visible spaces of a point Definition 1.2.1 Let x ∈ R n be a point and ε j an obstacle, with x ∈ ε j .

The visible space of the point x regards to the obstacle ε j is defined as

E εj (x) = {x i ∈ R n | (xVx i ) εj }.
(1.7)

The non-visible space of the point x regards to the obstacle ε j is defined as

Û E εj (x) = {x i ∈ R n | (xVx i ) εj }. (1.8) Remark 1.2.1 E c εj (x) = Û E εj (x).
(1.9)

Remark 1.2.2

(x 1 Vx 2 ) εj ⇔ x 1 ∈ E εj (x 2 ),
(1.10)

(x 1 Vx 2 ) εj ⇔ x 2 ∈ E εj (x 1 ),
(1.11)

x 2 ∈ E εj (x 1 ) ⇔ x 1 ∈ E εj (x 2 ).

(1.12)

Remark 1.2.3

(x 1 Vx 2 ) εj ⇔ x 1 ∈ Û E εj (x 2 ), (1.13) (x 1 Vx 2 ) εj ⇔ x 2 ∈ Û E εj (x 1 ), (1.14) x 2 ∈ Û E εj (x 1 ) ⇔ x 1 ∈ Û E εj (x 2 ).
(1.15) 1.3 Visible/non-visible/partially-visible spaces of a closed set Definition 1.3.1 Let X ⊂ R n be a closed set and ε j an obstacle, with X ∩ ε j = ∅.

The visible space of X regards to ε j is defined as

E εj (X) = {x i ∈ R n | ∀x ∈ X, (x i Vx) εj }.
(1.16)

The non-visible space of X regards to ε j is defined as

Û E εj (X) = {x i ∈ R n | ∀x ∈ X, (x i Vx) εj }.
(1.17)

The partially-visible space of X regards to ε j is defined as

E εj (X) = {x i ∈ R n | ∃x 1 ∈ X, ∃x 2 ∈ X, (x i Vx 1 ) εj ∧ (x i Vx 2 ) εj }.
(1.18)

x 1 x 2 X ε j Û E εj (X) E εj (X)
E εj (X) It can be noticed that the visibility relation is a binary relation when considering points, but a ternary relation when considering sets. The partially-visible space corresponds classically to the twilight (compared to the light (visible space) and the shade (non-visible space) ). Figure 1.3 presents an example of visible, non-visible and partially-visible spaces.

Proposition 1.3.1 links the visibility of a set to the visibility of its points.

Proposition 1.3.1 Let X ⊂ R n be a closed set, ε j an obstacle with X ∩ ε j = ∅, x ∈ X and x i ∈ R n two points with x i ∈ X. Then

(x i Vx) εj ⇒ x i ∈ E εj (X) ∪ E εj (X), (1.19) (x i Vx) εj ⇒ x i ∈ Û E εj (X) ∪ E εj (X).
(1.20) Proof (x i Vx) εj ⇒ x i ∈ Û E εj (X) (Eq. 1.16)

(x i Vx) εj ⇒ x i ∈ E εj (X) ∪ E εj (X)
(x i Vx) εj ⇒ x i ∈ E εj (X) (Eq. 1.16)

(x i Vx) εj ⇒ x i ∈ E εj (X) ∪ Û E εj (X)
1.4 Visibility regards to a set of obstacles

An environment of R n , noted E, is defined as a set of n O obstacles

E = n O j=1 ε j , (1.21) with ε 1 , • • • , ε j , • • • , ε n O obstacles of R n .
It is possible to extend the previous definitions to an environment:

(x 1 Vx 2 ) E ⇔ Seg(x 1 , x 2 ) ∩ E = ∅, (1.22) (x 1 Vx 2 ) E ⇔ Seg(x 1 , x 2 ) ∩ E = ∅, (1.23) E E (x) = {x i ∈ R n | (x i Vx) E }, (1.24) E c E (x) = Û E E (x), (1.25) E E (X) = {x i ∈ R n | ∀x ∈ X, (xVx i ) E }, (1.26) Û E E (X) = {x i ∈ R n | ∀x ∈ X, (xVx i ) E }.
(1.27)

The objective then is to characterize the visibility regards to an environment by considering the visibility regards to its obstacles.

x 1 x 1 x 2 ε 1 x 2 x 3 ε 2 ε 3
Figure 1.4: In this example (x 1 Vx 3 ) ε1 and (x 1 Vx 3 ) ε2 and (x 1 Vx 3 ) ε3 , then it can be conclude that (x 1 Vx 3 ) E . It can also be noticed that (x 1 Vx 2 ) ε1 and (x 1 Vx 2 ) ε2 and (x 1 Vx 2 ) ε3 , which leads to (x 1 Vx 2 ) E . The same idea applies to x 2 and x 3 : (x 2 Vx 3 ) ε1 and (x 2 Vx 3 ) ε2 and (x 2 Vx 3 ) ε3 , then (x 2 Vx 3 ) E .

Proposition 1.4.1 Let x 1 ∈ R n and x 2 ∈ R n be two distinct points, and E an environment of R n composed by n O obstacles with x 1 ∈ E and x 2 ∈ E. Then

(x 1 Vx 2 ) E ⇔ n O j=1 (x 1 Vx 2 ) εj ,
(1.28)

(x 1 Vx 2 ) E ⇔ n O j=1 (x 1 Vx 2 ) Ej .
(1.29)

Proof (Eq. 1.28)

(x 1 Vx 2 ) E ⇔ Seg(x 1 , x 2 ) ∩ E = ∅ (Eq. 1.22), ⇔ Seg(x 1 , x 2 ) ∩ n O j=1 ε j = ∅ (Eq. 1.21), ⇔ n O j=1 (Seg(x 1 , x 2 ) ∩ ε j ) = ∅, ⇔ ∀ε j ∈ E, Seg(x 1 , x 2 ) ∩ ε j = ∅, ⇔ ∀ε j ∈ E, (x 1 Vx 2 ) εj (Eq. 1.1), (x 1 Vx 2 ) E ⇔ n O j=1 (x 1 Vx 2 ) εj .
Proof (Eq. 1.29)

(x 1 Vx 2 ) E ⇔ Seg(x 1 , x 2 ) ∩ E = ∅ (Eq. 1.23), ⇔ Seg(x 1 , x 2 ) ∩ n O j=1 ε j = ∅ (Eq. 1.21), ⇔ n O j=1 (Seg(x 1 , x 2 ) ∩ ε j ) = ∅, ⇔ ∃ε j ∈ E|Seg(x 1 , x 2 ) ∩ ε j = ∅, ⇔ ∃ε j ∈ E|(x 1 Vx 2 ) εj (Eq. 1.6), (x 1 Vx 2 ) E ⇔ n O j=1 (x 1 Vx 2 ) εj . Figure 1.4 illustrates Propositions 1.4.1.
It is also possible to characterize the visibility spaces of a point regards to an environment to the visibility spaces of this point regards to the obstacles of the environment.

x x 1 x 2 Û E ε1 (x) ε 1 Û E ε2 (x) ε 2 Û E E (x) Figure 1.5: In this example Û E E (x) = Û E ε1 (x) ∪ Û E ε2 (x).
Proposition 1.4.2 Let x ∈ R n be a point and E an environment composed by n O obstacles with x ∈ E. Then

E E (x) = n O j=1 E εj (x), (1.30) Û E E (x) = n O j=1 Û E εj (x).
(1.31)

Proof (Eq. 1.30) E E (x) = {x i ∈ R n |(xVx i ) E } (Eq. 1.24), = {x i ∈ R n | n O j=1 (xVx i ) εj } (Eq. 1.28), = {x i ∈ R n |(xVx i ) ε1 } ∩ • • • ∩ {x i ∈ R n |(xVx i ) εj } ∩ • • • ∩ {x i ∈ R n |(xVx i ) εn O }, = E ε1 (x) ∩ • • • ∩ E εj (x) ∩ • • • ∩ E εn O (x) (Eq. 1.7), E E (x) = n O j=1 E εj (x).
Proof (Eq. 1.16)

Û E E (x) = E c E (x) (Eq. 1.25), = n O j=1 E εj (x) c (Eq. 1.30), = n O j=1 E c εj (x), Û E E (x) = n O j=1 Û E εj (x) (Eq. 1.9).
Figures 1.5 and 1.6 illustrate Proposition 1.4.2. Those propositions can be generalized to closed sets. It is possible to characterize the visibility spaces of a closed set regards to an environment by the visibility spaces of this set regards to the obstacles of the environment.

Proposition 1.4.3 Let X ⊂ R n be a closed set and E an environment defined by n O obstacles with X ∩ E = ∅. Then

E E (X) = n O j=1 E εj (X), (1.32) Û E E (X) ⊇ n O j=1 Û E εj (X).
(1.33)

x x 1 x 2 ε 1 ε 2 E ε1 (x) (a) Eε 1 (x).
x

x 1 x 2 ε 1 ε 2 E ε2 (x) (b) Eε 2 (x) x x 1 x 2 ε 1 ε 2 E E (x) (c) EE (x) Figure 1.6: In this example E E (x) = E ε1 (x) ∩ E ε2 (x).
Proof (Eq. 1.32)

E E (X) ={x i ∈ R n | ∀x ∈ X, (xVx i ) E } (Eq. 1.26), ={x i ∈ R n | ∀x ∈ X, n O j=1 (x i Vx) εj } (Eq. 1.28), ={x i ∈ R n | ∀x ∈ X, (x i Vx) ε1 } ∩ • • • ∩ {x i ∈ R n | ∀x ∈ X, (x i Vx) εj } ∩ • • • • • • ∩ {x i ∈ R n | ∀x ∈ X, (x i Vx) εn O }, = n O j=1 {x i ∈ R n | ∀x ∈ X, (x i Vx) εj }, E E (X) = m j=1 E Ej (X) (Eq. 1.16).
Proof (Eq. 1.33)

Û E E (X) = {x i ∈ R n | ∀x ∈ X, (x i Vx) E } (Eq. 1.27), = {x i ∈ R n | ∀x ∈ X, n O j=1 (x i Vx) εj } (Eq. 1.1). n O j=1 Û E εj (X) = n O j=1 {x i ∈ R n | ∀x ∈ X, (x i Vx) εj } (Eq. 1.17), = {x i ∈ R n | n O j=1 [∀x ∈ X, (x i Vx) εj ]}. {x i ∈ R n | ∀x ∈ X, n O j=1 (x i Vx) εj } ⊇ {x i ∈ R n | n O j=1 [∀x ∈ X, (x i Vx) εj ]}, ⇒ Û E E (X) ⊇ n O j=1 Û E εj (X).
It can be noticed that the non-visible space of a closed set regards to an environment can not be perfectly characterized by the non-visible spaces of this set regards to the obstacles of the environment (Equation 1.33). It can only be under approximated, this is illustrated Figure 1

.7. X x 1 x 2 ε 1 Û E ε1 (X) ε 2 (a) Û Eε 1 (X). X x 1 x 2 ε 1 Û E ε2 (X) ε 2 (b) Û Eε 2 (X) X x 1 x 2 ε 1 ε 2 Û E ε1 (X) ∪ Û E ε2 (X) (c) Û Eε 1 (X) ∪ Û Eε 2 (X). X x 1 x 2 ε 1 ε 2 Û E E (X) (d) EE (X) Figure 1.7: In this example it can be noticed that Û E E (X) ⊇ Û E ε1 (X) ∪ Û E ε2 (X).
Chapter 2

Particular cases of the visibility

In this section the visibility of three types of sources of R 2 are considered (point, segment and box -defined later -) regards to two types of obstacles of R 2 (segment and convex polygon). The interest is that in those cases the visibility spaces can be defined by sets of inequalities.

For a segment as obstacle, the following notation is used

ε s j = Seg(e 1j , e 2j ), (2.1)
with e 1j ∈ R 2 and e 2j ∈ R 2 two distinct points that represent the edges of the segment ε s j . ε p j is an obstacle that corresponds to a convex polygon defined by n Pj edges, named

e 1 , • • • , e k , • • • , e n P j , in a trigonometric order, with e k = (e 1 k , e 2 k ) ∈ R 2 .
ε p j can also be associated to a closed environment composed by n Pj segments:

ε p j ≡ n P j k=1
Seg(e k , e k+1 ), with e n P j +1 ≡ e 1 , (2.2)

In the following it is noted Seg(e k , e k+1 ) = ε s k .

(2.

3)

The interest of considering convex polygons remains in Proposition 2.0.4. Note that with random obstacles it is an inclusion, not an equality (Equation 1.33).

Proposition 2.0.4 Let X ∈ R 2 be a closed set and ε p j an obstacle composed by n Pj edges with X ∩ ε p j = ∅. Then

Û E ε p j (X) = n P j k=1 Û E ε s k (X). (2.4) Proof Û E ε p j (X) = {x i ∈ R 2 | ∀x ∈ X, (x i Vx) ε p j } (Eq. 1.17), = {x i ∈ R 2 | ∀x ∈ X, Seg(x i , x) ∩ ε p j = ∅} (Eq. 1.6), = {x i ∈ R 2 | ∀x ∈ X, Seg(x i , x) ∩ n P j k=1 ε s k = ∅} (Eq. 2.2), = {x i ∈ R 2 | ∀x ∈ X, n P j k=1 (Seg(x i , x) ∩ ε s k ) = ∅}, = n P j k=1 {x i ∈ R 2 | ∀x ∈ X, Seg(x i , x) ∩ ε s k = ∅}, = n P j k=1 {x i ∈ R 2 | ∀x ∈ X, (x i Vx)) ε s k } (Eq. 1.6), Û E ε p j (X) = n P j k=1 Û E ε s k (X) (Eq. 1.17).
Figure 2.1 illustrates Proposition 2.0.4.

X

x 1

x 2

e 1 Û E Seg(e1,e2) (X) e 2 e 3 ε p j (a) Û E Seg(e 1 ,e 2 ) (X). X x 1 x 2 e 1 Û E Seg(e2,e3) (X) = ∅ e 2 e 3 ε p j (b) Û E Seg(e 2 ,e 3 ) (X). X x 1 x 2 e 1 Û E Seg(e1,e3) (X) e 2 e 3 ε p j (c) Û E Seg(e 1 ,e 3 ) (X). X x 1 x 2 e 1 Û E ε p j (X) e 2 e 3 ε p j (d) Û E ε p j (X).
E ε s j (x) = {x i ∈ R 2 | [x i ∪ x] ∩ [e 1j ∪ e 2j ] = ∅ ∨ ζ x det(x i -e 1j |e 2j -e 1j ) > 0 ∨ ζ x det(x i -e 1j |x -e 1j ) > 0 ∨ ζ x det(x i -e 2j |x -e 2j ) < 0}, (2.5)
with

ζ x = ® 1 if det(x -e 1j |e 2j -e 1j ) > 0, -1 otherwise.
(2.6)

Proof E ε s j (x) = {x i ∈ R 2 | (xVx i ) ε s j } (Eq. 1.7), = {x i ∈ R 2 | Seg(x, x i ) ∩ Seg(e 1j , e 2j ) = ∅} (Eq. 1.1), = {x i ∈ R 2 | det(x -e 1j |e 2j -e 1j ) • det(x i -e 1j |e 2j -e 1j ) > 0 ∨ det(e 1j -x|x i -x) • det(e 2j -x|x i -x) > 0 ∨ [x ∪ x i ] ∩ [e 1j ∪ e 2j ] = ∅} (Eq. A.5).
According to Proposition C.1.1 (Appendix):

det(x -e 1j |e 2j -e 1j ) • det(x i -e 1j |e 2j -e 1j ) > 0 ∨ det(e 1j -x|x i -x) • det(e 2j -x|x i -x) > 0 ⇔ζ x det(x i -e 1j |e 2j -e 1j ) > 0 ∨ ζ x det(x i -e 1j |x -e 1j ) > 0 ∨ ζ x det(x i -e 2j |x -e 2j ) < 0.
(2.7)

Then E ε s j (x) = {x i ∈ R 2 | [x i ∪ x] ∩ [e 1j ∪ e 2j ] = ∅ ∨ ζ x det(x i -e 1j |e 2j -e 1j ) > 0 ∨ ζ x det(x i -e 1j |x -e 1j ) > 0 ∨ ζ x det(x i -e 2j |x -e 2j ) < 0}, x x 1 x 2 ζ x det(x i -e 1j |e 2j -e 1j ) > 0 ε s j e 1j e 2j ζ x det(x i -e 1j |x -e 1j ) > 0 ζ x det(x i -e 2j |x -e 2j ) < 0 (a) E ε s j (x).
x

x 1

x 2 The following proposition characterizes the non-visible space of a point regards to a segment.

ζ x det(x i -e 1j |e 2j -e 1j ) ≤ 0 ε s j e 1j e 2j ζ x det(x i -e 1j |x -e 1j ) ≤ 0 ζ x det(x i -e 2j |x -e 2j ) ≥ 0 (b) Û E ε s j (x)
Proposition 2.1.2 Let x ∈ R 2 be a point and ε s j = Seg(e 1j , e 2j ) an obstacle with x ∈ ε s j .

Then

Û E ε s j (x) = {x i ∈ R 2 | ζ x det(x i -e 1j |e 2j -e 1j ) ≤ 0 ∧ ζ x det(x i -e 1j |x -e 1j ) ≤ 0 ∧ ζ x det(x i -e 2j |x -e 2j ) ≥ 0 ∧ [x ∪ x i ] ∩ [e 1j ∪ e 2j ] = ∅ }, (2.8)
with

ζ x = ® 1 if det(x -e 1j |e 2j -e 1j ) > 0, -1 otherwise. Proof Û E ε s j (x) = (E ε s j (x)) c (Eq. 1.9), = {x i ∈ R 2 | [x ∪ x i ] ∩ [e 1j ∪ e 2j ] = ∅ ∨ ζ x det(x i -e 1j |e 2j -e 1j ) > 0 ∨ ζ x det(x i -e 1j |x -e 1j ) > 0 ∨ ζ x det(x i -e 2j |x -e 2j ) < 0} c (Eq. 2.5), = {x i ∈ R 2 | [x ∪ x i ] ∩ [e 1j ∪ e 2j ] = ∅ ∨ ζ x det(x i -e 1j |e 2j -e 1j ) > 0 ∨ ζ x det(x i -e 1j |x -e 1j ) > 0 ∨ ζ x det(x i -e 2j |x -e 2j ) < 0 c }, Û E ε s j (x) = {x i ∈ R 2 | [x ∪ x i ] ∩ [e 1j ∪ e 2j ] = ∅ ∧ ζ x det(x i -e 1j |e 2j -e 1j ) ≤ 0 ∧ ζ x det(x i -e 1j |x -e 1j ) ≤ 0 ∧ ζ x det(x i -e 2j |x -e 2j ) ≥ 0}.

Regards to a polygon obstacle

The following proposition characterizes the visible space of a point regards to a convex polygon.

Proposition 2.1.3 Let x ∈ R 2 be a point and ε p j a convex polygon defined by n Pj edges with x ∈ ε p j . Then

E ε p j (x) = n P j k=1 E ε s k (x).
(2.9) Proof

x 1 x 2 ε p j e 1 = e 6 E ε p j (x)
E ε p j (x) = n P j k=1 E ε s k (x) (Eq. 1.30 et 2.2).
The following proposition characterizes the non-visible space of a point regards to a polygon.

Proposition 2.1.4 Let x ∈ R 2 be a point and ε p j an obstacle defined by n Pj edges with x ∈ ε p j . Then

Û E ε p j (x) = n P j k=1 E ε s k (x).
(2.10)

Proof Û E ε p j (x) = n P j k=1 E ε s k (x) (

Visibility of a segment

A segment can be considered as a closed subset of R 2 .

Regards to a segment obstacle

First we consider the non-visible space of a segment regards to an other segment. It can be noticed that this space can be characterized by the non-visible spaces of the segment edges.

Proposition 2.2.1 Let Seg(x 1 , x 2 ) be a segment with x 1 ∈ R 2 and x 2 ∈ R 2 , and ε s j = Seg(e 1j , e 2j ) be an obstacle with Seg(

x 1 , x 2 ) ∩ ε s j = ∅. Then Û E ε s j (Seg(x 1 , x 2 )) = Û E ε s j (x 1 ) ∩ Û E ε s j (x 2 ). (2.11) Proof Û E ε s j (Seg(x 1 , x 2 )) = {x i ∈ R 2 | ∀x ∈ Seg(x 1 , x 2 ), (x i Vx) ε s j } (Eq. 1.16), = {x i ∈ R 2 | ∀x ∈ Seg(x 1 , x 2 ), [x ∪ x i ] ∩ [e 1j ∪ e 2j ] = ∅ ∧ ζ x det(x i -e 1j |e 2j -e 1j ) ≤ 0 ∧ ζ x det(x i -e 1j |x -e 1j ) ≤ 0 ∧ ζ x det(x i -e 2j |x -e 2j ) ≥ 0}(Eq. 2.8), x 1 x 1 x 2 ε s j e 1j e 2j x 2 Û E ε s j (x 1 ) (a) Û E ε s j (x1). x 1 x 1 x 2 ε s j e 1j e 2j x 2 Û E ε s j (x 2 ) (b) Û E ε s j (x2). x 1 x 1 x 2 ε s j e 1j e 2j x 2 Û E ε s j (Seg(x 1 , x 2 )) (c) Û E ε s j (Seg(x1, x2)) = Û E ε s j (x1) ∩ Û E ε s j (x2).
Û E ε s j (x 1 ) ∩ Û E ε s j (x 2 ) ={x i ∈ R 2 | ζ x1 det(x i -e 1j |e 2j -e 1j ) ≤ 0 ∧ ζ x1 det(x i -e 1j |x 1 -e 1j ) ≤ 0 ∧ ζ x1 det(x i -e 2j |x 1 -e 2j ) ≥ 0 ∧ [x 1 ∪ x i ] ∩ [e 1j ∪ e 2j ] = ∅}∩ {x i ∈ R 2 | ζ x2 det(x i -e 1j |e 2j -e 1j ) ≤ 0 ∧ ζ x2 det(x i -e 1j |x 2 -e 1j ) ≤ 0 ∧ ζ x2 det(x i -e 2j |x 2 -e 2j ) ≥ 0 ∧ [x 2 ∪ x i ] ∩ [e 1j ∪ e 2j ] = ∅}, (Eq. 2.8) Û E ε s j (x 1 ) ∩ Û E ε s j (x 2 ) ={x i ∈ R 2 | ζ x1 det(x i -e 1j |e 2j -e 1j ) ≤ 0 ∧ ζ x1 det(x i -e 1j |x 1 -e 1j ) ≤ 0 ∧ ζ x1 det(x i -e 2j |x 1 -e 2j ) ≥ 0 ∧ [x 1 ∪ x i ] ∩ [e 1j ∪ e 2j ] = ∅ ∧ ζ x2 det(x i -e 1j |e 2j -e 1j ) ≤ 0 ∧ ζ x2 det(x i -e 1j |x 2 -e 1j ) ≤ 0 ∧ ζ x2 det(x i -e 2j |x 2 -e 2j ) ≥ 0 ∧ [x 2 ∪ x i ] ∩ [e 1j ∪ e 2j ] = ∅}. According to Proposition C.2.1 (Appendix) ∀x ∈ Seg(x 1 , x 2 ), ζ x det(x i -e 1j |e 2j -e 1j ) ≤ 0 ∧ ζ x det(x i -e 1j |x -e 1j ) ≤ 0∧ ζ x det(x i -e 2j |x -e 2j ) ≥ 0 ⇔ ζ x1 det(x i -e 1j |x 1 -e 1j ) ≤ 0 ∧ ζ x2 det(x i -e 1j |x 2 -e 1j ) ≤ 0∧ ζ x1 det(x i -e 2j |x 1 -e 1j ) ≥ 0 ∧ ζ x2 det(x i -e 2j |x 2 -e 1j ) ≥ 0∧ ζ x1 det(x i -e 1j |e 2j -e 1j ) ≤ 0 ∧ ζ x2 det(x i -e 1j |e 2j -e 1j ) ≤ 0. Then Û E ε s j (Seg(x 1 , x 2 )) = Û E ε s j (x 1 ) ∩ Û E ε s j (x 2 ). Figure 2.4 illustrates Proposition 2.2.1.
The visible space of a segment regards to an other segment is more difficult to characterize. Indeed, it is not possible to characterize it by considering the visible spaces of the edges of the segment.

Proposition 2.2.2 Let Seg(x 1 , x 2 ) be a segment with x 1 ∈ R 2 and x 2 ∈ R 2 , and ε s j = Seg(e 1j , e 2j ) be an

obstacle with Seg(x 1 , x 2 ) ∩ ε s j = ∅. Then E ε s j (Seg(x 1 , x 2 )) = {x i ∈ R 2 | (ζ x1 = ζ x2 ) ∧ ζ x1 det(x i -e 1j |e 2j -e 1j ) > 0 ∨ ζ x1 det(x i -e 1j |x 1 -e 1j ) > 0 ∧ ζ x2 det(x i -e 1j |x 2 -e 1j ) > 0 ∨ ζ x1 det(x i -e 2j |x 1 -e 2j ) < 0 ∧ ζ x2 det(x i -e 2j |x 2 -e 2j ) < 0 ∨ (ζ x1 = -ζ x2 ) ∧ ζ e1 det(x i -e 1j |x 1 -e 1j ) > 0 ∨ ζ e1 det(x i -e 1j |x 2 -e 1j ) < 0 ∧ ζ e2 det(x i -e 2j |x 1 -e 2j ) > 0 ∨ ζ e2 det(x i -e 2j |x 2 -e 2j ) < 0 ∨ [x i ∪ x 1 ∪ x 2 ] ∩ [e 1j ∪ e 2j ] = ∅ }.
(2.12)

with

ζ x1 = ® 1 if det(x 1 -e 1j |e 2j -e 1j ) > 0, -1 otherwise. ζ x2 = ® 1 if det(x 2 -e 1j |e 2j -e 1j ) > 0, -1 otherwise. ζ e1 = ® 1 if det(e 1j -x 1 |x 2 -x 1 ) > 0, -1 otherwise. ζ e2 = ® 1 if det(e 2j -x 1 |x 2 -x 1 ) > 0, -1 otherwise.
Proof The proof of this proposition is presented in the appendix, Section C.3. Figures 2.5 and 2.6 illustrate Proposition 2.2.2.

Regards to a polygon obstacle

As it has already been pointed out, a polygon can be considered as a set of segments. It is then possible to characterize the visibility spaces of a segment regards to a polygon by considering the visibility spaces of the segment regards to the segments that define the polygon.

Then, for the visible space of a segment regards to a polygon:

Proposition 2.2.3 Let Seg(x 1 , x 2 ) be a segment with x 1 ∈ R 2 and x 2 ∈ R 2 , and ε p j an convex polygon defined by n Pj edges with Seg(

x 1 , x 2 ) ∩ ε p j = ∅. Then E ε p j (Seg(x 1 , x 2 )) = n P j k=1 E ε s k (Seg(x 1 , x 2 )). (2.13) Proof E ε p j (Seg(x 1 , x 2 )) = n P j k=1 E ε s k (Seg(x 1 , x 2 )) (Eq. 1.32 et 2.2).
And for the non-visible space of a segment regards to a polygon:

Proposition 2.2.4 Let Seg(x 1 , x 2 ) be a segment with x 1 ∈ R 2 and x 2 ∈ R 2 , and ε p j a convex polygon defined by n Pj edges with Seg(

x 1 , x 2 ) ∩ ε p j = ∅. Then Û E ε p j (Seg(x 1 , x 2 )) = n P j k=1 Û E ε s k (x 1 ) ∩ n P j k=1 Û E ε s k (x 2 ) .
(2.14)

x 1 x 1 x 2 ε s j e 1j e 2j
x 2

(a) ζx 1 det(xi -e1 j |e2 j -e1 j ) > 0.

x 1

x 1 x 2 ε s j e 1j e 2j
x 2

(b) ζx 1 det(xi -e1 j |x1 -e1 j ) > 0 ∧ ζx 2 det(xi -e1 j |x2 -e1 j ) > 0. x 1 x 1 x 2 ε s j e 1j e 2j x 2 (c) ζx 1 det(xi -e2 j |x1 -e1 j ) < 0 ∧ ζx 2 det(xi -e2 j |x2 -e1 j ) < 0. x 1 x 1 x 2 ε s j e 1j e 2j
x 2 Proof

E ε s j (Seg(x 1 , x 2 )) (d) E ε s j (Seg(x1, x2)).
Û E ε p j (Seg(x 1 , x 2 )) = n P j k=1 Û E ε s k (Seg(x 1 , x 2 )) (Eq. 2.4), = n P j k=1 ( Û E ε s k (x 1 ) ∩ Û E ε s k (x 2 )) (Eq. 2.11), Û E ε p j (Seg(x 1 , x 2 )) = n P j k=1 Û E ε s k (x 1 ) ∩ n P j k=1 Û E ε s k (x 2 ) .

Visibility of a box

As it is indicated in the appendix, a box [x] can be associated to four segments, Figure A.5. In the later, P x denotes the convex polygon associated to the box

[x] = [x 1 ] × [x 2 ] with [x 1 ] = [x 1 , x 1 ] and [x 2 ] = [x 2 , x 2 ].
P x = polygon defined by p 1 , p 2 , p 3 and p 4 ,

P x = n P k=1
Seg(p k , p k+1 ), with n P = 4 and p 5 ≡ p 1 ,

with p 1 = (x 1 , x 2 ), p 2 = (x 1 , x 2 ), p 3 = (x 1 , x 2 ), p 4 = (x 1 , x 2 ).
(2.15)

Thus the propositions of the previous section can be applied in order to characterize the visibility spaces of a box. x 1

x 1 x 1 x 2 ε s j e 1j e 2j x 2 (a) ζx 1 = -ζx 2 . x 1 x 1 x 2 ε s j e 1j e 2j x 2 (b) ζe 1 det(xi -e1 j |x1 -e1 j ) ∨ ζe 1 det(xi -e1 j |x2 -e1 j ). x 1 x 1 x 2 ε s j e 1j e 2j x 2 (c) ζe 2 det(xi -e2 j |x1 -e2 j ) ∨ ζe 2 det(xi -e2 j |x2 -e2 j ). x 1 x 1 x 2 ε s j e 1j e 2j x 2 (d) E ε s j (Seg(x1, x2)).
x 2

e 1 = e 6 E ε p j (Seg(x 1 , x 2 ))
x 1

e 2 e 4 e 5

x 2

ε p j e 3 (a) E ε p j (Seg(x1, x2)).
x 1

x 2

e 1 = e 6 Û E ε p j (Seg(x 1 , x 2 ))
x 1

e 2 e 4 e 5

x 2 x 1

ε p j e 3 (b) Û E ε p j (Seg(x1, x2)).
x 2 ε s j E ε s j ([x]) p 1 = p 5 p 2 e 2j e 1j p 3 p 4 [x] (a) E ε s j ([x]) = E ε s j (Px ).
x 1

x 2 Û E ε s j ([x]
)

p 1 = p 5 e 2j p 2 ε s j e 1j p 3 p 4 [x] (b) Û E ε s j ([x]) = Û E ε s j (Px ).

Regards to a segment obstacle

As denoted previously, the visibility spaces of a box can be characterized by the visibility spaces of the associated segments.

Proposition 2.3.1 Let [x] be a box with P x its corresponding polygon , and ε s j = Seg(e 1j , e 2j ) an obstacle with

P x ∩ ε s j = ∅. Then Û E ε p j ([x]) = Û E ε s j (P x ) = n P k=1 Û E ε s j (Seg(p k , p k+1 )).
(2.16)

Proof x i ∈ Û E ε s j (P x ) ⇔∀x p ∈ P x , (x i Vx p ) ε s j (Eq. 1.17), ⇔∀x p ∈ P x , x i ∈ Û E ε s j (x p ) (Eq. 1.13), ⇒∀Seg(p k , p k+1 ) ∈ P x , x i ∈ Û E ε s j (Seg(p k , p k+1 )), x i ∈ Û E ε s j (P x ) ⇒x i ∈ n P k=1 Û E ε s j (Seg(p k , p k+1 )). Then Û E ε s j (P x ) ⊇ n P k=1 Û E ε s j (Seg(p k , p k+1 )).
(2.17)

x i ∈ n P k=1 Û E ε s j (Seg(p k , p k+1 )) ⇔∀Seg(p k , p k+1 ) ∈ P x , ∀x s ∈ Seg(p k , p k+1 ), (x i Vx s ) ε s j (Eq. 1.17), ⇒∀x p ∈ P x , (x i Vx p ) ε s j , x i ∈ n P k=1 Û E ε s j (Seg(p k , p k+1 )) ⇒x i ∈ Û E ε s j (P x ) (Eq. 1.13).
Thus

n P k=1 Û E ε s j (Seg(p k , p k+1 )) ⊇ Û E ε s j (P x ).
(2.18)

It can be concluded (Eq. 2.17 et 2.18

) ⇒ Û E ε s j (P x ) = n P k=1 Û E ε s j (Seg(p k , p k+1 )).
And for the non-visible space of a box regards to a segment (Figure 2.8):

Proposition 2.3.2 Let [x] be a box with P x its corresponding polygon, and ε s j = Seg(e 1j , e 22 ) an obstacle with

P x ∩ ε s j = ∅. Then E ε p j ([x]) = E ε s j (P x ) = n P k=1 E ε s j (Seg(p k , p k+1 )). (2.19) Proof x i ∈ E ε s j (P x ) ⇔∀x p ∈ P x , (x i Vx p ) ε s j (Eq. 1.16), ⇔∀x p ∈ P x , x i ∈ E ε s j (x p ) (Eq. 1.10), ⇒∀Seg(p k , p k+1 ) ∈ P x , x i ∈ E ε s j (Seg(p k , p k+1 )), x i ∈ E ε s j (P x ) ⇒x i ∈ n P k=1 E ε s j (Seg(p k , p k+1 ))
.

Then E ε s j (P x ) ⊇ n P k=1 E ε s j (Seg(p k , p k+1 )).
(2.20)

x i ∈ n P k=1 E ε s j (Seg(p k , p k+1 )) ⇔∀Seg(p k , p k+1 ) ∈ P x , ∀x s ∈ Seg(p k , p k+1 ), (x i Vx s ) ε s j (Eq. 1.16), ⇒∀x p ∈ P x , (x i Vx p ) ε s j , x i ∈ n P k=1 E ε s j (Seg(p k , p k+1 )) ⇒x i ∈ E ε s j (P x ) (Eq. 1.10).
Thus

n P k=1 E ε s j (Seg(p k , p k+1 )) ⊇ E ε s j (P x ).
(2.21)

It can be concluded (Eq. 2.20 and 2.21

) ⇒ E ε s j (P x ) = n P k=1 E ε s j (Seg(p k , p k+1 )).
The last step consists of characterizing the visibility spaces of a box regards to a polygon obstacle.

Regards to a polygon obstacle

Proposition 2.3.3 Let [x] be a box with P x its corresponding polygon, and ε p j an obstacle defined by n Pj edges with

P x ∩ ε p j = ∅. Then Û E ε p j ([x]) = E ε p j (P x ) = n P k=1 n P j k =1 E ε s k (Seg(p k , p k+1 )) . (2.22) Proof E ε p j (P x ) = n P j k =1 E ε s k (P x ) (Eq. 1.32 et 2.2), E ε p j (P x ) = n P j k =1 n P k=1 E ε s k (Seg(p k , p k+1 )) (Eq. 2.19), E ε p j (P x ) = n P k=1 n P j k =1 E ε s k (Seg(p k , p k+1 )) .
And for the non-visible space it can be defined:

x 1 x 2 e 1 = e 6 E ε p j ([x]
)

p 1 = p 5 e 2 e 4 e 5 p 2 ε p j e 3 p 3 p 4 [x] (a) E ε p j ([x]) = E ε p j (Px ). x 1 x 2 e 1 = e 6 Û E ε p j ([x]
) Then

p 1 = p 5 e 2 e 4 e 5 p 2 ε p j e 3 p 3 p 4 [x] (b) Û E ε p j ([x]) = Û E ε p j (Px ).
Û E ε p j ([x]) = Û E ε p j (P x ) = n P k=1 n P j k =1 Û E ε s k (p k ) . (2.23) Proof Û E ε p j (P x ) = n P j k =1 Û E ε s k (P x ) (Eq. 2.4), = n P j k =1 n P k Û E ε s k (Seg(p k , p k+1
)) (Eq. 2.16),

= n P j k =1 n P k=1 ( Û E ε s k (p k ) ∩ Û E ε s k (p k+1 )) (Eq. 2.11), = n P j k =1 n P k=1 Û E ε s k (p k ) , Û E ε p j (P x ) = n P k=1 n P j k =1 Û E ε s k (p k ) .
Figure 2.9 illustrates Propositions 2.3.3 and 2.3.4.

We now have all the needed tools to detail the contractors.

Chapter 3

Visibility Contractors

Let x 1 ∈ [x 1 ] and x 2 ∈ [x 2 ] be two points, and ε p j a polygon obstacle. The idea is to reduce the domains [x 1 ] and [x 2 ] according to a visibility constraint (x 1 Vx 2 ) ε p j or a non-visibility constraint (x 1 Vx 2 ) ε p j (Figure 3.1). To be able to contract the domains, by using the propositions presented previously, we define contractors (algorithms). Those contractors rely on the following Proposition 3.0.5 Let a ∈ A be a point with A ⊂ R n , x ∈ [x] be a variable and E an environment defined in R n . Then

(aVx) E ⇒ x ∈ [x] ∩ Û E E (A) c (3.1) (aVx) E ⇒ x ∈ [x] ∩ E E (A) c (3.2)
Proof This proposition is deduced from Proposition 1.3.1.

The basic idea of the contractors is to use the characterizations of the visible and non-visible spaces to contract the domains.

As previously, the contractors are going to be described step by step. First the contractors associated to a point visibility are presented, then those associated to a segment visibility and finally to a box visibility.

It can be noticed that the contractors C det , C ∩=∅ , and C ∩ =∅ , used in the following, are presented in the appendix.

Contractions over a point visibility information

Point visibility contractor regards to a segment obstacle

This contractor, named C V ([x], a, ε s j ), is associated to the constraint (xVa) ε s j , (3.3) x 1 x 2 [x 2 ] ε p j [x 1 ] (a) Let x1 ∈ [x1] and x2 ∈ [x2]
be two points, and ε p j a polygon obstacle.

x 1

x 2

[x 2 ] ε p j [x 1 ] (b) Knowing that (x1Vx2) ε p
Û E ε s j (a) (a) (xVa) ε s j , with x ∈ [x]. a x 1 x 2 ε s j e 1j e 2j [x] Û E ε s j (a) (b) Contraction of [x]. Figure 3.2: Presentation of the contractor C V ([x], a, ε s j ).
with a ∈ R 2 , ε s j = Seg(e 1j , e 2j ), e 1j ∈ R 2 , e 2j ∈ R 2 and x ∈ [x]. Figure 3.2 illustrates its principle. This contractor is presented Algorithm 1. It is based on the complement of Equation 2.8.

Algorithm 1: Contractor C V ([x], a, ε s j ) Input: [x], a, ε s j = Seg(e 1j , e 2j ) 1 if det(a -e 1j |e 2j -e 1j ) > 0 then 2 ζ a = 1; 3 else 4 ζ a = -1; 5 [i 1 ] = C det ([x], e 1j , e 2j , ζ a ); 6 [i 2 ] = C det ([x], e 1j , a, ζ a ); 7 [i 3 ] = C det ([x], e 2j , a, -ζ a ); 8 [i 4 ] = C ∩=∅ ([x],
a, e 1j , e 2 );

Output:

[x] * = [i 1 ] ∪ [i 2 ] ∪ [i 3 ] ∪ [i 4 ]

Point non-visibility contractor regards to a segment obstacle

The dual of the previous contractor, named C V ([x], a, ε s j ), is associated to the constraint

(xVa) ε s j , (3.4) with a ∈ R 2 , ε s j = Seg(e 1j , e 2j ), e 1j ∈ R 2 , e 2j ∈ R 2 and x ∈ [x]
. This contractor is presented Algorithm 2. It is based on the complement of Equation 2.5. Figure 3.3 illustrates its principle.

Algorithm 2: Contractor C V ([x], a, ε s j ) Input: [x], a, ε s j = Seg(e 1j , e 2j ) 1 if det(a -e 1j |e 2j -e 1j ) > 0 then 2 ζ a = 1; 3 else 4 ζ a = -1; a x 1 x 2 ε s j e 1j e 2j [x] E ε s j (a) (a) (xVa) ε s j , with x ∈ [x]. a x 1 x 2 ε s j e 1j e 2j [x] E ε s j (a) (b) Contraction of [x].

Contractions over a segment visibility information

Segment visibility contractor regards to a segment obstacle

This contractor, named C V ([x], a, b, ε s j ), is associated to the constraint

(xVx ab ) ε s j , (3.5) with x ab ∈ Seg(a, b), a ∈ R 2 , b ∈ R 2 , ε s j = Seg(e 1j , e 2j ), e 1j ∈ R 2 , e 2j ∈ R 2 and x ∈ [x]
. It is detailed Algorithm 3. It is based on the complement of Equation 2.11. Figure 3.4 illustrates its principle.

Algorithm 3: Contractor C V ([x], a, b, ε s j ) Input: [x], a, b, ε s j = Seg(e 1j , e 2j ) 1 [i 1 ] = C V ([x], a, ε s j ); 2 [i 2 ] = C V ([x], b, ε s j ); Output: [x] * = [i 1 ] ∪ [i 2 ]

Segment non-visibility contractor regards to a segment obstacle

The dual of the previous contractor, named C V ([x], a, b, ε s j ), is associated to the constraint

(xVx ab ) ε s j , (3.6) a x 1 x 2 ε s j e 1j e 2j [x] E ε s j (Seg(a, b)) b (a) (xVx ab ) ε s j , with x ab ∈ Seg(a, b) and x ∈ [x]. a x 1 x 2 ε s j e 1j e 2j [x] E ε s j (Seg(a, b)) b (b) Contraction of [x]. Figure 3.5: Presentation of the contractor C V ([x], a, b, ε s j ). x 1 x 2 ε s j e 1j e 2j [x] Û E ε s j ([x s ]) [x s ] (a) (xVxs) ε s j , with xs ∈ [xs] and x ∈ [x].
x 1 with

x 2 ε s j e 1j e 2j [x] Û E ε s j ([x s ]) [x s ] (b) Contraction of [x].
x ab ∈ Seg(a, b), a ∈ R 2 , b ∈ R 2 , ε s j = Seg(e 1j , e 2j ), e 1j ∈ R 2 , e 2j ∈ R 2 and x ∈ [x]
. This contractor is presented Algorithm 4. It is based on the complement of Equation 2.12. Figure 3.5 illustrates its principle.

Contractions over a box visibility information

Box visibility contractor regards to a segment obstacle

The contractor C

V ([x], [x s ], ε s j ) is associated to the constraint (xVx s ) ε s j , (3.7) with ε s j = Seg(e 1j , e 2j ), e 1j ∈ R 2 , e 2j ∈ R 2 , x s ∈ [x s ] and x ∈ [x].

Box non-visibility contractor regards to a segment obstacle

The contractor C

V ([x], [x s ], ε s j ) is associated to the constraint (xVx s ) ε s j , (3.8) with ε s j = Seg(e 1j , e 2j ), e 1j ∈ R 2 , e 2j ∈ R 2 , x s ∈ [x s ] and x ∈ [x]
. This contractor is presented Algorithm 6. It is based on the complement of Equation 2.19. Figure 3.7 illustrates its principle.

Algorithm 4: Contractor C V ([x], a, b, ε s j ) Input: [x], a, b, ε s j = Seg(e 1j , e 2j ) 1 if det(a -e 1j |e 2j -e 1j ) > 0 then 2 ζ a = 1; 3 else 4 ζ a = -1; 5 if det(b -e 1j |e 2j -e 1j ) > 0 then 6 ζ b = 1; 7 else 8 ζ b = -1; 9 if det(e 1j -a|b -a) > 0 then ζ e1 = 1; else ζ e1 = -1; if det(e 2j -a|b -a) > 0 then ζ e2 = 1; else ζ e2 = -1; // Two possible cases if ζ a = ζ b then [i 11 ] = C det ([x], e 1j , e 2j , -ζ a ); [i 12 ] = C det ([x], e 1j , a, -ζ a ); [i 13 ] = C det ([x], e 1j , b, -ζ b ); [i 14 ] = C det ([x], e 2j , a, ζ a ); [i 15 ] = C det ([x], e 2j , b, ζ b ); [i output ] = [i 11 ] ∩ ([i 12 ] ∪ [i 13 ]) ∩ ([i 14 ] ∪ [i 15 ]) else // ζ a = -ζ b [i 21 ] = C det ([x], e 1j , a, -ζ e1 ); [i 22 ] = C det ([x], e 1j , b, ζ e1 ); [i 23 ] = C det ([x], e 2j , a, -ζ e2 ); [i 24 ] = C det ([x], e 2j , b, ζ e2 ); [i output ] = ([i 21 ] ∩ [i 22 ]) ∪ ([i 23 ] ∩ [i 24 ]) [i 0 ] = C ∩ =∅ ([x], a, e 1j , e 2j ) ∪ C ∩ =∅ ([x], b, e 1j , e 2j ); Output: [x] * = [i output ] ∩ [i 0 ] Algorithm 5: Contractor C V ([x], [x s ], ε s j ) Input: [x], [x s ], ε s j = Seg(e 1j , e 2j ) 1 P s = polygon associated to [x s ]; 2 for all p k ∈ P s do 3 [i k ] = C V ([x], p k , p k+1 , ε s j ); Output: [x] * = n P k=1 [i k ] Algorithm 6: Contractor C V ([x], [x s ], ε s j ) Input: [x], [x s ], ε s j = Seg(e 1j , e 2j ) 1 P s = polygon associated to [x s ]; 2 for all p k ∈ P s do 3 [i k ] = C V ([x], p k , p k+1 , ε s j ); Output: [x] * = n P k=1 [i k ] x 1 x 2 ε s j e 1j e 2j [x] E ε s j ([x s ]) [x s ] (a) (xVxs) ε s j , with xs ∈ [xs] et x ∈ [x].
x 1 x 1

x 2 ε s j e 1j e 2j [x] E ε s j ([x s ]) [x s ] (b) Contraction of [x]. Figure 3.7: Presentation of the contractor C V ([x], [x s ], ε s j ). x 1 x 2 ε p j e 1 = e 6 [x] Û E ε p j ([x s ]) [x s ]
x 2 ε p j e 1 = e 6 [x] Û E ε p j ([x s ]) [x s ]

Box visibility contractor regards to a polygon obstacle

The contractor C

V ([x], [x s ], ε p j ) is associated to the constraint (xVx s ) ε p j , (3.9) with ε p j a polygon defined by n Pj edges e k ∈ R 2 , x s ∈ [x s ] and x ∈ [x]
. This contractor is presented Algorithm 7. It is based on the complement of Equation 2.23. Figure 3.8 illustrates its principle.

Box non-visibility contractor regards to a polygon obstacle

The contractor C

V ([x], [x s ], ε p j ) is associated to the constraint (xVx s ) ε p j , (3.10)
with ε p j a polygon defined by n Pj edges e k ∈ R 2 , x s ∈ [x s ] and x ∈ [x]. This contractor is presented Algorithm 8. It is based on the complement of Equation 2.22. Figure 3.9 illustrates its principle. Algorithm 8:

Algorithm 7: Contractor C V ([x], [x s ], ε p j ) Input: [x], [x s ], ε p j P s = polygon associated to [x s ]; for all p k ∈ P s do for all e k ∈ ε p j do [j k ] = C V ([x], p k , Seg(e k , e k +1 )); [i k ] = n P j k =1 [j k ]; Output: [x] * = n P k=1 [i k ] [x s ] x 1 x 2 ε p j e 1 = e 6 [x] E ε p j ([x s ])
Contractor C V ([x], [x s ], ε p j ) Input: [x], [x s ], ε p j P s = polygon associated to [x s ]; for all p k ∈ P s do for all e k ∈ ε p j do [j k ] = C V ([x], p k , p k+1 , Seg(e k , e k +1 )); [i k ] = n P j k =1 [j k ]; Output: [x] * = n P k=1 [i k ] b = (7, 12)
x 1

x 2 c = (13, 6) a 1 = (4, 4)

a 2 = (3,
det(a 1 -b|c -b) = (4 -7)(6 -12) -(4 -12)(13 -7), = 66 > 0. det(a 2 -b|c -b) = (3 -7)(6 -12) -(16 -12)(13 -7), = 0. det(a 3 -b|c -b) = (15 -7)(6 -12) -(9 -12)(13 -7), = -30 < 0.
Algorithme 9 presents the contractor associated to the constraint

ζ det(x -a|b -a) ≥ 0 (A.3) with a = (a 1 , a 2 ) and b = (b 1 , b 2 ) two known points and ζ = {-1, 1}. By considering Equation A.3 x 1 ζ(b 2 -a 2 ) -x 2 ζ(b 1 -a 1 ) -ζ a 2 (b 1 -a 1 ) -a 1 (b 2 -a 2 ) ≥ 0 (A.4) Algorithm 9: Contractor C det ([x], a, b, ζ) Input: [x] = ([x 1 ], [x 2 ]), a = (a 1 , a 2 ), b = (b 1 , b 2 ), ζ 1 // Temporary variable to facilitate the reading 2 cst 1 = ζ(b 1 -a 1 ), cst 2 = ζ(b 2 -a 2 ), cst 3 = ζ a 2 (b 1 -a 1 ) -a 1 (b 2 -a 2 ) ; 3 // Initialization 4 [i 1 ] = [x 1 ]cst 2 , [i 2 ] = [x 2 ]cst 1 , [i 3 ] = [i 1 ] -[i 2 ] + cst 3 ; 5 // Contractions 6 [i 3 ] * = [i 3 ] ∩ R + ; 7 [i 1 ] * = [i 1 ] ∩ ([i 3 ] * -cst 3 + [i 2 ]); 8 [i 2 ] * = [i 2 ] ∩ ([i 1 ] * + cst 3 -[i 3 ] * ); 9 if cst2 = 0 then 10 [x 1 ] * = [x 1 ] ∩ ([i 1 ] * /cst 2 ); 11 else 12 [x 1 ] * = [x 1 ]; 13 if cst1 = 0 then 14 [x 2 ] * = [x 2 ] ∩ ([i 2 ] * /cst 1 ); 15 else 16 [x 2 ] * = [x 2 ]; Output: [x] * = ([x 1 ] * , [x 2 ] * ).

A.2.2 Intersection Test

The general idea to test the intersection between two segments is to test if the points of each segment are on both part of the other one [Jaulin 2001a]. Be four distinct points of

R 2 , a = (a 1 , a 2 ), b = (b 1 , b 2 ), c = (c 1 , c 2 ) and d = (d 1 , d 2 ). Then Seg(a, b) ∩ Seg(c, d) = ∅ ⇔ det(a -c|d -c) • det(b -c|d -c) > 0 ∨ det(c -a|b -a) • det(d -a|b -a) > 0 ∨ [a ∪ b] ∩ [c ∪ d] = ∅, (A.5) Seg(a, b) ∩ Seg(c, d) = ∅ ⇔ det(a -c|d -c) • det(b -c|d -c) ≤ 0∧ det(c -a|b -a) • det(d -a|b -a) ≤ 0 ∧ [a ∪ b] ∩ [c ∪ d] = ∅. (A.6) It can be noticed that it is needed to test [a ∪ b] ∩ [c ∪ d] to avoid the situation depicted in Figure A.3. A.2.3 Contractor for [a ∪ x] ∩ [c ∪ d]
We want the contractor associated to the constraint

[a ∪ [x]] ∩ [c ∪ d] = ∅, (A.7)
with a ∈ R 2 , b ∈ R 2 and c ∈ R 2 three known points and [x] ∈ IR 2 . By considering Equation A.7:

[a ∪ [x]] ∩ [c ∪ d] = ∅ ⇔ [min (a, [x]) , max (a, [x])] ∩ [min (c, d) , max (c, d)] = ∅ ⇔ [max (min (a, [x]) , min (c, d)) , min (max (a, [x]) , max (c, d))] = ∅ ⇔ max (min (a, [x]) , min (c, d)) ≤ min (max (a, [x]) , max (c, d)) ⇔ max (min (a, [x]) , min (c, d)) -min (max (a, [x]) , max (c, d)) ≤ 0 ⇔ Å max (min (a 1 , [x 1 ]) , min (c 1 , d 1 )) -min (max (a 1 , [x 1 ]) , max (c 1 , d 1 )) max (min (a 2 , [x 2 ]) , min (c 2 , d 2 )) -min (max (a 2 , [x 2 ]) , max (c 2 , d 2 )) ã ≤ Å 0 0 ã ⇔ (max (min (a 1 , [x 1 ]) , min (c 1 , d 1 )) -min (max (a 1 , [x 1 ]) , max (c 1 , d 1 ))) ≤ 0 ∧ (max (min (a 2 , [x 2 ]) , min (c 2 , d 2 )) -min (max (a 2 , [x 2 ]) , max (c 2 , d 2 ))) ≤ 0 (A.8) with min (a, [x]) = min ([x], a) = [min (a, x) , min (a, x)], (A.9) max (a, [x]) = max ([x], a) = [max (a, x) , max (a, x)]. (A.10)
It is needed to have contractors associated to the operators min () and max (). Algorithm 10 corresponds to the contractor associated to the constraint .11) and Algorithm 11 corresponds to the contractor associated to the constraint

[y] = min ([x], a) , (A
[y] = max ([x], a) . (A.12)
The two previous algorithms are inspired from [Jaulin 2001b].

Algorithm 10:

C min ([y], [x], a) Input: [x] = [x, x], [y] = [y, y], a // Contraction of [y] [y] * = [y] ∩ min ([x], a); // Contraction of [x] if a ∈ [y] * then [x] * = [x] ∩ [y] * ; else [x] * = [x] ∩ [y * , +∞]; Output: [x] * , [y] * . Algorithm 11: C max ([y], [x], a) Input: [x] = [x, x], [y] = [y, y], a // Contraction of [y] [y] * = [y] ∩ max ([x], a); // Contraction of [x] if a ∈ [y] * then [x] * = [x] ∩ [y] * ; else [x] * = [x] ∩ [-∞, y * ]; Output: [x] * , [y] * . Algorithm 12: C ∩ =∅ ([x], a, c, d) Input: [x] = [x, x], a, c, d // Initialization [i 1 ] = min (a, [x]); [i 2 ] = max ([i 1 ], min (c, d)); [i 3 ] = max (a, [x]); [i 4 ] = min ([i 3 ], max (c, d)); [i 5 ] = [i 2 ] -[i 4 ]; // Contractions [i 5 ] * = [i 5 ] ∩ [-∞, 0]; [i 2 ] * = [i 5 ] * + [i 4 ]; 10 [i 4 ] * = [i 2 ] * -[i 5 ]; 11 ([i 3 ] * , [i 4 ] * ) = C min ([i 4 ] * , [i 3 ], max (c, d)); 12 ([x] * , [i 3 ] * ) = C max ([i 3 ] * , [x], a); 13 ([i 1 ] * , [i 2 ] * ) = C max ([i 2 ] * , [i 1 ], min (c, d)); 14 ([x] * , [i 1 ] * ) = C min ([i 1 ] * , [x] * , a); Output: [x].

Proof

[x] ∪ a ∪ b ∩ [c ∪ d] = [min ([x], a, b) , max ([x], a, b)] ∩ [min (c, d) , max (c, d)].
(A.20)

[x] ∪ a ∩ [c ∪ d] ∪ [x] ∪ b ∩ [c ∪ d], = [min ([x, a]) , max ([x, a])] ∩ [min (c, d) , max (c, d)]∪ [min ([x], b) , max ([x], b)] ∩ [min (c, d) , max (c, d)], = [min (c, d) , max (c, d)]∩ [min ([x], a) , max ([x], a)] ∪ [min ([x], b) , max ([x], b)] , = [min (c, d) , max (c, d)]∩ [min (min ([x], b) , min ([x], a)) , max (max ([x], b) , max ([x], a))], = [min (c, d) , max (c, d)] ∩ [min ([x], a, b) , max ([x], a, b)], = [x] ∪ a ∪ b ∩ [c ∪ d]. (Eq. A.20) Algorithm 15: C ∩=∅ ([x], a, c, d) Input: [x] = ([x 1 ], [x 2 ]), a = (a 1 , a 2 ), c = (c 1 , c 2 ), d = (d 1 , d 2 ) 1 // Contraction over each component 2 [x 1 ] * = C ∩=∅ ([x 1 ], a 1 , c 1 , d 1 ); 3 [x 2 ] * = C ∩=∅ ([x 2 ], a 2 , c 2 , d 2 ); Output: [x] * = ([x 1 ] * , [x 2 ] * ).

A.3 Segments and Convex Polygons

A.3.1 Definitions

This section present polygons as considered in this report.

A convex Polygon P corresponds to a convex subset of R 2 , delimited by at least three segments. We note n P the number of edges (at least three) of the polygon P . The edges of P are denoted p k , k = 1, • • • , n P . Those edges are named according to a trigonometric order in this report.

Remark A.3.1 A polygon P with n P edges, is delimited by n P segments. In order to facilitate the reading, the first edge p 1 is equivalent to the edge p n P +1 . That leads to [

x] = ([x 1 ], [x 2 ]) x 2 x 2 x 2 [x 2 ] x 1 x 1 [x 1 ] x 1 p 1 p 2 p 3 p 4 Figure A.5: A box is a convex polygon. Definition A.3.1 Let P be a polygon with n P edges p k (k = 1, • • • , n P ), then ∀x ∈ P, ∀p k ∈ P, det(x -p k |p k+1 -p k ) ≤ 0. (A.22)
In other words, Equation A.22 describes all the points inside inside the polygon (border included). It can be noticed that this equation is correct only if the edges of the polygon are ordered in a trigonometric order. It is then possible to defined a polygon P as

P = {x i ∈ R 2 | n P k=1 det(x i -p k |p k+1 -p k ) ≤ 0}. (A.23) Remark A.3.2 A two dimensional interval vector (a box) can be assimilated to a convex polygon. Let [x] = ([x 1 ], [x 2 ]) = ([x 1 , x 1 ], [x 2 , x 2 ]
) be a box:

[x] = {x i ∈ R 2 | det(x i -(x 1 , x 2 )|(x 1 , x 2 ) -(x 1 , x 2 )) ≤ 0 ∧ det(x i -(x 1 , x 2 )|(x 1 , x 2 ) -(x 1 , x 2 )) ≤ 0 ∧ det(x i -(x 1 , x 2 )|(x 1 , x 2 ) -(x 1 , x 2 )) ≤ 0 ∧ det(x i -(x 1 , x 2 )|(x 1 , x 2 ) -(x 1 , x 2 )) ≤ 0}. (A.24)
Figure A.5 illustrates this remark. Algorithm 16 allows to match a two dimensional box R 2 with a convex polygon.

Algorithm 16: Boite2P olygone([x])

Input: [x] = ([x 1 ], [x 2 ]) 1 p 1 = (x 1 , x 2 ); 2 p 2 = (x 1 , x 2 ); 3 p 3 = (x 1 , x 2 ); 4 p 4 = (x 1 , x 2 ); 5 P x =
polygon defined by the four edges p 1 , p 2 , p 3 and p 4 ;

Output: P x .

A.3.2 Polygon/Segment Intersection

B.2 Second Proposition

Proposition B.2.1 Let a = (a 1 , a 2 ), b = (b 1 , b 2 ), c = (c 1 , c 2 ) and d = (d 1 , d 2 ) be four distinct points of R 2 . Then det(a -b|d -b) ≥ 0 ∧ det(a -b|c -b) ≤ 0 ∧ det(a -c|d -c) ≤ 0 ⇔ det(b -c|d -c) ≤ 0. (B.4) Figure B.1 illustrates this proposition. Proof      det(a -b|d -b) ≥ 0 det(a -b|c -b) ≤ 0 det(a -c|d -c) ≤ 0 , ⇔      (a 1 -b 1 )(d 2 -b 2 ) -(a 2 -b 2 )(d 1 -b 1 ) ≥ 0 (Eq. A.2) (a 1 -b 1 )(c 2 -b 2 ) -(a 2 -b 2 )(c 1 -b 1 ) ≤ 0 (Eq. A.2) (a 1 -c 1 )(a 2 -c 2 ) -(a 2 -c 2 )(d 1 -c 1 ) ≤ 0 (Eq. A.2) , ⇔      a 1 d 2 -a 1 b 2 -b 1 d 2 -a 2 d 1 + a 2 b 1 + b 2 d 1 ≥ 0 a 1 c 2 -a 1 b 2 -b 1 c 2 -a 2 c 1 + a 2 b 1 + b 2 c 1 ≤ 0 a 1 d 2 -a 1 c 2 -c 1 d 2 -a 2 d 1 + a 2 c 1 + c 2 d 1 ≤ 0 , ⇔      a 1 d 2 -b 1 d 2 -a 2 d 1 + b 2 d 1 ≥ a 1 b 2 -a 2 b 1 a 1 c 2 -b 1 c 2 -a 2 c 1 + b 2 c 1 ≤ a 1 b 2 -a 2 b 1 a 1 d 2 -a 1 c 2 -c 1 d 2 -a 2 d 1 + a 2 c 1 + c 2 d 1 ≤ 0 , ⇔ ® a 1 d 2 -b 1 d 2 -a 2 d 1 + b 2 d 1 ≥ a 1 b 2 -a 2 b 1 ≥ a 1 c 2 -b 1 c 2 -a 2 c 1 + b 2 c 1 a 1 d 2 -a 1 c 2 -c 1 d 2 -a 2 d 1 + a 2 c 1 + c 2 d 1 ≤ 0 , ⇔ ® a 1 d 2 -a 2 d 1 -a 1 c 2 + a 2 c 1 ≥ b 1 d 2 -b 2 d 1 -b 1 c 2 + b 2 c 1 a 1 d 2 -a 1 c 2 -a 2 d 1 + a 2 c 1 ≤ c 1 d 2 -c 2 d 1 , ⇔ c 1 d 2 -c 2 d 1 ≥ a 1 d 2 -a 2 d 1 -a 1 c 2 + a 2 c 1 ≥ b 1 d 2 -b 2 d 1 -b 1 c 2 + b 2 c 1 , ⇔ c 1 d 2 -c 2 d 1 ≥ b 1 d 2 -b 2 d 1 -b 1 c 2 + b 2 c 1 , ⇔ b 1 d 2 -b 1 c 2 -c 1 d 2 -b 2 d 1 + b 2 c 1 + c 2 d 1 ≤ 0, ⇔ (b 1 -c 1 )(d 1 -c 2 ) -(b 2 -c 2 )(d 1 -c 1 ) ≤ 0, ⇔ det(b -c|d -c) ≤ 0 (Eq. A.2).
det(a -c|d -c) ≥ det(b -c|d -c) ⇔ det(a -c|d -c) ≥ det(s -c|d -c) ≥ det(b -c|d -c), (B.5) det(a -c|d -c) ≤ det(b -c|d -c) ⇔ det(a -c|d -c) ≤ det(s -c|d -c) ≤ det(b -c|d -c). (B.6)
In other words, Proposition B.3.1 notifies that the distance between the point s and the line associated to the vector -→ cd is bounded by the distances of the two edges of the segment ab and this line. This is illustrated Figure

B.2. Proof det(a -c|d -c) = (a 1 -c 1 )(d 2 -c 2 ) -(a 2 -c 2 )(d 1 -c 1 ) (Eq. A.2), det(a -c|d -c) = a 1 d 2 -a 1 c 2 -c 1 d 2 -a 2 d 1 + a 2 c 1 + c 2 d 1 , (B.7) det(b -c|d -c) = (b 1 -c 1 )(d 2 -c 2 ) -(b 2 -c 2 )(d 1 -c 1 ) (Eq. A.2), det(b -c|d -c) = b 1 d 2 -b 1 c 2 -c 1 d 2 -b 2 d 1 + b 2 c 1 + c 2 d 1 . (B.8) det(b -c|d -c) -det(a -c|d -c) = b 1 d 2 -b 1 c2 -b 2 d 1 + b 2 c 1 -a 1 d 2 + a 1 c 2 + a 2 d 1 -a 2 c 1 . (B.9) det(s -c|d -c) = (s 1 -c 1 )(d 2 -c 2 ) -(s 2 -c 2 )(d 1 -c 1 ) (Eq. A.2), = s 1 d 2 -s 1 c 2 -c 1 d 2 -s 2 d 1 + s 2 c 1 + c 2 d 1 , = s 1 (d 2 -c 2 ) + s 2 (c 1 -d 1 ) + c 2 d 1 -c 1 d 2 , = (1 -t)a 1 + tb 1 (d 2 -c 2 ) + (1 -t)a 2 + tb 2 (c 1 -d 1 ) + c 2 d 1 -c 1 d 2 (Eq. A.1), = a 1 d 2 -a 1 c 2 -ta 1 d 2 + ta 1 c 2 + tb 1 d 2 -tb 1 c 2 + a 2 c 1 -a 2 d 1 , -ta 2 c 1 + ta 2 d 1 + tb 2 c 1 -tb 2 d 1 + c 2 d 1 -c 1 d 2 , = t(a 1 c 2 -a 1 d 2 + b 1 d 2 -b 1 c 2 -a 2 c 1 + a 2 d 1 + b 2 c 1 -b 2 d 1 ), + a 1 d 2 -a 1 c 2 + a 2 c 1 -a 2 d 1 -c 1 d 2 + c 2 d 1 , det(s -c|d -c) = t det(b -c|d -c) -det(a -c|d -c)
+ det(a -c|d -c) (Eq. B.9 et B.7). (B.10)

First case:

det(a -c|d -c)) ≥ det(b -c|d -c), ⇔ 0 ≥ det(b -c|d -c) -det(a -c|d -c), ⇔ 0 ≥ t det(b -c|d -c) -det(a -c|d -c) (t ≥ 0, Eq. A.1), ⇔ det(a -c|d -c) ≥ t det(b -c|d -c) -det(a -c|d -c) + det(a -c|d -c), ⇔ det(a -c|d -c) ≥ det(s -c|d -c) (Eq. B.10). (B.11) det(a -c|d -c) ≥ det(b -c|d -c), ⇔ 0 ≥ det(b -c|d -c) -det(a -c|d -c), ⇔ det(b -c|d -c) -det(a -c|d -c) ≤ t det(b -c|d -c) -det(a -c|d -c) (t ∈ [0, 1], Eq. A.1), ⇔ det(b -c|d -c) ≤ t det(b -c|d -c) -det(a -c|d -c) + det(a -c|d -c), ⇔ det(b -c|d -c) ≤ det(s -c|d -c) (Eq. B.10). (B.12) Then, if det(a -c|d -c) ≥ det(b -c|d -c), det(a -c|d -c) ≥ det(s -c|d -c) ≥ det(b -c|d -c) (Eq. B.11 et B.12).
Second case: We now aim to prove that:

det(a -c|d -c) ≤ det(b -c|d -c), ⇔ 0 ≤ det(b -c|d -c) -det(a -c|d -c), ⇔ 0 ≤ t det(b -c|d -c) -det(a -c|d -c) (t ≥ 0, Eq. A.1), ⇔ det(a -c|d -c) ≤ t det(b -c|d -c) -det(a -c|d -c) + det(a -c|d -c), ⇔ det(a -c|d -c) ≤ det(s -c|d -c) (Eq. B.10). (B.13) det(a -c|d -c) ≤ det(b -c|d -c), ⇔ 0 ≤ det(b -c|d -c) -det(a -c|d -c), ⇔ det(b -c|d -c) -det(a -c|d -c) ≥ t det(b -c|d -c) -det(a -c|d -c) (t ∈ [0, 1], Eq. A.1), ⇔ det(b -c|d -c) ≥ t det(b -c|d -c) -det(a -c|d -c) + det(a -c|d -c), ⇔ det(b -c|d -c) ≥ det(s -c|d -c) (Eq. B.10). (B.14) Then, if det(a -c|d -c) ≤ det(b -c|d -c), det(a -c|d -c) ≤ det(s -c|d -c) ≤ det(b -c|d -c) (Eq. B.13 et B.14). d(x i , e 1j , e 2j ) < 0 ∨ d(x i , e 1j , x) < 0 ⇔ d(x i , e 1j , e 2j ) < 0 ∨ d(x i , e 2j , x) < 0 ∧ d(x i , e 1j , x) < 0 ∨ d(x i , e 2j , x) > 0 ∧ d(x i , e 1j , x) < 0, ⇔ d(x i , e 1j , e 2j ) < 0 ∨ d(x i , e 2j , x) < 0 ∧ d(x i , e 1j , x) < 0 ∨ d(x i , e 2j , x) > 0 ∧ d(x i , e 1j , x) < 0 ∧ d(x, e 1j , e 2j ) < 0 (Eq. C.4), ⇔ d(x i , e 1j , e 2j ) < 0 ∨ d(x i , e 2j , x) < 0 ∧ d(x i , e 1j , x) < 0 ∨ d(x i , e 1j , e 2j ) < 0 (Eq. B.4), d(x i , e 1j , e 2j ) < 0 ∨ d(x i , e 1j , x) < 0 ⇔ d(x i , e 1j , e 2j ) < 0 ∨ d(x i , e 2j , x) < 0 ∧ d(x i , e 1j , x) < 0. (C.6) d(x i , e 1j , e 2j ) < 0 ∨ d(x i , e 1j , x) < 0 ∨ d(x i , e 2j , x) > 0, ⇔ d(x i , e 1j , e 2j ) < 0 ∨ d(x i , e 1j , x) > 0 ∧ d(x i , e 2j , x) > 0 ∨ d(x i , e 1j , x) < 0 ∧ d(x i , e 2j ,
d(x i , e 1j , e 2j ) > 0 ∨ d(e 1j , x, x i ) • d(e 2j , x, x i ) > 0 ⇔ d(x i , e 1j , e 2j ) > 0 ∨ d(x i , e 1j , x) > 0 ∨ d(x i , e 2j , x) < 0 (Eq. C.3 and C.7) ⇔ d(x i , e 2j , e 1j ) < 0 ∨ d(x i , e 1j , x) > 0 ∨ d(x i , e 2j , x) < 0 (Eq. B.3). d(x i , e 2j , e 1j ) < 0 ∨ d(x i , e 2j , x) < 0 ⇔ d(x i , e 2j , e 1j ) < 0 ∨ d(x i , e 2j , x) < 0 ∧ d(x i , e 1j , x) < 0 ∨ d(x i , e 2j , x) > 0 ∧ d(x i , e 1j , x) > 0, ⇔ d(x i , e 2j , e 1j ) < 0 ∨ d(x i , e 2j , x) < 0 ∧ d(x i , e 1j , x) < 0 ∨ d(x i , e 2j , x) < 0 ∧ d(x i , e 1j , x) > 0 ∧ d(x, e 2j , e 1j ) < 0 (Eq. C.7), ⇔ d(x i , e 2j , e 1j ) < 0 ∨ d(x i , e 2j , x) < 0 ∧ d(x i , e 1j , x) < 0 ∨ d(x i , e 2j , e 1j ) < 0 (Eq. B.4), d(x i , e 2j , e 1j ) < 0 ∨ d(x i , e 2j , x) < 0 ⇔ d(x i , e 2j , e 1j ) < 0 ∨ d(x i , e 2j , x) < 0 ∧ d(x i , e 1j , x) < 0. (C.8) d(x i , e 2j , e 1j ) < 0 ∨ d(x i , e 2j , x) < 0 ⇔ d(x i , e 2j , e 1j ) < 0 ∨ d(x i , e 2j , x) > 0 ∧ d(x i , e 1j , x) > 0 ∨ d(x i , e 2j , x) < 0 ∧ d(x i , e 1j , x) > 0, ⇔ d(x i , e 2j , e 1j ) < 0 ∨ d(x i , e 2j , x) > 0 ∧ d(x i , e 1j , x) > 0 ∨ d(x i , e 2j , x) < 0 ∧ d(x i , e 1j , x) > 0 ∧ d(x, e 2j , e 1j ) < 0 (Eq. C.7), ⇔ d(x i , e 2j , e 1j ) < 0 ∨ d(x i , e 2j , x) > 0 ∧ d(x i , e 1j , x) > 0 ∨ d(x i , e 2j , e 1j ) < 0 (Eq. B.4), d(x i , e 2j , e 1j ) < 0 ∨ d(x i , e 1j , x) < 0 ⇔ d(x i , e 1j , e 2j ) < 0 ∨ d(x i , e 2j , x) > 0 ∧ d(x i , e 1j , x) > 0. (C.9) d(x i , e 2j , e 1j ) < 0 ∨ d(x i , e 1j , x) > 0 ∨ d(x i , e 2j , x) < 0, ⇔ d(x i , e 2j , e 1j ) < 0 ∨ d(x i , e 1j , x) > 0 ∧ d(x i , e 2j , x) > 0 ∨ d(x i , e 1j , x) < 0 ∧ d(x i ,
) = ∅. Then ∀x ∈ Seg(x 1 , x 2 ), ζ x det(x i -e 1j |e 2j -e 1j ) ≤ 0 ∧ ζ x det(x i -e 1j |x -e 1j ) ≤ 0 ∧ ζ x det(x i -e 2j |x -e 2j ) ≥ 0 ⇔ ζ x1 det(x i -e 1j |x 1 -e 1j ) ≤ 0 ∧ ζ x2 det(x i -e 1j |x 2 -e 1j ) ≤ 0 ∧ ζ x1 det(x i -e 2j |x 1 -e 1j ) ≥ 0 ∧ ζ x2 det(x i -e 2j |x 2 -e 1j ) ≥ 0 ∧ ζ x1 det(x i -e 1j |e 2j -e 1j ) ≤ 0 ∧ ζ x2 det(x i -e 1j |e 2j -e 1j ) ≤ 0.
Proof According to Proposition B.3.1

ζ x ∈ [ζ x1 , ζ x2 ], det(x i -e 1j |x -e 1j ) ∈ [det(x i -e 1j |x 1 -e 1j ), det(x i -e 1j |x 2 -e 1j )], det(x i -e 2j |x -e 2j ) ∈ [det(x i -e 2j |x 1 -e 2j ), det(x i -e 2j |x 2 -e 2j )].
Then, C.3 Proof of Proposition 2.2.2 x 1

∀x ∈ Seg(x 1 , x 2 ), ζ x det(x i -e 1j |e 2j -e 1j ) ≤ 0 ∧ ∀x ∈ Seg(x 1 , x 2 ), ζ x det(x i -e 1j |x -e 1j ) ≤ 0 ∧ ∀x ∈ Seg(x 1 , x 2 ), ζ x det(x i -e 2j |x -e 2j ) ≥ 0 ⇔[ζ x1 , ζ x2 ] det(x i -e 1j |e 2j -e 1j ) ≤ 0 ∧ [ζ x1 , ζ x2 ] • [det(x i -e
E ε s j (Seg(x 1 , x 2 )) = {x i ∈ R 2 | ∀x s ∈ Seg(x 1 , x 2 ), (x i Vx s ) ε s j } = {x i ∈ R 2 | ∀x s ∈ Seg(x 1 , x 2 ),
x 1

x 2 e 1j

x 2 e 2j (a) ζe 1 = ζe 2 = 1.

x 1

x 1

x 2 e 1j

x 2 x 1

x 1

x 2 e 1j

x 2 e 2j (a) ζe 1 = ζe 2 = 1.

x 1

x 1

x 2 e 1j

x 2

Figure 1 . 2 :

 12 Figure 1.2: Visibility and non-visibility spaces example.

Figures 1 .

 1 Figures 1.2a and 1.2b present examples of visible and non-visible spaces.

Figure 1 . 3 :

 13 Figure 1.3: Example of visible, non-visible and partially-visible spaces.

Figure 2

 2 Figure 2.1: Non-visible space of a closed set X regards to a convex polygon ε p j

Figure 2 . 2 :

 22 Figure 2.2: Visible and non-visible spaces characterization example.

Figure

  Figure 2.2 illustrates Propositions 2.1.1 and 2.1.2.

Figure 2 . 3 :

 23 Figure 2.3: Visible and non-visible spaces of a point regards to a convex polygon.

Figure 2 . 4 :

 24 Figure 2.4: Non-visible space of a segment regards to a segment.

Figure 2 . 5 :

 25 Figure 2.5: Visible space of a segment regards to a segment : case where ζ x1 = ζ x2 .

Figure 2 .

 2 Figure 2.7 illustrates Propositions 2.2.3 and 2.2.4.

Figure 2 . 6 :

 26 Figure 2.6: Visible space of a segment regards to a segment: case where ζ x1 = -ζ x2 .

Figure 2

 2 Figure 2.7: Visible et non-visible spaces of a segment regards to a polygon.

Figure 2 . 8 :

 28 Figure 2.8: Visible and non-visible spaces of a box regards to a segment.

Figure 2 . 9 :

 29 Figure 2.9: Visible and non-visible spaces of a box regards to a convex polygon.

j,

  the objective is to contract (reduce) [x1] and [x2] by removing the values that are not compatible with the visibility constraint: the hatched area belongs to the nonvisible space of [x1] regards to ε p j , this area is then not feasible with the visibility constraint and can be removed from the domain [x2].

Figure 3 . 1 :

 31 Figure 3.1: Contraction example according to the constraint (x 1 Vx 2 ) ε p j .

Figure 3 . 3 :

 33 Figure 3.3: Presentation of the contractor C V ([x], a, ε s j ).

Figure 3 . 4 :

 34 Figure 3.4: Presentation of the contractor C V ([x], a, b, ε s j ).

Figure 3 . 6 :

 36 Figure 3.6: Presentation of the contractor C V ([x], [x s ], ε s j ).

  Figure 3.6 illustrates its principle. This contractor is presented Algorithm 5. It is based on the complement of Equation 2.16.

  xs ∈ [xs] and x ∈ [x].

Figure 3 . 8 :

 38 Figure 3.8: Presentation of the contractor C V ([x], [x s ], ε p j ).

  (xVxs) ε p j , with xs ∈ [xs] and x ∈ [x]. Contraction of [x].

Figure 3 . 9 :

 39 Figure 3.9: Presentation of the contractor C V ([x], [x s ], ε p j ).

  Figure A.2: Case study.

  Figure A.3: Particular case for the intersection: the two segments are on the same line. In this case det(a -c|d -c) • det(b -c|d -c) = 0 and det(c -a|b -a) • det(d -a|b -a) = 0 but the two segments do not intersect each other.

  Figure A.4: Polygon P composed by n P = 5 edges.

  Figure A.4 presents a convex polygon example.

  Figure A.6 illustrates this remark.

Figure B. 1 :

 1 Figure B.1: Illustration of Proposition B.2.1.

  Figure B.2: Illustration of Proposition B.3.1: a ≥ b ⇒ a ≥ s ≥ b

  1j |x 1 -e 1j ), det(x i -e 1j |x 2 -e 1j )] ≤ 0 ∧ [ζ x1 , ζ x2 ] • [det(x i -e 2j |x 1 -e 2j ), det(x i -e 2j |x 2 -e 2j )] ≥ 0 ⇔ζ x1 det(x i -e 1j |e 2j -e 1j ) ≤ 0 ∧ ζ x2 det(x i -e 1j |e 2j -e 1j ) ≤ 0 ∧ ζ x1 det(x i -e 1j |x 1 -e 1j ) ≤ 0 ∧ ζ x1 det(x i -e 1j |x 2 -e 1j ) ≤ 0 ∧ ζ x2 det(x i -e 1j |x 1 -e 1j ) ≤ 0 ∧ ζ x2 det(x i -e 1j |x 2 -e 1j ) ≤ 0 ∧ ζ x1 det(x i -e 2j |x 1 -e 2j ) ≥ 0 ∧ ζ x1 det(x i -e 2j |x 2 -e 2j ) ≥ 0 ∧ ζ x2 det(x i -e 2j |x 1 -e 2j ) ≥ 0 ∧ ζ x2 det(x i -e 2j |x 2 -e 2j ) ≥ 0. (C.10)It can be noticed thatζ x1 det(x i -e 1j |e 2j -e 1j ) ≤ 0 ∧ ζ x2 det(x i -e 1j |e 2j -e 1j ) ≤ 0 ⇔ ζ x1 = ζ x2 .Then it can be deducedζ x1 det(x i -e 1j |e 2j -e 1j ) ≤ 0 ∧ ζ x2 det(x i -e 1j |e 2j -e 1j ) ≤ 0 ∧ ζ x1 det(x i -e 1j |x 1 -e 1j ) ≤ 0 ∧ ζ x1 det(x i -e 1j |x 2 -e 1j ) ≤ 0 ∧ ζ x2 det(x i -e 1j |x 1 -e 1j ) ≤ 0 ∧ ζ x2 det(x i -e 1j |x 2 -e 1j ) ≤ 0 ∧ ζ x1 det(x i -e 2j |x 1 -e 2j ) ≥ 0 ∧ ζ x1 det(x i -e 2j |x 2 -e 2j ) ≥ 0 ∧ ζ x2 det(x i -e 2j |x 1 -e 2j ) ≥ 0 ∧ ζ x2 det(x i -e 2j |x 2 -e 2j ) ≥ 0 ⇔ζ x1 det(x i -e 1j |e 2j -e 1j ) ≤ 0 ∧ ζ x2 det(x i -e 1j |e 2j -e 1j ) ≤ 0 ∧ ζ x1 det(x i -e 1j |x 1 -e 1j ) ≤ 0 ∧ ζ x2 det(x i -e 1j |x 2 -e 1j ) ≤ 0 ∧ ζ x1 det(x i -e 2j |x 1 -e 2j ) ≥ 0 ∧ ζ x2 det(x i -e 2j |x 2 -e 2j ) ≥ 0 ⇔∀x ∈ Seg(x 1 , x 2 ),ζ x det(x i -e 1j |e 2j -e 1j ) ≤ 0 ∧ ζ x det(x i -e 1j |x -e 1j ) ≤ 0 ∧ ζ x det(x i -e 2j |x -e 2j ) ≥ 0 (Eq. C.10).

  ζ s det(x i -e 1j |e 2j -e 1j ) > 0 ∨ ζ s det(x i -e 1j |x s -e 1j ) > 0 ∨ ζ s det(x i -e 2j |x s -e 2j ) < 0 ∨ [x i ∪ x s ] ∩ [e 1j ∪ e 2j ] = ∅} (x s -e 1j |e 2j -e 1j ) > 0, -1 otherwise.(C.12)It can be noticed that∀x s ∈ Seg(x 1 , x 2 ), [x i ∪ x s ] ∩ [e 1j ∪ e 2j ] = ∅ ⇔ [x i ∪ x 1 ∪ x 2 ] ∩ [e 1j ∪ e 2j ] = ∅ (C.13)Then there are two ways of writing Equation C.11E ε s j (Seg(x 1 , x 2 )) = {x i ∈ R 2 | ∀x s ∈ Seg(x 1 , x 2 ), (x i Vx s ) ε s j } = {x i ∈ R 2 | ∀x s ∈ Seg(x 1 , x 2 ), ζ s det(x i -e 1j |e 2j -e 1j ) > 0 ∨ ζ s det(x i -e 1j |x s -e 1j ) > 0 ∨ ζ s det(x i -e 2j |x s -e 2j ) < 0}∪ {x i ∈ R 2 | | [x i ∪ x s ] ∩ [e 1j ∪ e 2j ] = ∅}. (C.14)There are two cases:ζ x1 = ζ x2 and ζ x1 = -ζ x2 . C.3.1 First case: ζ x 1 = ζ x 2In this caseζ x1 = ζ x2 ⇔ ζ s = ζ x1 = ζ x2 ⇒ ζ s det(x i -e 1j |e 2j -e 1j ) =ζ x1 det(x i -e 1j |e 2j -e 1j ) = ζ x2 det(x i -e 1j |e 2j -e 1j ), (C.15) and det(x i -e 1j |x s -e 1j ) ∈ [det(x i -e 1j |x 1 -e 1j ) ∪ det(x i -e 1j |x 2 -e 1j )], (C.16) det(x i -e 2j |x s -e 2j ) ∈ [det(x i -e 2j |x 1 -e 2j ) ∪ det(x i -e 2j |x 2 -e 2j )]. (C.17)Then∀x s ∈ Seg(x 1 , x 2 ), ζ s det(x i -e 1j |x 1 -e 1j ) > 0 ⇔ ζ x1 det(x i -e 1j |x 1 -e 1j ) > 0 ∧ ζ x2 det(x i -e 1j |x 2 -e 1j ) > 0, (C.18) ∀x s ∈ Seg(x 1 , x 2 ), ζ s det(x i -e 2j |x 1 -e 2j ) > 0 ⇔ ζ x1 det(x i -e 2j |x 1 -e 2j ) > 0 ∧ ζ x2 det(x i -e 2j |x 2 -e 2j ) > 0. (C.19) According to Equations C.18, C.19 et C.14, E ε s j (Seg(x 1 , x 2 )) = {x i ∈ R 2 | ζ x1 det(x i -e 1j |e 2j -e 1j ) > 0 ∨ ζ x1 det(x i -e 1j |x 1 -e 1j ) > 0 ∧ ζ x2 det(x i -e 1j |x 2 -e 1j ) > 0 ∨ ζ x1 det(x i -e 2j |x 1 -e 2j ) > 0 ∧ ζ x2 det(x i -e 2j |x 2 -e 2j ) > 0 ∨ [x i ∪ x s ] ∩ [e 1j ∪ e 2j ] = ∅}. (C.20) C.3.2 Second Case: ζ x 1 = -ζ x 2It has to be reminded that Seg(x 1 , x 2 ) ∩ Seg(e 1j , e 2j ) = ∅. Then it can be deduced thatζ x1 = -ζ x2 ⇒ ζ e1 = ζ e2 . (C.21)

  ζe 1 = ζe 2 = -1.

Figure C. 1 :

 1 Figure C.1: The two possible configurations.

  ζe 1 = ζe 2 = -1.

Figure C. 2 :

 2 Figure C.2: Visible spaces in both configurations.

  x) < 0 (Eq. C.5 and C.6),⇔ d(x i , e 1j , e 2j ) < 0 ∨ d(x i , e 1j , x) • d(x i , e 2j , x) > 0.

	The Proposition C.1.1 is then verified when ζ x = -1.
	Second case:
	ζ

x = 1 ⇔ d(x, e 1j , e 2j ) > 0 ⇔ d(x, e 2j , e 1j ) < 0 (Eq: C.2 and B.3). (C.7)

  Proposition C.2.1 Let Seg(x 1 , x 2 ) be a segment with x 1 ∈ R 2 and x 2 ∈ R 2 , and Seg(e 1j , e 2j ) be a segment with Seg(x 1 , x 2 ) ∩ Seg(e 1j , e 2j

	Proposition C.1.1 is then verified when ζ x = 1.
	C.2 Proof of Proposition 2.1.2

e 2j , x) < 0 (Eq. C.8 and C.9),

⇔ d(x i , e 2j , e 1j ) < 0 ∨ d(x i , e 1j , x) • d(x i , e 2j , x) > 0.

[i 1 ] = C det ([x], e 1j , e 2j , -ζ a );

[i 2 ] = C det ([x], e 1j , a, -ζ a );

[i 3 ] = C det ([x], e 2j , a, ζ a );

[i 4 ] = C ∩ =∅ ([x], a, e 1j , e 2 ); Output: [x] * = [i 1 ] ∩ [i 2 ] ∩ [i 3 ] ∩ [i 4 ]Once those two contractors defined, it is possible de get interested into the contractors associated to a segment visibility information.

Appendix A

Segment Tools

A.1 Parametric Equation of a Segment

Let Seg(a, b) be a segment with a = (a 1 , a 2 ) ∈ R 2 and b = (b 1 , b 2 ) ∈ R 2 . Every point s = (s 1 , s 2 ) ∈ Seg(a, b) can be written as

This notation corresponds to the parametric equation of the segment Seg(a, b).

A.2 Segment Intersection

A.2.1 Point Position Regards to a Segment

The sign of det(a -b|c -b) characterizes the position of the point a regards to the line associated to the vector This new contractor is presented Algorithm 12.

Considering Algorithm 12 and Equation A.8, it is possible to develop the contractor (Algorithme 13) associated to the constraint

We now want to develop the contractor associated to the constraint

Which leads to the contractor (Algorithm 14) associated to the constraint

and the contractor (Algorithm 15) associated to the constraint

Appendix C

Some Proofs

In order to make the reading of this report easier, some proofs are written here. Then we want to prove: (C.5)