Répondre à la discussion
Affichage des résultats 1 à 13 sur 13

Découpage d'un N-gon concave en polygones convexes simples



  1. #1
    Earthwormjim

    Découpage d'un N-gon concave en polygones convexes simples


    ------

    Bonjour à tous !

    Je suis à la recherche d'une solution sur un problème épineux : je souhaite décomposer un polygone concave à N cotés en une série de polygones convexes "simple" comme des quadrangles (rectangles ou trapèzes) des triangles ou des cercles...

    Voici un exemple de ce que souhaiterais obtenir :


    Merci d'avance pour votre aide

    -----

  2. Publicité
  3. #2
    Soliman

    Re : Découpage d'un N-gon concave en polygones convexes simples

    hi hi, je ne pourrais malheureusement pas t'aider mais j'aimerai vraiment satisfaire ma curiosité : à quoi cela sert-il concrètement ?

    Merci,
    Sami
    les fleurs sont multiples mais l'eau est unique... (sage)

  4. #3
    Earthwormjim

    Re : Découpage d'un N-gon concave en polygones convexes simples

    Je suis en train d'améliorer un script que j'ai fais pour un logiciel 3D.

    Ce script permet de dupliquer des objets 3D sur chaque polygones d'un autre objet, en conformant chaque copie à la forme du polygone servant de support.

    Pour le moment mon script ne gère que les quadrangles et les triangles, car il est beaucoup plus difficile de faire des interpolations sur d'autres polygones...

    C'est pourquoi je cherche un moyen de convertir automatiquement n'importe quel type de polygone en quadrangles ou en triangles, le cas des cercles pouvant être géré à part je pense.

    pour info, mon script se trouve ici : http://earthwormjim.free.fr/lscript/...ble/index.html


    Je cherche aussi une méthode pour placer aléatoirement un polygone de forme quelconque, à l'intérieur d'un autre polygone de forme quelconque et pouvant aussi avoir des trous.
    Mais bon, ça sera pour plus tard

    Je précise que pour tout ça je bosse presque entièrement en 2D pour simplifier les calculs.

    Je n'ai pas forcément besoin d'avoir tout un exposé mathématique, je suis plutot à la recherche d'une marche à suivre, ce découpage se faisant necéssairement en plusieurs étapes pour couvrir tous les cas.
    Dernière modification par Earthwormjim ; 02/09/2006 à 22h26.

  5. #4
    invite986312212
    Invité

    Re : Découpage d'un N-gon concave en polygones convexes simples

    tu peux peut-être traiter ce problème récursivement. Cela revient alors à trouver une diagonale incluse dans l'intérieur de ton polygone. J'ai l'impression qu'il en existe toujours une ayant comme sommet un sommet arbitraire du polygone (mais je ne sais pas le montrer). On doit pouvoir la trouver en triant les sommets restants selon l'angle que forme la diagonale avec une direction fixée. Il faut identifer un segment de la suite des sommets du polygone... (à compléter)

  6. A voir en vidéo sur Futura
  7. #5
    Earthwormjim

    Re : Découpage d'un N-gon concave en polygones convexes simples

    J'aurais peut etre du envoyer une autre image, sur celle-ci effectivement, pas mal de sommets se trouvent alignés, mais ça ne sera pas forcément toujours le cas

    Je bosse déjà sur deux fonctions récursives pour dépioter tout ça : un pour relier directement tous les sommets qui peuvent l'être et une autre pour ajouter des coupure entre un sommet et un milieu segment, ça marche pas pour tous les cas, mais c'est un bon début je pense.

    Je posterais bientôt une description de tout ça, c'est pas encore tout à fait au point...

  8. #6
    skydancer

    Re : Découpage d'un N-gon concave en polygones convexes simples

    Tu pourrais découper ton terrain en triangle. Cette méthode est simple et un algorithme de triangulation (Delaunay) est facilement implementable. Pour autant que je sache c'est comme ça que c'est réalisé dans certain jeu video pour seletionner uniquement les parties de terrain visible à partir d'un point, ce qui empeche l'affichage des parties cachés..

  9. Publicité
  10. #7
    Earthwormjim

    Re : Découpage d'un N-gon concave en polygones convexes simples

    Ouep, mais non...

    Je veux avoir le plus possible de quadrangles qui soient le plus proche possible de rectangles ou de carrés, donc exit les triangles... moins il seront nombreux et mieux ce sera.

    Merci quand même pour l'idée

  11. #8
    skydancer

    Re : Découpage d'un N-gon concave en polygones convexes simples

    Peut être que tu peux reflechir à une strategie pour fusionner les triangles de maniere à obtenir des polygones.

    Une autre approche serait une partition de Voronoi qui a la bonne propriété de fournir des polygones convexes. Mais la il faut trouver une maniere de définir les points à partir desquelles on calcule cette partition.

  12. #9
    Earthwormjim

    Re : Découpage d'un N-gon concave en polygones convexes simples

    J'ai déjà testé la triangulation, le problème c'est que c'est totalement imprévisible et les triangles résultants ne permettent pas toujours de les refusionner deux par deux pour retrouver des quadrangles corrects, du moins, pour l'utilisation que je veux en faire apres...

  13. #10
    invite7863222222222
    Invité

    Re : Découpage d'un N-gon concave en polygones convexes simples

    Moi je partirai sur une solution consistant à :
    1. déterminer les équations de toutes les droites
    2. calculer les points d'intersection pour toutes les droites deux à deux
    3. (incomplet) à "remplir" les segments entre les deux points à condition que ce segment n'est pas coupé par un autre éventuel prolongement

    La condition 3 n'est pas complète, il faut trouver une condition qui permette de déterminer dans quel cas exactement "remplir" entre les points d'intersection.

  14. #11
    Earthwormjim

    Re : Découpage d'un N-gon concave en polygones convexes simples

    hum ouep, je fais déjà à peu près un truc dans ce style

    pour le moment, je commence par relier tous les points qui peuvent l'être :

    1) je fais une boucle sur tous les segments
    2) dans cette boucle je fais une autre boucle sur tous les points (sauf ceux du segment en cours)
    3) je vérifie si le point est dans le prolongement du segement en cours
    4) si oui, je vérifie que la liaision entre ce point et l'extrémité du segement ne coupe pas un autre bord et si cette coupure se trouve bien à l'intérieur du polygone
    5) si tous les tests sont ok, alors je valide la coupure, j'obtiens donc deux polygones et je lance récursivement la même fonction sur ces deux polygones

    Sinon, je passe au point suivant

    6) Une fois que je suis passé par tous les points, je continue la boucle sur les bords, etc...

    après ça, il me reste déjà beaucoup moins de polygones tordus

    ensuite, j'ai un début de fonction qui fait aussi une boucle sur tous les bords en les considérant comme des droites infinies, là je teste la coupure avec tous les autres bords, si j'en trouve une je m'assure que c'est bien le bords plus proche qui est coupé et que la coupure reste bien dans le polygone
    si c'est le cas, je coupe, et je continue récursivement sur les deux polygones obtenus...

    l'idée est là, mais j'ai encore des erreurs par moment sur cette fonction.


    vous en pensez quoi ?

  15. #12
    invite7863222222222
    Invité

    Re : Découpage d'un N-gon concave en polygones convexes simples

    Déjà à bien y mieux regarder je trouve qu'il y a plusieurs facons de découper la fiirre déjà faudrait trouver une expression de la loi de découpage qui te donne qu'un seu découpage sinon informatiquement tu rsique de ne pas pouvoir y arriver.

  16. Publicité
  17. #13
    Earthwormjim

    Re : Découpage d'un N-gon concave en polygones convexes simples

    je ne pense pas que ceci soit un réel problème :

    Il y a bien sur grand nombre de possibilités pour découper le polygone, mais j'essaye d'aller au plus simple et/ou au plus rapide

    pour le moment, je garde le premier résultat valide pour chaque opération, même si visuellement, ce n'est pas forcément le plus avantageux, je ferais cette optimisation par la suite.

    par exemple, lorsque je fais mes découpes au lieu de m'arreter à la première coupure valide, je pourrais stocker le résultat et continuer la boucle jusqu'à la fin, et seulement là, conserver le résultat donnant la coupure la plus courte, (ou s'il y en a plusieurs de longueurs égales, en choisir une aléatoirement parmi celles-ci)

    Ainsi, j'orienterais le résultat afin de limiter le nombre de polygones rectangulaires de formes allongées, au détriment de la vitesse bien sur...

    enfin, je pense...

Discussions similaires

  1. DM polygônes MPSI
    Par Erin28 dans le forum Mathématiques du supérieur
    Réponses: 1
    Dernier message: 02/11/2007, 16h16
  2. concave
    Par dim756 dans le forum Mathématiques du supérieur
    Réponses: 2
    Dernier message: 17/10/2007, 06h51
  3. Espaces convexes
    Par haraelendil dans le forum Mathématiques du supérieur
    Réponses: 10
    Dernier message: 06/12/2006, 17h42
  4. découpage aléatoire d'un intervalle
    Par robert et ses amis dans le forum Mathématiques du supérieur
    Réponses: 17
    Dernier message: 24/10/2006, 16h05
  5. constante de polygones réguliers
    Par lany dans le forum Mathématiques du collège et du lycée
    Réponses: 30
    Dernier message: 15/10/2006, 18h05