Distance minimale entre deux polygones convexes

3.a. Algorithme

L'algorithme de Lin-Canny ([1]) permet de calculer la distance entre deux polyèdres dans un espace à trois dimensions. Lorsque les polyèdres se déplacent, l'algorithme permet de suivre les deux points les plus proches avec un temps de calcul constant pour chaque pas de temps (c'est-à-dire indépendant de la taille des polyèdres).

On considère ici une version simplifiée pour le problème à deux dimensions.

Cet algorithme consiste à rechercher les deux éléments E_A et E_B des polygones A et B vérifiant la condition suivante : les points P(A) et P(B) les plus proches de ces deux éléments vérifient $P\left(A\right)\in V\left(E_B\right)$ et $P\left(B\right)\in V\left(E_A\right)$

Pour cela, l'algorithme démarre par une paire d'éléments (E_A,E_B) choisie arbitrairement. Dans le cas d'une simulation de mouvement de solides, cette paire est celle ayant été obtenue au pas de temps précédent, dans laquelle les points les plus proches étaient situés.

Pour une paire (E_A,E_B), on recherche tout d'abord les points $P\left(E_A\right)\in E_A$ et $P\left(E_B\right)\in E_B$ les plus proches de ces deux éléments (voir paragraphe suivant). On exclue pour l'instant le cas de deux côtés parallèles (cas dégénéré). On teste l'appartenance de chacun de ces points à la région de Voronoi de l'élément auquel appartient l'autre point, c'est-à-dire les deux conditions suivantes :

$$\begin{array}{ccc}\hfill & \left(a\right)P\left(E_B\right)\in V\left(E_A\right)\hfill & \hfill \text{(6)}\\ \hfill & \left(b\right)P\left(E_A\right)\in V\left(E_B\right)\hfill & \hfill \text{(7)}\end{array}$$

Si les deux conditions (a) et (b) sont remplies alors les points P(E_A) et P(E_B) sont les deux points les plus proches des deux polygones et la recherche est terminée.

Si l'une au moins des deux conditions (a) et (b) n'est pas vérifiée, il faut poursuivre la recherche en choisissant une nouvelle paire. Supposons que la condition (a) ne soit pas vérifiée (soit (b) est vérifiée, soit (b) ne l'est pas mais (a) est la première testée). Il faut alors remplacer E_A par un de ses deux éléments voisins (un sommet a deux côtés voisins et un côté a deux sommets voisins). Ce remplacement soit se faire pour que la distance entre les deux éléments diminue ou reste constante.

Considérons les deux différents cas possibles.

Premier cas : E_A est un sommet, noté A₂ sur la figure ci-dessous :

Figure pleine page

Le point P=P(E_B) n'est pas dans la région de Volonoi du point A₂ car :

$$\overrightarrow{A_{2}P}\cdot \overrightarrow{A_2{A}_3}>0\text{(8)}$$

Le point P n'est pas dans le demi-plan défini par D(A₂A₃). Il faut alors remplacer A₂ par A₂A₃, pour que le nouvel élément de A se rapproche de P.

La première condition non vérifiée rencontrée impose la direction du déplacement, même si la seconde n'est pas non plus vérifiée.

Si le point appartient P appartient à la région de Voronoi de A₂ (les deux conditions sont satisfaites), alors on doit tester l'appartenance du point A₂ à la région de Voronoi de l'élément E_B contenant le point P(E_B).

Second cas : E_A est un côté, le côté A₂A₃ sur la figure ci-dessous :

Figure pleine page

Le point P=P(E_B) n'est pas dans la région de Volonoi du côté A₂A₃ car un des trois conditions n'est pas vérifiée :

$$\overrightarrow{A_{3}P}\cdot \overrightarrow{A_3{A}_2}\le 0\text{(9)}$$

On doit alors remplacer le côté par le sommet A₂.

Que doit-on faire si le point P n'appartient pas au demi-plan défini par le côté A₂A₃ (demi-plan extérieur au polygone) ? Voici un exemple de ce cas :

Figure pleine page

3.b. Détermination des points les plus proches de deux éléments

Voyons à présent comment se fait la recherche des points les plus proches de deux éléments.

Si les deux éléments sont des sommets, le résultat est trivial : les points les plus proches sont les sommets eux-mêmes.

Si l'un des éléments B₁ est un sommet et l'autre un côté A₁A₂ , le point le plus proche appartenant au côté est déterminé en considérant la projection orthogonale I du sommet sur la droite contenant le côté.

Figure pleine page

Pour déterminer le point I, considérons la forme paramétrée suivante vérifiée par tout point de la droite A₁A₂ :

$$\overrightarrow{OI}=(1-\lambda )\overrightarrow{O{A}_1}+\lambda \overrightarrow{O{A}_2}\text{(10)}$$

Comme de plus la droite IB₁ doit être perpendiculaire à A₁A₂ on a :

$$\overrightarrow{B_{1}I}\cdot \overrightarrow{A_1{A}_2}=0\text{(11)}$$

Ces deux équations conduisent à une équation du premier degré pour λ. Si $0<\lambda <1$ alors le point le plus proche est le point I. Si $\lambda \le 0$ alors le point le plus proche est A₁. Si $\lambda \ge 1$ alors le point le plus proche est A₂.

Le dernier cas à considérer est celui où les deux éléments sont des côtés. Les deux côtés sont supposés non parallèles et ne se coupent pas. La figure suivante montre un exemple :

Figure pleine page

Sur cet exemple, les points les plus proches sont B₁ et P(E_A), son projeté orthogonal sur le segment A₁A₂.

Voici un autre exemple, où les deux points les plus proches sont des sommets :

Figure pleine page

Supposons que le point P(E_A) ne soit pas sur une extrémité du segment, c'est-à-dire confondu ni avec A₁, ni avec A₂. La droite P(E_A)P(E_B) est alors nécessairement perpendiculaire au segment A₁A₂, car sinon il y aurait un point du segment plus proche de P(E_B) que P(E_A). Il s'en suit que si les deux segments ne sont pas parallèles, il est impossible que les deux points les plus proches soient tous les deux sur le segment (à l'exclusion des sommets). On en déduit qu'au moins l'un des points P(E_A) et P(E_B) est un sommet. Il faut tout d'abord rechercher les projections orthogonales des 4 sommets qui sont sur le segment de l'autre élément (méthode vue ci-dessus). Pour ces projections, on calcule aussi la distance et on garde la paire qui a la plus petite distance. On doit aussi prévoir le cas où les deux points sont des sommets. Il faut donc aussi comparer les distances pour les 4 paires de sommets. On garde finalement la paire de points qui a la plus petite distance.

3.c. Exemple

Voici un exemple de déroulement de l'algorithme. Pour chaque phase, les deux éléments testés sont marqués en couleur avec leur région de Voronoi.

Figure pleine page

On commence par la paire (A₁,B₁). Par convention, on commence par faire le test sur le point A₁. On constate qu'il ne vérifie par la condition d'appartenance à V(B₁) pour la droite D(B₁B₂). On remplace donc B₁ par le côté B₁B₂.

Les points les plus proches des éléments A₁ et B₁B₂ sont A₁ et B₂. Le point A₁ ne vérifie par la condition d'appartenance à la région de Voronoi de B₁B₂ pour la droite D(B₂B₁). On doit donc remplacer l'élément B₁B₂ par le sommet B₂.

Le point A₁ appartient à la région de Voronoi de B₂. Le point B₂ ne vérifie par la condition d'appartenance à la région de Voronoi de A₁ pour la droite D(A₁A₄). On doit donc remplacer l'élément A₁ par le côté (A₁A₄).

Pour cette nouvelle paire d'éléments, les points les plus proches sont A₄ et B₂. A₄ appartient à la région de Voronoi de B₂. B₂ ne vérifie par la condition d'appartenance à la région de Voronoi de A₁A₄ pour la droite D(A₄A₁). On doit donc remplacer A₁A₄ par A₄.

Pour cette nouvelle paire, A₄ est dans la région de Voronoi de B₂ et B₂ est dans la région de Voronoi de A₄. Les deux points les plus proches des polygones sont donc A₄ et B₂.

Si les deux polygones se déplacent légèrement (translation et/ou rotation) à partir de cette position, on reprend la recherche à partir de la paire (A₄,B₂). Pour un déplacement assez faible, cette paire vérifie toujours la condition, puis un des points sort de la région de Voronoi de l'autre. Le nouvel élément de remplacement contient probablement le nouveau point le plus proche de l'autre. Si les déplacements sont assez petits, la recherche se fait donc à temps constant.