convexite polygones en 2D

**spearman** · 26/01/2017, 08h54

Bonjour, j'ai des difficultes pour tester la convexite de polygone.
differents essais graham, ...
au plus simple, j'ai opte pour controle d'angles <180° entre chaque segments consecutifs.
pour cela, le code ci-apres me detecte toujours erreur angle complementaire entre 2 derniers segments.
Apres qques soirees de recherche,je nai pas reussi a trouver. Si qqun pouvait m'aider.
encore merci

Code Pascal:

Code pascal :

Sélectionner tout - Visualiser dans une fenêtre à part

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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
type tabpolygone=array of tpoint;
 
type rsegment=record
    Pta,ptb:tpoint;
    end;
 
type rpolaire=record
    Rayon,Angle:single;
    end;
......
 
var
  Form1: TForm1;vgr:tabpolygone;
 
implementation
 
{$R *.dfm}
uses math;
....
function segment(vpta,vptb:tpoint):rsegment;
begin
result.Pta:=vpta;result.ptb:=vptb
end;
 
function polaire(rayon,angle:single):rpolaire;
begin
result.Rayon:=rayon;result.Angle:=angle
end;
 
 
function message_formater_segment(vs:rsegment):string;
begin
result:='('+inttostr(vs.Pta.x)+'/'+inttostr(vs.Pta.y)+','+inttostr(vs.ptb.x)+'/'+inttostr(vs.ptb.y)+')';
end;
 
 
function distance_2points(pta,ptb:tpoint):integer;
begin
result:=round(sqrt(sqr(pta.X-ptb.X)+sqr(pta.y-ptb.y)));
end;
 
 
function calcpolaire_deg(pt0,pt1:tpoint;var pt10x,pt10y:single):rpolaire;
var Rayon:integer;
    //pt10x,pt10y:single;//pt1 dans rep pt0
    Aradian:single;
begin
result:=polaire(0,0);
    if (pt0=pt1) then
    begin
    result.Rayon:=0;result.Angle:=0;
    end
    else begin
    Rayon:=distance_2points(pt0,pt1);  //Distance
      if Rayon<>0 then
      begin
      //Calcul Coord dans repere Pt0 et ramene dans 0..1
      pt10X:=(pt1.X-pt0.X)/Rayon;
      pt10Y:=(pt1.Y-pt0.Y)/Rayon;
          if (pt10X=0) and (pt10Y=0) then
          begin
          ARadian:=0;Rayon:=0;
          end
          else begin
              if (pt10X>0) and (pt10y>=0)
              then ARadian:=arctan( pt10Y/pt10X )
              else
              if (pt10X>0) and (pt10y<0)
              then ARadian:=arctan( pt10Y/pt10X )+2*pi
              else
              if (pt10X<0)
              then ARadian:=arctan( pt10Y/pt10X )+pi
              else
              if (pt10X=0) and (pt10y>0)
              then ARadian:=3*pi/2//ARadian:=pi/2
              else
              if (pt10X=0) and (pt10y<0)
              then ARadian:=pi/2 //ARadian:=3*pi/2
          end;
      result.Angle:=round(radtodeg(ARadian));
      result.Rayon:=Rayon;
      end;
    end;
  end;
 
 
function calcul_angledeg_2segments(s1,s2:rsegment):single;
var ptorig:tpoint;ptpolfin1,ptpolfin2:rpolaire;xtmp,ytmp:single;
    pointcommunok:boolean;
