Rasterization de polygone complexe

Version imprimable

19/01/2020, 08h43
BeanzMaster

Rasterization de polygone complexe

Salut à tous,

je bute sur un problème depuis plusieurs jours, j'ai ouvert un sujet dans le forum algorithmique/traitement d'image.
S'il y en a parmi vous qui auraient des pistes ou une solution je suis preneur.

Merci d'avance, bon dimanche

A+

Jérôme
19/01/2020, 13h08
BeanzMaster

Je suis en train de finaliser un nouvel algo mais je bute sur un truc qui, je suis sûr, me paraîtra logique et évident par la suite, mais là je sèche.

Je m'explique : j'ai des tableaux dynamiques d'entiers pouvant contenir au minimum 2 valeurs.
Les valeurs sont à prendre 2 par 2 car elles décrivent le début et la fin d'une ligne horizontale.

Quand il n'y a que 2 valeurs pas de souci, rien à faire, le résultat est identique.
Quand, il y en a plus, je souhaite parcourir et nettoyer cette liste d'une certaine façon.

Exemple de liste :
[120, 120, 240, 240, 300, 300]

Je dois supprimer les doublons pour obtenir en sortie un nouveau tableau comme ceci : [120,240,240,300] (vous voyez le problème, tous les doublons ne sont pas bon à supprimer).

Autres exemples :
[120,180,240,300] ; [120,120,300,300] ; [120,120,240,280,300,300] dans ceux-là rien à faire ;

Ici [120,120, 120, 300,300, 300] devra retourner en sortie normalement [120,300].

Auriez-vous une méthodologie, un algorithme à me proposer, car je suis à la rue complet.

Merci d'avance

A+

Jérôme
19/01/2020, 14h45
plegat

Salut,

Citation:

Envoyé par BeanzMaster

J
quand, il y en a plus, je souhaite parcourir et nettoyer cette liste d'une certaine façon
[...]
vous voyer le problème, tous les doublons ne sont pas bon à supprimer)
[...]
dans ceux la rien à faire
[...]
ici [120,120, 120, 300,300, 300] devra retourner en sortie normalement [120,300]

Je dois dire que de mon côté, le pourquoi on nettoie parfois mais pas tout le temps n'est pas expressément clair... est-ce qu'on pourrait avoir plus de détails?
19/01/2020, 16h20
Andnotor

A mon sens, le premier exemple n'est pas simplifiable. Là, tu passes de trois points à deux lignes (qui pourrait sinon encore être compacté en une ligne de 120 à 300).

Par contre, le dernier l'est effectivement (point-ligne-point) puisque la deuxième "coordonnée" débute sur le premier point et que le dernier point chevauche également cette ligne.

Les autres n'ont pas de chevauchement, donc pas de simplification possible.

Donc point de départ plus petit ou égal au point d'arrivée précédent entraîne la suppression de ces deux points ;)

3 pièce(s) jointe(s)

Salut je m'explique (je vais essayé d'être simple) dans un tableau correspond à la hauteur de mon polygone, pour chaque segment je stocke tous les X. J'obtient donc un tableau à 2 dimensions

Ligne[0] = [x1,x2, x3,x4,x5.....]
...
Ligne[n] = [x1,x2, x3,x4.....]

pour chaque ligne j'ai un tableau ou chaque duo de valeurs du tableau correspond à un segment de droite horizontale [(x1,x2), (x3,x4),....]

Vu que je parcours chaque segment du polygone, les segments qui sont adjacent ou qui se chevauchent, va faire qu'a chaque point d'intersection la même valeur va être ajouté au tableau

Exemple avec le polygone

Pts 0(X: 120.00000 ,Y: 120.00000)
Pts 1(X: 120.00000 ,Y: 180.00000)
Pts 2(X: 180.00000 ,Y: 220.00000)
Pts 3(X: 300.00000 ,Y: 120.00000)
Pts 4(X: 300.00000 ,Y: 180.00000)
Pts 5(X: 240.00000 ,Y: 120.00000)

Pièce jointe 531867

A la ligne 0 du poygone, il y a 2 segments P0->P1 et P5->P0 = [(X: 120.00000 ,Y: 120.00000), (X: 120.00000 ,Y: 180.00000)] et [(X: 120.00000 ,Y: 120.00000), (X: 240.00000 ,Y: 120.00000)]
pour chacun de ces segment la valeur de X soit 120 sera ajouté à mon tableau
Vu que sur la ligne 0 il y a un autre segment de remplissage le tableau par rapport au ligne du polygone cela va donner [120,120,240,240,300,300]
Je doit ici dessiner deux ligne de 120 à 240 et de 300 à 300 (1 seul pixel)

J'ai trouvé un solution pour sélectionner les bon points mais ce n'ai pas suffisant pour des polygones complexe comme les 2 autres algorithmes que j'ai mentionner dans le forum "Traitement d'image"

Voici mon code temporaire :

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
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
procedure TBZ2DPolygonTool.ComputeRasterBuckets;
var
  Buckets : array of TBZIntegerList;
  LineIntersect : TBZIntegerList;
  I, J, K : Integer;
  idx1, idx2, idx3 : Integer;
  Ind1, Ind2, Ind3, Ind4, PrevInd, NextInd : Integer;
  RasterLine : TBZRasterItems;
  {$CODEALIGN VARMIN=16}
   p1, p2 : TBZFloatPoint;
  {$CODEALIGN VARMIN=4}
  s : String;
 
  procedure SwapPoint(var A, B : TBZFloatPoint);
  Var
    {$CODEALIGN VARMIN=16}
    Temp : TBZFloatPoint;
    {$CODEALIGN VARMIN=4}
  begin
    GlobalLogger.LogNotice('====> SWAP POINTS = [ ' + B.ToString + ' ; ' + A.ToString + ' ]');
    Temp := A;
    A := B;
    B := Temp;
 
  end;
 
  Procedure AddEdge(A, B : TBZFloatPoint);
  Var
    CurrentX, XIncr: Single;
    mw, Y, CurrentLine, cx: Integer;
   {$CODEALIGN VARMIN=16}
    p1i, p2i : TBZVector2i;
   {$CODEALIGN VARMIN=4}
 
  Begin
    GlobalLogger.LogStatus('====> Add Edge : ['+ A.ToString + ' ; '+B.ToString+']');
    {On va toujours de bas en haut }
    If B.Y < A.Y Then SwapPoint(A,B);
 
    if A.Y = B.y then
    begin
      p1i := A.Round;
      p2i := B.Round;
      CurrentLine := p1i.y - FStartY;
      GlobalLogger.LogStatus('======> Horizontal Line <======');
      GlobalLogger.LogStatus('====> Add Indice Line = '+CurrentLine.ToString + ' ===> ' + p1i.X.Tostring);
      GlobalLogger.LogStatus('====> Add Indice Line = '+CurrentLine.ToString + ' ===> ' + p2i.X.Tostring);
      Buckets[CurrentLine].Add(p1i.x);
      Buckets[CurrentLine].Add(p2i.x);
      exit;
    end;
 
    if A.x = B.X then
    begin
      p1i := A.Round;
      p2i := B.Round;
      GlobalLogger.LogStatus('======> Vertical Line <======');
      For y := p1i.Y to p2i.Y do
      begin
        CurrentLine := y - FStartY;
        GlobalLogger.LogStatus('=====> Add Indice Line = '+CurrentLine.ToString + ' ===> ' + p1i.X.Tostring);
        Buckets[CurrentLine].Add(p1i.X);
      end;
      Exit;
    end;
 
 
 
    GlobalLogger.LogStatus('======> Slope Line <======');
    XIncr := ((B.X - A.X) / (B.Y - A.Y));
    GlobalLogger.LogStatus('========> Slope = ' + XIncr.ToString);
    p1i := A.Round;
    p2i := B.Round;
    CurrentX := A.X;
    CurrentLine := p1i.y - FStartY;  // Nos Tableaux commencent a 0
 
    For Y := p1i.Y To p2i.Y Do
    Begin
      CurrentLine := y - FStartY;
      cx := Round(CurrentX);
 
      GlobalLogger.LogStatus('=====> Add Indice Line = '+CurrentLine.ToString + ' ===> ' + cX.Tostring);
      Buckets[CurrentLine].Add(cx);
      CurrentX := CurrentX + XIncr;
      Inc(CurrentLine);
    End;
  end;
 
begin
  FBounds := ComputeBounds;
  FRastersLineCount  := (FBounds.AsRect.Bottom - FBounds.AsRect.Top) + 1; // FBounds.AsRect.Height + 1; //
  GlobalLogger.LogNotice('====[ TBZ2DPolygonTool.ComputeRasterBuckets ]=========================================');
  GlobalLogger.LogStatus('Bounds = ' + FBounds.ToString);
  GlobalLogger.LogStatus('RastersLineCount = ' + FRastersLineCount.ToString);
  FStartY := FBounds.AsRect.Top;
 
  SetLength(Buckets, FRastersLineCount);
  SetLength(FRasters, FRastersLineCount);
 
  For I := 0 to FRastersLineCount-1 do
  begin
    Buckets[I] := TBZIntegerList.Create(12);
  end;
 
  // BuildEdgeTable
  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];
    AddEdge(p1,p2);
  end;
 
  LineIntersect := TBZIntegerList.Create(12);
  GlobalLogger.LogNotice('====> Sort and Pack');
  For I := 0 to FRastersLineCount-1 do
  begin
    GlobalLogger.LogStatus('====[ LINE = ' + I.ToString + ' ]=======================================');
    if I >0 then LineIntersect.Clear;
    // On trie les indice dans l'odre croissant
    Buckets[I].Sort(0,@CompareInteger);
    GlobalLogger.LogStatus('========> Before : ' + Buckets[i].Count.ToString);
    S := '';
    For k := 0 to Buckets[i].Count-1 do S := S + Buckets[i].Items[k].ToString + ', ';
    GlobalLogger.LogStatus('[ ' + s + ' ]');
    GlobalLogger.LogStatus('');
 
    // Ajoute du premier indice
 
 
    if  Buckets[I].Count <=3 then
    begin
      GlobalLogger.LogStatus('====> Add First : ' + Buckets[I].First.ToString);
      GlobalLogger.LogStatus('====> Add Last : ' + Buckets[I].Last.ToString);
      LineIntersect.Add(Buckets[I].First);
      LineIntersect.Add(Buckets[I].Last);
    end
    else if  Buckets[I].Count = 4 then
    begin
      Ind1 := Buckets[i].Items[0];
      Ind2 := Buckets[i].Items[1];
      Ind3 := Buckets[i].Items[2];
      Ind4 := Buckets[i].Items[3];
      LineIntersect.Add(Ind1);
      if (Ind2 <> Ind1) and (Ind2<>Ind4) then LineIntersect.Add(Ind2);
      if (Ind3 <> Ind1) and (Ind3<>Ind4) then LineIntersect.Add(Ind3);
      if (Ind4 <> Ind3) or Odd(LineIntersect.Count) then LineIntersect.Add(Ind4);
    end
    else if Buckets[I].Count > 4 then
    begin
      //GlobalLogger.LogStatus('====> Add first : ' + LastInd.ToString);
      //LineIntersect.Add(LastInd);
 
      // On supprime les indices en trop
      J := 0;
      PrevInd :=  -999999;
      While J <= Buckets[I].Count - 2 do
      //For J := 0 to Buckets[I].Count - 3 do
      begin
        idx1 := J;
        idx2 := J + 1;
        //idx3 := J + 2;
        Ind1 :=  Buckets[I].Items[idx1];
        Ind2 :=  Buckets[I].Items[idx2];
        //Ind3 :=  Buckets[I].Items[idx3];
        GlobalLogger.LogStatus('----> Indice 1     = ' + Ind1.ToString);
        GlobalLogger.LogStatus('----> Indice 2     = ' + Ind2.ToString);
        //GlobalLogger.LogStatus('----> Indice 3     = ' + Ind3.ToString);
        //GlobalLogger.LogStatus('----> Last Indice  = ' + LastInd.ToString);
        if (J< Buckets[I].Count - 2) then NextInd := Buckets[I].Items[idx2 + 1]
        else NextInd := Ind2;
        GlobalLogger.LogStatus('----> Prev Indice   = ' + PrevInd.ToString);
        GlobalLogger.LogStatus('----> Next Indice   = ' + NextInd.ToString);
        if PrevInd <> Ind1 then
        begin
          GlobalLogger.LogStatus('=======> Add Indice 1 : ' + Ind1.ToString);
          //GlobalLogger.LogStatus('=======> Add Indice : ' + Ind2.ToString);
          LineIntersect.Add(Ind1);
        end;
 
        if Ind1<Ind2 then
        begin
          //GlobalLogger.LogStatus('=======> Add Indice : ' + Ind2.ToString);
          if Ind2<NextInd then
          begin
            GlobalLogger.LogStatus('=======> Add Indice 2 : ' + Ind2.ToString);
            LineIntersect.Add(Ind2);
          end;
        end;
 
        if (J = Buckets[I].Count - 2) and (Ind2>=NextInd) then
        begin
          GlobalLogger.LogStatus('=======> Add Last Indice  : ' + Ind2.ToString);
          LineIntersect.Add(Ind2);
        end;
        //LineIntersect.Add(Ind2);
        PrevInd := Ind2;
        //end
        //else
        //begin
        //   GlobalLogger.LogStatus('======> PACK  <===========');
        //   GlobalLogger.LogStatus('==========> Add Indice : ' + Ind1.ToString);
        //   GlobalLogger.LogStatus('==========> Add Indice : ' + Ind3.ToString);
        //   LineIntersect.Add(Ind1);
        //   LineIntersect.Add(Ind3);
        //end;
 
        Inc(J,2);
        //else
        //begin
        //   GlobalLogger.LogStatus('=======> Add Indice : ' + Ind2.ToString);
        //   LineIntersect.Add(Ind2);
        //end;
        //LastInd := Ind1;
      end;
 
      // Ajoute du dernier indice
      //GlobalLogger.LogStatus('====> Add Last : ' + Buckets[I].Last.ToString);
      //LineIntersect.Add(Buckets[I].Last);
    end;
    GlobalLogger.LogStatus('=======> After : ' + LineIntersect.Count.ToString);
    // On remplit le tableau des segments
    GlobalLogger.LogNotice('====> Update Edge List');
    SetLength(RasterLine, (LineIntersect.Count shr 1) );
    K := 0;
    J := 0;
    While (J < LineIntersect.Count-1) do
    //For J := 0 to LineIntersect.Count - 2 do
    begin
      idx1 := J;
      idx2 := J + 1;
      GlobalLogger.LogStatus('====> Add Raster : ' + LineIntersect.Items[idx1].ToString + ' ==> ' + LineIntersect.Items[idx2].ToString);
      RasterLine[K].xStart := LineIntersect.Items[idx1];
      RasterLine[K].xEnd := LineIntersect.Items[idx2];
      Inc(K);
      Inc(J,2);
    end;
 
    FRasters[I] := RasterLine;
    SetLength(RasterLine,0);
  end;
 
  // On libère nos tableaux de travail
  FreeAndNil(LineIntersect);
  For I := FRastersLineCount-1 downto 0 do
  begin
    FreeAndNil(Buckets[I]);
  end;
  SetLength(Buckets, 0);
  Buckets := nil;
end;

Le remplissage est bon avec des polygones convexes ou concaves

Pièce jointe 531874

Mais avec un polygone complexe, j'ai encore des erreurs (le même polygone sauf que le contour fait 3 pixels de largeur) ce qui à la conversion du contour donne un polygone complexe

J'ai entouré en rouge les erreurs

Pièce jointe 531877

la partie qui pose problème est celle commençant par

Code:

1
2
3
4
 
else if Buckets[I].Count > 4 then
begin
  .....

De plus mon tableau peut avoir un nombre impair de données

Bref voila, je me rapproche de mon but, mais c'est pas encore ça

Merci

Jérôme

1 pièce(s) jointe(s)

Merci AndNotOr

Citation:

Envoyé par Andnotor

Donc point de départ plus petit ou égal au point d'arrivée précédent entraîne la suppression de ces deux points ;)

J'ai donc bien simplifié ma méthode :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 // On supprime les indices en trop
      J := 0;
      PrevInd := -999999;
      While J <= Buckets[I].Count - 1 do
      begin
        idx1 := J;
        if J = Buckets[I].Count - 1 then NextInd := 9999999 else NextInd := Buckets[I].Items[idx1 + 1];
        Ind1 :=  Buckets[I].Items[idx1];
 
        GlobalLogger.LogStatus('');
        GlobalLogger.LogStatus('----> Prev Indice    = ' + PrevInd.ToString);
        GlobalLogger.LogStatus('----> Current Indice = ' + Ind1.ToString);
        GlobalLogger.LogStatus('----> Next Indice    = ' + NextInd.ToString);
 
        if (Ind1 > PrevInd) and (Ind1 < NextInd) then
        begin
          GlobalLogger.LogStatus('=======> Add Indice 1 : ' + Ind1.ToString);
          LineIntersect.Add(Ind1);
        end;
 
        PrevInd := Ind1;
        Inc(J);
      end;

Par contre c'est meilleur, mais j'ai toujours un soucis lorsque le tableau contient un nombre impair de valeurs

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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
[STATUS]  ====[ LINE = 179 ]=======================================
[STATUS]  ========> Before : 9
[STATUS]  [ 120, 122, 122, 226, 229, 296, 299, 300, 302,  ]
[STATUS]  
[STATUS]  ----> Prev Indice    = -999999
[STATUS]  ----> Current Indice = 120
[STATUS]  ----> Next Indice    = 122
[STATUS]  =======> Add Indice 1 : 120
[STATUS]  
[STATUS]  ----> Prev Indice    = 120
[STATUS]  ----> Current Indice = 122
[STATUS]  ----> Next Indice    = 122
[STATUS]  
[STATUS]  ----> Prev Indice    = 122
[STATUS]  ----> Current Indice = 122
[STATUS]  ----> Next Indice    = 226
[STATUS]  
[STATUS]  ----> Prev Indice    = 122
[STATUS]  ----> Current Indice = 226
[STATUS]  ----> Next Indice    = 229
[STATUS]  =======> Add Indice 1 : 226
[STATUS]  
[STATUS]  ----> Prev Indice    = 226
[STATUS]  ----> Current Indice = 229
[STATUS]  ----> Next Indice    = 296
[STATUS]  =======> Add Indice 1 : 229
[STATUS]  
[STATUS]  ----> Prev Indice    = 229
[STATUS]  ----> Current Indice = 296
[STATUS]  ----> Next Indice    = 299
[STATUS]  =======> Add Indice 1 : 296
[STATUS]  
[STATUS]  ----> Prev Indice    = 296
[STATUS]  ----> Current Indice = 299
[STATUS]  ----> Next Indice    = 300
[STATUS]  =======> Add Indice 1 : 299
[STATUS]  
[STATUS]  ----> Prev Indice    = 299
[STATUS]  ----> Current Indice = 300
[STATUS]  ----> Next Indice    = 302
[STATUS]  =======> Add Indice 1 : 300
[STATUS]  
[STATUS]  ----> Prev Indice    = 300
[STATUS]  ----> Current Indice = 302
[STATUS]  ----> Next Indice    = 9999999
[STATUS]  =======> Add Indice 1 : 302
[STATUS]  =======> After : 7
[STATUS]  [ 120, 226, 229, 296, 299, 300, 302,  ]
[STATUS]  
[NOTICE]   [ 18:44:21 ] ====> Update Edge List
[STATUS]  ====> Add Raster : 120 ==> 226
[STATUS]  ====> Add Raster : 229 ==> 296
[STATUS]  ====> Add Raster : 299 ==> 300
[STATUS]  
[STATUS]  ====[ LINE = 180 ]=======================================
[STATUS]  ========> Before : 9
[STATUS]  [ 120, 120, 124, 225, 228, 297, 300, 300, 302,  ]
[STATUS]  
[STATUS]  ----> Prev Indice    = -999999
[STATUS]  ----> Current Indice = 120
[STATUS]  ----> Next Indice    = 120
[STATUS]  
[STATUS]  ----> Prev Indice    = 120
[STATUS]  ----> Current Indice = 120
[STATUS]  ----> Next Indice    = 124
[STATUS]  
[STATUS]  ----> Prev Indice    = 120
[STATUS]  ----> Current Indice = 124
[STATUS]  ----> Next Indice    = 225
[STATUS]  =======> Add Indice 1 : 124
[STATUS]  
[STATUS]  ----> Prev Indice    = 124
[STATUS]  ----> Current Indice = 225
[STATUS]  ----> Next Indice    = 228
[STATUS]  =======> Add Indice 1 : 225
[STATUS]  
[STATUS]  ----> Prev Indice    = 225
[STATUS]  ----> Current Indice = 228
[STATUS]  ----> Next Indice    = 297
[STATUS]  =======> Add Indice 1 : 228
[STATUS]  
[STATUS]  ----> Prev Indice    = 228
[STATUS]  ----> Current Indice = 297
[STATUS]  ----> Next Indice    = 300
[STATUS]  =======> Add Indice 1 : 297
[STATUS]  
[STATUS]  ----> Prev Indice    = 297
[STATUS]  ----> Current Indice = 300
[STATUS]  ----> Next Indice    = 300
[STATUS]  
[STATUS]  ----> Prev Indice    = 300
[STATUS]  ----> Current Indice = 300
[STATUS]  ----> Next Indice    = 302
[STATUS]  
[STATUS]  ----> Prev Indice    = 300
[STATUS]  ----> Current Indice = 302
[STATUS]  ----> Next Indice    = 9999999
[STATUS]  =======> Add Indice 1 : 302
[STATUS]  =======> After : 5
[STATUS]  [ 124, 225, 228, 297, 302,  ]
[STATUS]  
[NOTICE]   [ 18:44:21 ] ====> Update Edge List
[STATUS]  ====> Add Raster : 124 ==> 225
[STATUS]  ====> Add Raster : 228 ==> 297

Pièce jointe 531917

Merci

A+

19/01/2020, 21h16
Andnotor

Citation:

Envoyé par BeanzMaster

mais j'ai toujours un soucis lorsque le tableau contient un nombre impair de valeurs

Il ne devrait pas.

Ce qui m'interpelle, c'est AddEdge. Pour une ligne vertical (ligne 53), tu n'ajoutes qu'une donnée, tu peux donc être impair, mais ça veut aussi dire qu'à l'arrivée tu n'auras une hauteur que de Y div 2 puisque tu as besoin de pairs. Il devrait y avoir 2x Buckets[CurrentLine].Add(p1i.X).

Même chose en ligne 83 mais avec CX_Précédent -> CX_Courant.
20/01/2020, 17h07
anapurna

salut

ce ne serait pas plus simple de créer des triangles et de vérifier que les éléments sont à l’intérieur ou à l’extérieur de ses fameux triangles ?
tu as les point remarquable
dans ton exemple il manque juste le point d'intersection

2 pièce(s) jointe(s)

Bonjour merci, j'ai trouvé la réponse à mes soucis.

Là où je foirais c'était dans l'ordre de création de mes points pour le polygone complexe cf ici.

Des 5 méthodes que j'ai codées elle fonctionnent toutes. Un des problèmes qu'il y avait dans le dernier code c'était le tri (il y avait une chtite erreur dans la boucle) ce qui provoquait les erreurs de la ligne du bas.

Bref voilà la version la plus optimisée toujours basée sur le "pair-impair" et fonctionnelle que j'ai écrite :
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 procedure TBZ2DPolygonTool.ComputeRasters; Var Y, I, K, X, CurrentLine : 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.Height; 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; for I := 0 to FPoints.Count - 1 do begin p1 := FPoints.Items[I]; if (I = (FPoints.Count - 1)) then p2 := FPoints.Items[0] else p2 := FPoints.Items[I + 1]; if (p1.y > p2.y) then SwapPoint(p1,p2); if ((y >= p1.y) And (y < p2.y)) or ((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; end; LineIntersect.Sort(0,@CompareInteger); SetLength(RasterLine, (LineIntersect.Count shr 1) ); I := 0; K := 0; While (I < LineIntersect.Count-1) do begin RasterLine[K].xStart := LineIntersect.Items[I]; RasterLine[K].xEnd := LineIntersect.Items[I+1]; Inc(K); Inc(I,2); end; FRasters[CurrentLine] := RasterLine; SetLength(RasterLine,0); Inc(CurrentLine); end; FreeAndNil(LineIntersect); FRastersNeedUpdate := False; end;
Le seul souci qu'il reste c'est au croisement des deux lignes. Pour mes contours de polygone je vais devoir implémenter un genre de poly-polygone et revoir un peu ma méthode de génération des contours.

Ici le contour de 3 pixels est rempli (sauf à l'intersection) et c'est le résultat que je cherchais.

Pièce jointe 532245
et là le remplissage d'un autre polygone complexe et dessin de son contour de 1px
Pièce jointe 532246

Merci de votre aide

A+

Jérôme