Représentation d’intervalles modulo 2pi

Bonsoir,

Je programme en OCaml et je cherche à créer un type qui me permet de représenter facilement des intervalles modulo 2pi et de les manipuler (union).

Quand je dis modulo 2pi c’est dans le sens où par exemple : $[0, 4 \pi ] = [0,2 \pi]$, $[3 \pi, 3 \pi +1] = [ \pi, \pi +1]$.

Ma première idée c’est d’utiliser le type : float * float en utilisant la convention suivante les intervalles sont pris dans le sens direct. C’est à dire que par exemple : $[3\pi /2, 2\pi[ \cup [0, \pi] = (3\pi / 2, \pi)$.

Le problème c’est qu’avec cette représentation il m’est difficile de coder une fonction donnant l’union de deux intervalles, il y’a beaucoup beaucoup de cas à traiter…

Avez-vous des idées ?

Je vous remercie d’avance ! Bonne soirée !

Salut,

Ta représentation n’a pas l’air mauvaise. Quels problèmes rencontres-tu pour l’union ? As-tu une fonction de normalisation qui te donne le couple correspondant à l’intervalle entre 0 et 2 pi (le but serait alors de ne travailler qu’avec ces représentants) ?

Si on applique cette normalisation, l’intervalle [-pi/4; pi/4] n’est plus un intervalle, mais une réunion de 2 intervalles.

Mais en fait tu supposes que tes intervalles se touchent ou s’intersectent ? Comment tu gères $[0,\pi/4]\cup [\pi/2,\pi]$ par exemple ? Si tu n’acceptes que les entrées dont le résultat est un intervalle, alors il y a plein de manières de faire (exemple avec 2 cas : tu déplies temporairement tes intervalles dans $[0,4\pi]$, si ils s’intersectent tu sais faire, sinon y a qu’un cas possible direct à traiter).

Merci pour vos réponses. Je m’excuse je n’ai pas été très clair.

Je n’accepte effectivement que les intervalles (donc en gros une portion continue du cercle unité), et je veux donc faire une fonction qui donne l’union de deux intervalles d’intersection non-vide. fun : (a,b) (c,d) -> (e,f). Le problème c’est qu’il y a beaucoup de cas à traiter. Par exemple si je fais le simple : let union (a,b) (c,d) = (min a c, max d b), alors cette fonction ne marche pas sur l’entrée : $(3\pi /2, \pi), (\pi / 2, \pi +1)$. Donc en fait le truc chiant c’est les intervalles $(a,b)$ avec $\mid a -b \mid > \pi$…

@Lucas-84, j’avais pensé à l’idée de déployer les intervalles dans $[0, 4 \pi]$ mais j’ai eu l’impression d’avoir toujours autant de cas à traiter, puisqu’il faut déjà séléctionner pour quelle type d’intervalles on rajoute $2 \pi$. Les intervalles $(a,b)$ ou $a,b \leq \pi$, … ?

Ça concerne que les intervalles qui passent au dessus de 0. Autrement dit, si une de tes entrées est de la forme $b<a$, tu la remplaces par $[a,b+2\pi]$, et tu touches rien au reste. Maintenant tu travailles dans $[0,4\pi[$ :

• Si les deux entrées s’intersectent dans ce nouvel espace ($a\le d$ et $c\le b$), alors ta formule $[\min(a,c),\max(b,d)]$ donne bien l’union dans $[0,4\pi[$, et on peut repasser dans $[0,2\pi[$ en réduisant les bornes, à part quand tu remplis tout $[0,2\pi[$ (mais ça c’est facile à tester à partir de la longueur de l’intervalle que tu obtiens).
• Sinon, il n’y a qu’un cas possible : t’as un intervalle qui passe au-dessus de 0, et un autre qui commence « proche de 0 ». Tu peux le traiter à la main (c’est vraiment pas difficile), ou sinon te ramener au premier cas en shiftant de $2\pi$ les deux bornes de l’intervalle proche de 0.

On peut sûrement faire un peu plus simple, mais je serais pas étonné qu’il n’y ait pas de solution vraiment simple et élégante à ce problème, essentiellement parce que l’union d’intervalles n’est pas une opération vraiment naturelle, et donc on doit se restreindre aux seuls cas où le résultat est lui-même un intervalle — quand l’une des adhérences des intervalles de départ s’intersectent. La conséquence, c’est que pour utiliser cette information, on doit d’une certaine manière essayer de localiser l’intersection.

Et au passage, c’est pas des techniques complètement ad hoc : un autre domaine naturel où ce genre de choses apparaissent, c’est quand tu regardes des problèmes de balayage, par exemple en géométrie algorithmique (t’as des objets comme des points, des intervalles, des rectangles, etc.), et la question est « est-ce qu’on peut adapter nos algos dans le cas où on remplace $\mathbf{R}$ par le cercle unité, $\mathbf{R}^2$ par un tore, etc ». Et souvent la solution c’est de remplacer ton objet par plusieurs morceaux dans le cas où ils débordent, ou alors de rajouter une copie de l’espace global, faire comme si de rien n’était et ne gérer qu’a posteriori le fait que certains points du nouvel espace correspondent au même point dans l’espace de départ (ça serait l’analogue de ce que je propose ici, en concaténant deux copies de $[0,2\pi[$). Ça apparaît aussi dans des histoires de programmation dynamique avec des cycles.

J’ai l’impression qu’il manque des cas non ? J’ai peut-être mal compris. D’abord je pense que tu voulais parler de la formule : $[ \min (a,c), \max (d,b)]$. En prenant les intervalles : $(a,b) = (\pi +1, \pi -1)$ et $(c,d) = (\pi -2, \pi)$, il me semble que ce que tu dis oublie ce cas. Ou bien tu considère dans ce cas que $c$ est proche de $0$ ? Aussi la formule pour l’intersection : $a \leq d, c\leq b$ ne marche pas ici; il faut inverser les couples, ce qui rajoute un cas supplémentaire pour savoir quel intervalle "se trouve avant l’autre" et ainsi localiser l’intersection mais j’ai peut-être mal compris ce que tu proposais du coup.

Je pense qu’on peut faire sans regarder dans $[0, 4 \pi [$, mais uniquement en regardant lequel entre $(a,b)$ et $(c,d)$ passe par $0$ on a donc $4$ cas à tester mais cela revient à en traiter deux car un cas est symétrique et les deux autres renvoient le même résultat.

• si $(a, b)$ et $(c,d)$ passent par $0$ ou si $(a,b)$ et $(c,d)$ ne passent pas par $0$ alors on renvoie : $(\min (a$, $c$), $\max (b$, $d))$

• si $(a,b)$ passe par $0$ et pas $(c,d)$ alors soit $c \in (a,b)$ soit $d \in (a,b)$. Si $c, d \in (a,b)$ on renvoie $(0, 2\pi)$, si seulement $c \in (a,b)$ on renvoie $(a,d)$, si seulement $d \in (a,b)$ alors on renvoie $(c,d)$.

Effectivement pour les variables dans le $\min$ et le $\max$ mais par contre je suis pas sûr de comprendre ton contre-exemple (quand je dis "proche de 0" c’est par rapport à la borne de fin de l’autre intervalle, du coup on est bien dans le deuxième cas et quand on shifte de $2\pi$ on a bien une intersection non vide dans $[0,4\pi[$). J’ai pas non plus compris ta remarque sur l’intersection non vide, la formule marche tout le temps, non ? Pour limiter l’ambiguïté je propose un pseudo-code :

// entrée : [a, b], [c, d]
if (b < a) b += 2 * pi
if (d < c) d += 2 * pi
if (a > d) c += 2 * pi, d += 2 * pi
if (c > b) a += 2 * pi, b += 2 * pi
l = min(a, c), r = max(b, d)
// ici, si r - l >= 2 * pi, il faut gérer comment représenter [0, 2pi] en entier
l %= 2 * pi, r %= 2 * pi
// retourner [l, r]

J’arnaque ? Au fond, j’ai l’impression que c’est pareil que ta solution, mais en un peu plus factorisé et que finalement c’est toi qui a oublié des cas. (il manque le $[0,2\pi[$ dans ta première puce et le cas où $(c,d)\subseteq (a,b)$ dans ta deuxième — et je pense que tu voulais dire $(c,b)$ à la fin)

PS : L’IRL est en bonne voie

Effectivement pour les variables dans le $\min$ et le $\max$ mais par contre je suis pas sûr de comprendre ton contre-exemple (quand je dis "proche de 0" c’est par rapport à la borne de fin de l’autre intervalle, du coup on est bien dans le deuxième cas et quand on shifte de $2\pi$ on a bien une intersection non vide dans $[0,4\pi[$). J’ai pas non plus compris ta remarque sur l’intersection non vide, la formule marche tout le temps, non ?

Okay j’avais mal compris pour le proche de $0$ Sinon pour l’intersection non la formule ne marche pas tout le temps, on peut trouver une intersection non vide avec $a > d$, par exemple : $(a,b) = (2\pi-1, \pi/2)$ et $(c,d) = (\pi/2, \pi)$. C’est pour ça que je disais qu’il faut tester l’intersection dans les deux sens pour que ça marche (bon cette fonction ne termine pas dans le cas d’une non intersection mais c’est pour montrer l’idée )

let rec intersection (a,b) (c,d) = (a <= d && c<= b) || (intersection (c,d) (a,b) )

J’arnaque ? Au fond, j’ai l’impression que c’est pareil que ta solution, mais en un peu plus factorisé et que finalement c’est toi qui a oublié des cas. (il manque le $[0,2\pi[$ dans ta première puce et le cas où $(c,d)\subseteq (a,b)$ dans ta deuxième — et je pense que tu voulais dire $(c,b)$ à la fin)

Oups oui effectivement !

PS : L’IRL est en bonne voie

Haha, I am waiting for your call !

Okay j’avais mal compris pour le proche de $0$ Sinon pour l’intersection non la formule ne marche pas tout le temps, on peut trouver une intersection non vide avec $a > d$, par exemple : $(a,b) = (2\pi-1, \pi/2)$ et $(c,d) = (\pi/2, \pi)$

Ah mais le malentendu du coup, c’est que moi j’ai jamais voulu parler d’intersections d’intervalles cycliques : tous mes objets sont dans $[0,4\pi[$, c’est des intersections d’intervalles « classiques ». En tout cas l’exemple que tu donnes fonctionne bien sur le pseudo-code de mon dernier message.

C’est pour ça que je disais qu’il faut tester l’intersection dans les deux sens pour que ça marche (bon cette fonction ne termine pas dans le cas d’une non intersection mais c’est pour montrer l’idée )

let rec intersection (a,b) (c,d) = (a <= d && c<= b) || (intersection (c,d) (a,b) )

T’es conscient que si tu échanges les rôles de $(a,b)$ et $(c,d)$, la condition que tu obtiens c’est c <= b && a <= d, c’est-à-dire la même chose ? Je sais pas comment on pourrait tester l’intersection d’intervalles cycliques de manière compressée, mais si on veut être sûr de pas se tromper, on peut juste tester si l’une des extrémités est dans l’autre intervalle (honnêtement, ça se factorise bien).

Oups je suis désolé j’ai dis n’importe quoi (j’accuse les fêtes ). Du coup pour on a plutôt ça :

let in_angle ang (a,b) = if a <= b then ang >= a && ang <= b else ang >= a || ang <= b

let intersection (a,b) (c,d) = in_angle c (a,b) || in_angle d (a,b) || in_angle a (c,d) || in_angle b (c,d)