begin
result:=-1;
pointcommunok:=false;
//Si existe point commun 2 segment
  if(s1.Pta=s2.Pta) then
  begin
  ptorig    :=s1.pta;
  ptpolfin1 :=calcpolaire_deg(ptorig,s1.ptb,xtmp,ytmp);
  ptpolfin2 :=calcpolaire_deg(ptorig,s2.ptb,xtmp,ytmp);
  pointcommunok:=true;
  end;
  if(s1.Pta=s2.Ptb) then
  begin
  ptorig    :=s1.pta;
  ptpolfin1 :=calcpolaire_deg(ptorig,s1.ptb,xtmp,ytmp);
  ptpolfin2 :=calcpolaire_deg(ptorig,s2.pta,xtmp,ytmp);
  pointcommunok:=true;
  end;
  if(s1.Ptb=s2.Pta) then
  begin
  ptorig    :=s1.ptb;
  //ptpolfin1 :=calcpolaire_deg(ptorig,s1.pta,xtmp,ytmp);
  //ptpolfin2 :=calcpolaire_deg(ptorig,s2.ptb,xtmp,ytmp);
  ptpolfin1 :=calcpolaire_deg(ptorig,s1.pta,xtmp,ytmp);
  ptpolfin2 :=calcpolaire_deg(ptorig,s2.ptb,xtmp,ytmp);
 
  pointcommunok:=true;
  end;
  if(s1.Ptb=s2.Ptb) then
  begin
  ptorig    :=s1.ptb;
  ptpolfin1 :=calcpolaire_deg(ptorig,s1.pta,xtmp,ytmp);
  ptpolfin2 :=calcpolaire_deg(ptorig,s2.pta,xtmp,ytmp);
  pointcommunok:=true;
  end;
 
  if pointcommunok
  then result    :=abs(ptpolfin2.Angle-ptpolfin1.Angle)
 
end;
 
function tabpolygone_estconvexe(r:tabpolygone;var vmes:string):boolean;
var i,j,k,l:integer;
    vseg1,vseg2:rsegment;
    vangdeg:single;
begin
result:=false;vmes:='';
    if length(r)>2 then//Si aumoins polygone est triangle
    begin
    //Si est triangle
      if length(r)=3
      then result:=true  //Triangle est tjrs convexe
      else begin
      result:=true;
      //Tester Angle de chaque segment joint <=180°
          for i:=0 to length(r)-1 do
          begin
            if i<length(r)-2
            then begin j:=i+1;k:=j+1 end
            else begin
              if i=length(r)-2
              then begin j:=i+1;k:=0 end
              else begin j:=0;k:=1 end;
            end;
          //Test angle des 2 segments
          vseg1   :=segment(r[i],r[j]);
          vseg2   :=segment(r[j],r[k]);
          vangdeg :=calcul_angledeg_2segments(vseg1,vseg2);
            if vangdeg>180
            then begin
            result:=false;
            String_Concatener_SLINEBREAK(vmes,'ERR:Angle segments:'+message_formater_segment(vseg1)+
                                               ' et '+message_formater_segment(vseg2)+'='+floattostr(vangdeg));
            end
            else
            String_Concatener_SLINEBREAK(vmes,'OK :Angle segments:'+message_formater_segment(vseg1)+
                                               ' et '+message_formater_segment(vseg2)+'='+floattostr(vangdeg));
 
          end;  //ENd for
      end;
    end;
    if not result
    then vmes:='ERREUR:'+SLINEBREAK+vmes
    else vmes:='OK    :'+SLINEBREAK+vmes
 
end;
 
procedure TForm1.btn_test_convexeClick(Sender: TObject);
var vmes:string;
begin
    if Length(vgr)>0 then
    begin
        if tabpolygone_estconvexe(vgr,vmes)  //  tabpolygone_estcroise(vgr,vmes)
        then;
    memo1.Lines.Add(vmes)
    end;
end;
 
procedure TForm1.btn_initClick(Sender: TObject);
begin
setlength(vgr,4);
vgr[0]:=point(10,10);
vgr[1]:=point(100,100);
vgr[2]:=point(80,120);
vgr[3]:=point(10,120);
tracepolygone(paintbox1,vgr);
end;

**spearman** · 27/01/2017, 20h22

Pour partager si quelqu'un est interesse, bien que sujet largement traite sur le forum depuis quelques annees, mais avec des solutions complexes à mon gout.
La solution que jai retenue et qui marche tres correctement (a priori) est la suivante:
Convexite polygone si 2 conditions:
1)Si chaque point du polygone est extérieur au polygone reduit aux autres points
2)Si le polygone est non croise.

Merci a ce forum pour les nombreuses sources d'informations d'une facon generale.
==========================
Ci-joint code:

convexite polygones en 2D

Développement 2D, 3D et Jeux

Discussions similaires

Partager

Partager