Discussion :

[BeanzMaster]

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



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)



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]

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:

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

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;

[BeanzMaster]

Salut

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;

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

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



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

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]

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



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]

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



Les 2 algorithmes donnes des résultats similaires

Contour avec épaisseur de 3 pixels



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]

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 :



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]

Bonjour,

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

c'est probablement lié à une asymétrie de l'algorithme utilisé.

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

Le lien donné ne fonctionne malheureusement pas .
Rectification: il suffit de taper http://boolean.klaasholwerda.nl/algdoc/

[wiwaxia]

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

Bonjour,

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

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

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



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]

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]

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]

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

Salut

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

La valeur 1/m correspond à la valeur inverse de la pente d'une ligne (slope en anglais) la pente d'un ligne se calcul comme ceci : (y2 - y1) / (x2 - x1) par déduction l'inverse c'est 1/((y2 - y1) / (x2 - x1)) = (x2 - x1) / (y2 - y1) comme on le voit dans les codes sur l'algo "pair-impair que j'ai pu trouvé. J'avais fait cette petite App mathématique sur les lignes si cela t'intéresse.

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.

Merci wiwaxia t'es trop fort je gardes ton algo sous le coude, gràce à cette discussion j'ai pigé pourquoi l'algo de PyGame inverse les X comme me l'avais fait remarqué Anapurna. Mais cela ne suffisait pas.
En plus de tester la position en Y il faut doubler les points si p1.x < p2.x

Voilà le code modifié et fonctionnel, mais à voir si il se comporte bien dans tous les cas de figures (je met un petit bémol su le fait de doubler les "x" seulement si p1.x < p2.x )

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
procedure TBZ2DPolygonTool.ComputeRasters;
Var
  Y, I, K, X, TmpEdge, Idx,  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];
 
      // Prise en charge des lignes horizontales
      if (Y > FBounds.AsRect.Top) and (Y < FBounds.AsRect.Bottom) then
      begin
        if (Y = p1.Y) and (p1.Y = p2.Y) then
        begin
          if (p1.x = p2.x) then
          begin
            LineIntersect.Add(Round(p1.x));
            LineIntersect.Add(Round(p1.x));
            Continue;
          end
          else if (p1.x > p2.x) then
          begin
            LineIntersect.Add(Round(p2.x));
            LineIntersect.Add(Round(p1.x));
            Continue;
          end
          else //if (p1.x < p2.x) then
          begin
            LineIntersect.Add(Round(p1.x));
            LineIntersect.Add(Round(p1.x));
            LineIntersect.Add(Round(p2.x));
            LineIntersect.Add(Round(p2.x));
            Continue;
          end
        end;
      end;
 
      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;
    //Le trie QuickSort n'est pas "stable" on utilise donc un tri à bulle
    //Pour de grande quantité de point l'algorithme "MergeSort" serait plus indiqué
    For I := 0 to LineIntersect.Count-1 do
    begin
      Idx := I;
      For K := LineIntersect.Count-1 downto I do
      begin
        if LineIntersect.Items[K] <= LineIntersect.Items[Idx] then Idx := K;
        if (I<>Idx) then
        begin
          TmpEdge := LineIntersect.Items[I];
          LineIntersect.Items[I] := LineIntersect.Items[Idx];
          LineIntersect.Items[Idx] := TmpEdge;
        end;
      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;

La seule contrainte est lors de la construction du polygone, comme tu me l'avais fait remarqué

Bonjour,
Les deux polygones [concaves] doivent présenter la même orientation et s'enrouler dans le sens rétrograde.

A gauche s'enroule dans le sens rétrograde et à droite s'enroule dans le même sens

Le code actuel n'est pas 100% performant si le polygone se croisent (le noir)



Merci

Jérôme

[wiwaxia]

L'algorithme dont il est ici question a été évoqué en plusieurs occasions, mais jamais traité dans le détail.

Soit un polygone quelconque à (N) sommets, situés dans un plan orienté par un repère orthonormé direct (xOy).
Le procédé consiste, pour tout point (M), à sommer tous les angles orientés θ_ij = (MP_i , MP_j) séparant les directions des vecteurs joignant le point considéré (M) aux sommets successifs.
La somme obtenue correspond au nombre de tours effectués par la séquence des (N) arêtes autour de (M), soit:

