Inscription / Connexion Nouveau Sujet
Niveau algorithmique
Partager :

Savoir si un point se trouve dans un tracé (une zone délimitée)

Posté par
fredu
26-12-08 à 14:50

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é.

Posté par
akub-bkub
re : Savoir si un point se trouve dans un tracé (une zone délimi 26-12-08 à 22:12

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.

Posté par
jamo Moderateur
re : Savoir si un point se trouve dans un tracé (une zone délimi 27-12-08 à 08:39

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 ?

Posté par
jamo Moderateur
re : Savoir si un point se trouve dans un tracé (une zone délimi 27-12-08 à 08:41

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 ...

Posté par
JJa
re : Savoir si un point se trouve dans un tracé (une zone délimi 27-12-08 à 09:00

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.

Posté par
jamo Moderateur
re : Savoir si un point se trouve dans un tracé (une zone délimi 27-12-08 à 10:03

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 :

Posté par
jamo Moderateur
re : Savoir si un point se trouve dans un tracé (une zone délimi 27-12-08 à 10:06

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.

Posté par
akub-bkub
re : Savoir si un point se trouve dans un tracé (une zone délimi 27-12-08 à 11:18

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+

Posté par
fredu
re : Savoir si un point se trouve dans un tracé (une zone délimi 01-01-09 à 22:29

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!

Posté par
otto
re : Savoir si un point se trouve dans un tracé (une zone délimi 02-01-09 à 09:56

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+

Posté par
otto
re : Savoir si un point se trouve dans un tracé (une zone délimi 02-01-09 à 10:04

Voici à l'époque ce que j'avais codé

Citation :

%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

Posté par
otto
re : Savoir si un point se trouve dans un tracé (une zone délimi 02-01-09 à 10:30

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é...

Posté par
fredu
re : Savoir si un point se trouve dans un tracé (une zone délimi 02-01-09 à 15:00

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!

Posté par
jamo Moderateur
re : Savoir si un point se trouve dans un tracé (une zone délimi 02-01-09 à 17:04

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] !

Posté par
fredu
re : Savoir si un point se trouve dans un tracé (une zone délimi 03-01-09 à 13:29

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...

Répondre à ce sujet

Seuls les membres peuvent poster sur le forum !

Vous devez être connecté pour poster :

Connexion / Inscription Poster un nouveau sujet
Une question ?
Besoin d'aide ?
(Gratuit)
Un modérateur est susceptible de supprimer toute contribution qui ne serait pas en relation avec le thème de discussion abordé, la ligne éditoriale du site, ou qui serait contraire à la loi.


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

Inscription gratuite

Fiches en rapport

parmi 1446 fiches de maths

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 !