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