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

Algorithmes et structures de données Discussion :

Zone d'exclusion polygonale


Sujet :

Algorithmes et structures de données

Vue hybride

Message précédent Message précédent   Message suivant Message suivant
  1. #1
    Membre Expert Avatar de Nemerle
    Inscrit en
    Octobre 2003
    Messages
    1 106
    Détails du profil
    Informations personnelles :
    Âge : 55

    Informations forums :
    Inscription : Octobre 2003
    Messages : 1 106
    Par défaut Zone d'exclusion polygonale
    Le problème est le suivant: soit un polygone P quelconque du plan (i.e. pas forcément convexe). On recherche l'ensemble des points M vérifiant d(M,P)<D, où D est une constante.

    L'idée est de donner la séquence des sommets du polygone définissant cette nouvelle zone.

    J'ai construit une solution à ce problème, mais je voulais avoir votre avis...

  2. #2
    Modérateur

    Homme Profil pro
    Ingénieur en calculs scientifiques
    Inscrit en
    Août 2007
    Messages
    4 639
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Royaume-Uni

    Informations professionnelles :
    Activité : Ingénieur en calculs scientifiques

    Informations forums :
    Inscription : Août 2007
    Messages : 4 639
    Par défaut
    Salut,

    La distance d'un point par rapport à un polygone, c'est bien la plus petite distance entre ce point et chacun des points du polygone?

    Tu dis que tu obtiens un polygone, mais géométriquement, certains côtés sont des arcs de cercle. Sinon pour obtenir les sommets, il suffit de projeter les sommets du polygone initial sur des parallèles aux côtés de ce polygone pour des côtés adjacent avec un angle extérieur supérieur à 180. Pour des côtés adjacent avec un angle inférieur à 180, c'est l'intersection des parallèles.
    non?

    Je ne sais pas si j'ai été très clair, j'essaierai de faire un schéma si j'ai un peu de temps.
    Pour une bonne utilisation des balises code c'est ici!
    Petit guide du voyageur MATLABien : Le forum La faq Les tutoriels Les sources


    La nature est un livre écrit en langage mathématique. Galilée.

  3. #3
    Membre Expert Avatar de Nemerle
    Inscrit en
    Octobre 2003
    Messages
    1 106
    Détails du profil
    Informations personnelles :
    Âge : 55

    Informations forums :
    Inscription : Octobre 2003
    Messages : 1 106
    Par défaut
    Bonne réponse, ce n'est pas un polygone c'est une chaine de segments et de portions de cercle!

    Un petit exemple ci-dessous...


  4. #4
    Modérateur

    Homme Profil pro
    Ingénieur en calculs scientifiques
    Inscrit en
    Août 2007
    Messages
    4 639
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Royaume-Uni

    Informations professionnelles :
    Activité : Ingénieur en calculs scientifiques

    Informations forums :
    Inscription : Août 2007
    Messages : 4 639
    Par défaut
    J'ai gagné, alors? Et j'ai gagné quoi?
    Pour une bonne utilisation des balises code c'est ici!
    Petit guide du voyageur MATLABien : Le forum La faq Les tutoriels Les sources


    La nature est un livre écrit en langage mathématique. Galilée.

  5. #5
    Invité(e)
    Invité(e)
    Par défaut
    Bonjour,

    Je dirais que ça ressemble beaucoup à une dilatation non ?

  6. #6
    Membre Expert Avatar de Nemerle
    Inscrit en
    Octobre 2003
    Messages
    1 106
    Détails du profil
    Informations personnelles :
    Âge : 55

    Informations forums :
    Inscription : Octobre 2003
    Messages : 1 106
    Par défaut
    Citation Envoyé par magelan Voir le message
    J'ai gagné, alors? Et j'ai gagné quoi?
    nan, t'as pas gagné, ta "solution" est un peu légère... ou disons partielle

  7. #7
    Modérateur

    Homme Profil pro
    Ingénieur en calculs scientifiques
    Inscrit en
    Août 2007
    Messages
    4 639
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Royaume-Uni

    Informations professionnelles :
    Activité : Ingénieur en calculs scientifiques

    Informations forums :
    Inscription : Août 2007
    Messages : 4 639
    Par défaut
    Ah zut!

    C'est vrai que avec un papier et un crayon, c'est facile mais l'implémentation est plus délicate...

    Une idée mais je ne l'ai pas vérifié :

    On trace l'ensemble des segment parallèle aux côtés du polygone : on obtient un ensemble de point. On calcule l'enveloppe convexe de cet ensemble de points. cela devrait permettre d'éliminer l'ensemble des segments qui n'appartiennent pas au contour final. Dans cette enveloppe convexe, on retire les segments qui ne sont pas des segments parallèles aux cotés du polygone initial et on complète le contour avec les arcs de cercle en parcourant les segments dans un sens donné. Si le cercle possède une intersection avec le segment suivant, on continue, sinon il faut un autre arc de cercle. Et ainsi de suite jusqu'au point initial.

    Et ta solution, c'est quoi?
    Pour une bonne utilisation des balises code c'est ici!
    Petit guide du voyageur MATLABien : Le forum La faq Les tutoriels Les sources


    La nature est un livre écrit en langage mathématique. Galilée.

  8. #8
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 52
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Par défaut
    Citation Envoyé par Nemerle Voir le message
    Le problème est le suivant: soit un polygone P quelconque du plan (i.e. pas forcément convexe). On recherche l'ensemble des points M vérifiant d(M,P)<D, où D est une constante.

    L'idée est de donner la séquence des sommets du polygone définissant cette nouvelle zone.

    J'ai construit une solution à ce problème, mais je voulais avoir votre avis...
    La somme de Minkowski entre P et un disque de rayon D ?
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  9. #9
    Expert confirmé Avatar de Graffito
    Profil pro
    Inscrit en
    Janvier 2006
    Messages
    5 993
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Janvier 2006
    Messages : 5 993
    Par défaut
    J'ai implémenté un algo pour trouver l'envellope d'un polygone de forme quelconque, mais l'envellope résultante n'est qu'approchée en fonction d'une précision fournie en paramètre.

  10. #10
    Membre Expert Avatar de Nemerle
    Inscrit en
    Octobre 2003
    Messages
    1 106
    Détails du profil
    Informations personnelles :
    Âge : 55

    Informations forums :
    Inscription : Octobre 2003
    Messages : 1 106
    Par défaut
    Ok, ci-dessous une solution. On approxime polygonalement un arc de cercle par 3 points, pour simplifier. Sautez le point (b) en 1ière lecture, cas d'exception.


    Soit P1…Pn les sommets du polygones, et n(i,i+1) la normale extérieure unitaire au coté PiPi+1. Soit Ai le segment [P(i)+D* n(i,i+1),P(i+1)+D n(i,i+1)], i.e « PiPi+1 décalé de D ». On dira que Ai est un segment décalé. Soit Ri le rectangle défini par Ai et PiPi+1. Enfin, soit Ci le cercle de centre Pi et de rayon D, et Di son disque associé. On va constuire la séquence [W]=W1…Wq en ordre trigo des sommets définissant la zone d’exclusion :

    a. On recherche un i tel que l’intersection de Ai avec X\{Ri} ne soit pas tout Ai.
    b. Si le terrain n’est pas « une petite étoile » (a) est toujours vérifié. Si ce n’est pas le cas, on prendra i tel que :
    i. le centre de Ci a sa coordonnée en x minimale
    ii. on trouvera j tel que le centre de Cj, vu comme un sommet du parc, a son angle > à 180°, et est le plus proche du centre de Ci avec de plus Ci inter Cj non vide.

    c. Une fois le i de (a) trouvé :

    • le complémentaire de l’intersection de Ai avec X\{Ri} est un segment {A,B}=[Ai1+x(Ai2-Ai1), Ai1+y(Ai2-Ai1)] avec 0<=x<y<=1. De cette façon, le « sens » A->B reste dans l’ordre trigonométrique. Rq : on a noté {A,B}, car le segment a au moins une extrémité ouverte.
    • A est le 1ier point de [W], et B est le second.
    • Par construction, il existe au moins un objet Y de X qui contienne B.
    • S’il n’existe qu’un tel Y, on le sélectionne.
    • S’il en existe plus d’un (oh malheur…), notons X’ cet ensemble d’objets.

    • soit D la droite de sommets les points Ai1+n(i,i+1)/10 et Ai2+n(i,i+1)/10. C’est donc la droite contenant le segment « Ai translaté du dixième de sa normale ».
    • Pour chaque Y de X, soit éventuellement Q=Q(Y) le point d’intersection de Y avec D qui minimise d(Q,A). Si Q existe, on vérifie que Y appartient à X’. Si oui, Q est valide.
    • Pour chaque Q valide, on calcule le produit scalaire BQ.BA
    • On choisit l’objet Y tel que Q(Y) maximise ce produit scalaire. Un tel Y est UNIQUE.
    • S’il n’existe aucun point d’intersection avec D, alors il existe dans X’ un unique segment décalé : on le sélectionne.
    • Alors soit Y est un rectangle Rj, soit c’est un disque Dj. La 1ière passe de l’algo est finie. On sélectionne Z=Aj ou Cj en fonction de ce qu’est Y.

    d. A partir de Z, on détermine alors le plus grand segment ou arc de cercle {B,B’} issu de B qui ne coupe pas X\{Y} :

    • si Z est un segment, on ajoute B’ a la liste
    • si Z est un cercle de centre c, on ajoute 1.025*(cB+cB’)/2 puis B’.

    On réapplique alors (c) pour obtenir un nouvel objet Z.
    e. On réitère alors (d) jusqu’à ce que le point B’ soit égal à A.

Discussions similaires

  1. zone cliquable polygonale avec Fireworks
    Par vidole dans le forum Outils
    Réponses: 0
    Dernier message: 05/01/2013, 20h43
  2. Changement de couleur d'une zone polygonale
    Par Trunks dans le forum Balisage (X)HTML et validation W3C
    Réponses: 1
    Dernier message: 06/12/2005, 01h07
  3. Exclusion de caractere dans une zone de texte
    Par martsigo dans le forum Access
    Réponses: 7
    Dernier message: 23/08/2005, 20h03
  4. [VB6] Zone de liste modifiable basée sur un champ
    Par pepper dans le forum VB 6 et antérieur
    Réponses: 13
    Dernier message: 27/11/2002, 13h41
  5. Réponses: 17
    Dernier message: 17/10/2002, 20h06

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