Déterminer un germe
Bonjour,
on se donne un ensemble $P=\{p_1,...,p_n\}$ de points du plan et et $i \in [1,n]$, et on cherche à déterminer informatiquement le germe $G(p_i)$ constitué des points $X$ de $\mathbb{R}^2$ tels que $X$ soit plus proche de $p_i$ que tout autre point de $P$. Le germe est donc un polygone qui délimite la "zone d'influence" de $p_i$. Pour la calculer, on peut par exemple dire que c'est l'intersection de tous les demi-plans $DP_j$ définis par :
$$DP_j = \{X\in \mathbb{R^2}, |X-p_i| \leq |X-p_j|\}$$
où $j\in [1,n]-\{i\}$.
Cela se comprend bien mathématiquement mais je n'arrive pas à l'implémenter informatiquement. Une fois qu'on a les équations de toutes les médiatrices des segments $p_ip_j$ ($i$ fixé), comment obtenir ce qu'on veut, c'est à dire pouvoir afficher dans une fenêtre graphique (par exemple) le contour du germe ?
on se donne un ensemble $P=\{p_1,...,p_n\}$ de points du plan et et $i \in [1,n]$, et on cherche à déterminer informatiquement le germe $G(p_i)$ constitué des points $X$ de $\mathbb{R}^2$ tels que $X$ soit plus proche de $p_i$ que tout autre point de $P$. Le germe est donc un polygone qui délimite la "zone d'influence" de $p_i$. Pour la calculer, on peut par exemple dire que c'est l'intersection de tous les demi-plans $DP_j$ définis par :
$$DP_j = \{X\in \mathbb{R^2}, |X-p_i| \leq |X-p_j|\}$$
où $j\in [1,n]-\{i\}$.
Cela se comprend bien mathématiquement mais je n'arrive pas à l'implémenter informatiquement. Une fois qu'on a les équations de toutes les médiatrices des segments $p_ip_j$ ($i$ fixé), comment obtenir ce qu'on veut, c'est à dire pouvoir afficher dans une fenêtre graphique (par exemple) le contour du germe ?
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Mot clef: diagramme de Voronoï (et algorithme de Fortune).
Cordialement,
Rescassol
Ce n'est pas évident, une fois les médiatrices construites, on ne sait pas quels points d'intersection sont à conserver.
As tu cherché les mots que je t'ai donné sur le net ?
Cordialement,
Rescassol
L'algorithme de Fortune est explicité sur le net.
Cordialement,
Rescassol
Bon courage
F.
Voici quelques documents qui expliquent l'algorithme de Fortune (qui est assez ingénieux semble-t'il) :
1) Page 411 de ce PDF (explications assez détaillées théoriquement de prime abord)
2) Page 23 de ce PDF (explications basiques pour essayer de comprendre comment fonctionne l'algorithme)
3) Peut-être une implémentation (voir page 12).
"Ce n'est pas beaucoup mieux; les droites vertes ne sont pas des médiatrices." En revanche, ça part mal aussi de ton côté. Tu n'as a priori pas compris mon schéma. Il s'agit bien des médiatrices. Les droites vertes sont tracées arbitrairement, mais peu importe, on peut admettre que ce sont les médiatrices des $p_ip_j$ (j'ai précisé que les $p_j$ ne figurent pas sur mon schéma pour éviter de l'encombrer, vous confondez les points d'intersection des médiatrices, avec les points $p_j$. J'ai précisé cette distinction). Ce qui est important de voir, c'est qu'on peut obtenir un tel ensemble de droites qui correspondent effectivement aux médiatrices.
Une autre idée comme ça :
Pour chaque point d'intersection $I$ de deux médiatrices (sous-entendu médiatrice entre le point bleu et un autre $p_j$, pas entre deux $_j$ quelconques), tu regardes s'il existe une 3e médiatrice qui sépare $I$ du point bleu. S'il n'existe pas de telle médiatrice, tu mets $I$ dans une liste. La liste de points obtenue est la liste des sommets du polygone que tu veux tracer. Ensuite, il suffit de trier cette liste selon la direction angulaire des points $I$ par rapport au point bleu (il y a une formule pour trouver cet angle en fonction des coordonnées, avec du $\arctan$) pour que les points soient listés dans l'ordre dans lequel ils délimitent le polygone. Ensuite, tu peux afficher le polygone en reliant graphiquement les points de cette liste.
PS : Cet algorithme est de complexité $n^3$.
Edit : Je n'avais pas vu le message de @Soc.
-partant des équations de mes médiatrices, je déterminerais les éventuels points d'intersection de celle-ci,
-pour chacune de ces points je regarderais s'il est dans la partie du plan "qui va bien" ou pas,
-parmi tous les points "qui vont bien", je relierais ceux situés sur une même médiatrice (pas très sur de cette étape).
Pour le cas non borné, on doit pouvoir bricoler un truc avec les points à l'infini...
A+
F.
Quoi qu'il en soit, j'ai fini mon implémentation naïve. Je vais faire les autres maintenant.
Ouh là ! Avec environ $n^2/2$ médiatrices, cela fait de l'ordre de $n^4/4$ tests. Tu n'as pas peur ?
A+
F
Maintenant, est-ce que quelqu'un connaît une implémentation de l'algorithme de Fortune ? Je n'en connais pas de simple. Je ne sais pas vraiment pour quelles structures de données opter.
Mais je veux refaire l'algorithme de Fortune et pas un autre.
A+
F.
Justement, ça a l'air horrible à implémenter
On peut faire une droite qu'à partir de deux « intersections » de $\C$, donc au départ la droite ne peut pas délimiter une « zone fermée » qui est ce su'on recherche, on augmente alors le rayon du cercle $\C$ jusqu'à trouver un nouveau point suivant.
A nouveau avec 3 points on a forcément un triangle donc une « zone fermée », oui mais il faut vérifier que le point initial (centre du cercle $\C$) est bien dans cette « zone fermée ».
Si ce n'est pas le cas, on fait à nouveau grandir $r$ jusqu'à trouver un autre point etc.
Il ne doit pas être difficile, j'imagine, d'implémenter cela.
En passant question bête sans doute annexe : pour tout i, $G(p_i)=P$ n'est pas une solution avec cette seule contrainte ?🙂
« donc » ? Pourquoi les points les plus proches formeraient un polygone ? Les plus proches, les plus proches, ils sont tous les plus proches quelque part..
Par exemple, un point peut être proche d'un $p_i$ mais être rejeté car il ne permet pas de former un polygone ?
Mais ... il aurait pu peut-être avec plus de points.. dans ce cas quel germe choisir ?
tenter de présenter un peu plus le « contexte » mathématique ? 🙂
Bizarre ton interprétation de "plus proche de $p_i$ que de tout autre point de P"
Cordialement
On a un point $Q$ et $n$ points $P_i$
Pour un point $P_k$ donné, l'espace des points qui sont plus proches de $Q$ que de $P_k$, c'est un demi-plan.
Les points qui sont plus proches de $Q$ que de tous les points $P_i$, c'est l'intersection de $n$ demi-plans, c'est une zone délimitée par (au plus) $n$ segments. C'est un polygone avec au plus $n$ côtés.
Avec toujours, cette extension de la définition de polygone, pour le cas de surface infinie : par exemple, il faut considérer qu'un demi-plan est un polygone.
Souvent, pour se prémunir de ce cas de polygone infini, on commence par définir un rectangle (= on ajoute 4 points $P_i$ bien choisis), et on travaille dans ce rectangle.
Je n'ai pas compris ton objection. Mais pour répondre : non. A titre de contre exemple, il suffit de considérer $j$ différent de $i$, et on se rend compte que $p_j$ est plus proche de lui-même que de $p_i$ (à moins, à la rigueur, que $p_i=p_j$, ce qui n'est pas). Donc $P$ n'est même pas inclus dans l'ensemble des points $X$ tels que $p_i$ soit le point de $P$ le plus proche de $X$.
Le germe est bien unique, et c'est bien un polygone en tant qu'intersection de $n-1$ (et non $n$ lourrran, je pense) demi-plans.
@GaBuZoMeu Je veux le diagramme tout entier, à la différence de ce que suggère mon message initial, qui portait à la base sur un algorithme naïf et non sur celui de Fortune. Ce qui me pose problème, ce n'est pas l'algorithme en lui-même, mais les structures de données à utiliser pour l'implémenter. Donc c'est un problème d'implémentation. Déjà, par exemple, je ne sais pas trop comment représenter informatiquement de tels diagrammes de Voronoi efficacement. J'aurais bien aimé trouver une implémentation toute faite pour m'aider un peu, mais je trouve uniquement des ressources anglaises pour cela. Or, je suis incapable de les lire.
Maintenant, on parle du diagramme de Voronoï complet. Donc comme le dessin https://les-mathematiques.net/vanilla/index.php?p=/discussion/comment/2368832/#Comment_2368832
Tu ne sais pas comment représenter de tels diagrammes efficacement.
Je pense que c'est assez lié à ce que tu veux en faire ensuite.
Une option, c'est de définir pour chaque point le contour du polygone correspondant. Tu auras donc un tableau de $n$ polygones.
L'autre option, c'est de recenser tous les segments utiles. Une trentaine dans le cas de l'exemple.
Dans les 2 cas, un problème annexe, ce sera : comment gérer les bords du carré. A priori, tu as une zone du plan limitée (le carré (0,1)x(0,1) dans le code donné en exemple) ; Si ce n'est pas le cas, tu as plein de polygones qui sont 'infinis'.
Je parlais d'une trentaine de segments, il faut ajouter soit 4 segments, pour les 4 bords du carré, soit beaucoup plus (14 dans l'exemple) suivant comment tu veux avoir tes données.
Si tu veux avoir un tableau avec les $n$ polygones, ça veut dire que chaque segment est mémorisé 2 fois, parce qu'il participe à 2 polygones.
Et en fait, tu auras certainement le segment (AB) pour un polygone, et le segment opposé (BA) pour l'autre polygone, parce que l'usage veut qu'on stocke un polygone en tournant toujours dans le même sens.