Discussion :

[Leododo]

Bonjour à tous,

Je me suis attaqué à réaliser un diagramme de Voronoï sous Python tkinter, je cherche donc à obtenir un canevas de ce type :

Voilà où j'en suis, une capture d'écran de mon canevas, avec peu de points pour y voir clair.

J'ai donc mes points de zones en jaune. Pour délimiter les zones que l'on peut voir sur la première image, j'ai eu besoin de cercles minimum et de cercles circonscrit.
Les centres de ces cercles circonscrits sont vert, les milieux entre chaque points sont rouge.

Pour tracer les délimitations de ces zones, je vais relier certains de ces centres et milieux entre eux, et avec le bord de mon canevas.

La petite aide dont j'aurais besoin concerne cette partie : relier certains de ces centres et milieux entre eux.
Comment trier les bonnes des mauvaises délimitations ?
Je ne cherche pas la réponse exacte, mais juste une idée de méthode. Je ne cherche pas non plus un algorithme super optimisé, je programme ça moi même.

Merci de m'avoir lu

[Flodelarab]

Bonjour

Étrange de construire tout un tas de points, et se demander, après coup, à quoi ils peuvent servir.

En quoi la page wikipédia sur le sujet ne te comble-t-elle pas ?

[anapurna]

salut

effectivement c'est une étrange représentation du diagramme de voronoi

le graphe de voronoi est normalement un segment de droite passant par le centre d'une droite défini par deux point et perpendiculaire à celle-ci

[Trap D]

le graphe de voronoi est normalement un segment de droite passant par le centre d'une droite défini par deux point et perpendiculaire à celle-ci

Même des élèves de sixième ne font pas ce genre d'erreurs !

[anapurna]

salut

ouais bon le centre d'un segment de droite défini par deux point si tu préfère

[tbc92]

Je ne sais pas si leododo a avancé dans son projet.

Quand on n'a que 2 points, c'est simple. La droite qui va couper le plan en 2 est la MEDIATRICE des 2 points. L'étape n°1, c'est donc de faire une fonction qui va permettre de trouver la droite médiatrice à partir de 2 points.
Après , quand on a plus de 2 points, c'est un peu plus compliqué. Il va falloir faire par exemple une autre fonction qui va donner le point d'intersection à partir de 2 équations de droites.

[Leododo]

Merci pour vos réponses.

En quoi la page wikipédia sur le sujet ne te comble-t-elle pas ?

La transcription mathématique programmation me pose soucis, et je préfère comprendre de que je fais

L'étape n°1, c'est donc de faire une fonction qui va permettre de trouver la droite médiatrice à partir de 2 points.

J'ai suis en train de réaliser ça, je vous transmet mon avancement

[Leododo]

Re-bonjour,

J'ai réalisé ma fonction médiatrice, en voici deux exemples :

Après, quand on a plus de 2 points, c'est un peu plus compliqué. Il va falloir faire par exemple une autre fonction qui va donner le point d'intersection à partir de 2 équations de droites.

Je m'attaque à la réalisation de cette fonction .

[Flodelarab]

Le libriste que je suis se sent obligé de dire que, si ce que tu veux est un logiciel de géométrie, tu as kig comme logiciel libre, qui est très bien fait et extensible par du code python.

Je m'attaque à la réalisation de cette fonction

En ayant bien sûr mesurer que ce point est le centre du cercle circonscrit que tu sembles déjà avoir.

[anapurna]

salut,

dans ta deuxième images on s'aperçois qu'il y a des zones inutiles
il faut peut être optimiser

[Leododo]

Re bonjour, merci pour vos réponses, voilà où j'en suis

Je reprends mes médiatrices :


Ensuite :

Il va falloir faire par exemple une autre fonction qui va donner le point d'intersection à partir de 2 équations de droites.

En ayant bien sûr mesurer que ce point est le centre du cercle circonscrit que tu sembles déjà avoir.

On s'aperçois qu'il y a des zones inutiles.

J'ai donc réalisé une fonction qui me trouve le point d'intersection, une seconde qui arrête le tracé de médiatrice jusqu'à ce point d'intersection :


Malheureusement, le tracé de la médiatrice précédente devient partiellement faux :


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


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.

Donc mon nouveau problème est cette 'mise à jour' des médiatrices existantes.
Merci de m'avoir lu.

[Leododo]

Pour vous cibler un peu plus, ce que j'essaye de réaliser est une méthode incrémentale, se rapprochant de l'algorithme de Green et Sibson.https://commons.wikimedia.org/wiki/F...een_sibson.svg

Seulement, c'est difficilement compréhensible.
Pour l'instant mon programme se divise comme cela :

- Une fonction points(), posant les points sur le diagramme.
- Une fonction proximité(), qui détermine le point le plus proche du dernier point placé. Cette fonction fait appel à une fonction distance() calculant l'écart entre deux points.
- Une fonction médiatrice(), traçant la médiatrice d'un segment défini par deux points. Cette fonction fait appel à une fonction prolongation(), qui prolonge deux fois un vecteur à partir d'un point d'application, d'une direction et de deux sens.

Voilà

[souviron34]

Pourquoi tout simplement ne pas faire une triangulation incrémentale de Delaunay ?? (pleins de codes existent, et j'ai le mien aussi, il me semblait quelque part dans la rubrique Contribuez, mais je ne suis plus sûr)

Les points du Voronoi sont simplement les milieux des arêtes des triangles, qu'il suffit alors de joindre (je crois que dans Graphics Gems il y a un code)

[Leododo]

Merci pour la réponse.

J'ai trouvé cela :
http://www.developpez.net/forums/d48...-incrementale/
http://www.realtimerendering.com/res...msiv/delaunay/

Je vais essayer de comprendre et de reprendre mon code.

[tbc92]

Sur la base de ce que tu as déjà fait, voici des éléments pour continuer.
Pour chaque couple de point A B, tu sais déterminer la médiatrice M(A,B). Une idée est de déterminer cette médiatrice en prenant 2 points très loin (de part et d'autre de notre groupe de points)

On va en effet traiter des segments, et pas des droites.

- A partir de M(A,B) et M(A,C), on sait calculer leur point d'intersection X. Et donc on va pouvoir nettoyer un peu. Sur la médiatrice M(A,B), il y a au plus un des 2 segments qui sera repris dans le diagramme de Voronoï. Soit le Segment qui part de X vers l'extrémité A, soit le segment qui part de X vers l'extrémité 2. Et une des étapes de l'algorithme, ça va être de déterminer quel segment est à conserver, et quel segment est à rejeter. Comment choisir lequel des 2 segments est pertinent ?

Et en bouclant sur tous les couples de médiatrices, tu vas bâtir des segments de plus en plus adaptés.

[souviron34]

Je me permet de penser que ça va être un peu essais/erreurs, alors que la solution en partant de Delaunay, est , par construction, intrinsèquement unique et juste..

C'est la définition même...

https://en.wikipedia.org/wiki/Delaunay_triangulation

The Delaunay triangulation of a discrete point set P in general position corresponds to the dual graph of the Voronoi diagram for P

D'ailleurs, le code fourni par pseudocode l'illustre bien dès le premier post de la première discussion qu'il a trouvé..

[Leododo]

Pour chaque couple de point A B, tu sais déterminer la médiatrice M(A,B). Une idée est de déterminer cette médiatrice en prenant 2 points très loin (de part et d'autre de notre groupe de points)

Et bien, j'ai pu utiliser les bords de mon canevas afin de récupérer deux points éloignés. En reliant ces deux points, j'ai pu obtenir cette médiatrice

La solution en partant de Delaunay, est , par construction, intrinsèquement unique et juste.

Comment choisir lequel des 2 segments est pertinent ?

Et bien, en lisant la triangulation de Delaunay, je peux sélectionner les segments à partir du moment où ils relient deux barycentres, centres de cercles circonscrits ne contenant aucuns autres points.

Cela m'a donné ( les cercles circonscrits blancs sont ceux n'étant pas retenus ) :

Et ces fameux segments relient les points rouges (barycentres retenus) entre eux, et les points rouges avec les bords du canevas.

En combinant avec vos précieuses réponses, j'ai pu avancer vers ceci :

C'est pas terrible, mais toujours mieux qu'avant.