Inscription / Connexion Nouveau Sujet
Géométrie: Intérieur d'une figure
Bonsoir,
Je suis actuellement en train de faire un programme en C tourant autour de la géométrie. Je bloque actuellement sur un problème mathématique, et après de looooooooongues recherches, je me tourne vers vous en espérant trouver les réponses dont j'ai besoin.
Je vous explique donc mon problème: mon programme génére une "structure" contenant les coordonnées de tous les points d'un contour, qui peut avoir une forme quelconque (à terme, ce sera une fractale, donc une forme réellement compliquée. Et j'ai besoin de pouvoir déterminer si un point A de coordonnées [x,y] se trouve à l'intérieur du contour, ou pas.
J'ai d'abord pensé à regarder s'il y avait bien un point du contoure à gauche de A, à droite, en haut et en bas en même temps, mais il existe aussi des points, dans certains contours, qui peuvent remplir cette condition (voir image plus bas). J'ai aussi recherché sur ce forum, et trouver la possibilité de prendre un point B extérieur au contour, et voir combien de fois le segment [AB] coupe le contour, un nombre impair signifiant que le point est bien dans le contour. Mais encore une fois, dans certains cas ceci ne marchera pas. J'ai donc pensé à prendre deux points à l'extérieur, et étudier les deux droites, ça ne fait que réduire les chances que "l'improbable" se produise.
Après toutes ces désillusions, je me tourne vers vous, merci d'avance des réponses.
PS: Je précise ce que j'entendait par le terme structure. Ce n'est qu'en fait une liste, répertoriant les points dans l'ordre horaire du tracé. Pour les connaisseurs, c'est une liste doublement chainée.
Liens vers une image montrant mes deux méthodes et leurs problèmes:
édit Océane : image placée sur le serveur de l'
, merci d'en faire autant la prochaine fois 
Bonjour,
Je ne suis pas tout à fait sûr, mais il me semble que si A est un point connu à l'intérieur de la "structure" (polygone sans doute), alors un point M est à l'intérieur de celle-ci si et seulement si le segment AM un nombre pair d'intersections avec le contour (0, 2, 4 ...). Si cette idée est la bonne, alors il suffit de faire une boucle balayant tous les segments formant le contour, pour voir si le segment [AM] a une intersection avec les segments du contour ...
Je me suis mal exprimé :
Si A est un point connu à l'intérieur de la "structure" (polygone sans doute), alors un point M est à l'intérieur de celle-ci si et seulement si le segment AM a un nombre pair d'intersections avec le contour (0, 2, 4 ...). Si cette idée est la bonne, alors il suffit de faire une boucle balayant tous les segments formant le contour, pour voir si le segment [AM] a une intersection avec chacun des segments du contour ... Après la boucle, il suffit de compter le nombre d'intersections pour conclure
Ta réponse entre dans le même cas que le fait de tester le nombre d'intersection entre la droite reliant le point a tester et le contour. Il suffit que par malchance la droite tombe sur une pointe intérieure du contour, et il ne sera compté qu'une intersection au lieu de deux. Ou sinon il faut àa chaque fois considérer le segment [<point I du contoure><point I+1 du contour>], ce qui ferait que la pointe serait compter deux fois, vu qu'elle appartiend à deux segments (cette idée met venue aujourd'hui durant mes partiels 
). Ce n'est pas très opimal, mais dans le pire des cas je ferais ça. Si quelqu'un a une autre idée, je suis preneur^^.
OK, je reprécise ma pensée à partir des 2 modèles proposés par Océane :
Si on part d'un point connu à l'intérieur du contour, et si on trace un segment reliant ce point au point à tester, alors :
si le segment traverse le contour un nombre impair de fois, le point est à l'extérieur,
si le segment traverse le contour un nombre pair de fois, alors le point est à l'intérieur,
Les points du segment qui sont tangents au contour ne doivent pas être pris en compte.
Je suis presque sûr d'avoir lu ça quelque part dans un cours de topologie... mais ma mémoire est souvent défaillante et je suis prêt à faire amende honorable si mon affirmation est fausse
Annuler
connectez vous
géométrie en post-bac