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

Intérieur d'un polygône



  1. #1
    Ravaner

    Intérieur d'un polygône


    ------

    Bjr à tous,
    Un pb apparemment simple : je dispose d'un polygône assez complexe ( étoile à branches multiples par ex ) dont je connais les coordonnées de chaque sommet ( 2D ). Par ailleurs j'ai un point P ( x, y ). Comment puis-je savoir, de façon analytique simple, si P est intérieur ou extérieur au polygône ?

    -----

  2. Publicité
  3. #2
    shokin

    Re : Intérieur d'un polygône

    De façon analytique, comment résoudre le problème si on a un triangle ?

    A partir de ce problème "simple" (avec le triangle), on pourra s'étendre vers des polygones convexes à n côtés.

    Puis à des polygones non convexes.

    Shokin
    Pardon, humilité, humour, hasard, tolérance, partage, curiosité et diversité => liberté et sérénité.

  4. #3
    rvz

    Re : Intérieur d'un polygône

    Salut !

    Le problème évoqué par Skokin est simple, puisqu'il suffit de faire les produits scalaires sur chaque coté et vérifier le signe, ce qui doit pas prendre trop longtemps analytiquement

    Après, pour un polygone convexe, c'est la même chose, mais pour un non convexe, c'est toute suite beaucoup plus moche. Tu peux faire la même chose, puis vérifier que c'est pas dans les parties embêtantes...
    Ce qui revient à rajouter des polygones convexes afin d'obtenir un gros polygone conveexe. C'est pas clair que ça peut se programmer facilement...
    __
    rvz

  5. #4
    shokin

    Re : Intérieur d'un polygône

    Citation Envoyé par rvz
    Le problème évoqué par Skokin est simple, puisqu'il suffit de faire les produits scalaires sur chaque coté et vérifier le signe, ce qui doit pas prendre trop longtemps analytiquement
    Comment avec les produits scalaires ?

    Shokin
    Pardon, humilité, humour, hasard, tolérance, partage, curiosité et diversité => liberté et sérénité.

  6. #5
    Ravaner

    Re : Intérieur d'un polygône

    Merci pour vos réponses.,Le pb est assez trivial avec un triangle, bien évidemment je travaille sur des polygônes non convexes et a priori c'est coton !

  7. A voir en vidéo sur Futura
  8. #6
    martini_bird

    Re : Intérieur d'un polygône

    Salut,

    je ne sais pas s'il y a plus simple que de considérer que ton polygone est la différence entre son enveloppe convexe (le plus petit polygone convexe qui contient ton polygone, facile à déterminer à partir des sommets) et des polygones à déterminer (c'est la partie plus difficile a priori).

    Cordialement.

  9. Publicité
  10. #7
    matthias

    Re : Intérieur d'un polygône

    Citation Envoyé par martini_bird
    je ne sais pas s'il y a plus simple que de considérer que ton polygone est la différence entre son enveloppe convexe (le plus petit polygone convexe qui contient ton polygone, facile à déterminer à partir des sommets) et des polygones à déterminer (c'est la partie plus difficile a priori).
    Pour un polygone en étoile, ça doit bien marcher. Dans le cas général la différence entre l'enveloppe convexe et le polygone peut donner un ou plusieurs polygones eux-même non convexes, ce qui donnerait une procédure récursive. Je me demande même si on ne pourrait pas trouver un polygone telle que la différence donne un polygone semblable au polygone de départ, auquel cas la récursivité ne prendrait pas fin.
    Sinon on peut toujours découper un polygone en polygones convexes (vu qu'on peut le découper en triangle). A mon avis la meilleure solution consiste à trouver un "bon" découpage de ce type. Il existe peut-être un algo pour obtenir un découpage optimal, je ne sais pas.

  11. #8
    shokin

    Re : Intérieur d'un polygône

    Est-ce qu'il y aurait des pistes possibles ?

    - par les angles des triangles formés par le point en question et chaque paire de sommets du polygone ?

    - par les centres de gravité de ces mêmes triangles ?

    Shokin
    Pardon, humilité, humour, hasard, tolérance, partage, curiosité et diversité => liberté et sérénité.

  12. #9
    matthias

    Re : Intérieur d'un polygône

    Tu compliques shokin. Une fois que tu as des polygones convexes, il suffit de montrer que le point est du bon côté de chaque droite passant par deux sommets adjacents. Ce qu'on peut faire facilement avec les équations des droites ou avec un produit scalaire.

  13. #10
    martini_bird

    Re : Intérieur d'un polygône

    Citation Envoyé par matthias
    Pour un polygone en étoile, ça doit bien marcher. Dans le cas général la différence entre l'enveloppe convexe et le polygone peut donner un ou plusieurs polygones eux-même non convexes, ce qui donnerait une procédure récursive. Je me demande même si on ne pourrait pas trouver un polygone telle que la différence donne un polygone semblable au polygone de départ, auquel cas la récursivité ne prendrait pas fin.
    Sinon on peut toujours découper un polygone en polygones convexes (vu qu'on peut le découper en triangle). A mon avis la meilleure solution consiste à trouver un "bon" découpage de ce type. Il existe peut-être un algo pour obtenir un découpage optimal, je ne sais pas.
    Oui en effet, je voulais dire la différence entre l'enveloppe convexe et des triangles à déterminer (le problème demeurant comment les déterminer).

    Cordialement.

  14. #11
    matthias

    Re : Intérieur d'un polygône

    Ce qui est facile à faire de manière bourrin, c'est de découper le polygone en triangles, sans même parler d'enveloppe convexe.
    Tu prends le sommet d'abscisse (ou d'ordonnée) min (ou max) et tu remarques que le triangle formé par ce sommet et les deux sommets adjacents est toujours dans l'intérieur du polygone. Tu enlèves le sommet en question, tu le remplaces par une arête joignant les deux sommets qui lui étaient adjacents et tu recommences.

  15. #12
    matthias

    Re : Intérieur d'un polygône

    On peut avoir des problèmes dans le cas de polygones dégénérés, genre arêtes qui se croisent, se superposent partiellement, arête qui passe par un troisième sommet, etc.
    Dans la plupart des cas ça doit se résoudre en prenant par exemple le sommet d'ordonnée minimale parmi les sommets d'abscisse minimale.

  16. Publicité
  17. #13
    matthias

    Re : Intérieur d'un polygône

    Autre précision, il se peut que tout le triangle ne soit pas dans l'intérieur du polygone, il faut d'abord vérifier qu'aucun autre sommet n'est à l'intérieur du triangle. Si il y en a un, il faut réétudier le découpage mais ça se fait relativement bien.
    Par contre c'est vraiment bourrin, moche et pas optimal du tout.

  18. #14
    shokin

    Re : Intérieur d'un polygône

    Citation Envoyé par matthias
    Tu compliques shokin. Une fois que tu as des polygones convexes, il suffit de montrer que le point est du bon côté de chaque droite passant par deux sommets adjacents. Ce qu'on peut faire facilement avec les équations des droites ou avec un produit scalaire.
    C'était juste pour savoir.

    Avec les équations des droites, oui, c'est facile. Mais comment est-ce avec le produit scalaire ? le produit scalaire de quels vecteurs ? peux-tu me donner un exemple ou un lien ?

    A priori, je pense que la méthode des produits scalaires est plus rapide que celle de l'équation des droites. Donc je crois bien que j'emploierai celle-ci (d'une fois que j'aurai démontré sa validité).

    Shokin
    Pardon, humilité, humour, hasard, tolérance, partage, curiosité et diversité => liberté et sérénité.

  19. #15
    Nemat

    Re : Intérieur d'un polygône

    Bonjour,

    Une fois que tu as des polygones convexes, il suffit de montrer que le point est du bon côté de chaque droite passant par deux sommets adjacents.
    Avec les équations des droites, oui, c'est facile. Mais comment est-ce avec le produit scalaire ? le produit scalaire de quels vecteurs ?
    Voici un algorithme possible pour monter que I est inclus dans le triangle ABC :
    - choisir un vecteur U perpendiculaire à BC (sens arbitraire)
    - calculer les produits scalaires de U avec successivement BI et BA et vérifier qu'ils sont de même signe
    - recommencer avec les deux autres côtés


    Cordialement

  20. #16
    invite986312212
    Invité

    Re : Intérieur d'un polygône

    pour moi la question de la convexité du polygone ne joue aucun rôle.

    soient x0,x1,...,xn les ommets (avec xn=x0) et soit y un point du plan. Alors la somme des angles (xi, y, x(i+1) ) est soit 0 soit 2pi selon que y est à l'extérieur ou à l'intérieur du polygone.

  21. #17
    rvz

    Re : Intérieur d'un polygône

    Sauf qu'évaluer ces angles n'est pas forcément très simple à faire analytiquement !

    __
    rvz

  22. #18
    martini_bird

    Re : Intérieur d'un polygône

    Citation Envoyé par rvz
    Sauf qu'évaluer ces angles n'est pas forcément très simple à faire analytiquement !

    __
    rvz
    Et ça revient à calculer des produits scalaires: ...

    Cordialement.

  23. Publicité
  24. #19
    invite986312212
    Invité

    Re : Intérieur d'un polygône

    Citation Envoyé par rvz
    Sauf qu'évaluer ces angles n'est pas forcément très simple à faire analytiquement !

    __
    rvz
    pourquoi? le produit scalaire donne le cosinus et le déterminant (produit vectoriel) donne le signe. en tout cas pas besoin de se soucier de la convexité.

  25. #20
    rvz

    Re : Intérieur d'un polygône

    D'accord, je me terre dans une grande cave...

  26. #21
    shokin

    Re : Intérieur d'un polygône

    Merci pour le truc, je file l'essayer, l'explorer...

    Shokin
    Pardon, humilité, humour, hasard, tolérance, partage, curiosité et diversité => liberté et sérénité.

  27. #22
    matthias

    Re : Intérieur d'un polygône

    Citation Envoyé par ambrosio
    soient x0,x1,...,xn les ommets (avec xn=x0) et soit y un point du plan. Alors la somme des angles (xi, y, x(i+1) ) est soit 0 soit 2pi selon que y est à l'extérieur ou à l'intérieur du polygone.
    Effectivement c'est plus simple

    Ceci-dit je regarderai quand-même comment découper un polygone en polygones convexes de manière plus simple. Mon algo d'hier est un peu pourri et il y a plein de cas à traiter.

  28. #23
    Nemat

    Re : Intérieur d'un polygône

    Bonsoir,

    Citation Envoyé par ambrosio
    pour moi la question de la convexité du polygone ne joue aucun rôle.

    soient x0,x1,...,xn les ommets (avec xn=x0) et soit y un point du plan. Alors la somme des angles (xi, y, x(i+1) ) est soit 0 soit 2pi selon que y est à l'extérieur ou à l'intérieur du polygone.
    Il y a quelque chose que je ne saisis pas.
    1) pour tracer un polygone j'utilise deux cercles concentriques (centre O, rayon R et r). Je choisis les sommets du polygone notés Sk et sk , situés sur ces deux cercles, repérés (en coordonnées polaires) par des angles, repérés depuis O, par les angles Enfin, pour tracer mon polygone je prend la succession de sommets : S1 - S2 - Sk-1 puis je poursuis sur l'autre cercle dans l'autre sens : sk-1 - sk-2 - s2 -s1 et je ferme.
    Depuis O, pourtant extérieur au cercle, la somme des angles, telle qu'elle est calculée avec la proposition de Martini-Bird, vaut pratiquement

    2) A présent je construis un polygone selon le même principe, mais avec des spirales emboîtées au lieu de cercles. La somme des angles peut alors être rendue arbitrairement aussi grande qu'on le veut, que le point étudié soit extérieur ou d'ailleurs intérieur

    Il me semble à moi que la question de la convexité est fondamentale. Ou alors il faut trouver le moyen de mesurer des angles orientés.

    Cordialement,

  29. #24
    Nemat

    Re : Intérieur d'un polygône

    Citation Envoyé par matthias
    Mon algo d'hier est un peu pourri et il y a plein de cas à traiter.
    Matthias,

    L'algorithme dont tu parles est-il celui que j'ai posté en début de journée (appartenance à un triangle) ou celui qui consiste à classer les sommets selon les valeurs croissantes (ou décroissantes) d'une des coordonnées ?

    Sur le premier d'accord il faut prévoir les cas ou l'un et/ou l'autre des produits scalaires vaut 0 : un peu long mais on doit quand même pouvoir y arriver

    Sur le second je ne vois pas trop : le cas où à l'intérieur du triangle qu'on a isolé est présent un autre sommet ? Il me semble qu'on peut alors substituer un des triangles internes ainsi trouvés ?

    Cordialement

  30. Publicité
  31. #25
    matthias

    Re : Intérieur d'un polygône

    Citation Envoyé par Nemat
    Ou alors il faut trouver le moyen de mesurer des angles orientés.
    Il s'agit bien d'angles orientés, et cela ne pose pas de problème (utilisation du produit vectoriel par exemple).

  32. #26
    matthias

    Re : Intérieur d'un polygône

    Citation Envoyé par Nemat
    L'algorithme dont tu parles est-il celui que j'ai posté en début de journée (appartenance à un triangle) ou celui qui consiste à classer les sommets selon les valeurs croissantes (ou décroissantes) d'une des coordonnées ?
    Je parlai de celui que j'ai plus ou moins décrit.

    Citation Envoyé par Nemat
    Sur le second je ne vois pas trop : le cas où à l'intérieur du triangle qu'on a isolé est présent un autre sommet ? Il me semble qu'on peut alors substituer un des triangles internes ainsi trouvés ?
    Oui mais c'est quand même pénible.
    De toute façon, su on veut juste savoir si un point est à l'intérieur du polygone, la solution d'ambrosio est bien meilleure. Si on veut découper un polygone en polygones convexes, je pense qu'il y a bien plus simple.

  33. #27
    Nemat

    Re : Intérieur d'un polygône

    Citation Envoyé par matthias
    De toute façon, su on veut juste savoir si un point est à l'intérieur du polygone, la solution d'ambrosio est bien meilleure. Si on veut découper un polygone en polygones convexes, je pense qu'il y a bien plus simple.
    Bonsoir,

    Il me semble qu'il faut définir ce qu'on appelle "simple". Si c'est un programme tel que, si N est le nombre de sommets, le temps de calcul est de l'ordre de avec p le plus petit possible, ou bien si on veut un algorithme executable "à la main"

    Personnellement je commencerai à calculer pour chaque côté le nombre de sommets situés de part et d'autre de cette direction. Puis je m'intéresserais à l'ensemble des côtés où les N-2 sommets sont d'un même côté (propriété P1). Pour éviter de refaire des traitements je stockerais l'ensemble les résultats dans une matrice de N lignes (1 par côté du polygone) et N colonnes (1 par sommet), avec un codage du type (manquant = sommet appartenant au côté étudié, +p = le sommet fait partie du groupe majoritaire de p sommets situés d'un même côté et -q : le sommet fait partie d'un groupe de q sommets qui lui est minoritaire)
    a) Cas où le polygone de départ est convexe
    L'algorithme m'oblige à faire N(N-2) opérations, alors que sauf erreur il en suffit de N(N-2)/2 dans le cas où le polygone de départ est effectivement convexe (je pense qu'il suffit de tester successivement la propriété P pour S1S2, puis S3S4 etc. Mais si c'est le cas rien ne m'empêche d'appliquer l'algorithme ci dessus en commençant de la même façon)
    b) Deuxième phase
    A ce stade j'ai un résultat indirect : si je fais la réunion de tous les côtés vérifiant la propriété P je peux remarquer que je reconstitue déjà une partie de l'enveloppe convexe. Mais pour passer à la décomposition il me semble qu'il faut utiliser une autre indication : la liste des sommets qui figurent le plus souvent dans la liste des points minoritaires. En partant d'une part d'un ensemble de côtés contigus vérifiant la propriété P, puis en éliminant les colonnes (sommets) où figurent souvent un nombre négatif, je pense qu'on devrait arriver à un ensemble relativement faible de polygones

    Cet algorithme est libre de tous droits ! mais je signale aux personnes intéressées qu'il faut encore affiner le calcul dans le cas où trois sommets non adjacents sont alignés, et de plus qu'il n'a jamais été testé

    Cordialement

  34. #28
    Ravaner

    Re : Intérieur d'un polygône

    Merci à tous pour vos réponses. Je retiens la méthode du calcul de la somme des angles de visée. Cela fonctionne très finement et très simplement pourquoi n'y ai-je pas pensé ?

  35. #29
    sebsheep

    Re : Intérieur d'un polygône

    Une autre méthode que je n'ai pas vu sur ce fil :
    A partir de ton point P(x,y), tu traces une demi-droite verticale (vers le haut ou vers le bas, peu importe).
    Et ensuite, tu testes combien de fois la droite coupe chacun des côtés.

    Si elle coupe 0 fois, c'est que le point n'est pas dedans.
    Si elle coupe 1 seule fois, c'est que le point est dedans.
    Si elle coupe 2 fois, c'est que le point n'est pas dedans.
    Etc ... la droite coupe un nombre impair de fois si, et seulement, si le point est dans l'intérieur du convexe.

    Ca me semble plus rapide que toutes ces multiplications avec le produit scalaire.

Sur le même thème :

Discussions similaires

  1. Perpendiculaire aux cotés d'un polygone
    Par defluc dans le forum Mathématiques du collège et du lycée
    Réponses: 2
    Dernier message: 08/12/2007, 08h17
  2. aire et CG d'un polygone irregulier
    Par ABN84 dans le forum Mathématiques du supérieur
    Réponses: 4
    Dernier message: 21/01/2007, 13h39
  3. Somme des angles d'un polygone
    Par kNz dans le forum Mathématiques du collège et du lycée
    Réponses: 5
    Dernier message: 11/11/2006, 19h12
  4. Caracterisation de la forme d'un polygone
    Par sunshine dans le forum Mathématiques du supérieur
    Réponses: 0
    Dernier message: 12/07/2006, 21h05
  5. Distance la + grande d'un polygone variable à 3 branches
    Par NicoLasticot dans le forum Mathématiques du supérieur
    Réponses: 4
    Dernier message: 22/05/2006, 09h21