Inscription / Connexion Nouveau Sujet
Niveau algorithmique
Partager :

Formules d'appartenance d'un point à une surface simple

Posté par
slay_mithos
25-03-10 à 19:45

Bonjour,

Je ne suis pas certain de poster au bon endroit, mais j'ai eu il y a quelques jours le problème suivant, et mes derniers cours de maths remontant à la terminale S il y a plus de 4 ans, je ne sais pas trop où chercher.


On a un hexagone régulier , dont je connais les coordonnées dans le plan des 6 points.

On a un point P que l'on pourra qualifier d'aléatoire dans le sens où il peut se trouver n'importe où dans le plan.

On cherche à déterminer si le point est compris dans la surface interne de notre hexagone.

On appellera les points A, B, C, D, E et F en partant du sommet en "haut" et en tournant dans le sens trigonométrique.



J'avoue ne pas trouver comment faire, j'ai donc décomposé mon hexagone en deux triangles et un rectangle.

Je compare donc les coordonnées pour le rectangle sans difficulté, mais je suis coincé pour les triangles, bien que je sois certain que la solution soit simple.


Je tiens à ajouter que je ne cherche pas forcément une formule, sachant que le but est simplement de trouver si le pointeur de la souris est dans la figure dans un programme informatique.

Notez aussi que j'ai tendance à m'embrouiller:
P(Xp, Yp)
B(x1, y1)
A(x2, y2)

(ne vous étonnez pas du -12/23, il est du à un axe des Y inversé par rapport à l'axe mathématique)
Ma droite passant par A et B a pour équation y=(-12/23) * x + b
on obtient donc b=12/23 * x + y
ce qui donne au final y=-12/23 * x + 12/23*x+y (oui, je sais, ça donne y=y, mais b changeant deux fois par hexagone, je ne peux pas me permettre de faire un calcul plus de 800 fois simplement pour b)

une des conditions d'appartenance du point à ma figure serait donc que pour un Xp donné, Yp soit inférieur à l'équation de la droite, mais je ne sais pas trop que remplacer pour pouvoir faire le calcul sans tomber sur Yp<Yp.

Je sais que je ne suis pas très clair, mais j'apprécierais toute l'aide apportée à la résolution de ce problème.
merci d'avance.

Posté par
patrice rabiller
re : Formules d'appartenance d'un point à une surface simple 25-03-10 à 20:25

Bonjour,

Une piste possible :

On désigne par O le centre de l'hexagone ABCDEF.
Chacun des 6 côtés de l'hexagone est un segment de droite.
Notons ax+by+c=0 l'équation d'une droite contenant un des côtés de l'hexagone.
Les coordonnées du point O vérifient soit ax+by+c>0 soit ax+by+c<0. Pour que le point M quelconque soit à l'intérieur de l'hexagone, il faut que ses coordonnées vérifient la même inéquation que celle vérifiée par O. Et ceci pour chacune des 6 droites ...

Posté par
pgeod
re : Formules d'appartenance d'un point à une surface simple 27-03-10 à 08:48

En algorithmie, pour savoir si un point M est intérieur à un triangle ABC,
on peut procéder par calcul l'aire algébrique en utilisant les coordonnées.

on calcule Aire(ABM) --> si Aire(ABM) est de signe différent Aire(ABC) => M est à l'extérieur.
A faire pour les trois côtés du triangle, sauf si on peut conclure avant.

...

Posté par
pgeod
re : Formules d'appartenance d'un point à une surface simple 27-03-10 à 09:09

pour compléter..

s'agissant d'un hexagone régulier, on pourrait déjà avoir un test simple
sur la distance de M à O (centre de l'exagone) que l'on peut comparer
au rayon du cercle inscrit et au rayon du cercle circonscrit à l'hexagone.

Ensuite seulement, on passe aux tests de superficie par rapport aux 6 côtés,
pour traiter "les coins et les méplats" de l'exagone.

...

Posté par
slay_mithos
re : Formules d'appartenance d'un point à une surface simple 27-03-10 à 14:45

j'ai fait les tests par les droites, car il s'agit d'hexagones emboités , donc les cercles se superposeraient, ce qui pourrait causer des problèmes.

Merci encore pour cette piqure de rappel.

Posté par
pgeod
re : Formules d'appartenance d'un point à une surface simple 27-03-10 à 16:29



Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !