Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

  1. #1
    Membre expert
    Rasterization de polygone complex
    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
    • "L'Homme devrait mettre autant d'ardeur à simplifier sa vie qu'il met à la compliquer" - Henri Bergson
    • "Bien des livres auraient été plus clairs s'ils n'avaient pas voulu être si clairs" - Emmanuel Kant
    • "La simplicité est la sophistication suprême" - Léonard De Vinci
    • "Ce qui est facile à comprendre ou à faire pour toi, ne l'est pas forcément pour l'autre." - Mon pèrei

    Mes projets sur Github - Blog - Site DVP

  2. #2
    Membre chevronné
    Rastérisation de polygone complexe
    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:


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique

  3. #3
    Expert confirmé
    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
    Nous souhaitons la vérité et nous trouvons qu'incertitude. [...]
    Nous sommes incapables de ne pas souhaiter la vérité et le bonheur, et sommes incapables ni de certitude ni de bonheur.
    Blaise Pascal
    PS : n'oubliez pas le tag

  4. #4
    Membre expert
    Citation Envoyé par wiwaxia Voir le message
    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;
    • "L'Homme devrait mettre autant d'ardeur à simplifier sa vie qu'il met à la compliquer" - Henri Bergson
    • "Bien des livres auraient été plus clairs s'ils n'avaient pas voulu être si clairs" - Emmanuel Kant
    • "La simplicité est la sophistication suprême" - Léonard De Vinci
    • "Ce qui est facile à comprendre ou à faire pour toi, ne l'est pas forcément pour l'autre." - Mon pèrei

    Mes projets sur Github - Blog - Site DVP

  5. #5
    Membre expert
    Salut
    Citation Envoyé par anapurna Voir le message
    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
    Citation Envoyé par anapurna Voir le message

    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

    Citation Envoyé par anapurna Voir le message

    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



    Citation Envoyé par anapurna Voir le message

    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
    • "L'Homme devrait mettre autant d'ardeur à simplifier sa vie qu'il met à la compliquer" - Henri Bergson
    • "Bien des livres auraient été plus clairs s'ils n'avaient pas voulu être si clairs" - Emmanuel Kant
    • "La simplicité est la sophistication suprême" - Léonard De Vinci
    • "Ce qui est facile à comprendre ou à faire pour toi, ne l'est pas forcément pour l'autre." - Mon pèrei

    Mes projets sur Github - Blog - Site DVP

  6. #6
    Membre expert
    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
    • "L'Homme devrait mettre autant d'ardeur à simplifier sa vie qu'il met à la compliquer" - Henri Bergson
    • "Bien des livres auraient été plus clairs s'ils n'avaient pas voulu être si clairs" - Emmanuel Kant
    • "La simplicité est la sophistication suprême" - Léonard De Vinci
    • "Ce qui est facile à comprendre ou à faire pour toi, ne l'est pas forcément pour l'autre." - Mon pèrei

    Mes projets sur Github - Blog - Site DVP

  7. #7
    Membre expert
    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
    • "L'Homme devrait mettre autant d'ardeur à simplifier sa vie qu'il met à la compliquer" - Henri Bergson
    • "Bien des livres auraient été plus clairs s'ils n'avaient pas voulu être si clairs" - Emmanuel Kant
    • "La simplicité est la sophistication suprême" - Léonard De Vinci
    • "Ce qui est facile à comprendre ou à faire pour toi, ne l'est pas forcément pour l'autre." - Mon pèrei

    Mes projets sur Github - Blog - Site DVP

  8. #8
    Membre expert
    Citation Envoyé par wiwaxia Voir le message
    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)
    • "L'Homme devrait mettre autant d'ardeur à simplifier sa vie qu'il met à la compliquer" - Henri Bergson
    • "Bien des livres auraient été plus clairs s'ils n'avaient pas voulu être si clairs" - Emmanuel Kant
    • "La simplicité est la sophistication suprême" - Léonard De Vinci
    • "Ce qui est facile à comprendre ou à faire pour toi, ne l'est pas forcément pour l'autre." - Mon pèrei

    Mes projets sur Github - Blog - Site DVP

  9. #9
    Membre chevronné
    Rastérisation de polygone complexe
    Bonjour,

    Citation Envoyé par BeanzMaster Voir le message
    ... 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é.
    Citation Envoyé par BeanzMaster Voir le message
    ... 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/


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique

  10. #10
    Membre chevronné
    Rastérisation de polygone complexe
    Citation Envoyé par BeanzMaster Voir le message
    ... 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.


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique

  11. #11
    Membre expert
    Bonjour,

    Citation Envoyé par wiwaxia Voir le message
    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


    Citation Envoyé par wiwaxia Voir le message

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

    Citation Envoyé par wiwaxia Voir le message

    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
    • "L'Homme devrait mettre autant d'ardeur à simplifier sa vie qu'il met à la compliquer" - Henri Bergson
    • "Bien des livres auraient été plus clairs s'ils n'avaient pas voulu être si clairs" - Emmanuel Kant
    • "La simplicité est la sophistication suprême" - Léonard De Vinci
    • "Ce qui est facile à comprendre ou à faire pour toi, ne l'est pas forcément pour l'autre." - Mon pèrei

    Mes projets sur Github - Blog - Site DVP

  12. #12
    Membre expert
    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
    • "L'Homme devrait mettre autant d'ardeur à simplifier sa vie qu'il met à la compliquer" - Henri Bergson
    • "Bien des livres auraient été plus clairs s'ils n'avaient pas voulu être si clairs" - Emmanuel Kant
    • "La simplicité est la sophistication suprême" - Léonard De Vinci
    • "Ce qui est facile à comprendre ou à faire pour toi, ne l'est pas forcément pour l'autre." - Mon pèrei

    Mes projets sur Github - Blog - Site DVP

  13. #13
    Expert confirmé
    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
    Nous souhaitons la vérité et nous trouvons qu'incertitude. [...]
    Nous sommes incapables de ne pas souhaiter la vérité et le bonheur, et sommes incapables ni de certitude ni de bonheur.
    Blaise Pascal
    PS : n'oubliez pas le tag

  14. #14
    Membre chevronné
    Rastérisation de polygone complexe
    Citation Envoyé par BeanzMaster Voir le message
    ... 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.


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique

  15. #15
    Membre expert
    Ce message n'a pas pu être affiché car il comporte des erreurs.
    • "L'Homme devrait mettre autant d'ardeur à simplifier sa vie qu'il met à la compliquer" - Henri Bergson
    • "Bien des livres auraient été plus clairs s'ils n'avaient pas voulu être si clairs" - Emmanuel Kant
    • "La simplicité est la sophistication suprême" - Léonard De Vinci
    • "Ce qui est facile à comprendre ou à faire pour toi, ne l'est pas forcément pour l'autre." - Mon pèrei

    Mes projets sur Github - Blog - Site DVP

  16. #16
    Membre chevronné
    Rastérisation de polygone complexe
    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 &#952;ij = (MPi , MPj) 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:
    Atot = 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 = (V1|V2) = x1.x2 + y1.y2 = N1N2.Cos(&#952 ;
    # le déterminant Dt = (V1×V2) = x1.y2 - y1.x2 = N1N2.Sin(&#952
    - en convenant de noter (N1, N2) les normes des vecteurs correspondants.

    Cependant aucune des relations réciproques:
    &#952; = ArcSin(Dt/N1N2) , &#952; = ArcCos(Ps/N1N2)
    ne peut être utilisée seule pour la détermination de l'angle orienté (&#952, 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é (&#952 appartient au semi-ouvert ]-&#960; ; +&#960;] 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(&#952| , |Cos(&#952|) , soit: &#952; = ± &#960;/4 ou ± 3&#960; /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é N1N2 = 0 ).


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique

  17. ###raw>post.musername###
    Membre chevronné
    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;
      0  0

  18. #18
    Membre expert
    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
    • "L'Homme devrait mettre autant d'ardeur à simplifier sa vie qu'il met à la compliquer" - Henri Bergson
    • "Bien des livres auraient été plus clairs s'ils n'avaient pas voulu être si clairs" - Emmanuel Kant
    • "La simplicité est la sophistication suprême" - Léonard De Vinci
    • "Ce qui est facile à comprendre ou à faire pour toi, ne l'est pas forcément pour l'autre." - Mon pèrei

    Mes projets sur Github - Blog - Site DVP

  19. #19
    Membre expert
    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
    • "L'Homme devrait mettre autant d'ardeur à simplifier sa vie qu'il met à la compliquer" - Henri Bergson
    • "Bien des livres auraient été plus clairs s'ils n'avaient pas voulu être si clairs" - Emmanuel Kant
    • "La simplicité est la sophistication suprême" - Léonard De Vinci
    • "Ce qui est facile à comprendre ou à faire pour toi, ne l'est pas forcément pour l'autre." - Mon pèrei

    Mes projets sur Github - Blog - Site DVP

  20. #20
    Membre chevronné
    Rastérisation de polygone complexe
    Ce message n'a pas pu être affiché car il comporte des erreurs.


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique