Journal question de math,

Posté par blackshack le 26 février 2003 à 22:13.

Étiquettes : aucune

fév.

2003

Considérons un repère à 2 dimensions, j'ai les coordonnées de 4 points, ceux ci formant les sommets d'un polygone - quadrilatères exclus- , mais de n'importe quelle forme - losange principalement pour ce que je veux faire. Comment savoir si un cinquième point se trouve dans le polygone ainsi formé.
Donc quel fonction pourrait me faire cela?
Merci d'avance

# Re: question de math,

Posté par pasBill pasGates le 26 février 2003 à 22:43. Évalué à 0.

Ben a premiere vue un algo qui marche serait :

- Tu prends les droites diagonales de ton polygone, tu mesures la distance du point a ces droites, avec ca tu trouve dans quel quadrant est le point (quand je dis quadrant, ca signifie les 4 aires definies par le trace de lignes diagonales infinies dans ton polygone).
- apres tu prends les 2 points de ton polygone qui definissent ce quadrant, tu tires une droite infinie entre eux, et tu mesures la distance du point a cette droite, selon que la valeur est negative ou positive, ton point sera dans le quadrant ou hors du quadrant.

Je sais pas si c'est l'algo optimal, et pour etre franc je doutes que ce soit optimal, mais a 1ere vue ca doit marcher.
- [^] # Re: question de math,
  
  Posté par blackshack le 26 février 2003 à 22:56. Évalué à 1.
  
  j'y ai pensé mais alors comment calculer la distance d'un point avec une droite pouvant être incliné. Je sais que je suis nul mais ca fait tellement longtemps que j'ai pas fait de math, il faut que je m'y remette (enfin de trigo dans ce cas là)
  - [^] # Re: question de math,
    
    Posté par feth le 27 février 2003 à 09:36. Évalué à 1.
    
    exception à traiter : la droite de type x=n.
    pour toute droite du type y=ax +b, il te suffit de savoir si le point est au dessus ou au dessous, donc calculer le y de la droite selon l'abcisse de ton point et comparer avec celui de ton point.
- [^] # Re: question de math,
  
  Posté par Edouard Gomez (site web personnel) le 26 février 2003 à 23:00. Évalué à 3.
  
  L'idée des diagonales est bonne, cependant le coup des quadrants et distances est pas utile.
  
  Suffit de faire un changement de repère passant de la base [centre(0,0), x(1,0), y(0,1)] à la base [centre("point croisement des diagonales(noté c par la suite)"), x("c-un sommet sur une premiere diagonale"), y("c-unsommet sur la seconde diagonale")]
  
  Si les coordonnées dans ce repère sont comprises dans les intervalles [-1,1] pour x et y, alors le point est à l'intérieur du polygone.
  
  PS: google un coup sur les repères barycentriques. Mon explication n'étant que l'illustration du passage au repère iso barycentrique.
  PPS: je partais du principe que ton polygone etait convexe.
# Re: question de math,

Posté par Ben le 26 février 2003 à 23:13. Évalué à 3.

sinon tu peux aller voir là http://perso.wanadoo.fr/maxence.delannoy/pt_poly.htm(...) ca a l'air assez convaincant.
pour voir s'il y a intersection, il suffit de calculer les equations de droite correspondant aux côtés de ton quadrilatère.
- [^] # Re: question de math,
  
  Posté par blackshack le 26 février 2003 à 23:33. Évalué à 1.
  
  ouais c pas con du tout. par contre j'ai un problème n'ayant que 4 points, donc les cotés m'étant donnée par 2 points, comment trouver la liste des points constituant le coté en question?
  - [^] # Re: question de math,
    
    Posté par redfish le 27 février 2003 à 18:38. Évalué à 1.
    
    tu as l'équation de la droite, pour toute valeur comprise entre l'abcisse du premier point et celle du deuxième, tu peux calculer l'ordonnée. Voila, tu as tous les points.
    
    PS : Tous est un bien grand mot, puisqu'il y en a une infinité ;)
  - [^] # Re: question de math,
    
    Posté par didbaba le 27 février 2003 à 21:22. Évalué à 1.
    
    k dans [0;1] tout point M de [AB] s'écrit M=kA+(1-k)B
# Re: question de math,

Posté par Vivi (site web personnel) le 26 février 2003 à 23:29. Évalué à 1.

si le polygone est convexe, tu peux faire un truc assez simple avec des produits vectoriels.
- [^] # Re: question de math,
  
  Posté par daggett le 26 février 2003 à 23:39. Évalué à 4.
  
  [ J'avais commencé à rediger ça, mais le temps que la deconnexion ADSL soit finie, y'avait deja pleins de réponses :) alors je le poste en supplément de ton indication un peu vague sur les produits vectoriels, je pense que ça pourrait lui servir :) ]
  
  Si ton polygone est convexe (ça n'est pas le cas général, mais si tu considere des losanges alors ça va) et si tu connais l'ordre de tes points A B C D, un algo simple consiste à partir du principe que ton 5eme point M est à l'intérieur du poly s'il est toujours "du même coté" des bords du poly (c'est à dire si on parcourt le bord du polygone, on verra toujours M à droite ou à gauche).
  
  Pour ça il faut utiliser le produit vectoriel, et comme je ne connais pas ton niveau en math, on va simplifier :)
  
  pour deux vecteurs en dimension 2 U={x1,y1} et V={x2,y2} le résultat qui nous interesse est le signe de (x1*y2 - x2*y1).
  
  (si le signe est positif, c'est que l'angle entre U et V et entre 0 et 180°, sinon c'est qu'il est entre 0 et -180°) (ou 'inverse si le repere n'est pas dans la convention mathématique, pas exemple les coordonnée utilisées par X-Window :p )
  
  Pour un polygone convexe, il suffit pour chaque sommet de faire cette opération entre vecteur qui le relie au sommet suivant, et le vecteur qui le relie au point testé. Si on a à chaque fois le meme signe, c'est que le point est à l'intérieur.
  
  tu vas donc comparer les signes du (x1*y2-x2*y1) correspondant à AB*AM, BC*BM, CD*CM et DA*DM.
  - [^] # Re: question de math,
    
    Posté par Vivi (site web personnel) le 02 mars 2003 à 21:49. Évalué à 1.
    
    oui c'était ça :)
# Re: question de math,

Posté par peyo (site web personnel) le 26 février 2003 à 23:30. Évalué à 3.

yop,

pour n'importe quel polygone (même percé)

pour savoir si un point est dedans, tracer une demi-droite à partir de ce point vers l'infini,

si elle coupe un nombre pair de fois la frontière du polygone, le point est dehors, sinon dedans

garanti
- [^] # Re: question de math,
  
  Posté par blackshack le 26 février 2003 à 23:38. Évalué à 1.
  
  c la meme solution que dans le lien que l'on m'a donné plus haut, donc cela doit être bien. Par contre même question comment obtenir la liste de pts constitutifs d'un coté du polygone, n'ayant que 2 pts me donnant les sommets de ce coté?
  - [^] # Re: question de math,
    
    Posté par peyo (site web personnel) le 26 février 2003 à 23:41. Évalué à 1.
    
    liste chainée,
    tu dev en quoi ?
- [^] # Re: question de math,
  
  Posté par Moby-Dik le 27 février 2003 à 00:47. Évalué à 4.
  
  C'est en effet la meilleure méthode. Surtout que pour optimiser on peut prendre une demi-droite horizontale ou verticale, au choix, ce qui allège énormément les calculs (pas de division, très peu de multiplications).
  
  Choisis une des quatre demi-droites possibles (vers le haut, le bas, la droite, la gauche). Mettons que tu prennes celle partant vers la droite. Pour chaque côté [AB], regarder s'il y a intersection revient alors à :
  
  - si A et B sont tous deux au-dessus de la droite, ou tous deux en-dessous, alors il n'y a pas intersection. Il suffit ici de calculer ((yB - yDroite) > 0) XOR (yA - yDroite) > 0). Le CPU est heureux.
  
  - sinon, il faut calculer l'intersection avec la droite. En posant et transformant l'inégalité (xIntersection > 0) tu te débarrasses du dénominateur, donc de la division. Tu te retrouves donc avec le calcul de quelques multiplications et additions.
  
  Tu refais la même chose pour tous les côtés (ici quatre, mais ça vaut pour n'importe quel polygone), ce qui permet de compter le nombre d'intersections et donc de répondre à ta question.
- [^] # Re: question de math,
  
  Posté par didbaba le 27 février 2003 à 12:58. Évalué à 1.
  Si le point est dedans que le polygone n'est pas convexe, il y a des cas ou la demi-droite peux couper un nombre paire de fois et pourtant M est à l'intérieur.
  
  M dedans, la demi droite "sort" par un segment, puis coupe le polygone en un sommet.
```
|\ 

|   \       /] A

|Mx  \/    |

|_______| 
```
  [MA) coupe deux fois et M est dedans...
  - [^] # Re: question de math,
    
    Posté par Moby-Dik le 27 février 2003 à 15:31. Évalué à 1.
    
    Si le point est dedans que le polygone n'est pas convexe, il y a des cas ou la demi-droite peux couper un nombre paire de fois et pourtant M est à l'intérieur.
    
    Ce n'est pas une question de convexité, c'est un cas limite où la demi-droite passe par un sommet du polygone. Mais du point de vue algorithmique, tu vas en fait détecter, selon les inégalités (strictes ou larges) que tu as choisies, soit un côté intersecté, soit trois côtés intersectés, donc bien un nombre impair.
    - [^] # Re: question de math,
      
      Posté par didbaba le 27 février 2003 à 21:34. Évalué à 1.
      
      La convéxité est un condition nécessaire pour que la régle énoncé précedemment soit vérifiée. De plus, un polygone convexe étant un ouvert étoilé en chacun de ses points, toute demi-droite d'origine M ne peut couper les bords du polygones qu'une seule fois.
      
      Donc je persiste à dire que si le polygone est convexe on a pas de cas limite.
      Dans les autres cas il faudra faire attention, et les galipettes algorithmiques ne change rien, l'énoncé de départ était incomplet.
  - [^] # Re: question de math,
    
    Posté par tuiu pol le 27 février 2003 à 18:39. Évalué à 1.
    
    Les sommets sont donnés, il suffit de verifier ce cas (est ce que des points resolvent l'equation de la demi-droite partant de M vers l'infini)
  - [^] # Re: question de math,
    
    Posté par peyo (site web personnel) le 27 février 2003 à 21:11. Évalué à 1.
    
    oui,
    
    il y a qqs cas particuliers en passant par les sommets, pour être sûr, tester plusieurs droites. de toute façon l'algo est rapide et marche sur des ploygones complexes. c'est le seul que je connaisse et qui donne un résultat juste sans partir dans du bricolage géométrique.
# Barycentres !

Posté par didbaba le 26 février 2003 à 23:50. Évalué à 4.

En supposant qu'on prenne l'enveloppe convexe de tes quatres point. Ton point M est à l'intérieur s'il est barycentre des 4 points, ceux-ci ayant des coefficient positif. Reste à trouver les quatres coefficient positifs.

En tout cas tout point M à l'intérieur de ABCD est sous la forme :
M=aA+bB+cC+dD
avec a,b,c, et d positif... et avec a+b+c+d != 0

On peut por plus de facilité supposé que a+b+c+d=1.

x_M=ax_A+bx_B+cx_C+dx_D
y_M=ay_A+by_B+cy_C+dy_D

Bon il y a assez d'équations pour trouver...

En gros faut savoir passer en coordonnées barycentriques, et après il y a plus qu'à regarder le signe des coordonnées de M.
# Re: question de math,

Posté par blackshack le 27 février 2003 à 14:36. Évalué à 1.

bon Je vous remercie tous de vos conseil, et est bien étudié toutes les propositions. Celle retenue, car la plus simple je trouve à mettre en pratique, et il me semnle une des plus rapide en temps de calcul, est celle utilisant des vecteurs, donc celle de vivi et dagette.
De plus elle me parait plus simple a la faire passer dans un espace à 3 dimensions et à lui permettre d' utiliser aussi des hexagones ou hoctogones en rajoutant simplement des vecteurs

Vivi et dagette on donc gagner une petite claque ;-).

Je précise qu'avant la mise en place de cette solution, je n'avais utiliser qu'un pis aller -je devais implémenter d'autres choses plus compliqués et urgente- qui était d'utiliser des rectangles, car plus simple comme mise en place du test de l'inclusion ou non d'un point dans un poligone. Bien sûr avec cette solution un certain nombre de points n'étaient pas pries en compte.
- [^] # Re: question de math,
  
  Posté par QS le 27 février 2003 à 17:08. Évalué à 1.
  
  j'ai ce lien (pas pour la solution mais pour l'implémentation): Numerical recipes http://www.library.cornell.edu/nr/nr_index.cgi(...)
  pour le C en pdf :
  http://www.library.cornell.edu/nr/bookcpdf.html(...)
  dis-moi si c'est utile.
  - [^] # Re: question de math,
    
    Posté par blackshack le 27 février 2003 à 17:47. Évalué à 1.
    
    disons que c'est surement tres bien, je ne peux en juger -si ce n'est le concept même du livre) mais je ne vois où cela pourrait/peut mettre utile pour l'instant.
    Si tu peux me le dire
    - [^] # Re: question de math,
      
      Posté par QS le 28 février 2003 à 10:39. Évalué à 1.
      
      ben, je me disais qu'à partir de la solution mathématique, ce bouquin peut aider à l'implémenter (le coder) efficacement. c'était juste une suggestion.

Suivre le flux des commentaires

Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.