Segment sur l'enveloppe convexe

Version imprimable

Bonjour,
J'ai fait un programme pour savoir si un segment appartient à l'enveloppe convexe mais celui ci ne fonctionne pas et je n'arrive pas a voir ce qui ne va pas.
Merci d'avance pour votre aide

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
function t=TestSegConv(x,y)
 
ok=0;i=1;
while(ok==0 && i<numel(convhull(x,y))
if(convhull(i)==x)
        if(convhull(i+1)==y)
            ok=1;
        else
            ok=0;
        end;
    else
        if (convhull(i)==y)
            if(convhull(i+1)=x)
                ok=1;
            else
                ok=0;
            end;
        end;
    end;
end;
i=i+1;

03/01/2009, 10h28
Jerome Briot

Qu'est-ce qui ne marche pas ?
Le code tourne-t-il ? Y-a-t-il des messages d'erreurs ?

Que représentent x et y ?

Est-ce que convhull est une variable ou bien la fonction CONVHULL ?
Si c'est une variable, il faudrait la nommer différemment.

Desolé de ne pas avoir été assez clair. Je vais essayer d'expliquer au maximum.
Alors voila, j'ai deja crée un programme qui permet sur un nuage de point de faire la triangulation de delaunay, puis l'enveloppe convexe, puis d'appliquer le graphe de gabriel à tous cotés des triangles de Delaunay, alors voila ce programme :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
 
function enveloppeconvexe
 
clc;
a=0;b=10;c=0;d=10;
clf;
axis([a b c d])
hold on
grid
[xn,yn,but]=ginput(1);
x=[xn];y=[yn];plot(xn,yn,'.r');
n=1;k=n;Go=1;
ListPt2=[k];
while Go==1;
     [xn,yn,but]=ginput(1);
     if but<3   x=[x xn]; y=[y yn];plot(xn,yn,'.r');n=n+1;
                plot([x(n-1) x(n)],[y(n-1) y(n)],'-g');
     end;
     if but>1  ;plot([x(n) x(1)],[y(n) y(1)],'-g'); Go=0; end; 
end;
ListPt2=[[1:n] 1];
triplot(delaunay(x,y),x,y)
 
pause;
 
plot(x,y,'.k');
hold on; 
ListPt = convhull(x,y);
n=size(ListPt,2);
for i=1:n 
    j=ListPt(i);
end; 
plot(x(ListPt),y(ListPt),'green',x,y,'.r');hold on;
 
pause;
 
plot(x(ListPt2),y(ListPt2),'-rs','LineWidth',2,...
                'MarkerEdgeColor','black',...
                'MarkerFaceColor','black',...
                'MarkerSize',10)
 
pause;
clc;
 
NbTr=size(delaunay(x,y),1);
MC=[];
Triang=delaunay(x,y);
for l=1:NbTr
    Tr=Triang(l,:);
    i=Tr(1,1);j=Tr(1,2);k=Tr(1,3);
    MC=[MC;[i,j];[j,k];[k,i] ];   
end;
SML=sort(MC,2);
SML=sortrows(SML);
N=MC(1,:);
n=size(MC,1);
for i=2:n 
    if MC(i-1,:)==MC(i,:) ;else N=[N;MC(i,:)]; end;
end;    
 
GGT=[];
n=size(MC,1);
for k=1:n
    Cote=MC(k,:);i=Cote(1);j=Cote(2);
    n=numel(x);
    A=[x(i) y(i)]; B=[x(j) y(j)];
    M=1/2*(A+B);R=(1/2)*norm(B-A);
    Go=1;k=0;Bool=0;
    while Go
         k=k+1;
         if ismember(k,[i j]); 
         else
            C=[x(k) y(k)];d=norm(C-M);Bool=d<R; 
         end;    
            Go=not(Bool) & (k<n);
    end;   
    BSG=not(Bool);
    if BSG GGT=[GGT;Cote];
    end;
end;    
clf;
axis([a b c d]);
GGT
plot(x,y,'.r');
 
n=size(GGT,1);
for k=1:n
    i=GGT(k,1);j=GGT(k,2);
    plot([x(i) x(j)],[y(i) y(j)],'-b');hold on;
end;

Et en fait j'ai crée une nouvelle fonction qui permet de savoir si un segment est sur l'enveloppe convexe, pour pouvoir le mettre dans la fonction precedente et appliquer le graphe de gabriel juste aux segments de l'enveloppe convexe, alors voici cette fonction :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function t=TestSegConv(x,y)
 
ok=0;i=1;
while(ok==0 && i<numel(convhull(x,y))
    if(convhull(i)==x)
        if(convhull(i+1)==y)
            ok=1;
        else
            ok=0;
        end;
    else
        if (convhull(i)==y)
            if(convhull(i+1)=x)
                ok=1;
            else
                ok=0;
            end;
        end;
    end;
end;
i=i+1;

avec convhull la fonction préprogrammée de matlab.
J'espere que j'ai été assez clair.
N'hesitez pas s'il y a encore des questions.
Merci par avance pour votre aide

03/01/2009, 13h26
Jerome Briot

Citation:

Envoyé par clara1815

avec convhull la fonction préprogrammée de matlab.

Dans ce cas que représente convhull(i) ?
03/01/2009, 13h54
clara1815

oui vous avez raison convhull depend de 2 variables. En fait en prenant i et i+1, je voulais prendre 2 points qui se suivent, parce que 1 point peu appartenir a l'enveloppe, un autre à l'enveloppe alors que le segment est à l'interieur, il me faut donc des points consecutifs, et je suis bien d'accord ca ne va pas
03/01/2009, 16h51
clara1815

Du coup je ne sais pas comment faire? Est-ce que vous pourriez m'aider?
Merci d'avance

Ce que tu cherches est directement donné par la fonction CONVHULL.
Les segments sont données par la liste des indices successifs.
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 x = rand(1,8); y = rand(1,8); tri = delaunay(x,y); K = convhull(x,y); figure hold on plot(x,y,'r*',x(K),y(K),'m'); text(x,y,num2str((1:numel(x)).')) triplot(tri,x,y,'k:') axis equal T = sort([tri(:,1:2) ; tri(:,2:3) ; tri(:,[1 3])],2); uT = unique(T,'rows'); KK = sort([K(1:end-1) K(2:end)],2); uKK = unique(KK,'rows') ismember(uT,uKK,'rows')
Une petite remarque, pense à mettre des commentaires (beaucoup de commentaire) dans ton code. Sinon c'est imbuvable :aie:

Merci tout d'abord pour votre reponse. Desole de ne pas vous avoir repondu plus tot mais j'avais des soucis avec internet.
Je trouve ce programme tres bien mais je n'arrive pas à l'insérer à mon programme pour que ca fasse le graphe de gabriel sur l'enveloppe convexe parce que pour le moment ca fait le graphe de gabriel sur tous les triangles. J'ai essayé de mettre un peu plus de commentaires.
Merci d'avance pour votre aide.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
function ReconnaissanceFormebbbb
 
 
%creation nuage de points
xmin=0;xmax=10;ymin=0;ymax=10;
axis([xmin xmax ymin ymax])
hold on
grid off
x=[];y=[];
n=0;but=1;
while but==1
     [xi,yi,but]=ginput(1);
     if(xi>=xmin && xi<=xmax && yi>=ymin && yi<=ymax)
         if but==1
             plot(xi,yi,'.r');
             n=n+1;
             x(:,n)=xi;y(:,n)=yi;
         end;
     else
         but=0;
     end;
end;
x=x';y=y';         
ListPoint=[(1:n) 1];
 
%Triangulation de Delaunay
triplot(delaunay(x,y),x,y)
 
pause;
 
%Tracé de l'enveloppe convexe
plot(x,y,'.k');
hold on; 
ListPoint = convhull(x,y);
n=size(ListPoint,2);
for i=1:n 
    j=ListPoint(i);
end; 
plot(x(ListPoint),y(ListPoint),'green',x,y,'.r');hold on;
 
pause;
clc;
 
%Creation des matrices des cotés des triangles de Delaunay
NbTr=size(delaunay(x,y),1);
MCT=[];
Triangle=delaunay(x,y);
for l=1:NbTr
    Tr=Triangle(l,:);
    i=Tr(1,1);j=Tr(1,2);k=Tr(1,3);
    MCT=[MCT;[i,j];[j,k];[k,i] ];   
end;
 
pause;
%Graphe de Gabriel
hold on;
RF=[];
n=size(MCT,1);
for k=1:n
    Cote=MCT(k,:);i=Cote(1);j=Cote(2);
    n=numel(x);
    A=[x(i) y(i)]; B=[x(j) y(j)]; 
    %Milieu M de AB pour tracer un cercle de diametre de AB pour voir si il y  a  des points a l'interieur de ce cercle
    M=1/2*(A+B);
    R=(1/2)*norm(B-A);
    Go=1;k=0;Bool=0;
        while Go
        k=k+1;
        if ismember(k,[i j]); 
        else
            C=[x(k) y(k)];
            d=norm(C-M);
            Bool=d<R; 
        end;    
        Go=not(Bool) & (k<n);
    end;    
    if not(Bool) RF=[RF;Cote];
    end;
end;
clf;
%Tracer du graphe en enlevant les segments qui ne sont pas de Gabriel
plot(x,y,'.r');
n=size(RF,1);
for k=1:n
    i=RF(k,1);j=RF(k,2);
    plot([x(i) x(j)],[y(i) y(j)],'-b');hold on;
end;

Si je n'ai pas bien expliqué, vous pouvez me poser des questions

J'ai un petit peu avancé voila mon nouveau code :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
function ReconnaissanceFormebbbb
 
 
%creation nuage de points
xmin=0;xmax=10;ymin=0;ymax=10;
axis([xmin xmax ymin ymax])
hold on
grid off
x=[];y=[];
n=0;but=1;
while but==1
     [xi,yi,but]=ginput(1);
     if(xi>=xmin && xi<=xmax && yi>=ymin && yi<=ymax)
         if but==1
             plot(xi,yi,'.r');
             n=n+1;
             x(:,n)=xi;y(:,n)=yi;
         end;
     else
         but=0;
     end;
end;
x=x';y=y';         
ListPoint=[(1:n) 1];
 
%Triangulation de Delaunay
triplot(delaunay(x,y),x,y)
 
pause;
 
plot(x,y,'.k');
hold on; 
ListPoint = convhull(x,y);
n=size(ListPoint,2);
for i=1:n 
    j=ListPoint(i);
end; 
plot(x(ListPoint),y(ListPoint),'green',x,y,'.r');hold on;
 
pause;
clc;
 
NbTr=size(delaunay(x,y),1);
MCT=[];
Triangle=delaunay(x,y);
for l=1:NbTr
    Tr=Triangle(l,:);
    i=Tr(1,1);j=Tr(1,2);k=Tr(1,3);
    MCT=[MCT;[i,j];[j,k];[k,i] ];   
end;
 
pause;
hold on;
RF=[];
T=sort([Triangle(:,1:2) ; Triangle(:,2:3) ; Triangle(:,[1 3])],2);
uT=unique(T,'rows');
KK=sort([ListPoint(1:end-1) ListPoint(2:end)],2);
n=size(KK,1);
for k=1:n
    Cote=KK(k,:);i=Cote(1);j=Cote(2);
    n=numel(x);
    A=[x(i) y(i)]; B=[x(j) y(j)]; 
    M=1/2*(A+B);
    R=(1/2)*norm(B-A);
    Go=1;k=0;Bool=0;
        while Go
        k=k+1;
        if ismember(k,[i j]); 
        else
            C=[x(k) y(k)];
            d=norm(C-M);
            Bool=d<R; 
        end;    
        Go=not(Bool) & (k<n);
    end;    
    if not(Bool) RF=[RF;Cote];
    end;
end;
clf;
plot(x,y,'.r');
n=size(RF,1);
for k=1:n
    i=RF(k,1);j=RF(k,2);
    plot([x(i) x(j)],[y(i) y(j)],'-b');hold on;
end;

Le probleme maintenant est le suivant :
Mon programme m'affiche juste l'enveloppe convexe des segments supprimés. Mais je voudrais le nuage de points avec la triangulation de Delaunay avec ces aretes supprimés sur l'enveloppe convexe.
Et je veux itérer ce processus, jusqu'a ce qu'il n'y ai plus d'aretes a supprimer sur le contour.
Je suppose qu'il faut utiliser une fonction iterative. Mais je n'y arrive pas.
Merci d'avance pour votre aide.