A_tot = k.2p ;

elle est nulle pour tout point situé à l'extérieur du polygone, positive à l'intérieur lorsque l'enroulement s'effectue dans le sens direct (antihoraire) et négative dans le cas contraire;

L'angle recherché intervient dans les expression de deux grandeurs concernant des vecteurs du plan:
# le produit scalaire Ps = (V₁|V₂) = x₁.x₂ + y₁.y₂ = N₁N₂.Cos(θ) ;
# le déterminant Dt = (V₁×V₂) = x₁.y₂ - y₁.x₂ = N₁N₂.Sin(θ)
- en convenant de noter (N₁, N₂) les normes des vecteurs correspondants.

Cependant aucune des relations réciproques:

θ = ArcSin(Dt/N₁N₂) , θ = ArcCos(Ps/N₁N₂)

ne peut être utilisée seule pour la détermination de l'angle orienté (θ), parce que:
a) la fonction ArcSin(u) retourne un angle limité au domaine [-π/2 ; +π/2] , et que
b) la fonction ArcCos(u) conduit à une valeur non-négative, située dans l'intervalle [0 ; π],
alors que l'angle recherché (θ) appartient au semi-ouvert ]-π ; +π] deux fois plus large.

D'autre part chacune de ces fonctions présente aux extrémités de leur domaine un point singulier en lesquels la tangente au graphe est verticale, et la dérivation n'est plus possible; le calcul numérique au voisinage de ces points est alors entaché d'erreurs beaucoup plus importantes, susceptibles de compromettre la fiabilité du résultat.
D'où la nécessité, pour ne jamais s'en approcher, d'une partition en sous-domaines adjacents, dont les limites correspondent à l'égalité des valeurs absolues (|Sin(θ)| , |Cos(θ)|) , soit: θ = ± π/4 ou ± 3π /4 .

L'algorithme suivant fournit le résultat recherché (le code complet sera donné plus loin):

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
     Angle:= 0;
     FOR i:= 1 TO NmaxV DO
       BEGIN
         IF (i<NmaxV) THEN j:= i + 1
                      ELSE j:= 1;
         V1.x:= L_V[i].x - X_; V1.y:= L_V[i].y - Y_;
         V2.x:= L_V[j].x - X_; V2.y:= L_V[j].y - Y_;
         N21:= Norme2(V1);     N22:= Norme2(V2); N1N2:= Sqrt(N21 * N22);
         p:= V1.x * V2.x;      q:= V1.y * V2.y;  Ps:= p + q;
         p:= V1.x * V2.y;      q:= V1.y * V2.x;  Dt:= p - q;
         T1:= (N1N2<1E-18);    T2:= (Abs(Ps)<Abs(Dt));
         IF T1 THEN Theta:= 0
               ELSE IF T2 THEN IF (Dt>0) THEN Theta:= ArcCos(Ps/N1N2)
                                         ELSE Theta:= -ArcCos(Ps/N1N2)
                          ELSE IF (Ps>0) THEN Theta:= ArcSin(Dt/N1N2)
                                         ELSE BEGIN
                                                p:= ArcSin(Dt/N1N2);
                                                IF (Dt>0) THEN Theta:= Pi - p
                                                          ELSE Theta:= p - Pi
                                              END;
         IncR(Angle, Theta)

Une simple représentation manuelle des graphes des fonctions Sin(xà, Cos(x) sur [-π ; +π] permet de retrouver facilement les 5 expressions qui se présentent (hormis le cas dégénéré N₁N₂ = 0 ).

[wiwaxia]

Voici ce que donne un polygone pseudo-aléatoire sans croisement, dont les positions des 80 sommets sont définies en coordonnées relatives

(x, y) in [0 ; 1]×[0 ; 1] ,

pourvu (ou non) d'une bordure:

Le même polygone peut être employé à la modification d'une image;



Ci-dessous le code relatif à la définition du polygone, et au traitement des matrices des corps des images (Matrice_1, Matrice_2):

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
 CONST K_Entete = 54; Dim_Max = 1500;
       Chemin = 'D:\ZZZZZZ\#\';                    // Données concernant la création des images Bitmap
       NmaxV  = 80;
 
 TYPE Pixel = ARRAY[1..3] OF Byte;
      Tab_Pix = ARRAY[0..Dim_Max, 0..Dim_Max] OF Pixel;
      Vect_2D = RECORD  x, y: Z_32  END;
      Tab_V2d = ARRAY[1..NmaxV] OF Vect_2D;
 
 VAR Larg_Image, Haut_Image, T_Fichier, T_Image: Z_32;
     V_Fich_1, V_Fich_2: File OF Byte;
     Matrice_1, Matrice_2: Tab_Pix;
     Nom_F2: String;
     LstV: Tab_V2d;
 
 
(*HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH
 
 Calcul de la seconde matrice
 
HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH*)
 
 PROCEDURE Trace_Polygone(L_V: Tab_V2d; VAR Ma2: Tab_Pix);
   CONST Pligne: Pixel = (0, 255, 0);
   VAR i, j: Byte; Dx, Dy, k, Npoint, Xm, Ym: Z_32; Kx, Ky: Reel;
   BEGIN
     FOR i:= 1 TO NmaxV DO
       BEGIN
         IF (j<NmaxV) THEN j:= i + 1
                      ELSE j:= 1;
         Dx:= L_V[j].x - L_V[i].x; Dy:=  L_V[j].y - L_V[i].y;
         Npoint:= 1;               Inc(Npoint, Abs(Dx));
         Inc(Npoint, Abs(Dy));
         Kx:= Dx / Npoint;         Ky:= Dy / Npoint;
         FOR k:= 0 TO Npoint DO
           BEGIN
             Xm:= L_V[i].x; Inc(Xm, Round(k * Kx));
             Ym:= L_V[i].y; Inc(Ym, Round(k * Ky));
             Ma2[Xm, Ym]:=  Pligne
           END
       END
   END;
 
 PROCEDURE IncR(VAR u: Reel; v: Reel);
   VAR w: Reel;
   BEGIN
     w:= u + v; u:= w
   END;
 
 PROCEDURE DecR(VAR u: Reel; v: Reel);
   VAR w: Reel;
   BEGIN
     w:= u - v; u:= w
   END;
 
 FUNCTION Norme2(V: Vect_2D): Reel;
   VAR X2, Y2: Z_32;
   BEGIN
     X2:= Sqr(V.x); Y2:= Sqr(V.y);
     Result:= X2 + Y2
   END;
 
 CONST D_Pi = 2 * Pi;
 
 FUNCTION Ntour(X_, Y_: Z_32; VAR L_V: Tab_V2d): Bool;
   VAR i, j: Byte; k: Z_08; Angle, Dt, N1N2, N21, N22, p, Ps, q, Theta: Reel;
       T1, T2: Bool; V1, V2: Vect_2D;
   BEGIN
     Angle:= 0;
     FOR i:= 1 TO NmaxV DO
       BEGIN
         IF (i<NmaxV) THEN j:= i + 1
                      ELSE j:= 1;
         V1.x:= L_V[i].x - X_; V1.y:= L_V[i].y - Y_;
         V2.x:= L_V[j].x - X_; V2.y:= L_V[j].y - Y_;
         N21:= Norme2(V1);     N22:= Norme2(V2); N1N2:= Sqrt(N21 * N22);
         p:= V1.x * V2.x;      q:= V1.y * V2.y;  Ps:= p + q;
         p:= V1.x * V2.y;      q:= V1.y * V2.x;  Dt:= p - q;
         T1:= (N1N2<1E-18);    T2:= (Abs(Ps)<Abs(Dt));
         IF T1 THEN Theta:= 0
               ELSE IF T2 THEN IF (Dt>0) THEN Theta:= ArcCos(Ps/N1N2)
                                         ELSE Theta:= -ArcCos(Ps/N1N2)
                          ELSE IF (Ps>0) THEN Theta:= ArcSin(Dt/N1N2)
                                         ELSE BEGIN
                                                p:= ArcSin(Dt/N1N2);
                                                IF (Dt>0) THEN Theta:= Pi - p
                                                          ELSE Theta:= p - Pi
                                              END;
         IncR(Angle, Theta)
       END;
     k:= Round(Angle/D_Pi); Result:= (k=1)
   END;
 
 PROCEDURE ZeroM(VAR Ma: Tab_Pix);
   CONST Pzero: Pixel = (0, 0, 255);
   VAR i, j: Z_32;
   BEGIN
     FOR i:= 0 TO Dim_Max DO
       FOR j:= 0 TO Dim_Max DO Ma[i, j]:= Pzero
   END;
 
 PROCEDURE Calc_Mat_Im2(La, Ha: Z_32; VAR Ma1, Ma2: Tab_Pix);
   CONST Pint: Pixel = (255, 100, 0);
         Pext: Pixel = (0, 100, 255);
   VAR j, Xm, Ym: Z_32; Px: Pixel;
   BEGIN
     ZeroM(Matrice_2);
     FOR Xm:= 0 TO (La - 1) DO
       FOR Ym:= 0 TO (Ha - 1) DO
(*         IF Ntour(Xm, Ym, LstV) THEN Ma2[Xm, Ym]:= Ma1[Xm, Ym]
                                ELSE BEGIN
                                       Px:= Ma1[Xm, Ym];
                                       Dec(Px[1], Px[1] DIV 2);
                                       Dec(Px[2], Px[2] DIV 2);
                                       j:= 255 * Px[3];
                                       Px[3]:= Round(Sqrt(j));
                                       Ma2[Xm, Ym]:= Px               *)
         IF Ntour(Xm, Ym, LstV) THEN Ma2[Xm, Ym]:= Pint
                                ELSE Ma2[Xm, Ym]:= Pext
   END;
 
(*HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH
 
 Calcul du tableau de coordonn‚es al‚atoires
 
HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH*)
 
 PROCEDURE Calc_Lv(La, Ha: Z_32; VAR L_V: Tab_V2d);
   CONST D_PisN = D_Pi / NmaxV;
         R0 = 0.500; R1 = 0.200; R2 = R0 - R1;
   VAR i: Byte; Ct, St, t, u, v, w: Reel;
       Lst1: Tab_V2d;
   BEGIN
     RandSeed:= 1222333555;
     FOR i:= 1 TO NmaxV DO
       BEGIN
         t:= i * D_PisN; Ct:= Cos(t); St:= Sin(t);
         u:= Random;     v:=  R1 + (R2 * u);
         w:= v * Ct;     Lst1[i].x:= Round(La * (w + R0));
         w:= v * St;     Lst1[i].y:= Round(Ha * (w + R0))
       END;
     L_V:= Lst1
   END;

Les appels de procédures interviennent dans le bloc suivant:

Code pascal :

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

1
2
3
4
5
6
 PROCEDURE P2;
   BEGIN
     Calc_Lv(Larg_Image, Haut_Image, LstV);
     Calc_Mat_Im2(Larg_Image, Haut_Image, Matrice_1, Matrice_2);
     Trace_Polygone(LstV, Matrice_2);
   END;

Vous reconnaîtrez sans difficultés les variantes reléguées en commentaires.

Et cela va sans dire mais beaucoup mieux en le disant:

Code pascal :

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

1
2
3
TYPE Z_32 = LongInt;     // Entier signé codé sur 32 octets
     Reel = Extended;
     Bool = Boolean;

[BeanzMaster]

Bonjour merci wiwaxia pour tes explications j'incorporerai ta solution dès que j'aurais fini de me prendre la tête avec la conversion du code de Michael Abrash.

En attendant, j'ai quand même une petite question. Peut-on se servir de ta méthode "NTours" pour savoir si un polygone est concave ? si oui comment procéder ?

A l'heure actuelle j'ai cette méthode pour connaitre si un polygone est convexe (trouvé sur stackoverflow)

On part du principe que le polygone n'est pas un polygone complexe

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
Function TBZ2DPolygonTool.IsConvex : Boolean;
var
  {$CODEALIGN VARMIN=16}
  PA, PB : TBZFloatPoint;
  {$CODEALIGN VARMIN=4}
  i,i1, i2, n, nn : Integer;
  zCrossProduct : Single;
  Sign : Boolean;
Begin
  Result := True;
  n := FPoints.Count;
 
  if (n<4) then exit;// C'est un triangle donc forcément convex
 
  nn:=n-1; // Nombre de point a scanner
  n:=n-2; // Une polygone est fermé, on ignore le dernier point
 
  for i := 0 to n do
  begin
    i1 := (i + 1) mod nn;
    i2 := (i + 2) mod nn;
    PA := FPoints.Items[i2] -  FPoints.Items[i1];
    PB := FPoints.Items[i] -  FPoints.Items[i1];
    zCrossProduct := PA.Perp(PB);
 
    if (i=0) then
    begin
      if (zcrossproduct > 0) then
      begin
        Result := False;
        Exit;
      end;
    end
    else if (zcrossproduct < 0) then
    begin
      Result := False;
      Exit;
    end;
  end;
End;

D’où ma question si le polygone n'est ni convexe ni concave il sera forcément complexe (ce qui m'éviterai de mettre en place un test des intersections des segments par "brute-force" (tes des segment un à un) ou au pire j'essayerai d'implémenter l'algorithme décrit ici

Merci

Jérôme

[BeanzMaster]

Bon pour ce qui est de savoir si un polygone est concave j'ai ma réponse il faut simplement que je compares tous les angle et si il y en à un qui fait moins de la somme de 2 ??? angles consécutifs fait moins 180° bingo le polygone est concave, c'est bien cela, non ?

Merci

Jérôme

[wiwaxia]

... Peut-on se servir de ta méthode "NTours" pour savoir si un polygone est concave ? si oui comment procéder ?
... / ...
si le polygone n'est ni convexe ni concave il sera forcément complexe (ce qui m'éviterai de mettre en place un test des intersections des segments par "brute-force" (tes des segment un à un) ou au pire j'essayerai d'implémenter l'algorithme décrit ici ...

... pour ce qui est de savoir si un polygone est concave j'ai ma réponse il faut simplement que je compares tous les angle et si il y en à un qui fait moins de la somme de 2 ??? angles consécutifs fait moins 180° bingo le polygone est concave, c'est bien cela, non ? ...

Plusieurs questions sont formulées, dont les réponses ne sont ni simples, ni indépendantes les unes des autres.
Quatre notions sont en cause, au sujet des courbes planes fermées, dont les polygones constituent un cas particulier: la convexité d'un domaine, les nombres d'enroulements et d'auto-intersections, et éventuellement l'aire algébrique du domaine délimité.

1°) Un domaine fermé de R² ou R³ est convexe si pour deux points quelconques (M_i,M_j) situés à l'intérieur de ce domaine ou sur sa frontière, tout autre point (M) du segment ouvert ]M_i,M_j[ appartient lui aussi au domaine considéré:

C'est manifestement le cas du premier polygone (I); le second présente un sommet rentrant qui fait de lui un polygone non-convexe.
La notion de "concavité" s'applique plutôt à une partie du contour - ici la séquence (P_k-1P_kP_k+1); l'alternative que tu présentes

si le polygone n'est ni convexe ni concave il sera forcément complexe (ce qui m'éviterai de mettre en place un test des intersections des segments par "brute-force"

est trompeuse parce que trop simple: le polygone étoilé utilisé au message #17 est délibérément dépourvu d'auto-intersection, et la "complexité" que tu évoques se réfère à deux notions (nombres d'enroulements et de croisements) largement (mais non strictement) indépendantes.

Le repérage des sommets rentrants sur un polygone (P) dépourvu de croisements peut s'effectuer simplement à l'aide de la fonction déjà donnée (Ntour(...)) , moyennant une correction minime de l'algorithme, en associant à chacun des sommets le polygone (P') privé du sommet considéré, et en comparant, relativement à (P'), les situations respectives du point (P_k) et d'un point fixe (Q) manifestement en-dehors de tout contour fermé compte tenu du choix de ses coordonnées;

(x_Q = 1.1 *x_max , y_Q = 1.1 *y_max).

La somme (établie sur P') des angles polaires vaut en effet
# A_total = 0 pour le point (Q) comme pour tout sommet sortant;
# A_total = ± 2π pour tout sommet rentrant, selon le sens de l'enroulement (direct ou rétrograde) du polyèdre associé (P'):

Je m'arrête ici pour l'instant.