Rasterization de polygone complex

**BeanzMaster** · 16/01/2020, 22h24

Bonjour a tous, je but sur une problème depuis quelques jours je suis confronter à un problème pour remplir mes polygones, a l'heure actuelle j'utilise un algorithme basé sur le "pair-impair" celui-ci pour des polygone convexe ou concave, fonctionne bien, mais pour des polygones complexe c'est une autre histoire.

Alors pour commencer voici comment est construit mon polygone

Nom : polygoncomplex.png
Affichages : 422
Taille : 5,6 Ko

Nom : polygoncomplex.png
Affichages : 422
Taille : 5,6 Ko

Ensuite j'ai trituré mon algo dans tous les sens, j'ai testé d'autres solutions similaire ici (draw_fillpoly) et la mais à chaque fois il y a des points non remplis (en rouge)

Nom : 2020-01-16_215433B.png
Affichages : 357
Taille : 10,7 Ko

Nom : 2020-01-16_215433B.png
Affichages : 357
Taille : 10,7 Ko

Connaissez vous un algorithme qui prenne en compte tous les types de polygone pour les remplir par "scanline"
Je n'ai rien trouvé sur le web de concluant ou je n'ai pas cherché avec les bon mots clefs ou sinon comment corriger le problème

voici mon algo correspondant au 3eme essais (basé sur pygame)

Code :

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
procedure TBZ2DPolygonTool.ComputeRasters;
Var
  Y, I, K, X, CurrentLine : Integer;
  Idx1, idx2 : Integer;
  LineIntersect : TBZIntegerList;
  RasterLine : TBZRasterItems;
  {$CODEALIGN VARMIN=16}
  p1, p2, Diff : TBZFloatPoint;
  {$CODEALIGN VARMIN=4}
 
  procedure SwapPoint(var A, B : TBZFloatPoint);
  Var
    {$CODEALIGN VARMIN=16}
    Temp : TBZFloatPoint;
    {$CODEALIGN VARMIN=4}
  begin
    Temp := A;
    A := B;
    B := Temp;
  end;
 
begin
  FBounds := ComputeBounds;
  FRastersLineCount  := (FBounds.AsRect.Bottom - FBounds.AsRect.Top) + 1; // FBounds.AsRect.Height + 1; //
  FStartY := FBounds.AsRect.Top;
  LineIntersect := TBZIntegerList.Create(12);
 
  SetLength(FRasters, FRastersLineCount);
  CurrentLine := 0;
  for  Y := FBounds.AsRect.Top to FBounds.AsRect.Bottom do
  begin
    if (Y > FStartY) then LineIntersect.Clear;
    I := 0;
    While I < FPoints.Count - 1 do
    //for I := 0 to FPoints.Count - 1 do
    begin
      if I = 0 then
      begin
        idx1 := FPoints.Count - 1;
        idx2 := 0;
      end
      else
      begin
        idx1 := I - 1;
        idx2 := I;
      end;
      p1 := FPoints.Items[idx1];
      p2 := FPoints.Items[idx2];
 
      if (p1.y > p2.y) then
      begin
        SwapPoint(p1,p2);
      end;
 
      if ((y >= p1.y) And (y < p2.y)) then
      begin
        Diff := p2 - p1;
        X := Round((y-p1.y) * Diff.X / Diff.Y + p1.x);
        LineIntersect.Add(X);
      end
      else if ((y = FBounds.AsRect.Bottom) And (y > p1.y) And (y <= p2.y)) then
      begin
        Diff := p2 - p1;
        X := Round((y-p1.y) * Diff.X / Diff.Y + p1.x);
        LineIntersect.Add(X);
      end;
      Inc(I);
    end;
 
    LineIntersect.Sort(0,@CompareInteger);
    SetLength(RasterLine, (LineIntersect.Count shr 1) );
    I := 0;
    K := 0;
    While (I < LineIntersect.Count) do
    begin
      RasterLine[K].xStart := LineIntersect.Items[I];
      RasterLine[K].xEnd := LineIntersect.Items[I+1];
      Inc(I,2);
      Inc(K);
    end;
    FRasters[CurrentLine] := RasterLine;
    SetLength(RasterLine,0);
    Inc(CurrentLine);
  end;
  FreeAndNil(LineIntersect);
end;

et la méthode de remplissage qui va avec

Code :

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
procedure TBZBitmapCanvas.FillPolygon(Pts : TBZArrayOfFloatPoints);
Var
  i, j, c: Integer;
  PolygonRasterizer: TBZ2DPolygonTool;
  Buckets: TBZRastersList;
  OldWidth : word;
  OldColor : TBZColor;
Begin
  PolygonRasterizer := TBZ2DPolygonTool.Create;
  Try
    PolygonRasterizer.AssignPoints(Pts);
    Buckets := PolygonRasterizer.Rasters;
    For i := 0 To PolygonRasterizer.RastersLineCount-1 Do
    Begin
      c := High(Buckets[i]);
      {On parcours la liste}
      For j := 0 To c Do
      Begin
        DrawLineBrush(Buckets[i][J].xStart, I + PolygonRasterizer.StartY , Buckets[i][J].xEnd);
      End;
    End;
    // On Dessine le contour avec la couleur de fond
    if FPen.Style = ssClear then
    begin
      OldWidth := FPen.Width;
      OldColor := FPen.Color;
      FPen.Width := 1;
      FPen.Color := FBrush.Color;
      if Antialias  then DrawAntiaAliasPolyLine(Pts, True) else DrawPolyLine(Pts, True);
      FPen.Width := OldWidth;
      FPen.Color := OldColor;
    end;
  Finally
    FreeAndNil(PolygonRasterizer);
  End;
end;

Merci d'avance pour votre aide

Jérôme

**wiwaxia** · 17/01/2020, 07h41

Bonjour,

Le fait d'avoir pris un polygone croisé n'aurait-il pas de l'importance ?

Le croisement se produit au niveau des arêtes (4,5) et (9:0); il pourrait être supprimé en inversant le sens de l'indexation de la partie interne:

Nom : Polygone_1_2.png
Affichages : 566
Taille : 16,2 Ko

**anapurna** · 17/01/2020, 11h03

salut

il y a quelques différence entre l'algorithme draw_fillpoly et le tiens ComputeRasters
je ne parle pas des element de langage mais de logique

de le tien
tu as

Code :

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

1
2
 
  if (Y > FStartY) then LineIntersect.Clear;

dans l'autre il remet tout a zéro a chaque boucle

Code :

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

1
2
3
4
 
   for y :=miny  to maxy do 
   begin 
       ints := 0;

autre différence

Code :

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

1
2
3
4
5
 
    if (p1.y > p2.y) then
      begin
        SwapPoint(p1,p2);
      end;

dans le drawPoly tu as

Code :

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
 
    //////////////////////////
	y1 := vy[ind1];
        y2 := vy[ind2];
	//////////////////////////
        if (y1 < y2)  then // ici on reste dans le sens 
	begin 
          x1 := vx[ind1];
          x2 := vx[ind2];
        end
	else 
	  if (y1 > y2) then  //Ici on Swap 
	  begin 
          // On inverse les indice
	    y2 := vy[ind1];
            y1 := vy[ind2];
            x2 := vx[ind1];
           x1 := vx[ind2];
        end 
	else 
          continue; // sinon on passe au suivant sans continuer le traitement

dans le tiens le cas de l’égalité n'est pas traité de la même manière

autre chose tu ne gère pas la notion de y ni de couleur dans le "RasterLine"
qui si je comprend bien devrais correspondre au drawhorzlineclip

**BeanzMaster** · 17/01/2020, 20h05

Salut

Envoyé par anapurna

salut

il y a quelques différence entre l'algorithme draw_fillpoly et le tiens ComputeRasters
je ne parle pas des element de langage mais de logique

de le tien

Envoyé par anapurna

tu as

Code :

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

1
2
 
  if (Y > FStartY) then LineIntersect.Clear;

dans l'autre il remet tout a zéro a chaque boucle

Code :

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

1
2
3
4
 
   for y :=miny  to maxy do 
   begin 
       ints := 0;

C'est la même chose ici ma liste est remise à zero et le tableau c'est un par ligne

Envoyé par anapurna

autre différence

Code :

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

1
2
3
4
5
 
    if (p1.y > p2.y) then
      begin
        SwapPoint(p1,p2);
      end;

dans le drawPoly tu as

Code :

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
 
    //////////////////////////
	y1 := vy[ind1];
        y2 := vy[ind2];
	//////////////////////////
        if (y1 < y2)  then // ici on reste dans le sens 
	begin 
          x1 := vx[ind1];
          x2 := vx[ind2];
        end
	else 
	  if (y1 > y2) then  //Ici on Swap 
	  begin 
          // On inverse les indice
	    y2 := vy[ind1];
            y1 := vy[ind2];
            x2 := vx[ind1];
           x1 := vx[ind2];
        end 
	else 
          continue; // sinon on passe au suivant sans continuer le traitement

