Diagramme de Voronoï Tkinter

Bonjour à tous,
Cela fait un moment que je me suis lancé dans une représentation d'un diagramme de Voronoï sous Tkinter. Vous vous en doutez, je rencontre des problèmes :?

Ce que j'essaye de réaliser doit ressembler à cela :
Pièce jointe 211142

J'utilise une méthode incrémentale, je place un point, le canevas se met à jour. Cela se rapproche de cet algorithme : https://fr.wikipedia.org/wiki/Diagra...reen_et_Sibson

Où j'en suis :
J'ai réalisé une fonction qui me place mes points. Une autre fonction qui trace les médiatrices des points, tout en arrêtant le tracé aux points d'intersections :
Pièce jointe 211143

Mon problème :
Malheureusement, le tracé des médiatrices est partiellement faux :
Pièce jointe 211144

Donc ça devient vite le bazar ensuite ( même si cela ressemble plus à un diagramme de Voronoï ):
Pièce jointe 211145

Ce que j'ai essayé :
J'ai détecté la médiatrice erronée, et essayé de la retracer en fonction du point d'intersection, mais ce fut un échec car le nouveau tracé dépends d'autres points aux alentours de ce point d'intersection, qui varient suivant la zone du diagramme.
Ensuite j'ai essayé pour chaque nouveau point placé, que mon programme détecte les deux autres points les plus proches et réalise les médiatrices de ces points ( les 3 points d'un cercle circonscrit ). Mais des médiatrices inutiles se tracent.

Merci de m'avoir lu :) Je peux mettre les parties de code qui vous sont nécessaires pour m'aiguiller.

Salut,

Citation:

---

Envoyé par Leododo

J'ai détecté la médiatrice erronée, et essayé de la retracer en fonction du point d'intersection, mais ce fut un échec car le nouveau tracé dépends d'autres points aux alentours de ce point d'intersection, qui varient suivant la zone du diagramme.
Ensuite j'ai essayé pour chaque nouveau point placé, que mon programme détecte les deux autres points les plus proches et réalise les médiatrices de ces points ( les 3 points d'un cercle circonscrit ). Mais des médiatrices inutiles se tracent.

---

La question est de savoir si le problème vient du tracé des segments de droite (1) ou du calcul des extrémités à tracer (2).
Dans le cas (2), réduisez le nombre de points, fabriquez quelques cas de figures "pathologiques" et vérifiez que les calculs sont justes.
Pour (1), il devrait vous être possible de postez un exemple construit hors de votre programme.
Si vous n'arrivez pas à faire la part des choses entre (1) et (2), essayer de reconstruire votre programme sur des bases plus saines? C'est une méthode raisonnable lorsqu'un programme devient trop touffu et qu'on ne comprend plus trop les parties qui font assez bien leur boulot (comparées à d'autres).

- W

Merci pour la réponse :) Pour l'instant, mon programme fait 60 lignes environ, tout est réparti en fonctions.
Le problème vient du tracé des segments de droite (1).

En fait, dans mon programme le tracé de médiatrice se fait en deux étapes :
- Le calcul du milieu entre deux points, pour récupérer un point et une direction de médiatrice. Je peux alors avoir deux vecteurs.
- La prolongation des vecteurs de la médiatrice dans chacun des deux sens. Cette prolongation s'arrête dès qu'une autre médiatrice est rencontrée.

Extrait :

Code:

---

1 2 3 4 5 6 7 8 9 10 11

def prolongation(x0,y0,dx,dy): # Mon point d'application et ma direction   x,y,SensA,choc = 1,1,0,False while x>0 and x<LG and y>0 and y<HT and choc == False : # Tant que le tracé ne rencontre ni un autre tracé ni les bords du canevas x,y = x0+SensA*dx,y0+SensA*dy SensA += 1 # Je continue le tracé   detect = can.find_overlapping(x,y,x,y) if detect is not () : # Si la détection d'objet ne renvoie pas rien ( = un objet est détecté ) choc = True # La prolongation du vecteur s'arrête, ma médiatrice se trace ensuite

---

Donc c'est normal que je rencontre ce problème :
Pièce jointe 211162

Ce que j'ai essayé, c'est de retracé en deux morceaux la médiatrice choquée, la mettre à jour en quelque sorte. Et ça je n'y arrive pas vraiment :/

Citation:

---

Envoyé par Leododo

En fait, dans mon programme le tracé de médiatrice se fait en deux étapes :
- Le calcul du milieu entre deux points, pour récupérer un point et une direction de médiatrice. Je peux alors avoir deux vecteurs.
- La prolongation des vecteurs de la médiatrice dans chacun des deux sens. Cette prolongation s'arrête dès qu'une autre médiatrice est rencontrée.

---

Et vous comptez sur l'interface graphique pour calculer l'intersection à votre place? L'interface doit juste servir à afficher le résultat de vos calculs (l'intersection de deux droites dans le plan c'est quand même pas si compliqué).

- W

Je peux utiliser le cercle circonscrit. Puisque les deux médiatrices qui se coupent ont un point en commun, en réalisant une fonction prenant comme paramètres 3 couples points, je calcule le centre du cercle circonscrit, qui est le point d'intersection des médiatrices. J'ai réalisé cela auparavant.

Je peux aussi simuler le tracé de médiatrices, récupérer les 4 points correspondants aux bouts des médiatrices, en déduire l'équation de chaque médiatrice, résoudre le système permettant de savoir si elles sont sécantes, si elles le sont j'ai mon point d'intersection. J'ai ça aussi.

Je récupère le problème différemment, car je devrais choisir lequel des deux bouts de la médiatrice relier à mon point d'intersection :/