![[Utilisateur supprimé]](https://w0.vanillicon.com/06e033c229d2c3b99cf35e0f43a173e8_100.png)
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 ?
Réponses
-
Bonjour,
Mot clef: diagramme de Voronoï (et algorithme de Fortune).
Cordialement,
Rescassol
-
Il n'y a pas de documentation sur les diagrammes de Voronoï sur le web?
Une fonction est un ensemble $f$ de couples tel que pour tous $x,y,z$, si $(x,y)\in f$ et $(x,z)\in f$ alors $y = z$. -
Ben je ne trouve pas vraiment d'implémentation facile non. Ce n'est pas les concepts mathématiques qui me posent souci, mais simplement l'implémentation. J'aimerais trouver une sorte de "TP" guidé là dessus.
-
En fait, concrètement, mon problème est le suivant : comment faire pour implémenter une fonction (en python par exemple) qui prend un ensemble de points P et un indice i en paramètres, et renvoie l'intersection des demi-plans $DP_j$ décrits dans mon premier message ?
Ce n'est pas évident, une fois les médiatrices construites, on ne sait pas quels points d'intersection sont à conserver. -
En fait, si on a les médiatrices et les points d’intersection de ces médiatrices deux à deux, je ne vois pas sur quel critère retirer les points qu’on n'est pas censé avoir dans le germe
-
Bonjour
As tu cherché les mots que je t'ai donné sur le net ?
Cordialement,
Rescassol
-
Bien sûr, je connaissais ces mots avant de poster mon message. J’ai besoin d’un renseignement précis.
-
Bonjour,
L'algorithme de Fortune est explicité sur le net.
Cordialement,
Rescassol
-
Bien sûr, mais pas les détails techniques. C’est l’objet de ma question.
-
Bonsoir,naïvement pour chaque point de ma fenêtre graphique, je calculerais la distance entre ce point et les Pj. Si Pi est le point le plus proche de M bleu, sinon rouge...On peut par exemple imaginer définir une fonction couleur(M,i) qui réalise cette opération. Il doit également falloir bricoler des fonctions "changements de coordonnées" en fonction de la fenêtre graphique.
Bon courage
F. -
Le problème c’est que vous discretisez R^2. Or je veux éviter de perdre en généralité. Vous essayez de faire un algo des plus proches voisins. C’est un autre exercice.
-
Mon but ce n'est pas d'aboutir aux résultats, mais d'utiliser les algorithmes valables dans l'espace vectoriel euclidien du plan réel.
-
Pour mieux comprendre mon problème, supposons que pour un germe $p_i$, on trace les médiatrices de tous les segments $p_ip_j$ (ce sont les droites vertes). Les autres points $p_j$ ne figurent pas car on suppose qu'on a déjà construit ces médiatrices. En bleu figure $p_i$ et en orange foncé figurent les points d'intersection de ces médiatrices. Bien sûr, l'intersection de tous les demi-plan $DP_j$ est la cellule qu'on cherche à trouver : c'est la zone orange clair. Comment trouver cette zone. C'est une sorte d'enveloppe convexe, mais intérieure. Comment procéder ?
-
Franchement ce n'est vraiment pas trivial. Il y a déjà des algorithmes existants, donc des gens qui ont réfléchi au problème et qui ont trouvé des solutions, il serait dommage de passer à côté et réinventer la roue.
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). -
Bonjour"on trace les bissectrices de tous les segments pipj (ce sont les droites vertes)."Ça part mal. Il n'y a aucune bissectrice dans ton dessin. Voulais-tu dire "médiatrices" ? Ce n'est pas beaucoup mieux; les droites vertes ne sont pas des médiatrices.Voici ce que j'imagine être tes médiatrices autour du point bleu dans ton dessin dans une configuration ressemblante.
Ce site est fatigant. Les gens modifient sans cesse leurs messages passés, et on ne comprend plus rien à la discussion. Je suis nostalgique du temps où, si on postait une bêtise, on devait l'assumer. Et si on cite le passage pour l'ancrer, l'administrateur supprime en disant qu'on n'a pas besoin de recopier le message passé. -
Effectivement, ce ne sont pas les bissectrices, mais bien les médiatrices. Je n'ai pas fait attention.
"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.
-
raoul, merci pour ces ressources. Je compte implémenter les algorithmes connus après. Mais pour le coup, là, j'essaie juste d'implémenter l'algorithme naïf, qui consiste à prendre les intersections des demi plans. (c'est simple à faire en maths, mais moins de l'implémenter). Pour ce faire, je vais finalement opter pour une solution similaire à celle qu'a proposé malavita. En effet, je vais considérer les équations de toutes les médiatrices (et donc les inéquations vérifiées par les points des demi-plans), et je vais parcourir toutes les cases de la cellule, pour colorier les points qui vérifient toutes les équations.
-
Une version néophyte suboptimale j'imagine: tu as n points et tu t'intéresse à p1. Tu obtiens n-1 demi-plans et 2 parmi n-1points d'intersection. Pour chacun tu regardes de quel côté il est de chaque demi-plan en l'éliminant dès qu'il est du mauvais côté. Je préfère ne pas estimer le nombre d'opérations nécessaires, mais ça doit marcher
Il y a aussi le cas où ton lieu n'est pas borné à tester, c'est à dire quand ton p1 n'est pas dans l'enveloppe convexe des intersections qui te restent.The fish doesnt think. The Fish doesnt think because the fish knows. Everything. - Goran Bregovic -
Bonjour,
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. -
Merci pour vos retours. Oui ça doit marcher. ça m'a l'air quand même plus dur à implémenter que ce que je propose.
-
Restera le cas particulier évoqué par Soc, et qui peut générer bien des problèmes : parfois, le domaine-solution n'est pas borné.Tu me dis, j'oublie. Tu m'enseignes, je me souviens. Tu m'impliques, j'apprends. Benjamin Franklin
-
De façon toujours aussi naïve :
-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...Une question bête : si j'ai une fonction qui me dit si $M(x,y)$ est dans la partie du plan "qui va bien", pourquoi n'est ce pas une bonne implémentation ?
A+
F. -
C'est ce que j'ai proposé au départ. Mais prendre les points "qui vont bien" n'est pas si trivial que ça. Comment les déterminer facilement ? Et en faisant ainsi, on est encore confrontés au problème des cellules non bornées.
Quoi qu'il en soit, j'ai fini mon implémentation naïve. Je vais faire les autres maintenant. -
- 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,
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 dépend, il peut aussi être plus pertinent de ne regarder que les médiatrices entre le point qui nous intéresse ("le point bleu" = $p_i$) et les autres $p_j$, ce qui ne fait que $n-1$ médiatrices et $\binom{n-1}{2}$ intersections. Mais je ne n'ai pas bien compris ce message de @malavita, donc je ne sais pas de quelles médiatrices il ou elle parle.
-
@mathcoss: c'est l'avantage d'être naif, on a pas peur ;-) Ceci dit j'ai envie de dire qu'il n'y a que n-1 médiatrices à considérer , celles de $[P_iP_j]$ pour $j \neq i$ .@Tony: pour $M(x,y)$, je vérifierais juste que $a_jx+b_jy+c_j$ a le même signe que $a_jx_i+b_jy_i+c_j$, l'équation de la médiatrice de $[P_iP_j]$ étant $a_jx+b_jy+c_j=0$.@calli: nos messages se sont croisés. Pour ma "méthode", j'essayais juste de tracer l'enveloppe convexe des points de concours des médiatrices, qui sont proche de $P_i$. Je me suis bêtement dit que le bord de cette enveloppe est constitué de morceaux de médiatrices, d'où mon idée un peu rocambolesque.
A+
F -
Oui d'accord.
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. -
BonjourIl y a dans SageMath une implémentation du calcul du diagramme de Voronoi. D'après ce qui est expliqué, elle ne repose pas sur l'algorithme de Fortune mais utilise les calculs sur les polyèdres.L'idée est de remonter les points donnés dans le plan sur le paraboloïde $z=x^2+y^2$. L'intersection des demi-espaces supérieurs délimités par les plans tangents au paraboloïde en ces points est un polyèdre convexe qu'on projette sur le plan pour obtenir le diagramme de Voronoi.
-
Merci.
Mais je veux refaire l'algorithme de Fortune et pas un autre. -
Bah, tu fais ce que tu veux.Pour faire joli :
pts=[(random(),random()) for i in range(15)] P=point(pts,color="black") V = VoronoiDiagram(pts); S=V.plot() show(S+P,axes=False,xmin=0,ymin=0,xmax=1,ymax=1)
-
Re,naïf is back ;-)Pour ma part, je créerais deux listes de points : les points à traiter et ceux déjà traités, la seconde étant initialement vide. Il suffit après de "traiter" le point le plus à gauche de la première liste et de le mettre dans la seconde. Après je suis bien incapable de développer ce fameux "traiter" ;-) Ceci dit, je ne pense pas que l'on puisse s'en tirer sans créer une classe point avec les méthodes "qui vont bien" ;-)
A+
F. -
"Après je suis bien incapable de développer ce fameux "traiter""
Justement, ça a l'air horrible à implémenter -
Dans l'animation de l'algorithme de fortune sur wikipédia, la droite se déplace de façon "continue" donc sûrement avec un pas, ce qui laisse supposer des valeurs approximatives pour les intersections.
The fish doesnt think. The Fish doesnt think because the fish knows. Everything. - Goran Bregovic -
Pourquoi est-ce que le problème est plus simple avec une dimension de plus ? Comment calcule-t-on les sommets et les arêtes d'un polyèdre ?
-
Les régions du diagramme de Voronoi sont les projections des facettes du polyèdre construit au dessus, ce qui permet d'employer les routines déjà présentes pour traiter les polyèdres (passer d'une description comme intersection de demi-espaces à une description avec sommets et arêtes).
-
@Tony Schwarzer : que veux-tu en fait ? Juste le germe d'un $p_i$ donné, ou tout le diagramme de Voronoi ? L'algorithme de Fortune n'est peut-être pas le plus adapté dans le premier cas. Pourtant, dans ton premier message, c'est ce premier cas qui semblait t'intéresser.
-
Tu prends un cercle $\C$ centré en un point, en partant d'un rayon $r=0$, puis tu augmentes $r$ jusqu'à tomber sur d'autres points qui tombent donc sur le cercle, puis tu considères les droites formées par les points dans l'ordre de leur rencontre (cycliquement : le dernier point est à relier avec le 1er) avec le cercle $\C$, parti de $0$.
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. -
Cette histoire de cercle qui grandit ne me plaît pas trop.Je verrais plutôt un truc du genre suivant. Appelons $q$ le point dont on veut calculer le germe, $p_i$ les autres. On les suppose ordonnés pour $i=1,\ldots,n$ suivant leur angle polaire par rapport à l'origine $q$, et on construit le bord du germe en tournant. On commence par la médiatrice $M_1$ de $q$ et $p_1$. Puis la médiatrice $M_2$ de $q$ et $p_2$ et son intersection $I_{1,2}$ avec $M_1$. Puis $M_3$ ; si $M_3$ laisse $I_{1,2}$ du mauvais côté, on oublie ce dernier, on prend l'intersection $I_{1,3}$ de $M_1$ avec $M_3$.etc.
-
Tony Schwarzer a dit :
Ca ne définit pas un objet, ces points ne forment pas obligatoirement par exemple un polygone, ou quelque chose d'à peu prés défini dont on se serait attendu qu'elle le soit, genre question : il faudrait pouvoir les ordonner, ou essayer toutes les combinaisons pour éventuellement trouver un « 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$.
En passant question bête sans doute annexe : pour tout i, $G(p_i)=P$ n'est pas une solution avec cette seule contrainte ?🙂Le germe est donc un polygone qui délimite la "zone d'influence" de $p_i$.
« 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 ?Pour la calculer, on peut par exemple...
tenter de présenter un peu plus le « contexte » mathématique ? 🙂 -
Bonjour.
Bizarre ton interprétation de "plus proche de $p_i$ que de tout autre point de P"
Cordialement -
Pourquoi un polygone ?
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.Tu me dis, j'oublie. Tu m'enseignes, je me souviens. Tu m'impliques, j'apprends. Benjamin Franklin -
Ok merci j'ai pige.
-
La complexité de l'algorithme que j'ai esquissé est en $O(n\log(n))$, où $n$ est le nombre de points ; pas mal, non ? Le $n\log(n)$ vient du tri, le reste du travail est de complexité linéaire en $n$.Bon, l'algorithme de Fortune a aussi une complexité en $O(n\log(n))$.
-
"En passant question bête sans doute annexe : pour tout i, G(pi)=P n'est pas une solution avec cette seule contrainte ?🙂"
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.
-
Dans mon baratin, j'avais un point $Q$ et $n$ points $P_i$ tout autour, d'où mes $n$ demi-plans.
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.
Tu me dis, j'oublie. Tu m'enseignes, je me souviens. Tu m'impliques, j'apprends. Benjamin Franklin -
Ok merci. Je vais essayer de faire comme ça.
-
"Je veux le diagramme tout entier, à la différence de ce que suggère mon message initial"D'accord. Juste que ton premier message et ton titre ne "suggèrent" pas : ils demandent explicitement UN germe.
Connectez-vous ou Inscrivez-vous pour répondre.
Bonjour!
Catégories
- 163.2K Toutes les catégories
- 9 Collège/Lycée
- 21.9K Algèbre
- 37.1K Analyse
- 6.2K Arithmétique
- 53 Catégories et structures
- 1K Combinatoire et Graphes
- 11 Sciences des données
- 5K Concours et Examens
- 11 CultureMath
- 47 Enseignement à distance
- 2.9K Fondements et Logique
- 10.3K Géométrie
- 65 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 69 Informatique théorique
- 3.8K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 24 Mathématiques et finance
- 314 Mathématiques et Physique
- 4.9K Mathématiques et Société
- 3.3K Pédagogie, enseignement, orientation
- 10K Probabilités, théorie de la mesure
- 773 Shtam
- 4.2K Statistiques
- 3.7K Topologie
- 1.4K Vie du Forum et de ses membres
In this Discussion
Qui est en ligne 32
+26 Invités