dans le tiens le cas de l’égalité n'est pas traité de la même manière

Bien vu pour l'égalité je n'avais pas fait gaffe, mais cela ne change rien
idem pour l'inversion des X d'ailleurs je ne comprend pas pourquoi le faire ici car on trie notre tableau par la suite
en activant

Code :

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

1
2
3
4
5
if (y1 < y2)  then // ici on reste dans le sens 
	begin 
          x1 := vx[ind1];
          x2 := vx[ind2];
        end

voila le résultat, on perd 1 pixel sur la 1ere ligne

Nom : 2020-01-17_194339.png
Affichages : 287
Taille : 279 octets

pour l'égalité que j'ai rajouté cela ne change rien

Code :

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

if (p1.y = p2.y) then  continue;

le résultat est identique avec ou sans

Nom : 2020-01-17_194604.png
Affichages : 318
Taille : 270 octets

Envoyé par anapurna

autre chose tu ne gère pas la notion de y ni de couleur dans le "RasterLine"
qui si je comprend bien devrais correspondre au drawhorzlineclip

Si, si, c'est dans la 2ème méthode procedure TBZBitmapCanvas.FillPolygon(Pts : TBZArrayOfFloatPoints);

Bon j'ai modifié un tout petit peu la démarche mais le résultat est le même sur la 3ème ligne (cf dernière image ci-dessus)

Code :

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
procedure TBZ2DPolygonTool.ComputeRasters;
Var
  Y, I, K, X, XE, CurrentLine : Integer;
  Idx1, idx2 : Integer;
  LineIntersect : TBZIntegerList;
  RasterLine : TBZRasterItems;
  {$CODEALIGN VARMIN=16}
  p1, p2, Diff : TBZFloatPoint;
  {$CODEALIGN VARMIN=4}
 
  procedure SwapPoint(var A, B : TBZFloatPoint);
  Var
    {$CODEALIGN VARMIN=16}
    Temp : TBZFloatPoint;
    {$CODEALIGN VARMIN=4}
  begin
    Temp := A;
    A := B;
    B := Temp;
  end;
 
begin
  FBounds := ComputeBounds;
  FRastersLineCount  := (FBounds.AsRect.Bottom - FBounds.AsRect.Top) + 1; // FBounds.AsRect.Height + 1; //  
  FStartY := FBounds.AsRect.Top;
 
  LineIntersect := TBZIntegerList.Create(12);
 
  SetLength(FRasters, FRastersLineCount);
  CurrentLine := 0;
  for  Y := FBounds.AsRect.Top to FBounds.AsRect.Bottom do
  begin    
    if (Y > FStartY) then LineIntersect.Clear;
    I := 0;
    for I := 0 to FPoints.Count - 1 do
    begin
      Idx1 := I;
      if (I = (FPoints.Count - 1)) then Idx2 := 0 else Idx2 := I + 1;
 
      p1 := FPoints.Items[idx1];
      p2 := FPoints.Items[idx2];
 
      //if (p1.y = p2.y) then  continue;
 
      //if (p1.y < p2.y) then
      //begin
      //  t := p1.x;
      //  p1.x := p2.x;
      //  p2.x := t;
      //end
      //else
      if (p1.y > p2.y) then
      begin
        SwapPoint(p1,p2);        
      end;
 
      if ((y >= p1.y) And (y < p2.y)) then  // METHODE A
      begin
        Diff := p2 - p1;
        X := Round((y-p1.y) * Diff.X / Diff.Y + p1.x);       
        LineIntersect.Add(X);       
      end
      else if ((y = FBounds.AsRect.Bottom) And (y > p1.y) And (y <= p2.y)) then // METHODE B
      begin
        Diff := p2 - p1;
        X := Round((y-p1.y) * Diff.X / Diff.Y + p1.x);        
        LineIntersect.Add(X);        
      end;      
    end;
 
    LineIntersect.Sort(0,@CompareInteger);
    SetLength(RasterLine, (LineIntersect.Count shr 1) );
    I := 0;
    K := 0;
    While (I < LineIntersect.Count-1) do
    begin
      X := LineIntersect.Items[I];
      XE := LineIntersect.Items[I+1];      
      RasterLine[K].xStart := X;
      RasterLine[K].xEnd := XE;      
      Inc(K);      
      Inc(I,2);
    end;
    FRasters[CurrentLine] := RasterLine;
    SetLength(RasterLine,0);
    Inc(CurrentLine);
  end;
  FreeAndNil(LineIntersect);
end;

J'ai généré un log histoire de voir (la 3ème ligne c'est la ligne 8)

Code :

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
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
[NOTICE]   [ 19:45:10 ] FillStrokePolygon
[NOTICE]   [ 19:45:10 ] =============================================
[STATUS]  Pts 0(X: 6.00000 ,Y: 6.00000)
[STATUS]  Pts 1(X: 14.00000 ,Y: 6.00000)
[STATUS]  Pts 2(X: 14.00000 ,Y: 14.00000)
[STATUS]  Pts 3(X: 6.00000 ,Y: 14.00000)
[STATUS]  Pts 4(X: 6.00000 ,Y: 6.00000)
[STATUS]  Pts 5(X: 8.00000 ,Y: 8.00000)
[STATUS]  Pts 6(X: 8.00000 ,Y: 12.00000)
[STATUS]  Pts 7(X: 12.00000 ,Y: 12.00000)
[STATUS]  Pts 8(X: 12.00000 ,Y: 8.00000)
[STATUS]  Pts 9(X: 8.00000 ,Y: 8.00000)
[NOTICE]   [ 19:45:10 ] ====[ PolygonRasterizer.Rasters ]=========================================
[NOTICE]   [ 19:45:10 ] ====[ TBZ2DPolygonTool.ComputeRasters ]=========================================
[STATUS]  Bounds = (Left : 6.00000 ,Top : 6.00000 ,Right : 14.00000 ,Bottom : 14.00000)
[STATUS]  RastersLineCount = 9
[STATUS]  
[STATUS]  =====[ LINE : 6 ]===============================
[STATUS]  =====[ POINT : 0 ]===============================
[STATUS]  Index1 : 0 P1 = (X: 6.00000 ,Y: 6.00000)
[STATUS]  Index2 : 1 P2 = (X: 14.00000 ,Y: 6.00000)
[STATUS]  =====[ POINT : 1 ]===============================
[STATUS]  Index1 : 1 P1 = (X: 14.00000 ,Y: 6.00000)
[STATUS]  Index2 : 2 P2 = (X: 14.00000 ,Y: 14.00000)
[STATUS]  =====> Add Intersection (A) : 14
[STATUS]  =====[ POINT : 2 ]===============================
[STATUS]  Index1 : 2 P1 = (X: 14.00000 ,Y: 14.00000)
[STATUS]  Index2 : 3 P2 = (X: 6.00000 ,Y: 14.00000)
[STATUS]  =====[ POINT : 3 ]===============================
[STATUS]  Index1 : 3 P1 = (X: 6.00000 ,Y: 14.00000)
[STATUS]  Index2 : 4 P2 = (X: 6.00000 ,Y: 6.00000)
[STATUS]  =====> Swap point
[STATUS]  =====> Add Intersection (A) : 6
[STATUS]  =====[ POINT : 4 ]===============================
[STATUS]  Index1 : 4 P1 = (X: 6.00000 ,Y: 6.00000)
[STATUS]  Index2 : 5 P2 = (X: 8.00000 ,Y: 8.00000)
[STATUS]  =====> Add Intersection (A) : 6
[STATUS]  =====[ POINT : 5 ]===============================
[STATUS]  Index1 : 5 P1 = (X: 8.00000 ,Y: 8.00000)
[STATUS]  Index2 : 6 P2 = (X: 8.00000 ,Y: 12.00000)
[STATUS]  =====[ POINT : 6 ]===============================
[STATUS]  Index1 : 6 P1 = (X: 8.00000 ,Y: 12.00000)
[STATUS]  Index2 : 7 P2 = (X: 12.00000 ,Y: 12.00000)
[STATUS]  =====[ POINT : 7 ]===============================
[STATUS]  Index1 : 7 P1 = (X: 12.00000 ,Y: 12.00000)
[STATUS]  Index2 : 8 P2 = (X: 12.00000 ,Y: 8.00000)
[STATUS]  =====> Swap point
[STATUS]  =====[ POINT : 8 ]===============================
[STATUS]  Index1 : 8 P1 = (X: 12.00000 ,Y: 8.00000)
[STATUS]  Index2 : 9 P2 = (X: 8.00000 ,Y: 8.00000)
[STATUS]  =====[ POINT : 9 ]===============================
[STATUS]  Index1 : 9 P1 = (X: 8.00000 ,Y: 8.00000)
[STATUS]  Index2 : 0 P2 = (X: 6.00000 ,Y: 6.00000)
[STATUS]  =====> Swap point
[STATUS]  =====> Add Intersection (A) : 6
[STATUS]  ---------------------------
[STATUS]  COUNT SEG = 2
[STATUS]  Line : 0 --> Segments[0] Start = 6 End = 6
[STATUS]  Line : 0 --> Segments[1] Start = 6 End = 14
[STATUS]  
[STATUS]  =====[ LINE : 7 ]===============================
[STATUS]  =====[ POINT : 0 ]===============================
[STATUS]  Index1 : 0 P1 = (X: 6.00000 ,Y: 6.00000)
[STATUS]  Index2 : 1 P2 = (X: 14.00000 ,Y: 6.00000)
[STATUS]  =====[ POINT : 1 ]===============================
[STATUS]  Index1 : 1 P1 = (X: 14.00000 ,Y: 6.00000)
[STATUS]  Index2 : 2 P2 = (X: 14.00000 ,Y: 14.00000)
[STATUS]  =====> Add Intersection (A) : 14
[STATUS]  =====[ POINT : 2 ]===============================
[STATUS]  Index1 : 2 P1 = (X: 14.00000 ,Y: 14.00000)
[STATUS]  Index2 : 3 P2 = (X: 6.00000 ,Y: 14.00000)
[STATUS]  =====[ POINT : 3 ]===============================
[STATUS]  Index1 : 3 P1 = (X: 6.00000 ,Y: 14.00000)
[STATUS]  Index2 : 4 P2 = (X: 6.00000 ,Y: 6.00000)
[STATUS]  =====> Swap point
[STATUS]  =====> Add Intersection (A) : 6
[STATUS]  =====[ POINT : 4 ]===============================
[STATUS]  Index1 : 4 P1 = (X: 6.00000 ,Y: 6.00000)
[STATUS]  Index2 : 5 P2 = (X: 8.00000 ,Y: 8.00000)
[STATUS]  =====> Add Intersection (A) : 7
[STATUS]  =====[ POINT : 5 ]===============================
[STATUS]  Index1 : 5 P1 = (X: 8.00000 ,Y: 8.00000)
[STATUS]  Index2 : 6 P2 = (X: 8.00000 ,Y: 12.00000)
[STATUS]  =====[ POINT : 6 ]===============================
[STATUS]  Index1 : 6 P1 = (X: 8.00000 ,Y: 12.00000)
[STATUS]  Index2 : 7 P2 = (X: 12.00000 ,Y: 12.00000)
[STATUS]  =====[ POINT : 7 ]===============================
[STATUS]  Index1 : 7 P1 = (X: 12.00000 ,Y: 12.00000)
[STATUS]  Index2 : 8 P2 = (X: 12.00000 ,Y: 8.00000)
[STATUS]  =====> Swap point
[STATUS]  =====[ POINT : 8 ]===============================
[STATUS]  Index1 : 8 P1 = (X: 12.00000 ,Y: 8.00000)
[STATUS]  Index2 : 9 P2 = (X: 8.00000 ,Y: 8.00000)
[STATUS]  =====[ POINT : 9 ]===============================
[STATUS]  Index1 : 9 P1 = (X: 8.00000 ,Y: 8.00000)
[STATUS]  Index2 : 0 P2 = (X: 6.00000 ,Y: 6.00000)
[STATUS]  =====> Swap point
[STATUS]  =====> Add Intersection (A) : 7
[STATUS]  ---------------------------
[STATUS]  COUNT SEG = 2
[STATUS]  Line : 1 --> Segments[0] Start = 6 End = 7
[STATUS]  Line : 1 --> Segments[1] Start = 7 End = 14
[STATUS]  
[STATUS]  =====[ LINE : 8 ]===============================
[STATUS]  =====[ POINT : 0 ]===============================
[STATUS]  Index1 : 0 P1 = (X: 6.00000 ,Y: 6.00000)
[STATUS]  Index2 : 1 P2 = (X: 14.00000 ,Y: 6.00000)
[STATUS]  =====[ POINT : 1 ]===============================
[STATUS]  Index1 : 1 P1 = (X: 14.00000 ,Y: 6.00000)
[STATUS]  Index2 : 2 P2 = (X: 14.00000 ,Y: 14.00000)
[STATUS]  =====> Add Intersection (A) : 14
[STATUS]  =====[ POINT : 2 ]===============================
[STATUS]  Index1 : 2 P1 = (X: 14.00000 ,Y: 14.00000)
[STATUS]  Index2 : 3 P2 = (X: 6.00000 ,Y: 14.00000)
[STATUS]  =====[ POINT : 3 ]===============================
[STATUS]  Index1 : 3 P1 = (X: 6.00000 ,Y: 14.00000)
[STATUS]  Index2 : 4 P2 = (X: 6.00000 ,Y: 6.00000)
[STATUS]  =====> Swap point
[STATUS]  =====> Add Intersection (A) : 6
[STATUS]  =====[ POINT : 4 ]===============================
[STATUS]  Index1 : 4 P1 = (X: 6.00000 ,Y: 6.00000)
[STATUS]  Index2 : 5 P2 = (X: 8.00000 ,Y: 8.00000)
[STATUS]  =====[ POINT : 5 ]===============================
[STATUS]  Index1 : 5 P1 = (X: 8.00000 ,Y: 8.00000)
[STATUS]  Index2 : 6 P2 = (X: 8.00000 ,Y: 12.00000)
[STATUS]  =====> Add Intersection (A) : 8
[STATUS]  =====[ POINT : 6 ]===============================
[STATUS]  Index1 : 6 P1 = (X: 8.00000 ,Y: 12.00000)
[STATUS]  Index2 : 7 P2 = (X: 12.00000 ,Y: 12.00000)
[STATUS]  =====[ POINT : 7 ]===============================
[STATUS]  Index1 : 7 P1 = (X: 12.00000 ,Y: 12.00000)
[STATUS]  Index2 : 8 P2 = (X: 12.00000 ,Y: 8.00000)
[STATUS]  =====> Swap point
[STATUS]  =====> Add Intersection (A) : 12
[STATUS]  =====[ POINT : 8 ]===============================
[STATUS]  Index1 : 8 P1 = (X: 12.00000 ,Y: 8.00000)
[STATUS]  Index2 : 9 P2 = (X: 8.00000 ,Y: 8.00000)
[STATUS]  =====[ POINT : 9 ]===============================
[STATUS]  Index1 : 9 P1 = (X: 8.00000 ,Y: 8.00000)
[STATUS]  Index2 : 0 P2 = (X: 6.00000 ,Y: 6.00000)
[STATUS]  =====> Swap point
[STATUS]  ---------------------------
[STATUS]  COUNT SEG = 2
[STATUS]  Line : 2 --> Segments[0] Start = 6 End = 8
[STATUS]  Line : 2 --> Segments[1] Start = 12 End = 14
[STATUS]  
[STATUS]  =====[ LINE : 9 ]===============================
[STATUS]  =====[ POINT : 0 ]===============================
[STATUS]  Index1 : 0 P1 = (X: 6.00000 ,Y: 6.00000)
[STATUS]  Index2 : 1 P2 = (X: 14.00000 ,Y: 6.00000)
[STATUS]  =====[ POINT : 1 ]===============================
[STATUS]  Index1 : 1 P1 = (X: 14.00000 ,Y: 6.00000)
[STATUS]  Index2 : 2 P2 = (X: 14.00000 ,Y: 14.00000)
[STATUS]  =====> Add Intersection (A) : 14
[STATUS]  =====[ POINT : 2 ]===============================
[STATUS]  Index1 : 2 P1 = (X: 14.00000 ,Y: 14.00000)
[STATUS]  Index2 : 3 P2 = (X: 6.00000 ,Y: 14.00000)
[STATUS]  =====[ POINT : 3 ]===============================
[STATUS]  Index1 : 3 P1 = (X: 6.00000 ,Y: 14.00000)
[STATUS]  Index2 : 4 P2 = (X: 6.00000 ,Y: 6.00000)
[STATUS]  =====> Swap point
[STATUS]  =====> Add Intersection (A) : 6
[STATUS]  =====[ POINT : 4 ]===============================
[STATUS]  Index1 : 4 P1 = (X: 6.00000 ,Y: 6.00000)
[STATUS]  Index2 : 5 P2 = (X: 8.00000 ,Y: 8.00000)
[STATUS]  =====[ POINT : 5 ]===============================
[STATUS]  Index1 : 5 P1 = (X: 8.00000 ,Y: 8.00000)
[STATUS]  Index2 : 6 P2 = (X: 8.00000 ,Y: 12.00000)
[STATUS]  =====> Add Intersection (A) : 8
[STATUS]  =====[ POINT : 6 ]===============================
[STATUS]  Index1 : 6 P1 = (X: 8.00000 ,Y: 12.00000)
[STATUS]  Index2 : 7 P2 = (X: 12.00000 ,Y: 12.00000)
[STATUS]  =====[ POINT : 7 ]===============================
[STATUS]  Index1 : 7 P1 = (X: 12.00000 ,Y: 12.00000)
[STATUS]  Index2 : 8 P2 = (X: 12.00000 ,Y: 8.00000)
[STATUS]  =====> Swap point
[STATUS]  =====> Add Intersection (A) : 12
[STATUS]  =====[ POINT : 8 ]===============================
[STATUS]  Index1 : 8 P1 = (X: 12.00000 ,Y: 8.00000)
[STATUS]  Index2 : 9 P2 = (X: 8.00000 ,Y: 8.00000)
[STATUS]  =====[ POINT : 9 ]===============================
[STATUS]  Index1 : 9 P1 = (X: 8.00000 ,Y: 8.00000)
[STATUS]  Index2 : 0 P2 = (X: 6.00000 ,Y: 6.00000)
[STATUS]  =====> Swap point
[STATUS]  ---------------------------
[STATUS]  COUNT SEG = 2
[STATUS]  Line : 3 --> Segments[0] Start = 6 End = 8
[STATUS]  Line : 3 --> Segments[1] Start = 12 End = 14
[STATUS]  
[STATUS]  =====[ LINE : 10 ]===============================
[STATUS]  =====[ POINT : 0 ]===============================
[STATUS]  Index1 : 0 P1 = (X: 6.00000 ,Y: 6.00000)
[STATUS]  Index2 : 1 P2 = (X: 14.00000 ,Y: 6.00000)
[STATUS]  =====[ POINT : 1 ]===============================
[STATUS]  Index1 : 1 P1 = (X: 14.00000 ,Y: 6.00000)
[STATUS]  Index2 : 2 P2 = (X: 14.00000 ,Y: 14.00000)
[STATUS]  =====> Add Intersection (A) : 14
[STATUS]  =====[ POINT : 2 ]===============================
[STATUS]  Index1 : 2 P1 = (X: 14.00000 ,Y: 14.00000)
[STATUS]  Index2 : 3 P2 = (X: 6.00000 ,Y: 14.00000)
[STATUS]  =====[ POINT : 3 ]===============================
[STATUS]  Index1 : 3 P1 = (X: 6.00000 ,Y: 14.00000)
[STATUS]  Index2 : 4 P2 = (X: 6.00000 ,Y: 6.00000)
[STATUS]  =====> Swap point
[STATUS]  =====> Add Intersection (A) : 6
[STATUS]  =====[ POINT : 4 ]===============================
[STATUS]  Index1 : 4 P1 = (X: 6.00000 ,Y: 6.00000)
[STATUS]  Index2 : 5 P2 = (X: 8.00000 ,Y: 8.00000)
[STATUS]  =====[ POINT : 5 ]===============================
[STATUS]  Index1 : 5 P1 = (X: 8.00000 ,Y: 8.00000)
[STATUS]  Index2 : 6 P2 = (X: 8.00000 ,Y: 12.00000)
[STATUS]  =====> Add Intersection (A) : 8
[STATUS]  =====[ POINT : 6 ]===============================
[STATUS]  Index1 : 6 P1 = (X: 8.00000 ,Y: 12.00000)
[STATUS]  Index2 : 7 P2 = (X: 12.00000 ,Y: 12.00000)
[STATUS]  =====[ POINT : 7 ]===============================
[STATUS]  Index1 : 7 P1 = (X: 12.00000 ,Y: 12.00000)
[STATUS]  Index2 : 8 P2 = (X: 12.00000 ,Y: 8.00000)
[STATUS]  =====> Swap point
[STATUS]  =====> Add Intersection (A) : 12
[STATUS]  =====[ POINT : 8 ]===============================
[STATUS]  Index1 : 8 P1 = (X: 12.00000 ,Y: 8.00000)
[STATUS]  Index2 : 9 P2 = (X: 8.00000 ,Y: 8.00000)
[STATUS]  =====[ POINT : 9 ]===============================
[STATUS]  Index1 : 9 P1 = (X: 8.00000 ,Y: 8.00000)
[STATUS]  Index2 : 0 P2 = (X: 6.00000 ,Y: 6.00000)
[STATUS]  =====> Swap point
[STATUS]  ---------------------------
[STATUS]  COUNT SEG = 2
[STATUS]  Line : 4 --> Segments[0] Start = 6 End = 8
[STATUS]  Line : 4 --> Segments[1] Start = 12 End = 14
[STATUS]  
[STATUS]  =====[ LINE : 11 ]===============================
[STATUS]  =====[ POINT : 0 ]===============================
[STATUS]  Index1 : 0 P1 = (X: 6.00000 ,Y: 6.00000)
[STATUS]  Index2 : 1 P2 = (X: 14.00000 ,Y: 6.00000)
[STATUS]  =====[ POINT : 1 ]===============================
[STATUS]  Index1 : 1 P1 = (X: 14.00000 ,Y: 6.00000)
[STATUS]  Index2 : 2 P2 = (X: 14.00000 ,Y: 14.00000)
[STATUS]  =====> Add Intersection (A) : 14
[STATUS]  =====[ POINT : 2 ]===============================
[STATUS]  Index1 : 2 P1 = (X: 14.00000 ,Y: 14.00000)
[STATUS]  Index2 : 3 P2 = (X: 6.00000 ,Y: 14.00000)
[STATUS]  =====[ POINT : 3 ]===============================
[STATUS]  Index1 : 3 P1 = (X: 6.00000 ,Y: 14.00000)
[STATUS]  Index2 : 4 P2 = (X: 6.00000 ,Y: 6.00000)
[STATUS]  =====> Swap point
[STATUS]  =====> Add Intersection (A) : 6
[STATUS]  =====[ POINT : 4 ]===============================
[STATUS]  Index1 : 4 P1 = (X: 6.00000 ,Y: 6.00000)
[STATUS]  Index2 : 5 P2 = (X: 8.00000 ,Y: 8.00000)
[STATUS]  =====[ POINT : 5 ]===============================
[STATUS]  Index1 : 5 P1 = (X: 8.00000 ,Y: 8.00000)
[STATUS]  Index2 : 6 P2 = (X: 8.00000 ,Y: 12.00000)
[STATUS]  =====> Add Intersection (A) : 8
[STATUS]  =====[ POINT : 6 ]===============================
[STATUS]  Index1 : 6 P1 = (X: 8.00000 ,Y: 12.00000)
[STATUS]  Index2 : 7 P2 = (X: 12.00000 ,Y: 12.00000)
[STATUS]  =====[ POINT : 7 ]===============================
[STATUS]  Index1 : 7 P1 = (X: 12.00000 ,Y: 12.00000)
[STATUS]  Index2 : 8 P2 = (X: 12.00000 ,Y: 8.00000)
[STATUS]  =====> Swap point
[STATUS]  =====> Add Intersection (A) : 12
[STATUS]  =====[ POINT : 8 ]===============================
[STATUS]  Index1 : 8 P1 = (X: 12.00000 ,Y: 8.00000)
[STATUS]  Index2 : 9 P2 = (X: 8.00000 ,Y: 8.00000)
[STATUS]  =====[ POINT : 9 ]===============================
[STATUS]  Index1 : 9 P1 = (X: 8.00000 ,Y: 8.00000)
[STATUS]  Index2 : 0 P2 = (X: 6.00000 ,Y: 6.00000)
[STATUS]  =====> Swap point
[STATUS]  ---------------------------
[STATUS]  COUNT SEG = 2
[STATUS]  Line : 5 --> Segments[0] Start = 6 End = 8
[STATUS]  Line : 5 --> Segments[1] Start = 12 End = 14
[STATUS]  
[STATUS]  =====[ LINE : 12 ]===============================
[STATUS]  =====[ POINT : 0 ]===============================
[STATUS]  Index1 : 0 P1 = (X: 6.00000 ,Y: 6.00000)
[STATUS]  Index2 : 1 P2 = (X: 14.00000 ,Y: 6.00000)
[STATUS]  =====[ POINT : 1 ]===============================
[STATUS]  Index1 : 1 P1 = (X: 14.00000 ,Y: 6.00000)
[STATUS]  Index2 : 2 P2 = (X: 14.00000 ,Y: 14.00000)
[STATUS]  =====> Add Intersection (A) : 14
[STATUS]  =====[ POINT : 2 ]===============================
[STATUS]  Index1 : 2 P1 = (X: 14.00000 ,Y: 14.00000)
[STATUS]  Index2 : 3 P2 = (X: 6.00000 ,Y: 14.00000)
[STATUS]  =====[ POINT : 3 ]===============================
[STATUS]  Index1 : 3 P1 = (X: 6.00000 ,Y: 14.00000)
[STATUS]  Index2 : 4 P2 = (X: 6.00000 ,Y: 6.00000)
[STATUS]  =====> Swap point
[STATUS]  =====> Add Intersection (A) : 6
[STATUS]  =====[ POINT : 4 ]===============================
[STATUS]  Index1 : 4 P1 = (X: 6.00000 ,Y: 6.00000)
[STATUS]  Index2 : 5 P2 = (X: 8.00000 ,Y: 8.00000)
[STATUS]  =====[ POINT : 5 ]===============================
[STATUS]  Index1 : 5 P1 = (X: 8.00000 ,Y: 8.00000)
[STATUS]  Index2 : 6 P2 = (X: 8.00000 ,Y: 12.00000)
[STATUS]  =====[ POINT : 6 ]===============================
[STATUS]  Index1 : 6 P1 = (X: 8.00000 ,Y: 12.00000)
[STATUS]  Index2 : 7 P2 = (X: 12.00000 ,Y: 12.00000)
[STATUS]  =====[ POINT : 7 ]===============================
[STATUS]  Index1 : 7 P1 = (X: 12.00000 ,Y: 12.00000)
[STATUS]  Index2 : 8 P2 = (X: 12.00000 ,Y: 8.00000)
[STATUS]  =====> Swap point
[STATUS]  =====[ POINT : 8 ]===============================
[STATUS]  Index1 : 8 P1 = (X: 12.00000 ,Y: 8.00000)
[STATUS]  Index2 : 9 P2 = (X: 8.00000 ,Y: 8.00000)
[STATUS]  =====[ POINT : 9 ]===============================
[STATUS]  Index1 : 9 P1 = (X: 8.00000 ,Y: 8.00000)
[STATUS]  Index2 : 0 P2 = (X: 6.00000 ,Y: 6.00000)
[STATUS]  =====> Swap point
[STATUS]  ---------------------------
[STATUS]  COUNT SEG = 1
[STATUS]  Line : 6 --> Segments[0] Start = 6 End = 14
[STATUS]  
[STATUS]  =====[ LINE : 13 ]===============================
[STATUS]  =====[ POINT : 0 ]===============================
[STATUS]  Index1 : 0 P1 = (X: 6.00000 ,Y: 6.00000)
[STATUS]  Index2 : 1 P2 = (X: 14.00000 ,Y: 6.00000)
[STATUS]  =====[ POINT : 1 ]===============================
[STATUS]  Index1 : 1 P1 = (X: 14.00000 ,Y: 6.00000)
[STATUS]  Index2 : 2 P2 = (X: 14.00000 ,Y: 14.00000)
[STATUS]  =====> Add Intersection (A) : 14
[STATUS]  =====[ POINT : 2 ]===============================
[STATUS]  Index1 : 2 P1 = (X: 14.00000 ,Y: 14.00000)
[STATUS]  Index2 : 3 P2 = (X: 6.00000 ,Y: 14.00000)
[STATUS]  =====[ POINT : 3 ]===============================
[STATUS]  Index1 : 3 P1 = (X: 6.00000 ,Y: 14.00000)
[STATUS]  Index2 : 4 P2 = (X: 6.00000 ,Y: 6.00000)
[STATUS]  =====> Swap point
[STATUS]  =====> Add Intersection (A) : 6
[STATUS]  =====[ POINT : 4 ]===============================
[STATUS]  Index1 : 4 P1 = (X: 6.00000 ,Y: 6.00000)
[STATUS]  Index2 : 5 P2 = (X: 8.00000 ,Y: 8.00000)
[STATUS]  =====[ POINT : 5 ]===============================
[STATUS]  Index1 : 5 P1 = (X: 8.00000 ,Y: 8.00000)
[STATUS]  Index2 : 6 P2 = (X: 8.00000 ,Y: 12.00000)
[STATUS]  =====[ POINT : 6 ]===============================
[STATUS]  Index1 : 6 P1 = (X: 8.00000 ,Y: 12.00000)
[STATUS]  Index2 : 7 P2 = (X: 12.00000 ,Y: 12.00000)
[STATUS]  =====[ POINT : 7 ]===============================
[STATUS]  Index1 : 7 P1 = (X: 12.00000 ,Y: 12.00000)
[STATUS]  Index2 : 8 P2 = (X: 12.00000 ,Y: 8.00000)
[STATUS]  =====> Swap point
[STATUS]  =====[ POINT : 8 ]===============================
[STATUS]  Index1 : 8 P1 = (X: 12.00000 ,Y: 8.00000)
[STATUS]  Index2 : 9 P2 = (X: 8.00000 ,Y: 8.00000)
[STATUS]  =====[ POINT : 9 ]===============================
[STATUS]  Index1 : 9 P1 = (X: 8.00000 ,Y: 8.00000)
[STATUS]  Index2 : 0 P2 = (X: 6.00000 ,Y: 6.00000)
[STATUS]  =====> Swap point
[STATUS]  ---------------------------
[STATUS]  COUNT SEG = 1
[STATUS]  Line : 7 --> Segments[0] Start = 6 End = 14
[STATUS]  
[STATUS]  =====[ LINE : 14 ]===============================
[STATUS]  =====[ POINT : 0 ]===============================
[STATUS]  Index1 : 0 P1 = (X: 6.00000 ,Y: 6.00000)
[STATUS]  Index2 : 1 P2 = (X: 14.00000 ,Y: 6.00000)
[STATUS]  =====[ POINT : 1 ]===============================
[STATUS]  Index1 : 1 P1 = (X: 14.00000 ,Y: 6.00000)
[STATUS]  Index2 : 2 P2 = (X: 14.00000 ,Y: 14.00000)
[STATUS]  =====> Add Intersection (B) : 14
[STATUS]  =====[ POINT : 2 ]===============================
[STATUS]  Index1 : 2 P1 = (X: 14.00000 ,Y: 14.00000)
[STATUS]  Index2 : 3 P2 = (X: 6.00000 ,Y: 14.00000)
[STATUS]  =====[ POINT : 3 ]===============================
[STATUS]  Index1 : 3 P1 = (X: 6.00000 ,Y: 14.00000)
[STATUS]  Index2 : 4 P2 = (X: 6.00000 ,Y: 6.00000)
[STATUS]  =====> Swap point
[STATUS]  =====> Add Intersection (B) : 6
[STATUS]  =====[ POINT : 4 ]===============================
[STATUS]  Index1 : 4 P1 = (X: 6.00000 ,Y: 6.00000)
[STATUS]  Index2 : 5 P2 = (X: 8.00000 ,Y: 8.00000)
[STATUS]  =====[ POINT : 5 ]===============================
[STATUS]  Index1 : 5 P1 = (X: 8.00000 ,Y: 8.00000)
[STATUS]  Index2 : 6 P2 = (X: 8.00000 ,Y: 12.00000)
[STATUS]  =====[ POINT : 6 ]===============================
[STATUS]  Index1 : 6 P1 = (X: 8.00000 ,Y: 12.00000)
[STATUS]  Index2 : 7 P2 = (X: 12.00000 ,Y: 12.00000)
[STATUS]  =====[ POINT : 7 ]===============================
[STATUS]  Index1 : 7 P1 = (X: 12.00000 ,Y: 12.00000)
[STATUS]  Index2 : 8 P2 = (X: 12.00000 ,Y: 8.00000)
[STATUS]  =====> Swap point
[STATUS]  =====[ POINT : 8 ]===============================
[STATUS]  Index1 : 8 P1 = (X: 12.00000 ,Y: 8.00000)
[STATUS]  Index2 : 9 P2 = (X: 8.00000 ,Y: 8.00000)
[STATUS]  =====[ POINT : 9 ]===============================
[STATUS]  Index1 : 9 P1 = (X: 8.00000 ,Y: 8.00000)
[STATUS]  Index2 : 0 P2 = (X: 6.00000 ,Y: 6.00000)
[STATUS]  =====> Swap point
[STATUS]  ---------------------------
[STATUS]  COUNT SEG = 1
[STATUS]  Line : 8 --> Segments[0] Start = 6 End = 14

On voit qu'aux points 0 et 4 un segment de 1x1 pixel de trop est créé

Pour la ligne 8 (segment[p5,p8] et qui est connecté au segment[p4,p5]) nb : le polygone intérieur est inversé par rraport à l'image de mon 1er post La portion du milieu n'est pas affecté d'ou ces 3 pixels manquants

Je pu lire que pour des polygones comlexe la méthode "pair-impair" n'est pas fiable. Je suis tombé sur ce document mon anglais étant basique je ne comprend pas clairement et ou mettre en oeuvre le test du pixel dans le polygone (je sais comment faire pour savoir si un pixel est à l'intérieur ou non)

Je suis également tombé sur ce document décrivant un algorithme "Active Edge Table" et ici que je tenterai de coder demain

Voila merci pour votre aide

A+

Jérôme

**BeanzMaster** · 18/01/2020, 16h25

Salut je reviens vers vous en cherchant sur le web hier j'ai trouvé ce document sur le "Active Edge Table" avec un code en C assez simple que j'ai convertie :

Code :

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
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
procedure TBZ2DPolygonTool.ComputeRastersAET;
Type
  PEdge = ^TEdge;
  TEdge = record
    yUpper : Integer;
    xIntersect : Single;
    Slope : Single;
    Next : PEdge;
  end;
 
Var
  EdgeTable : array of PEdge;
  ActiveEdgeTable : PEdge;
  i, idx, Scan : Integer;
 
  procedure InsertEdge(ToEdge, anEdge : PEdge);  //OK
  Var
    Edge1, Edge2 : PEdge;
  begin
    GlobalLogger.LogNotice('-----> InsertEdge');
    Edge1 := ToEdge; //q
    Edge2 := Edge1^.Next; //p
    while (Edge2 <> nil) do
    begin
      if (anEdge^.xIntersect < Edge2^.xIntersect) then
      begin
        Edge2 := nil;
      end
      else
      begin
        Edge1 := Edge2;
        GlobalLogger.LogStatus('-------> Add Edge : ' + Edge2^.xIntersect.ToString());
        Edge2 := Edge2^.Next;
      end;
    end;
    anEdge^.Next := Edge1^.Next;
    Edge1^.Next := anEdge;
  end;
 
  function GetYNext(ptIdx : Integer) : Single;  //OK
  var
    jj : Integer;
  begin
    GlobalLogger.LogNotice('----> GetYNext');
    if ((ptIdx + 1) > (FPoints.Count-1)) then
      jj := 0
    else
      jj := ptIdx + 1;
 
    While (FPoints.items[ptIdx].y = FPoints.Items[jj].y) do
    begin
      if ((jj + 1) > (FPoints.Count - 1)) then
       jj := 0
      else
       Inc(jj);
    end;
    Result := FPoints.Items[jj].y;
  end;
 
  procedure MakeEdge(LowerPt, UpperPt : TBZFloatPoint; yComp : Single; anEdge : PEdge); //OK
  Var
    {$CODEALIGN VARMIN=16}
    Diff : TBZFloatPoint;
    {$CODEALIGN VARMIN=4}
  begin
    GlobalLogger.LogNotice('---> MakeEdge');
    GlobalLogger.LogStatus('----> Lower Point = ' + LowerPt.ToString);
    GlobalLogger.LogStatus('----> Upper Point = ' + UpperPt.ToString);
    Diff := UpperPt - LowerPt;
    GlobalLogger.LogStatus('----> Diff Point  = ' + Diff.ToString);
    anEdge^.Slope := Diff.x / Diff.y; //(UpperPt.X - LowerPt.X) / (UpperPt.y - UpperPt.y);
    anEdge^.xIntersect := LowerPt.x;
    GlobalLogger.LogStatus('----> Slope      = ' + anEdge^.Slope.ToString());
    GlobalLogger.LogStatus('----> xIntersect = ' + anEdge^.xIntersect.ToString());
    if (UpperPt.y < yComp) then
      anEdge^.yUpper := Round(UpperPt.y) - 1
    else
      anEdge^.yUpper := Round(UpperPt.y);
 
    //anEdge^.Next := nil;
 
    GlobalLogger.LogStatus('-----> InsertEdge at : ' + (Round(LowerPt.y)-FBounds.AsRect.Top).ToString +' == ' +anEdge^.xIntersect.ToString());
    InsertEdge(EdgeTable[Round(LowerPt.y)-FBounds.AsRect.Top], anEdge);
  end;
 
  procedure BuildEdgeTable; //OK
  var
    {$CODEALIGN VARMIN=16}
    p1, p2 : TBZFloatPoint;
    {$CODEALIGN VARMIN=4}
    CurrentEdge : PEdge;
    yPrev : Single;
    J : Integer;
  begin
    GlobalLogger.LogNotice('--> BuildEdgeTable');
    Idx := FPoints.Count - 2;
    yPrev := FPoints.Items[Idx].Y;
    P1 := FPoints.Last;
 
    For J := 0 to (FPoints.Count - 1) do
    begin
      p2 := FPoints.Items[J];
      if (p1.y <> p2.y) then
      begin
         CurrentEdge := nil;
         New(CurrentEdge); //GetMem(CurrentEdge, Sizeof(TEdge));
         CurrentEdge^.Next := nil;
        if (p1.y < p2.y) then
          MakeEdge(p1, p2, GetYnext(J),CurrentEdge)
        else
          MakeEdge(p2, p1, yPrev,CurrentEdge);
      end;
      yPrev := p1.y;
      p1 := p2;
    end;
  end;
 
  procedure DeleteAfter(anEdge : PEdge); // OK
  Var
    Edge1 : PEdge;
  begin
    GlobalLogger.LogNotice('-----> DeleteAfter');
    Edge1 := anEdge^.Next;
    anEdge^.Next := Edge1^.Next;
    if (Edge1 <> nil) then Dispose(Edge1);
  end;
 
  procedure UpdateActiveEdgeTable(CurrentY : Integer; anActiveEdge : PEdge); // OK
  Var
    Edge1, Edge2 : PEdge;
  begin
    GlobalLogger.LogNotice('---> UpdateActiveEdgeTable');
    Edge1 := anActiveEdge;  //q
    Edge2 := anActiveEdge^.Next; //p
    while (Edge2 <> nil) do
    begin
      if (CurrentY >= Edge2^.yUpper) then
      begin
        Edge2 := Edge2^.Next;
        DeleteAfter(Edge1);
      end
      else
      begin
        Edge2^.xIntersect := Edge2^.xIntersect + Edge2^.Slope;
        Edge1 := Edge2;
        GlobalLogger.LogStatus('---> New Intersection = ' + Edge1^.xIntersect.ToString());
        Edge2 := Edge2^.Next;
      end;
    end;
  end;
 
  procedure SortActiveEdgeTable(anActiveEdge : PEdge); // OK
  Var
    Edge1, Edge2 : PEdge;
  begin
    GlobalLogger.LogNotice('---> SortActiveEdgeTable');
    Edge1 := anActiveEdge^.Next;  //p
    anActiveEdge^.Next := nil;
    while (Edge1 <> nil) do
    begin
      Edge2 := Edge1^.Next;
      insertEdge (anActiveEdge, Edge1);
      Edge1 := Edge2;
    end;
  end;
 
  procedure FillBuckets(CurrentLine : Integer; anActiveEdge : PEdge);  // OK
  Var
    Edge1, Edge2 : PEdge;
    RasterLine : TBZRasterItems;
    K : Integer;
  begin
    GlobalLogger.LogNotice('---> FillBuckets');
    Edge2 := nil;
    Edge1 := anActiveEdge^.Next;
    K := 0;
    while (Edge1 <> nil) do
    begin
 
      Edge2 := Edge1^.Next;
      if (Edge2 <> nil) then
      begin
        SetLength(RasterLine, K + 1);
        RasterLine[K].xStart := Round(Edge1^.xIntersect);
        RasterLine[K].xEnd := Round(Edge2^.xIntersect);
        inc(K);
        Edge1 := Edge2^.Next;
      end
      else
        Edge1 := Edge1^.Next;
 
    end;
    FRasters[CurrentLine] := RasterLine;
    SetLength(RasterLine, 0);
    RasterLine := nil;
  end;
 
  procedure BuildActiveEdgeTable(anIdx : Integer; anActiveEdge : PEdge);  // OK
  Var
    Edge1, Edge2 : PEdge;
  begin
    GlobalLogger.LogNotice('---> BuildActiveEdgeTable');
    Edge2 := nil;
    Edge1 := EdgeTable[anIdx]^.Next;
    While (Edge1<>nil) do
    begin
      Edge2 := Edge1^.Next;
      InsertEdge(anActiveEdge, Edge1);
      Edge1 := Edge2;
    end;
 end;
 
