Critère de Delaunay (in-circle)
Test géométrique pour triangulation
Enonce
Implémenter in_circle(a, b, c, d) qui retourne True ssi le point $d$ est strictement à l'intérieur du cercle circonscrit au triangle $(a,b,c)$ supposé orienté trigonométriquement.
⚠ Bonus : Écrire orientation(a, b, c) qui retourne +1 (CCW), -1 (CW) ou 0 (alignés) via le signe du produit vectoriel 2D.
Signature attendue
def in_circle(a: tuple, b: tuple, c: tuple, d: tuple) -> bool:Exemples
in_circle((1, 0), (0, 1), (-1, 0), (0, 0))→Truein_circle((1, 0), (0, 1), (-1, 0), (2, 2))→False
📖 Rappel de cours
La triangulation de Delaunay d'un nuage de points est celle qui maximise le plus petit angle des triangles. Caractérisation : pour tout triangle $(a,b,c)$ de la triangulation, aucun autre point n'est à l'intérieur du cercle circonscrit à $(a,b,c)$.
Test in-circle (déterminant) :
Si $(a,b,c)$ est orienté dans le sens trigonométrique, alors $d$ est strictement à l'intérieur du cercle circonscrit ssi :
$\det\begin{pmatrix}a_x-d_x & a_y-d_y & (a_x-d_x)^2+(a_y-d_y)^2\\ b_x-d_x & b_y-d_y & (b_x-d_x)^2+(b_y-d_y)^2\\ c_x-d_x & c_y-d_y & (c_x-d_x)^2+(c_y-d_y)^2\end{pmatrix} > 0$
C'est la brique de base de tous les algos de Delaunay : on retourne une arête tant qu'elle viole ce critère (flip-edge).
← Exercices sur les graphes en Python — BFS, DFS, Dijkstra
Exercices du meme theme
La correction commentee, les indices progressifs, l'execution du code dans le navigateur et la verification par l'IA sont reserves aux abonnes.