Un de mes sujets favoris: le tirage de points uniformément dans une région!
Je confirme ce qui a été dit, pour tirer un point uniforme dans une région un tout petit peu compliquée le rejet est très souvent la bonne méthode. Avec un peu de changement de repère, souvent - les transformations affines ne changent pas l'uniformité du tirage (aucun besoin de se forcer à utiliser un repère orthnormé, bien que là pour les disques c'est sans doute préférable). Attention, de manière plus générale les transformations non affines ne préservent souvent pas l'uniformité (cf le passage depuis des coordonnées polaires ci-dessous).
* tirer un point dans un disque: la méthode revient à tirer un point dans un carré qui contient le disque, et à rejeter s'il est trop loin du centre. Sur ce coup je valide l'estimation de Souly, la proba de rejet est de 1-pi/4, moins de 25%. Cool.
* tirer un point dans l'intersection de deux disques: une méthode bourrine consisterait à tirer un point dans le plus petit des deux, et à rejeter s'il n'est pas dans le plus grand. Mais l'intersection peut être arbitrairement petite par rapport au petit disque, donc inefficace.
* tirer un point dans l'intersection de deux disques, comme ici: effectivement je chercherais un rectangle englobant aligné sur l'axe des deux centres. Attention, il est possible que la distance entre les deux points d'intersection ne soit pas suffisante comme dimension! Mais dans les cas où les deux disques sont un peu gros par rapport à leur intersection (qui aura un peu la forme d'une lentille concave des deux côtés), ce sera assez simple, la hauteur sera donnée par les deux points d'intersection et la largeur par les points d'intersection avec l'axe des centres; et la proba de rejet sera de l'ordre de 1/3 si mes souvenirs sont bons (cas limite avec des bouts de paraboles).
Au passage, pour tirer un point uniforme dans un disque il y a une méthode sans rejet: tirer deux uniformes entre 0 et le rayon, et une uniforme entre 0 et 2 pi; et utiliser la plus grande des deux premières comme rayon, et la troisième comme angle, en polaires (si on tire le rayon et l'angle uniformément le résultat n'est pas uniforme, les points sont trop concentrés près du centre; explication à peu près compréhensible par mes étudiants qui ne savent pas calculer d'intégrales: la moitié des points vont tomber dans le disque de rayon moitié moins, qui ne représente que le quart de l'aire). Ceci dit, pour le coup il faut utiliser des fonctions trigo (sinus et cosinus pour le passage en polaires), et la valeur numérique de pi, c'est moins propre que le rejet qui ne fait que des opérations arithmétiques et, en moyenne, moins de 3 tirages (8/pi, environ 2.54)
Sur ce sujet, un truc rigolo: le tirage d'un point uniformément à l'intérieur d'une ligne polygonale donnée. Le rejet peut être arbitrairement inefficace (l'aire de la région peut être arbitrairement petite par rapport à celle du rectangle englobant); la meilleure méthode que je connaisse passe par un précalcul pas évident: découpage en régions triangulaires, puis choix d'un triangle avec proba proportionnelle à son aire, et enfin tirage d'un point uniforme dans un triangle.