begin
  GlobalLogger.LogNotice('=====[ TBZ2DPolygonTool.ComputeRastersAET ]==========================');
  FBounds := ComputeBounds;
  FRastersLineCount  := (FBounds.AsRect.Bottom - FBounds.AsRect.Top) + 1; // FBounds.AsRect.Height + 1;
  FStartY := FBounds.AsRect.Top;
  SetLength(EdgeTable, FRastersLineCount);
  SetLength(FRasters, FRastersLineCount);
  For i := 0 to FRastersLineCount-1 do
  begin
    EdgeTable[i] := nil;
    New(EdgeTable[i]); //GetMem(EdgeTable[i], Sizeof(TEdge));
    EdgeTable[i]^.Next := nil;
  end;
 
  BuildEdgeTable;
 
  ActiveEdgeTable := nil;
  New(ActiveEdgeTable); // GetMem(ActiveEdgeTable, Sizeof(TEdge));
  ActiveEdgeTable^.Next := nil;
  GlobalLogger.LogNotice('===> START SCANNING');
  for i := FBounds.AsRect.Top to FBounds.AsRect.Bottom do
  Begin
    Scan := i - FBounds.AsRect.Top;
    GlobalLogger.LogStatus('');
    GlobalLogger.LogStatus('===== Line ['+ i.ToString + '] ======================');
 
    BuildActiveEdgeTable(Scan , ActiveEdgeTable);
    FillBuckets(Scan, ActiveEdgeTable);
    UpdateActiveEdgeTable(I, ActiveEdgeTable);
    SortActiveEdgeTable(ActiveEdgeTable);
 
  end;
  GlobalLogger.LogNotice('===> END SCANNING');
 
  For i := FRastersLineCount-1 downto 0 do
  begin
    if (EdgeTable[i] <> nil) then
    begin
      Dispose(EdgeTable[i]); //FreeMem(EdgeTable[i]);
      EdgeTable[i] := nil;
    end;
  end;
  if (ActiveEdgeTable <> nil) then
  begin
    Dispose(ActiveEdgeTable); //FreeMem(ActiveEdgeTable);
    ActiveEdgeTable := nil;
  end;
  SetLength(EdgeTable, 0);
  EdgeTable := nil;
