IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Python Discussion :

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


Sujet :

Python

  1. #1
    Futur Membre du Club
    Profil pro
    Inscrit en
    Avril 2010
    Messages
    12
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Avril 2010
    Messages : 12
    Points : 7
    Points
    7
    Par défaut 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.

  2. #2
    Rédacteur
    Avatar de Zavonen
    Profil pro
    Inscrit en
    Novembre 2006
    Messages
    1 772
    Détails du profil
    Informations personnelles :
    Âge : 76
    Localisation : France

    Informations forums :
    Inscription : Novembre 2006
    Messages : 1 772
    Points : 1 913
    Points
    1 913
    Par défaut
    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/
    Ce qu'on trouve est plus important que ce qu'on cherche.
    Maths de base pour les nuls (et les autres...)

  3. #3
    Membre extrêmement actif
    Profil pro
    Inscrit en
    Janvier 2007
    Messages
    1 418
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Janvier 2007
    Messages : 1 418
    Points : 1 658
    Points
    1 658
    Par défaut
    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.

  4. #4
    Rédacteur
    Avatar de Zavonen
    Profil pro
    Inscrit en
    Novembre 2006
    Messages
    1 772
    Détails du profil
    Informations personnelles :
    Âge : 76
    Localisation : France

    Informations forums :
    Inscription : Novembre 2006
    Messages : 1 772
    Points : 1 913
    Points
    1 913
    Par défaut
    @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.
    Ce qu'on trouve est plus important que ce qu'on cherche.
    Maths de base pour les nuls (et les autres...)

  5. #5
    Membre extrêmement actif
    Profil pro
    Inscrit en
    Janvier 2007
    Messages
    1 418
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Janvier 2007
    Messages : 1 418
    Points : 1 658
    Points
    1 658
    Par défaut
    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 !

  6. #6
    Rédacteur
    Avatar de Zavonen
    Profil pro
    Inscrit en
    Novembre 2006
    Messages
    1 772
    Détails du profil
    Informations personnelles :
    Âge : 76
    Localisation : France

    Informations forums :
    Inscription : Novembre 2006
    Messages : 1 772
    Points : 1 913
    Points
    1 913
    Par défaut
    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
    Ce qu'on trouve est plus important que ce qu'on cherche.
    Maths de base pour les nuls (et les autres...)

  7. #7
    Membre extrêmement actif
    Profil pro
    Inscrit en
    Janvier 2007
    Messages
    1 418
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Janvier 2007
    Messages : 1 418
    Points : 1 658
    Points
    1 658
    Par défaut
    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“.

  8. #8
    Futur Membre du Club
    Profil pro
    Inscrit en
    Avril 2010
    Messages
    12
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Avril 2010
    Messages : 12
    Points : 7
    Points
    7
    Par défaut
    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!

Discussions similaires

  1. Intersection entre segment et cercle
    Par chadliii dans le forum Mathématiques
    Réponses: 15
    Dernier message: 03/10/2019, 19h52
  2. Gérer une collection d'objets
    Par yttrium dans le forum VB 6 et antérieur
    Réponses: 3
    Dernier message: 22/10/2007, 10h43
  3. Réponses: 1
    Dernier message: 10/04/2007, 16h25
  4. Réponses: 4
    Dernier message: 20/08/2006, 17h20
  5. Réponses: 9
    Dernier message: 30/03/2006, 21h16

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo