Choisir un point dans une surface bircornue.

Bonjour,

J'ai une surface décrite par une réunion d'ensemble, et je voudrais choisir un point de facon aléatoire dessus.

La surface $S$ est decrite par

Soit $p \in \mathbb{R}^2$, $N$ un ensemble fini de points de $\mathbb{R}^2$, $S = D(p, r) \backslash \bigcap_{u \in N} D(u, r)$. Avec $D(p, r) = \{u \in \mathbb{R}^2, |u-p| < r\}$ et $r \in \mathbb{R}^2$.

En gros, choisir un point dans le voisinage d'un point donné mais pas dans le voisinage de tous les autres point.

Determiner si un point est dans $S$ est simple, par contre c'est en choisir un que je n'arrive pas.

Le but final est de réaliser un petit jeu 2d, donc j'avais pensé discrétiser le plan directement, mais avec un pas assez fin (1 px), le nombre de points augmente tres vite ($\# D(p, 60) \sim 11.400$). Une autre approche était de choisir aléatoirement un point dans $D(p, 60)$ tant qu'il est dans un des autres voisinages, mais encore une fois, c'est pas une méthode tres efficace.

Est ce qu'il existe une méthode moins systématique ?

Edit : Comment on édite un titre ?

À priori $S$ peut être vide, quelles sont les hypothèses supplémentaires ?

Salut,

Il y a peut-être des hypothèses un peu plus fortes pour $N$ ? Et est-ce dynamique (les boules varient au cours du temps ou on peut prétraiter sans se poser de questions ?).

Si $N$ n'est pas trop gros, ça me semble relativement simple avec la norme infinie. On veut générer des points uniformément dans un gros carré privé de $|N|$ « petits » carrés. On peut alors discrétiser le problème en considérant uniquement les abscisses/ordonnées des carrés (un peu sur le principe des algos de sweep line en géométrie algorithmique). On partitionne le gros carré en polygones simples, et quitte à les trianguler (on a de l'ordre de $|N|$ points au total), on obtient une partition avec des triangles. On peut ainsi générer uniformément des points là-dedans (on pondère ça par l'aire des triangles).

C'est peut-être un peu trop substantiel par rapport au problème de départ, et ça ne me paraît intéressant que si $|N|$ est petit par rapport au nombre de pixels dans la solution « tout discrétiser ». Au besoin, je peux détailler davantage (notamment les complexités, pas tout regardé en détail).

De plus, je ne sais pas si on peut directement se ramener à la norme euclidienne à partir de là. Des avis ? (Ça m'intéresse aussi.)

ÉDIT : En fait, je viens de relire l'OP, je n'avais pas vu que le but final était de générer cet ensemble $N$. On peut sans doute faire mieux, du coup.

Dans les faits, $S$ est non vide.

En gros, je veux creer proceduralement un emsemble de points $N$ de $\mathbb{R}^2$.

• Chaque point p a un voisinage $D(p, r)$ ou on ne peux pas placer de points.
• Chaque point est placé dans un voisinage $D(p, R)$ ou $p$ est un point de $N$. ($r < R$).
• On a une origine.

Le but est d'avoir un ensemble de points joliment espacés, généré aléatoirement et potentiellement infini.

Les rayons sont fixes et, a priori, $|N|$ est tres faible par rapport au nombre de pixel.

Le milieu de ton message, j'ai pas trop compris .

Ce que tu dis n'est pas très clair. Est-ce que tu peux reformuler ? (Notamment sur qui est $p$, ce qui change entre ton premier message et ce dernier). Qu'entends-tu par « a une origine » ?

Je n'ai pas de technique applicable en pratique, mais voici ce que l'on peut faire pour générer un point uniformément dans une forme 2d quelconque à partir d'un générateur uniforme dans [0,1], avec un nombre d'essai constant (c'est tout bête mais c'est déjà ça) :

1. Identifier les point du plan par deux réels (sans que forcément chaque couple de réels corresponde à un point valide).
2. Calculer pour chaque valeur du premier paramètre la densité de probabilité correspondante (généralement longueur d'un chemin dans le plan, éventuellement coupé en plusieurs bouts).
3. Tirer le premier paramètre avec cette densité de probabilité (avec le générateur uniforme dans [0,1]).
4. Tirer le deuxième paramètre avec la densité de probabilité valant 1 aux endroits valides et 0 aux autres (normalisée).

Cela requiert d'intégrer certains trucs et de connaitre la réciproque d'une fonction. Par exemple, dans le cas du triangle avec deux vecteurs $v_1$ et $v_2$, on peut paramétrer un point du plan par sa décomposition en base $(v_1,v_2)$ et prendre $v_1(1-\sqrt{1-x_1}) + v_2(\sqrt{1-x_1})x_2$, avec $x_1$ et $x_2$ tirés uniformément entre $0$ et $1$. Les transformations qui préservent l'uniformité du tirage sont les transformations affines, donc on pouvait se réduire à tirer un point dans un triangle rectangle. Mais cela est moins bien que ce vers quoi a pointé Lucas-84 pour le triangle (moins simple et moins performant).

Pour un disque, on peut faire quelque chose un peu pareil en coordonnées polaires. Mais dans le cas du disque troué, ça a l'air trop complexe, je ne vois que l'essai-erreur (en maintenant une liste des positions valides (régulières ou aléatoires) ?).

Un problème intermédiaire pourrait être de tirer dans un rectangle des trous en forme de disques aléatoirement. Déjà, on voit que si on fait coup par coup, ce ne sera pas réparti uniformément sur l'ensemble des configurations possibles (il se peut qu'on laisse plus ou moins de place pour la suite).

Une idée pourrait être de générer une configuration imparfaite (trop régulière, ou bien avec des trous qui se chevauchent), et de la modifier pour la faire respecter tous les critères (bouger aléatoirement les cercles, gérer des collisions). Sinon, pour faire un essai-erreur, je ne sais pas si ça vaut le coup de faire quelque chose de plus performant asymptotiquement (avec de la triangulation et des diagrammes de Voronoï)…

Es-tu obligé de générer ça dynamiquement ? C'est pour quoi plus exactement ?

Voici des trucs assez jolis qui ressemblent : http://www.paulbourke.net/texture_colour/randomtile/

edit défi : En s'inspirant de ce qui a été dit plus haut dans ce topic, à partir d'un générateur uniforme de réel dans [0,1], produire un générateur aléatoire entre [0,1] avec pour fonction de répartition √x, et ce sans calculer de racine carrée.

Ce serait pas plus simple de faire un tirage aléatoire et d'itérer ce tirage tant qu'on n'a pas trouvé un résultat satisfaisant ? Par exemple, tu pourrais tirer aléatoirement un point P dans le disque $D(p,r)$ (facile à faire, en tirant aléatoirement une distance $a$ entre $0$ et $r$ et un angle $theta$). Puis tu regardes si ce point P est effectivement dans ton ensemble S ou pas. Pour ça, tu utilises une fonction de vérification, puisque tu as dit qu'il était assez simple de vérifier si un point est dans S ou pas.

Deux possibilités : - soit P est dans S (ce qui arrive avec une probabilité non nulle), dans ce cas c'est gagné - soit P n'est pas dans S. Dans ce cas, tu réitères et tu régénères un nouveau point P de la même façon que précédemment, puis tu refais la même vérification, ce qui t'amène à nouveau à deux possibilités, etc. etc.

Le premier réflexe qu'on a avec cet algorithme est de penser à une boucle infinie. Et bien non, il n'y a pas de boucle infinie tout simplement parce que la probabilité de tomber sur cette boucle infinie est de zéro (cela tient au fait que la probabilité que P n'est pas dans S est inférieure strictement à 1). Et cet algorithme a l'avantage est très simple à mettre en place.

Oui, c'est ce que Umbra me semble avoir voulu dire vers la fin de son premier message, et c'est ce que j'entendais par « essai-erreur ». Concernant le tirage aléatoire dans un disque, si on tire uniformément un rayon et un angle (« aléatoirement » comment ?), il va y avoir plus de chance de tirer le point proche du centre, donc il faut pondérer.

Concernant la boucle infinie, il se peut que l'on n'ait plus de place pour rien placer, ou plus beaucoup. Si on a une proportion p d'espace libre, on va faire en moyenne 1/p tirages. Mais pour calculer le nombre moyen de tirages au total pour faire $n$ trous, je ne vois pas comment faire car on n'enlève pas la même aire à chaque trou ajouté. Dans le pire des cas, on suppose que tous les trous enlèvent chacun une proportion p de l'aire totale. Le nombre de coups moyen pour faire n+1 trous est alors $1 + \frac{1}{1-p} + \cdots + \frac{1}{1-np}$. Si on considère ça comme une somme de Riemann, lorsque $n$ devient grand ça vaut à peu près $-\frac{\ln(1-np)}{p} = n(1 + O(np))$ (lorsque $np$ est petit). On peut aussi majorer ça par $\frac{1}{\frac{1}{n} - p}$…

Pour le tirage aléatoire dans un disque, effectivement tu as raison. On a plus de chances de tirer un point proche du centre. (De la manière dont je le voyais, on tirait un rayon $r$ uniformément entre $0$ et le rayon du disque, et un angle $theta$ uniformément entre $0$ et $2\pi$. Les fonctions aléatoires en programmation sont généralement similaires à un tirage uniforme (en tout cas elles essaient).

Pour résoudre ce problème du disque, en notant $R$ le rayon du disque, on peut considérer le carré de côtés $2R$ x $2R$ qui contient le disque. On peut tirer uniformément un point $P(x,y)$ dans le carré, en tirant uniformément deux nombres $x$ et $y$ entre $0$ et $2R$. Par suite, si on tombe sur un point $P$ qui n'est pas dans le disque, on élimine et on réitère. De cette manière, on effectue un tirage aléatoire uniforme sur le disque : de cette manière, on a autant de chances de tirer n'importe quel point du disque.

Sinon, beaucoup plus simple, on peux juste mettre une racine sur le rayon :