end;

Il y a toujours des problèmes de remplissage, mais ceux-ci ne sont pas situés au même endroit

Nom : 2020-01-18_162012.png
Affichages : 281
Taille : 283 octets

Nom : 2020-01-18_162012.png
Affichages : 281
Taille : 283 octets

Je vais tenter une approche différente du AET. Mais j'espère qu'il y a une autre solution que la triangulation

A+

Jérôme

**BeanzMaster** · 18/01/2020, 17h12

Voila un petit test avec les 2 algos en rouge l'AET et en bleu le 1er sur un polygone avec une intersection des contours

Contour avec épaisseur de 1 pixel

Nom : 2020-01-18_170039.png
Affichages : 349
Taille : 3,3 Ko

Nom : 2020-01-18_170039.png
Affichages : 349
Taille : 3,3 Ko

Nom : 2020-01-18_170258.png
Affichages : 310
Taille : 3,6 Ko

Les 2 algorithmes donnes des résultats similaires

Contour avec épaisseur de 3 pixels

Nom : 2020-01-18_165818.png
Affichages : 300
Taille : 3,6 Ko

Nom : 2020-01-18_170411.png
Affichages : 267
Taille : 3,6 Ko

Ici le 1er est meilleur, il y a juste le point à l'intersection, dans le cas de l'AET gros couac en haut et à l'intersection il y a un pixel de plus qui est remplis.

Compliqué cette histoire, je vais tester et jeter un oeil, dès que j'ai le temps à la bibliothèque Clipper mais j'aimerai m'en passer

A+

Jérôme

**BeanzMaster** · 17/01/2020, 19h38

Envoyé par wiwaxia

Bonjour,

Le fait d'avoir pris un polygone croisé n'aurait-il pas de l'importance ?

Le croisement se produit au niveau des arêtes (4,5) et (9:0); il pourrait être supprimé en inversant le sens de l'indexation de la partie interne:

Hum, je ne sait pas trop si je pourrais faire comme ça car en fait mon polygone est généré depuis une polyline (pour chaque ligne je trace "virtuellement" sa parallèle à un distance X et je cherche l'intersection de 2 segment consécutifs pour obtenir le nouveau point qui se trouve à l'extérieur ) j'ajoute donc les points trouvé 1 à 1 et une fois revenu à l'indice 0 je le joins au point 0 du polygone de base et ajoutes les points de celui-ci dans l'odre ou (ordre inverse, cela ne change rien au problème de remplissage)

Faudrait que je regardes comment changer ma méthode sans trop sacrifié les performances

Code :

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
197
198
199
200
201
202
203
204
205
206
207
function TBZ2DPolyLineTool.BuildStroke : TBZArrayOfFloatPoints;
Type
  TStrokeLineInfos = packed record
    LeftPerp  : Array[0..1] of TBZVector2f;
    RightPerp : Array[0..1] of TBZVector2f;
    StartPoint, EndPoint : TBZVector2f;
    LeftIntersectPoint : TBZVector2f;
    RightIntersectPoint : TBZVector2f;    
    NormalizeDirection : TBZVector2f;
  end;
  TArrayOfLines = Array of TBZ2DLineTool;
var
  Width : Single;
  //OutPoints : TBZArrayOfFloatPoints; // Closed path for polygon
  LinesInfos : Array of TStrokeLineInfos;
  Lines : TArrayOfLines;
 
  procedure FreeLines;
  var
    n, i : Integer;
  begin
    n := High(Lines);
    For i := n downto 0 do
    begin
      FreeAndNil(Lines[i]);
    end;
    Lines := nil;
  end;
 
  function ConvertPointsToLines : TArrayOfLines;
  Var
    n, i, k: Integer;
 
  Begin
    n := FCount;
    if not(FClosePath) then
    begin
      n := FCount-1;
    end
    else
    begin
      FPoints.Add(FPoints.Items[0]);
      FCount := FPoints.Count;
      n:= FCount -1;
    end;
 
    SetLength(Result,n);
 
    if (n=1) then
    begin
      Result[0] := TBZ2DLineTool.Create;
      Result[0].SetLineFromPoints(FPoints.Items[0], FPoints.Items[1]);
    end
    else
    begin
      For i := 0 To n-1 Do
      Begin
        k := (i + 1) Mod n;
 
        if not(FClosePath) then if k=0 then k:=n;
        Result[i] := TBZ2DLineTool.Create;
        Result[i].SetLineFromPoints(FPoints.Items[i], FPoints.Items[k]);
      End;
    end;
  End;
 
  procedure ComputeLinesInfos;
  Var
    n, i : Integer;
    CloseLeftPoint, CloseRightPoint : TBZVector2f;
    LineSlope : Single;
    LineA, LineB : TBZ2DLineTool;
  begin
    n := High(Lines)+1;
 
    Setlength(LinesInfos,n);
 
    if (n=1) then
    begin
	  // 1 seule ligne
      LinesInfos[0].StartPoint := Lines[0].StartPoint;
      LinesInfos[0].EndPoint   := Lines[0].EndPoint;
      LinesInfos[0].NormalizeDirection := Lines[0].GetNormalizeDirection;
      Lines[0].GetPerpendicularPointsAtStartPoint(Width,LinesInfos[0].LeftPerp[0],LinesInfos[0].RightPerp[0]);
      Lines[0].GetPerpendicularPointsAtEndPoint(Width,LinesInfos[0].LeftPerp[1],LinesInfos[0].RightPerp[1]);
      LinesInfos[0].LeftIntersectPoint := cNullVector2f;
      LinesInfos[0].RightIntersectPoint := cNullVector2f;
 
    end
    else
    begin
      for i := 0 to n-1 do
      begin
 
        LinesInfos[i].StartPoint := Lines[i].StartPoint;
        LinesInfos[i].EndPoint   := Lines[i].EndPoint;
 
        LinesInfos[i].NormalizeDirection := Lines[i].GetNormalizeDirection;
 
        Lines[i].GetPerpendicularPointsAtStartPoint(Width,LinesInfos[i].LeftPerp[0],LinesInfos[i].RightPerp[0]);
        Lines[i].GetPerpendicularPointsAtEndPoint(Width,LinesInfos[i].LeftPerp[1],LinesInfos[i].RightPerp[1]);
        LinesInfos[i].LeftIntersectPoint := cNullVector2f;
        LinesInfos[i].RightIntersectPoint := cNullVector2f;
      end;
 
      // Trouve les points d'intersection
      LineA := TBZ2DLineTool.Create;
      LineB := TBZ2DLineTool.Create;
      For i := 1 to n-1 do
      begin
        // Left
        LineA.SetLineFromPoints(LinesInfos[i-1].LeftPerp[0], LinesInfos[i-1].LeftPerp[1]);
        LineB.SetLineFromPoints(LinesInfos[i].LeftPerp[0], LinesInfos[i].LeftPerp[1]);
        LineA.GetInfiniteIntersectPoint(LineB,LinesInfos[i].LeftIntersectPoint);
 
        // Right
        LineA.SetLineFromPoints(LinesInfos[i-1].RightPerp[0], LinesInfos[i-1].RightPerp[1]);
        LineB.SetLineFromPoints(LinesInfos[i].RightPerp[0], LinesInfos[i].RightPerp[1]);
        LineA.GetInfiniteIntersectPoint(LineB,LinesInfos[i].RightIntersectPoint);
      end;
 
      if FClosePath then
      begin
        //Left
        LineA.SetLineFromPoints(LinesInfos[0].LeftPerp[0], LinesInfos[0].LeftPerp[1]);
        LineB.SetLineFromPoints(LinesInfos[n-1].LeftPerp[0], LinesInfos[n-1].LeftPerp[1]);
        LineA.GetInfiniteIntersectPoint(LineB,CloseLeftPoint);
 
        // Right
        LineA.SetLineFromPoints(LinesInfos[0].RightPerp[0], LinesInfos[0].RightPerp[1]);
        LineB.SetLineFromPoints(LinesInfos[n-1].RightPerp[0], LinesInfos[n-1].RightPerp[1]);
        LineA.GetInfiniteIntersectPoint(LineB,CloseRightPoint);
 
        LinesInfos[0].LeftPerp[0] := CloseLeftPoint;
        LinesInfos[0].RightPerp[0] := CloseRightPoint;
        LinesInfos[n-1].LeftPerp[1] := CloseLeftPoint;
        LinesInfos[n-1].RightPerp[1] := CloseRightPoint;
      end;
      FreeAndNil(LineB);
      FreeAndNil(LineA);
    end;
  end;
 
  function ComputeOuterStroke : TBZArrayOfFloatPoints;
  Var
    idx, n, i,nn : Integer;
    OutPoints :TBZArrayOfFloatPoints;
  begin
    nn := FCount * 2;
    OutPoints := TBZArrayOfFloatPoints.Create(nn);
    n := High(LinesInfos);
 
    // Premiers Points --> LIGNE OUVERTE
    OutPoints.Add(LinesInfos[0].RightPerp[0]);
 
    idx := 1;
    for i:=1 to n do
    begin
      OutPoints.Add(LinesInfos[i].RightIntersectPoint);      
      inc(idx);
    end;
    // Derniers Points
    OutPoints.Add(LinesInfos[n].RightPerp[1]);
    inc(idx);
    OutPoints.Add(LinesInfos[n].EndPoint);
    inc(idx);
 
    for i := FCount-2 downto 1 do
    //for i := 1 to FCount-2 do
    begin
      OutPoints.Add(FPoints.Items[i]);   
      inc(idx);
    end;
    OutPoints.Add(FPoints.Items[0]);
    Result := OutPoints;
  end; 
 
begin
 
  Lines := ConvertPointsToLines;
 
  Case FStrokeMode of
    smInner :
    begin
      Width := FStrokeWidth;
      ComputeLinesInfos;
      Result := ComputeInnerStroke;
    end;
    smOuter :
    begin
      Width := FStrokeWidth-1;
      ComputeLinesInfos;
      Result := ComputeOuterStroke;
    end;
    smAround :
    begin
      Width := (FStrokeWidth * 0.5);
      ComputeLinesInfos;
      Result := ComputeAroundStroke;
    end;
  end;
 
  FreeLines;
  Setlength(LinesInfos,0);
  LinesInfos := nil;
 
end;

**wiwaxia** · 21/01/2020, 08h48

Envoyé par BeanzMaster

... car en fait mon polygone est généré depuis une polyline (pour chaque ligne je trace "virtuellement" sa parallèle à un distance X et je cherche l'intersection de 2 segment consécutifs pour obtenir le nouveau point qui se trouve à l'extérieur ) j'ajoute donc les points trouvé 1 à 1 et une fois revenu à l'indice 0 je le joins au point 0 du polygone de base et ajoutes les points de celui-ci dans l'odre ou (ordre inverse, cela ne change rien au problème de remplissage) ...

Qu'est-ce qu'une polyline ? Par quel type de données le polygone est-il défini ?
Ne pourrait-on envisager plus simplement un tableau des coordonnées des sommets ?
Il existe un procédé simple de remplissage, indifférent à la présence de croisements ou de points doubles - mais ce n'est probablement pas le plus rapide, et il est étranger au tracé des contours, qu'il faut reprendre par la suite.

**BeanzMaster** · 22/01/2020, 17h16

Bonjour,

Envoyé par wiwaxia

Qu'est-ce qu'une polyline ? Par quel type de données le polygone est-il défini ?

Polyline = plusieurs segment de ligne (Point_Debut, point_1, point_2....point_fin) Qu'entend tu par quel type ?

je prend l'exemple que à la base c'est un rectangle, je transforme les 4 segments en polygone complexe afin de pouvoir dessiner un contour de plus de 1 pixel

par la suite j'aimerai implémenter ceci : http://www.angusj.com/delphi/clipper...s/JoinType.htm pour la génération de mes contours

Envoyé par wiwaxia

Ne pourrait-on envisager plus simplement un tableau des coordonnées des sommets ?

C'est déja le cas je traite, un tableau de coordonnées (p1, p2, p3......)

Envoyé par wiwaxia

Il existe un procédé simple de remplissage, indifférent à la présence de croisements ou de points doubles - mais ce n'est probablement pas le plus rapide, et il est étranger au tracé des contours, qu'il faut reprendre par la suite.

Pourrais tu m'expliquer le principe, cela pourrait être intéressant même si c'est un peu moins rapide

Bon avec l'algo actuel, toujours le même problème il manque un bout de segment

Nom : 2020-01-17_194604.png
Affichages : 305
Taille : 270 octets

Nom : 2020-01-17_194604.png
Affichages : 305
Taille : 270 octets

J'ai trouvé ce site https://www.cs.rit.edu/~icss571/fill...ial_cases.html qui le confirme. L'algorithme "pair-impair" en est la cause.
La solution serai peut-être de ne pas prendre en compte les segments qui vont des points en haut gauche du polygone extérieur vers celui de l'intérieur.
Je tenterai bien aussi l'algorithme de l'enroulement mais le résultat va être identique (enfin tout dépend comment est construit le polygone, si j'ai bien compris ) L'autre solution est la triangulation. Ou sinon cela serai de créer une suite de polygone-rectangle (1 par segment, ce qui résoudrait également le problème en cas d'intersection de 2 lignes) J'aimerai bien savoir par exemple comme GDI sous windows fait pour dessiner les polygones

Merci

Jérôme

**BeanzMaster** · 22/01/2020, 19h12

Je me suis rappelé d'un très très vieux livre : le "Graphic black book de Michael Abrash" (une mine d'informations) que j'avais lu il y a quelques années. Je l'ai retrouvé sur le net et j'y ai trouvé mon bonheur, reste plus qu'a implémenter le code de la fin du chapitre en pascal et tester

**anapurna** · 22/01/2020, 19h30

salut

en reprenant leur exemple ici

il est assez simple de retrouver les valeurs YMin YMax et XVal mais par contre je comprend pas trop la valeur 1/m

Code :

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

1
2
3
4
5
 
 TABEDGE[I].YMin  := MIN(TABEDGE[I].Y,TABEDGE[I+1].Y);
 TABEDGE[I].YMax := Max(TABEDGE[I].Y,TABEDGE[I+1].Y);
 TABEDGE[I].XVal  := IFF(TABEDGE[I].Y = TABEDGE[I].YMax, TABEDGE[I+1].X,TABEDGE[I].X);
 TABEDGE[I]._1DIVM := ??

il faut prendre la liste comme une liste circulaire c'est dire que si on arrive au bout alors on reprend au premier indice

**wiwaxia** · 22/01/2020, 19h59

Envoyé par BeanzMaster

... Polyline = plusieurs segment de ligne (Point_Debut, point_1, point_2....point_fin) Qu'entend tu par quel type ?

Les données sont donc (ou peuvent être) mémorisées dans un tableau de coordonnées: voilà l'essentiel.

Tu peux te reporter à cette discussion qui concernait un sujet quasiment identique (désolé pour l'auto-citation).
Je m'aperçois d'ailleurs, après relecture rapide, que l'algorithme en cause s'apparente probablement au procédé pair-impair que tu as évoqué, et qu'il y a donc encore une autre solution à laquelle je songeais, et que l'on pourrait éventuellement détailler.

Tu devrais pouvoir incorporer sans difficulté le coeur du programme; s'il faut y regarder de plus près, je relancerai celui qui sommeille dans mes archives.

**BeanzMaster** · 20/01/2020, 20h44

Envoyé par wiwaxia

Bonjour,

Le fait d'avoir pris un polygone croisé n'aurait-il pas de l'importance ?

Le croisement se produit au niveau des arêtes (4,5) et (9:0); il pourrait être supprimé en inversant le sens de l'indexation de la partie interne:

Salut après avoir demandé de l'aide également sur le forum de Lazarus ici

j'ai finalisé l'algorithme,(cf forum Lazarus) et tu avais raison Wiwaxia le problème venait bien de l'ordre dans lequel je définis les points du polygone, mais l'ordre est différent que celui que tu m'a proposé

il faut faire en fait :

Nom : flowRoot915.png
Affichages : 257
Taille : 5,0 Ko

Nom : flowRoot915.png
Affichages : 257
Taille : 5,0 Ko

cf ce site ou j'ai compris comment créer mes polygones "complexes"

Merci

Jérôme

PS : Pour mes contours va falloir que j'utilise une autre technique (genre polypolygone)

**wiwaxia** · 21/01/2020, 08h07

Bonjour,

Envoyé par BeanzMaster

... le problème venait bien de l'ordre dans lequel je définis les points du polygone, mais l'ordre est différent que celui que tu m'a proposé ...

Les deux polygones concaves présentent la même orientation et s'enroulent dans le sens rétrograde; ils ne diffèrent que par la position du point de départ: