Inscription / Connexion Nouveau Sujet
Savoir si un point se trouve dans un tracé (une zone délimitée)
Bonjour,
Je suis de passage ici. Ma situation est un peu particulière, alors je me permet 3 mots pour me présenter:
Je suis étudiant en médecine, et en même temps fou de programmation. J'ai appris pas mal de langage (surtout web) de manière autodidacte.
Dans le cadre de mon mémoire d'étude, je veux réaliser une application qui permette de lire des images d'IRM et les faire défiler. L'application doit permettre de tracer des zones (par exemple, une région digne d'intérêt médical sur l'IRM) puis de l'associer à nombre de fonction, comme des explications sur la physio ou patho de cette zone... enfin je ne vais pas vous faire un discours!
J'ai donc un problème mathématique pour la réalisation de mon programme (donc un gros problème, d'autant que les math sont pas ma spécialité!)
Peut être que vos lumières pourront me sortir de cette galère.
Je pose le problème:
Je crée un tracé. Un tracé est un ensemble de points x;y (des coordonnées) sur un plan 2d (ie mon image IRM) qui sont reliée par des droites (vecteurs). Ensembles, ces points (et ces droites) forment une zone (un polygone, une forme). Il y a un nombre variable de points (autant que voulu pour créer des zones aussi grandes/complexes que voulu). Les zones sont *fermées* de sorte que le dernier point posé fasse une droite avec le premier. Une règle aussi: un vecteur entre deux points ne peut pas croiser un autre vecteur existant pour le même tracé. De cette manière il n'y a pas de portion de mon polygone qui recouvre (se superpose à) une autre portion de ce même polygone.
Maintenant, imaginons que l'utilisateur de mon applic clic quelque par sur l'image. Je peux récupérer la coordonnée x;y de son clic.
Je voudrais savoir comment tester si ce dernier clic se trouve à l'intérieur ou à l'extérieur de ma zone faites de points.
Ahhhlala! Les math! C'est le pied, mais c'est aussi la misère!
J'ai déjà posé la question sur des forums spécialisés en code, mais je dois dire que les réponses ne sont que rarement abouties!
Merci d'avance donc et j'espère ne pas être hors sujet!
A + et joyeuses fêtes!
Edit jamo : forum modifié.
slt fredu,
J'espère avoir cerner ton problème correctement.
Je me réfère à cette figure : 
Sur la figure, le point O est à l'intérieur du polygone ABCDE. Les angles AOB, BOC, COD, ..., EOA ont TOUS des amplitudes inférieures à 180°. Une fois que le point O 'sort', un des angles dépasse alors 180°. Je pense que cette propriété t'intéressera.
Voilà, j'espère t'avoir aidé. Sinon, je suis convaincu que d'autres s'y essayeront! 
Bien à toi. Joyeuses fêtes.
Bonjour,
en effet, cette méthode avec les angles semble fonctionner.
Mais je me pose une question : si le polygone n'est pas convexe, cette méthode peut-elle marcher ?
Après une courte reflexion : non, cette méthode ne fonctionne pas si le polygone est concave ou présente des "trous".
Donc, fredu doit nous en dire un peu plus sur la nature de ses polygones ...
Bonjour,
Une méthode consiste à balayer un segment de droite partant du point considéré et aboutissant à un point connu comme étant à l'extérieur du domaine (un choix simple consiste à prendre un segment horizontal, par exemple).
On se donne une variable booléenne B=false au départ. Chaque fois que le point variable sur le segment passe sur un point appartenant à une limite du domaine, on inverse la variable (B=false devient B=true, ou inversement)
Quand on est arrivé à l'extrémité du segment (donc au point connu extérieur au domaine), si on est est à B=false, c'est que le point initial était à l'extérieur, si B=true, c'est qu'il était à l'intérieur.
Il faut gérer les cas particuliers : par exemple, si le segment de balayage passe exactement en un sommet du polygone limite, ou si le segment recouvre exactement un coté du polygone. Le plus simple pour éviter les complications de programmation est alors de recommencer avec un autre segment (par exemple vertical au lieu d'horizontal, ou autre...).
Il y a des procédés encore plus simples, mais qui dépendent du logiciel et du langage que l'on utilise. Certaines resources permettent de créer un "masque", c'est à dire une image accessoire sur laquelle les pixels du domaine ont une couleur différente des pixels extérieurs. Etant donné le point (x,y) considéré, la capture du pixel correspondant sur le "masque" indique immédiatement s'il est dans ou hors du domaine.
Ah oui, cette méthode qui consiste à utiliser un "rayon" et de compter le nombre de côtés qu'il traverse me rappelle quelque chose. Si le nombre de côtés traversé est pair, le point est à l'exterieur, et si le nombre de côté est impair, le point est à l'intérieur. Et cette méthode marche quel que soit la type de polygone (convexe ou pas).
Je crois même que cette question a déjà été abordée sur le forum de l'ile des maths, il faudrait faire une petite recherche.
En attendant, un petit coup de Google avec "point à l'intérieur d'un polygone" donne pas mal de liens intéressants.
On trouve même des programmes tout fait, par exemple ici :
Voici 2 liens vers des topics abordés sur l'ile : Trouvé si une coordonnée X,Y se trouve à l int. d une forme géo. et Géométrie: Intérieur d'une figure
Mais il doit y en avoir d'autres, car je me souviens d'avoir déjà participé à une discussion sur ce sujet.
Slt jamo et JJa,
Effectivement, ma méthode ne fonctionne pas avec les concaves... Zut, et moi qui pensais avoir fait avancer la sciences.
Il faudrait quand-même que j'apprenne à réfléchir un petit peu plus loin que le sommet de mon polygone!!!
fredu, j'espère que tu parviendras a résoudre ton problème.
A+
rebonjour, joyeuse nouvelle année et pardon d'avoir mis tant de temps à retrouver mon propre topic 
En effet, la méthode doit pouvoir accepter des polygone dont les sommets soient à des angles complètement variés. Donc polys convexes aussi et la technique des angles ne peut donc pas marcher... (merci quand meme).
La techniques de Jja m'est passée par l'esprit. mais sous une autre forme
Si on comprend que le poly est composé d'une série de points, je vais analyser les segments de droites qui composent polygone. Il me faut les considérer comme des vecteurs pour arriver à mes fins, car j'ai besoin d'une information sur le sens de mes segments de droites. Je partirai donc du principe que tous mes polygones, doivent être tracés dans le sens des aiguilles d'une montre. Sinon, la zone sélectionnée est l'inverse.
Je choisis ensuite un point au hasard (il me semble que cette méthode fonctionne de manière identique avec tous les points d'un poly quelconque). Nommons le B. Je vais également chercher les coordonnées du point juste avant (A) et juste après (C). Cela me crée donc un sommet sur B tel que ABC. Je calcul l'angle. (toujours l'angle interne au polygone (d'ou la nécessité des vecteurs)).
Lorsque l'utilisateur pose un point CLICK que j'appelle D, je calcul alors l'angle d'un nouveau sommet ABD.
Je garde en mémoire ABD et ABC.
Je pose aussi un booléen:
in = true (si je suis DANS le poly)
in = false (si je suis en dehors...)
Si l'angle ABD est supérieur à l'angle ABC, je pose in = true ; Sinon, je pose in = false
Je vais maintenant tirer une droite depuis le point choisi (B) vers le point CLICK (D). Je compte le nombre d'intersection que cette nouvelle droite fait avec tous les segments engeigistrés dans mon poly. A chaque intersection, je switch mon booléen.
....
bref...............
C'est basiquement la même idée que Jja (et pour le moment, elle marche aussi très bien), mais c'est clair que celle de Jja est plus simple, moins couteuse en ressources ordinateur et plus directe...
Donc merci Jja!
Bonjour,
j'ai déjà fait ça il y'a quelques temps dans le cadre de mon mémoire de maitrise. Il suffit de calculer l'indice du point par rapport à ta courbe. Il sera nul si et seulement si ton point est extérieur à la courbe (c'est un résultat classique d'analyse complexe).
Dans ton cas, cela revient simplement à calculer la somme des angles orientés
0A1A2 + OA2A3 + OA3A4 + ... + OAnA1
si je ne dis pas de bétise...
Cela devrait être un multiple entier de 2 pi et sera nul si et seulement si O est en dehors du tracé.
En fait, dans ton cas ca devrait être -1, 0 ou 1.
Je pense ne pas avoir dit de bétise.
a+
Voici à l'époque ce que j'avais codé
%La matrice définie une courbe de Jordan en considérant que la courbe est une interpolation
linéaire entre chaque entrée.La fonction vérifie si point est dans l'intérieur de la courbe.
Elle retourne 1 si oui et 0 sinon.
function booleen=dansinterieur(point,matrice)
s=size(matrice); s=s(1);
X=matrice(:,1);
Y=matrice(:,2);
Z=X+i*Y;
w=point(1,1)+i*point(1,2);
wide=0;
j=1;
s=size(Z);s=s(1);
for j=1:s-1
wide=wide+log((Z(j+1)-w)/(Z(j)-w));
end
wide=(wide+log((Z(1)-w)/(Z(s)-w)))/(2*i*pi);
y=[];
if abs(wide)<1+0.000001 & abs(wide)>1-0.000001
y=1;
else
y=0;
end
booleen=y;
Remarque que la condition n'est pas si "wide=1" parce que pour matlab, 1.000000000 n'est pas égal à 1. Il doit y avoir une facon de changer mon double en int pour utiliser cette condition mais je ne me suis pas cassé la tête et j'ai dit que mon nombre valait 1 s'il était compris entre 1-0.000001 et 1+0.000001
Si certains se demandent pourquoi "wide" comme variable, en fait je ne sais pas, le terme anglais est winding number, c'est surement ce qui m'a inspiré...
Merci otto,
Je ne suis de loin pas un matheux, juste un petit étudiant qui programme depuis quelques temps et ton analyse va me confronter à l'exercice de quelques vieux souvenir et à un bon moment de réflexion.
Qu'à cela ne tienne, ma petite applic se doit d'être la plus économe possible (ce genre de calcul est exécuté à plusieurs reprises dans mon code). Je vais donc passer par l'analyse de ta méthode...
Mais en attendant:
J'ai aussi fais quelque devoir qui me rappellent ma maturité (bac suisse... eh oui, un suisse) et je suis arrivé à un petit problème.
Je résous un système à deux inconnues pour trouver le point d'intersection entre deux droites. Mais je me rappelle que les droites sont par défaut infinies et donc, lors que je résous mon système, pour peu que les deux droites n'aient pas la même pentes (droites parallèles), elles finissent toujours par se croiser un jour ou l'autre.
Je comprend donc que mon polygone n'est pas formé de droites, mais de segments de droites. et que ce que je désire en fait, c'est de savoir si deux segments de droites (avec les extrémités A et B, ce sont des droites "finies") se croisent dans leurs limites.
Ma solution initiale est de trouver les coordonnées du point d'intersection et de vérifier s'il est bien supérieur aux coordonnées de A et inférieur aux coordonnées de B.
Je n'ai pas encore codé cette petite partie de l'applic, mais j'imagine que ça doit marcher. Par contre, il est clair que je passe par encore plus de calcules qui se réitèrent au sein d'une boucle. S'il existe donc une méthode plus puissante et qui me permette d'éconmiser quelques milisec d'exécution, je suis preneur.
Encore merci à vous, et bonne année!
Si je comprends bien tout ce que tu viens d'écrire, tu veux connaitre l'intersection de 2 segments ?
Alors prenons deux segments [AB] et [CD].
Ce que je proposerais, c'est que tu determines tout d'abord l'intersection des droites (AB) et (CD) : c'est assez simple, une formule doit pouvoir donner tout de suite l'abscisse et l'ordonnée de ce point M (s'il existe).
Ensuite, pour savoir si le point appartient au segment [AB], on peut par exemple calculer les longueurs AB, AM et MB. Ensuite, si on a : AM+MB=AB, alors le point est sur [AB] ! 
Oui, donc c'est bien comme ceci qu'il faut procéder: en deux temps... Je pensais peut-être qu'il existait une formule qui permette de renseigner sur ce point M d'un seul coup, mais comme ça c'est très bien aussi!
Au passage, merci pour le lien vers le site des courbes (géotruc)... c'est assez formidable...
Annuler
connectez vous