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 ?
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é.
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
Comment avec les produits scalaires ?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
Shokin
Pardon, humilité, humour, hasard, tolérance, partage, curiosité et diversité => liberté et sérénité.
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 !
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.
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.
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é.
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.
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.
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.
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.
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.
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é.
Bonjour,
Voici un algorithme possible pour monter que I est inclus dans le triangle ABC :Avec les équations des droites, oui, c'est facile. Mais comment est-ce avec le produit scalaire ? le produit scalaire de quels vecteurs ?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.
- 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
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.
Sauf qu'évaluer ces angles n'est pas forcément très simple à faire analytiquement !
__
rvz
Et ça revient à calculer des produits scalaires:...
Cordialement.
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é.
D'accord, je me terre dans une grande cave...
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é.
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.
Bonsoir,
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
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,
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
Il s'agit bien d'angles orientés, et cela ne pose pas de problème (utilisation du produit vectoriel par exemple).
Je parlai de celui que j'ai plus ou moins décrit.
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.
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
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
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é ?
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.
