Gérer l'intersection d'objets (cercles, ellipses, etc.)

Bonjour,

Je suis en ce moment en train d'écrire un petit programme python qui me permet de générer des structures type béton. En 2D ça ressemble donc a un rectangle dans lequel on vient mettre des cercles... Mais ces cercles ne doivent pas se croiser.
Pour les cercles pas de problème, ça marche, je lui dit que la distance entre les cerlces doit ètre inferieure à la somme des rayons. Je fait le test pour tout nouveau cercle avec chaque cercles existant. En revanche je souhaite le faire maintenant avec des ellipses. Et là, pour gerer la non-intersection je galere carrément. Je me contente pour le moment d'ellipse orientée à 0 ou 90 degrés.

Quelqu'un à t'il déja fait ce genre de chose sous python??
Est il possible de définir l'aire que forme l'ellipse et considérer qu'on la condamne ou un truc comme ça? car géométriquement parlant je vois trop comment faire.
Pour l'instant j'arrive à les générer, les orienter et voir si elle sont dans le meme sens ou pas, mais l'intersection, impossible :-(

Merci beaucoup d'avance.

Le problème n'a rien à voir avec python.
On est justement sur ce problème sur le forum d'algo (sous-forum maths).
Tu peux commencer par lire cela (voir les références du dernier post)
http://www.developpez.net/forums/d90...nt-ellipsoide/

Bonsoir,



Une idée:

Utiliser un logiciel de graphisme, comme PIL, matplotlib ou je ne sais quel autre

En partant de deux surfaces elliptiques (surfaces contenues dans des ellipses) ayant deux couleurs différentes.....

il me semble qu’un logiciel de graphisme doit être capable de modifier la couleur de la partie d’une surface qui est en intersection avec une autre surface.

Yadonkpluka lancer le logiciel pour qu’il fasse cette modif sur une des deux ellipses en tenant compte de l’autre,

puis on vérifie si tous les pixels de la surface soumise au traitement sont restés inchangés ou non.

L’idée, c’est de résoudre le problème graphiquement plutôt que mathématiquement, en faisant supporter le travail par un logiciel de graphisme optimisé pour ses opérations.





Sinon, une résolution à base de mathématique me semble présenter une difficulté:

une équation analytique d’une courbe a des variables mathématiques parcourant des ensembles continus,

tandis qu’une représentation graphique d’une surface repose sur des pixels discrets

Il se pose donc la question de la précision voulue pour considérer qu’il y a ou n’y a pas recouvrement de deux surfaces.

@eyquem
Bonsoir,
A mon avis ce n'est pas une bonne idée.
En effet, pour trouver ton intersection tu vas être obligé de balayer tous les pixels de l'image. Dans le genre 'force brute', il y a plus simple: Tu paramètres une des deux ellipses et tu balayes le pourtour avec un certain 'step' correspondant à un pixel maxi. Pour chaque point tu vérifies si la somme des distances aux foyers de l'autre ellipse est inférieure au grand axe de l'autre ellipse, si tu trouves un seul point pour lequel ça marche, il y a intersection.

Bonsoir Zavonen,



À vrai dire, avant même de poster, je pensais parfaitement prévisible que ça n’allait pas être une bonne idée.



Mais ta réponse m’en donne une autre.

C’est vrai que c’est pas mal bourrin de vouloir faire travailler un logiciel sur des surfaces, et de façon exhaustive en plus, avant de vérifier s’il y a eu modification.

Mais pourquoi ne pas faire une recherche d’intersection des deux COURBES ellipses ?

Si une carte graphique sait quels pixels allumer pour dessiner une courbe, c’est bien qu’elle doit recevoir, ou calculer, la liste des pixels précisément identifiés qu’elle doit activer de telle ou telle manière.

je me dis qu'il devrait être possible de lister les pixels (c à dire leurs coordonnées) d’une ellipse, de lister les pixels de l’autre ellipse, et avec une fonction du genre de celles qu’on trouve dans numpy et qui travaillent à toute alure, on doit pouvoir trouver l’intersection en un rien de temps.



On devrait ainsi trouver soit deux spots, soit aucun, soit beaucoup plus rarement un seul spot.

Par spot, j’entends un petit groupement de pixels en un endroit de l’écran, car je suppose que, pour représenter une courbe avec des pixels organisés de façon discrète , la trace effective d’une courbe sur un écran prend des angles droits et des lignes droites .. et comme l’autre courbe fait de même....



De plus, si on connaît les centres de chaque ellipse, on peut concevoir aussi de traiter algorithmiquement les positions des spots d’intersection quand il y en a, pour déduire par quelles sortes de translation et de rotation on pourrait modifier le mieux possible la position d’une ellipse pour l’éloigner de l’autre afin d’atteindre de proche en proche une situation où les deux ellipses ne seraient plus qu’a peine séparées d’un pixel et dans une distance minimale de leurs centres.

Voilà un beau sujet pour se régaler à mettre en œuvre des maths.

Comme je ne suis pas bon en GAO et pas autant que toi en maths, je te laisse trouver un collègue pour le graphisme, et toi comme matheux, je suis sûr que vous allez le sortir cet algorithme ! :D

Avant toute chose on peut essayer de déterminer les cas où il ne peut y avoir aucune intersection.
Une façon de faire consiste à mettre chaque ellipse dans un rectangle ayant pour longueur le grand axe et pour largeur le petit axe.
On peut commencer par étudier l'intersection des deux rectangles, si elle est vide, les deux ellipses ne peuvent se couper, sinon on peut mettre en œuvre un algorithme de recherche.
Le problème de l'intersection de deux rectangles (Oriented Bounding Box: axe séparateur=arête séparatrice est abondamment traité sur tous les forums).
Par la suite si l'intersection existe c'est un polygone convexe et on peut faire la recherche à l'intérieur de ce polygone.
En fait tout est traité ici:
http://www.google.fr/url?sa=t&source...2SNY8MPLaKHvwA

Dans le principe, ce problème m’intéresse. Mais pratiquement, je ne peux pas m’y consacrer, j’ai déjà plein de sujets fondamentaux sur Python que je néglige et je ne suis compétent ni en maths ni en graphisme.

J’ai juste voulu apporter ma petite réflexion: je pense qu’on a toujours intérêt à examiner si on peut insuffler de la mathématique dans une résolution envisagée au départ comme computation informatique, mais aussi inversement de ne pas se priver des capacités informatiques pour diminuer la complexité d’une résolution engagée dans une voie de raisonnement mathématique. Je ne me rappelle plus le nom de cette discipline qui a pour principe de recourir aux possibilités informatiques pour établir même des démonstrations d’ordre théorique en mathématiques.



J’ai rapidement regardé le lien que tu donnes.
Je n’ai pas compris quelles sont les parts de la computation informatique et de la résolution mathématique pure dans chacune des méthodes “Find intersection“ et “Test intersection“.

bon j'ai un peu regardé les réponses que vous m'avez apportées, je vous en remercie. Tout ça m'a l'air TRES mathématique et pas forcement de mon niveau. Je pense donc que je vais me contenter de gerer l'intersection des rectangles contenant les ellipses. cela minimisera deja beaucoup mon erreur.
Quelqu'un à t'il déja vu un sujet la dessus, je suis moi meme en train de cherché.


Merci en tout cas a tous ceux qui on répondu!