Un algo efficace pour remplir un polygone

Thyphoon

j'essaie de convertir ce code en C trouvé ici http://alienryderflex.com/polygon_fill/ pour remplir rapidement un polygone.
Vous vous douter que ça ne fonctionne pas

Voici le code d'origine

Code:

//  public-domain code by Darel Rex Finley, 2007



int  nodes, nodeX[MAX_POLY_CORNERS], pixelX, pixelY, i, j, swap ;

//  Loop through the rows of the image.
for (pixelY=IMAGE_TOP; pixelY<IMAGE_BOT; pixelY++) {

  //  Build a list of nodes.
  nodes=0; j=polyCorners-1;
  for (i=0; i<polyCorners; i++) {
    if (polyY[i]<(double) pixelY && polyY[j]>=(double) pixelY
    ||  polyY[j]<(double) pixelY && polyY[i]>=(double) pixelY) {
      nodeX[nodes++]=(int) (polyX[i]+(pixelY-polyY[i])/(polyY[j]-polyY[i])
      *(polyX[j]-polyX[i])); }
    j=i; }

  //  Sort the nodes, via a simple “Bubble” sort.
  i=0;
  while (i<nodes-1) {
    if (nodeX[i]>nodeX[i+1]) {
      swap=nodeX[i]; nodeX[i]=nodeX[i+1]; nodeX[i+1]=swap; if (i) i--; }
    else {
      i++; }}

  //  Fill the pixels between node pairs.
  for (i=0; i<nodes; i+=2) {
    if   (nodeX[i  ]>=IMAGE_RIGHT) break;
    if   (nodeX[i+1]> IMAGE_LEFT ) {
      if (nodeX[i  ]< IMAGE_LEFT ) nodeX[i  ]=IMAGE_LEFT ;
      if (nodeX[i+1]> IMAGE_RIGHT) nodeX[i+1]=IMAGE_RIGHT;
      for (pixelX=nodeX[i]; pixelX<nodeX[i+1]; pixelX++) fillPixel(pixelX,pixelY); }}}

et voilà un code pour tester ma conversion en PB... le code en C si dessus converti en PB est dans la procédure drawPollyFull.
Mais j'ai du faire des erreurs... je n'ai fait que peu de C dans ma vie .. et je suis pas certain d'avoir fait comme il fallait

si il y a quelqu'un qui maîtrise suffisamment le C a le temps de jeter un oeil pour m'indiquer ou chercher l'erreur ?

Code:

NewList V.point()
ClearList(V())

AddElement(V()):V()\x=300:V()\y=250:n+1
AddElement(V()):V()\x=350:V()\y=250:n+1
AddElement(V()):V()\x=80:V()\y=10:n+1
AddElement(V()):V()\x=450:V()\y=250:n+1
AddElement(V()):V()\x=400:V()\y=300:n+1
AddElement(V()):V()\x=450:V()\y=280:n+1
AddElement(V()):V()\x=280:V()\y=400:n+1
AddElement(V()):V()\x=340:V()\y=280:n+1

;-Pour tracer le contour du Polygone 
Procedure drawPoly(List polylist.point())
  Protected pa.point
  Protected pb.point
  Protected dist.l
  Protected baryCenter.point
  For i=0 To ListSize(polylist())-1
    SelectElement(polylist(),i)
    pa\x=polylist()\x
    pa\y=polylist()\y
    ;si on arrive a la fin de la liste on prend comme point i+1 le premier point
    If i=ListSize(polylist())-1
      SelectElement(polylist(),0)
    Else  
      SelectElement(polylist(),i+1)
    EndIf  
    pb\x=polylist()\x
    pb\y=polylist()\y
    
    color=#Green
    
    LineXY(pa\x,pa\y,pb\x,pb\y,color)
    Circle(pa\x,pa\y,5,#Red)
    DrawText(pa\x+10,pa\y+10,Str(i))
    
  Next
  
EndProcedure

;tracer un Polygone plein
Procedure drawPolyFull(List polylist.point())
  ;http://alienryderflex.com/polygon_fill/
  Protected.l nodes,pixelX,pixelY,i,j,Swp
  Protected Dim _nodeX.l(ListSize(polylist()))
  Protected Dim polyX.l(ListSize(polylist()))
  Protected Dim polyY.l(ListSize(polylist()))
  ;Found Image_Top
  Protected IMAGE_BOP=1080
  Protected IMAGE_BOT=0
  Protected IMAGE_LEFT=1920
  Protected IMAGE_RIGHT=0
  ForEach polylist()
    If polylist()\y<IMAGE_BOP
      IMAGE_BOP=polylist()\y
    EndIf
    If polylist()\y>IMAGE_TOP
      IMAGE_TOP=polylist()\y
    EndIf
    If polylist()\x<IMAGE_LEFT
      IMAGE_LEFT=polylist()\x
    EndIf
    If polylist()\x>IMAGE_RIGHT
      IMAGE_RIGHT=polylist()\x
    EndIf
    
    polyX(ListIndex(polylist()))=polylist()\x
    polyY(ListIndex(polylist()))=polylist()\y
  Next
  
  Debug ElapsedMilliseconds()
  Debug "IMAGE_BOP:"+Str(IMAGE_BOP)
  Debug "IMAGE_TOP:"+Str(IMAGE_TOP)
  Debug "IMAGE_LEFT:"+Str(IMAGE_LEFT)
  Debug "IMAGE_RIGHT:"+Str(IMAGE_RIGHT)
  
  ;  Loop through the rows of the image.
  For pixelY=IMAGE_BOP To IMAGE_TOP
    
    ;  Build a list of nodes.
    
    polycorners=ListSize(polylist())
    nodes=0
    j=polyCorners-1
    
    For i=0 To polyCorners-1
      
      If (polyY(i)<pixelY And polyY(j)>=pixelY Or polyY(j)<pixelY And polyY(i)>=pixelY)
        _nodeX(nodes)=(polyX(i)+(pixelY-polyY(i))/(polyY(j)-polyY(i))*(polyX(j)-polyX(i)))
        Debug "nodeX("+Str(nodes)+")="+Str(_nodeX(nodes))
        nodes=nodes+1
      EndIf 
      j=i;
    Next i
    
    ;  Sort the nodes, via a simple “Bubble” sort.
    i=0;
    While (i<nodes-1)
      If (_nodeX(i)>_nodeX(i+1)) 
        Swp=_nodeX(i)
        _nodeX(i)=_nodeX(i+1)
        _nodeX(i+1)=Swp
        If (i)
          i=i-1;
        EndIf  
      Else
        i=i+1; 
      EndIf 
    Wend 
    
    ;  Fill the pixels between node pairs.
    Debug nodes
    For i=0 To nodes-1 Step 2; i<nodes; i+=2) <<<<<<<<<<<<<<<Pas sur d'avoir fait ce qu'il faut
      If   (_nodeX(i  )>=IMAGE_RIGHT) 
        Break;
      EndIf 
      If   (_nodeX(i+1)> IMAGE_LEFT )
        If (_nodeX(i  )< IMAGE_LEFT )
          _nodeX(i  )=IMAGE_LEFT ;
        EndIf 
        If (_nodeX(i+1)> IMAGE_RIGHT)
          _nodeX(i+1)=IMAGE_RIGHT;
        EndIf 
        For pixelX=_nodeX(i) To _nodeX(i+1) ;<<<<<< TO DO remplacer cette boucle une simple commande LINE
          Debug Str(pixelX)+","+Str(pixelY)
          Plot(pixelX,pixelY,RGB(255,0,0))
        Next PixelX
      EndIf 
    Next i
    
  Next pixelY
  
EndProcedure




If InitSprite()
  If InitKeyboard() And InitMouse()
    winMain = OpenWindow(#PB_Any,0,0,800,600,"Press [Esc] to close",#PB_Window_ScreenCentered | #PB_Window_SystemMenu)
    OpenWindowedScreen(WindowID(winMain), 0, 0,800,600, 1, 0, 0)
    SetFrameRate(60)
  EndIf
Else
  MessageRequester("","Unable to initsprite") :
EndIf
Repeat
  Delay(1)
  EventID = WindowEvent()
  ExamineKeyboard()
  ExamineMouse()
  ClearScreen(col)
  
  StartDrawing(ScreenOutput())
  drawPoly(V())
  drawPolyFull(V())
  Circle(MouseX(),MouseY(),5,#Blue)
  
  
  StopDrawing()
  FlipBuffers()
Until KeyboardReleased(#PB_Key_Escape) Or EventID = #PB_Event_CloseWindow

Fig · **Inscription:** Jeu 14/Oct/2004 19:48 **Messages:** 1113

Une remarque en passant, la priorité des opérateurs logiques va au && puis au || en C...
La priorité entre les opérateurs booléens n'est pas clair dans la doc de Pb (tous priorité basse, mais entre eux, mystère), mais il est plus sûr de rajouter des parenthèses.

documentation Pb a écrit:

Thyphoon

Fig a écrit:

Une remarque en passant, la priorité des opérateurs logiques va au && puis au || en C...
La priorité entre les opérateurs booléens n'est pas clair dans la doc de Pb (tous priorité basse, mais entre eux, mystère), mais il est plus sûr de rajouter des parenthèses.

Merci beaucoup ^_^ J'avais pas pensé à ça

bon c'est pas encore ça mais déjà ça dessine quelques choses

j'ai remplacé la dernière boucle qui trace pixel par picel par la commande LineXY... c'est un peu plus rapide ... ^_^

Code:

NewList V.point()
ClearList(V())

AddElement(V()):V()\x=300:V()\y=250:n+1
AddElement(V()):V()\x=350:V()\y=250:n+1
;AddElement(V()):V()\x=80:V()\y=10:n+1
;AddElement(V()):V()\x=450:V()\y=250:n+1
AddElement(V()):V()\x=400:V()\y=300:n+1
;AddElement(V()):V()\x=450:V()\y=280:n+1
;AddElement(V()):V()\x=280:V()\y=400:n+1
AddElement(V()):V()\x=340:V()\y=280:n+1

;-Pour tracer le contour du Polygone 
Procedure drawPoly(List polylist.point())
  Protected pa.point
  Protected pb.point
  Protected dist.l
  Protected baryCenter.point
  For i=0 To ListSize(polylist())-1
    SelectElement(polylist(),i)
    pa\x=polylist()\x
    pa\y=polylist()\y
    ;si on arrive a la fin de la liste on prend comme point i+1 le premier point
    If i=ListSize(polylist())-1
      SelectElement(polylist(),0)
    Else  
      SelectElement(polylist(),i+1)
    EndIf  
    pb\x=polylist()\x
    pb\y=polylist()\y
    
    color=#Green
    
    LineXY(pa\x,pa\y,pb\x,pb\y,color)
    Circle(pa\x,pa\y,5,#Red)
    DrawText(pa\x+10,pa\y+10,Str(i))
    
  Next
  
EndProcedure

;tracer un Polygone plein
Procedure drawPolyFull(List polylist.point())
  ;http://alienryderflex.com/polygon_fill/
  Protected.l nodes,pixelX,pixelY,i,j,Swp
  If ListSize(polylist())<3
    ProcedureReturn 0
  EndIf
  
  Protected Dim _nodeX.l(ListSize(polylist()))
  Protected Dim polyX.l(ListSize(polylist()))
  Protected Dim polyY.l(ListSize(polylist()))
  ;Found Image_Top
  Protected IMAGE_BOP=1080
  Protected IMAGE_BOT=0
  Protected IMAGE_LEFT=1920
  Protected IMAGE_RIGHT=0
  ForEach polylist()
    If polylist()\y<IMAGE_BOP
      IMAGE_BOP=polylist()\y
    EndIf
    If polylist()\y>IMAGE_TOP
      IMAGE_TOP=polylist()\y
    EndIf
    If polylist()\x<IMAGE_LEFT
      IMAGE_LEFT=polylist()\x
    EndIf
    If polylist()\x>IMAGE_RIGHT
      IMAGE_RIGHT=polylist()\x
    EndIf
    
    polyX(ListIndex(polylist()))=polylist()\x
    polyY(ListIndex(polylist()))=polylist()\y
  Next
  
  Debug ElapsedMilliseconds()
  Debug "IMAGE_BOP:"+Str(IMAGE_BOP)
  Debug "IMAGE_TOP:"+Str(IMAGE_TOP)
  Debug "IMAGE_LEFT:"+Str(IMAGE_LEFT)
  Debug "IMAGE_RIGHT:"+Str(IMAGE_RIGHT)
  
  ;  Loop through the rows of the image.
  For pixelY=IMAGE_BOP To IMAGE_TOP
    
    ;  Build a list of nodes.
    
    polycorners=ListSize(polylist())
    nodes=0
    j=polyCorners-1
    
    For i=0 To polyCorners-1
      
      If (polyY(i)<pixelY And polyY(j)>=pixelY) Or (polyY(j)<pixelY And polyY(i)>=pixelY)
        _nodeX(nodes)=(polyX(i)+(pixelY-polyY(i))/(polyY(j)-polyY(i))*(polyX(j)-polyX(i)))
        ;Debug "nodeX("+Str(nodes)+")="+Str(_nodeX(nodes))
        nodes=nodes+1
      EndIf 
      j=i;
    Next i
    
    ;  Sort the nodes, via a simple “Bubble” sort.
    i=0;
    While (i<nodes-1)
      If (_nodeX(i)>_nodeX(i+1)) 
        Swp=_nodeX(i)
        _nodeX(i)=_nodeX(i+1)
        _nodeX(i+1)=Swp
        If (i)
          i=i-1;
        EndIf  
      Else
        i=i+1; 
      EndIf 
    Wend 
    
    ;  Fill the pixels between node pairs.
    Debug nodes
    For i=0 To nodes-1 Step 2; i<nodes; i+=2) <<<<<<<<<<<<<<<Pas sur d'avoir fait ce qu'il faut
      If   (_nodeX(i  )>=IMAGE_RIGHT) 
        Break;
      EndIf 
      If   (_nodeX(i+1)> IMAGE_LEFT )
        If (_nodeX(i  )< IMAGE_LEFT )
          _nodeX(i  )=IMAGE_LEFT ;
        EndIf 
        If (_nodeX(i+1)> IMAGE_RIGHT)
          _nodeX(i+1)=IMAGE_RIGHT;
        EndIf 
        LineXY(_nodeX(i),pixelY,_nodeX(i+1),pixelY,RGB(255,0,0))
        ;For pixelX=_nodeX(i) To _nodeX(i+1) ;<<<<<< TO DO remplacer cette boucle une simple commande LINE
          ;Debug Str(pixelX)+","+Str(pixelY)
         ; Plot(pixelX,pixelY,RGB(255,0,0))
        ;Next PixelX
      EndIf 
    Next i
    
  Next pixelY
  
EndProcedure




If InitSprite()
  If InitKeyboard() And InitMouse()
    winMain = OpenWindow(#PB_Any,0,0,800,600,"Press [Esc] to close",#PB_Window_ScreenCentered | #PB_Window_SystemMenu)
    OpenWindowedScreen(WindowID(winMain), 0, 0,800,600, 1, 0, 0)
    SetFrameRate(60)
  EndIf
Else
  MessageRequester("","Unable to initsprite") :
EndIf
Repeat
  Delay(1)
  EventID = WindowEvent()
  ExamineKeyboard()
  ExamineMouse()
  ClearScreen(col)
  
  StartDrawing(ScreenOutput())
  drawPolyFull(V())
  drawPoly(V())
  
  Circle(MouseX(),MouseY(),5,#Blue)
  
  
  StopDrawing()
  FlipBuffers()
Until KeyboardReleased(#PB_Key_Escape) Or EventID = #PB_Event_CloseWindow

Fig · **Inscription:** Jeu 14/Oct/2004 19:48 **Messages:** 1113

Je ne l'aurai pas écrit comme ça, mais voila...
J'ai décomposé le calcul, il faut faire attention en C l'ordre du calcul et des arrondis/cast par rapport à ce que fait Pb...
J'ai retiré le tri à bulle pour un tri Pb, mais tu peux le remettre...
Ca n'est pas parfait manifestement, je pense que ça vient de là:

Code:

        If (poly(i)\y<pixelY And poly(j)\y>=pixelY) Or (poly(j)\y<pixelY And poly(i)\y>=pixelY)
            division.f=(pixelY-poly(i)\y)/(poly(j)\y-poly(i)\y)*(poly(j)\x-poly(i)\x)
            NodesX(nodes)=division+poly(i)\x
            nodes+1
        EndIf

Mais c'est déja le cas dans le code en C.
Pour améliorer ça, il faudrait tracer les lignes avec Bresenham et sauvegarder les points, puis appliquer le même principe en évitant les calculs de pente, donc.

Code:

NewList V.point()
AddElement(V()):V()\x=300:V()\y=250
AddElement(V()):V()\x=350:V()\y=250
AddElement(V()):V()\x=80:V()\y=10
AddElement(V()):V()\x=450:V()\y=250
AddElement(V()):V()\x=400:V()\y=300
AddElement(V()):V()\x=450:V()\y=280
AddElement(V()):V()\x=280:V()\y=400
AddElement(V()):V()\x=340:V()\y=280



;-Pour tracer le contour du Polygone 
Procedure drawPoly(List V.point())
    Protected pa.point,pb.point
    LastElement(V())
    pb\x=V()\x:pb\y=V()\y
    ForEach V()
        pa\x=V()\x
        pa\y=V()\y
        LineXY(pa\x,pa\y,pb\x,pb\y,#Green)
        Circle(pa\x,pa\y,2,#Green)
        DrawText(pa\x+10,pa\y+10,Str(ListIndex(V())))
        pb\x=pa\x
        pb\y=pa\y
    Next
EndProcedure

;tracer un Polygone plein
Procedure drawPolyFull(List V.point())
  ;http://alienryderflex.com/polygon_fill/
  Protected.i nodes,pixelX,pixelY,i,j
  Protected Dim NodesX.i(ListSize(V()))
  Protected Dim poly.point(ListSize(V()))
  ;définit les extrémités du polygone
  Protected BOT.i=0
  Protected TOP.i=1080
  Protected RIGHT.i=0
  Protected LEFT.i=1920
  ForEach V()
      If V()\y>Bot:BOT=V()\y:EndIf
      If V()\y<TOP:TOP=V()\y:EndIf
      If V()\x<LEFT:LEFT=V()\x:EndIf
      If V()\x>RIGHT:RIGHT=V()\x:EndIf
      poly(ListIndex(V()))\x=V()\x
      poly(ListIndex(V()))\y=V()\y
  Next
 
  ;  Loop through the rows of the image.
  For pixelY=TOP To BOT
    ;  Build a list of nodes.    
    polycorners=ListSize(V())
    nodes=0
    j=polyCorners-1
    For i=0 To polyCorners-1
        If (poly(i)\y<pixelY And poly(j)\y>=pixelY) Or (poly(j)\y<pixelY And poly(i)\y>=pixelY)
            division.f=(pixelY-poly(i)\y)/(poly(j)\y-poly(i)\y)*(poly(j)\x-poly(i)\x)
            NodesX(nodes)=division+poly(i)\x
            nodes+1
        EndIf 
        j=i
    Next i
    ;  Sort the nodes
    SortArray(NodesX(),#PB_Sort_Ascending)

    ;  Fill the pixels between node pairs.
    For i=0 To nodes-1 Step 2
        If (NodesX(i)>=RIGHT):Break:EndIf 
        If (NodesX(i+1)>LEFT )
            If (NodesX(i)<LEFT):NodesX(i)=LEFT:EndIf
            If (NodesX(i+1)>RIGHT):NodesX(i+1)=RIGHT:EndIf 
            LineXY(NodesX(i),pixely,NodesX(i+1),pixely,RGB(255,0,0))
        EndIf 
    Next i
  Next pixelY
EndProcedure

If InitSprite()
  If InitKeyboard() And InitMouse()
    winMain = OpenWindow(#PB_Any,0,0,800,600,"Press [Esc] to close",#PB_Window_ScreenCentered | #PB_Window_SystemMenu)
    OpenWindowedScreen(WindowID(winMain), 0, 0,800,600, 1, 0, 0)
    SetFrameRate(60)
  EndIf
Else
  MessageRequester("","Unable to initsprite") :
EndIf
Repeat
  Delay(1)
  EventID = WindowEvent()
  ExamineKeyboard()
  ExamineMouse()
  ClearScreen(col)
  
  StartDrawing(ScreenOutput())
  drawPolyFull(V())
  drawPoly(V())
  Circle(MouseX(),MouseY(),5,#Blue)  
  StopDrawing()
  FlipBuffers()
Until KeyboardReleased(#PB_Key_Escape) Or EventID = #PB_Event_CloseWindow

Thyphoon

génial Merci ... Je vais étudier ton code ... :mrgreen:

Fig · **Inscription:** Jeu 14/Oct/2004 19:48 **Messages:** 1113

Code:

Pour améliorer ça, il faudrait tracer les lignes avec Bresenham et sauvegarder les points, puis appliquer le même principe en évitant les calculs de pente, donc.

Le mieux ça serait ça. Ce n'est pas très compliqué à faire, mais là je n'ai ni le temps ni la tête à ça. Peut être quand les choses que j'ai à régler se seront calmés...

Thyphoon

Fig a écrit:

Code:

Pour améliorer ça, il faudrait tracer les lignes avec Bresenham et sauvegarder les points, puis appliquer le même principe en évitant les calculs de pente, donc.

Le mieux ça serait ça. Ce n'est pas très compliqué à faire, mais là je n'ai ni le temps ni la tête à ça. Peut être quand les choses que j'ai à régler ce seront calmés...

j'ai pas eu le temps de regarder ce qu'était Bresenham... mais je vais essayer ce week-end

Ollivier · **Inscription:** Ven 29/Juin/2007 17:50 **Messages:** 3220

Bonjour à vous,

mon humble suggestion :

1) Une méthode consiste à balayer tout le graphique et faire alterner un état interieur/extérieur du polygone dès que le curseur de balayage touche un segment du polygone. Ça marche pour les polygones concaves et convexes.

Avantage : peut remplir simultanément plusieurs polygones séparés
Inconvénient : gourmand en mémoire, sauf si utilisation d'une map.
Difficulté : la gestion des sommets

2) Une autre méthode consiste à découper le polygone en triangles et à remplir les triangles.
Avantage : le plus rapide, et compatible avec l'accélération matérielle

Inconvénient : non fiable avec les concaves
Difficulté : détermination du centre commun à tous les triangles.

3) Une troisième méthode : fillArea ou "paint"

Conclusion : remplir efficacement un ou plusieurs polygones nécessite sûrement un choix de méthode en fonction du nombre de polygones à remplir simultanément et en fonction de la nature du polygone, si un seul polygone est à remplir.

En espérant vous aider...

Nota : Il me semble que Comtois a publié un algo pour Bresenheim et LSI un algo de tracé de ligne avec anti-crénelage.

Bon courage à vous.

Fig · **Inscription:** Jeu 14/Oct/2004 19:48 **Messages:** 1113

Voir les notes en tête de listing...
C'est rapide, fini le scan de chaque x de chaque ligne.

Code:

;Note: Reste à faire
;Résoudre le bug
;Supprimer les ariables globals X(), Top, Bot
;Remplacer la map par un Dim
;Remplacer le tri PB par un tri par insertion, car déja quasiment trié et peu d'élements...
Structure xx
    List x.i()
EndStructure
NewList V.point()
Global NewMap X.xx();attention au nombre de slot...
Global Top.i=1080
Global Bot.i=0
AddElement(V()):V()\x=300:V()\y=250
AddElement(V()):V()\x=350:V()\y=250
AddElement(V()):V()\x=80:V()\y=10
AddElement(V()):V()\x=450:V()\y=250
AddElement(V()):V()\x=400:V()\y=300
AddElement(V()):V()\x=450:V()\y=280
AddElement(V()):V()\x=280:V()\y=400
AddElement(V()):V()\x=340:V()\y=280

Macro tracePixel()
    mapkey.s=Str(y1)
    If FindMapElement(X(),mapkey)=0 
        AddMapElement(X(),mapkey)
        AddElement(x()\x())
        X()\x()=x1
    ElseIf y11<>y22
        LastElement(x()\x())
        If Abs(x()\x()-x1)>1
            AddElement(x()\x())
            X()\x()=x1
        ElseIf x1<x()\x()
            X()\x()=x1
        EndIf      
    EndIf
EndMacro

Procedure LineBresenham(x11.i,y11.i,x22.i,y22.i)
    x1.i=x11
    y1.i=y11
    x2.i=x22
    y2.i=y22
    ;Adapté du pseudo code https://fr.wikipedia.org/wiki/Algorithme_de_trac%C3%A9_de_segment_de_Bresenham
    ;Algorithme général optimisé
    Define.i dx,dy,err
    dx=x2-x1
    If dx<>0
        If dx>0
            dy=y2-y1
            If dy<>0
                If dy>0
                    ; vecteur oblique dans le 1er quadran
                    If dx>=dy
                        ; vecteur diagonal ou oblique proche de l’horizontale, dans le 1er octant
                        err=dx
                        dx*2
                        dy*2 ;  e est positif
                        Repeat  ; déplacements horizontaux
                            tracePixel();
                            x1+1
                            If x1=x2:Break:EndIf ;
                            err-dy
                            If err<0
                                y1+1 ;  // déplacement diagonal
                                err+dx  ;
                            EndIf       ;
                        ForEver         ;
                    Else
                        ; vecteur oblique proche de la verticale, dans le 2d octant
                        err=dy
                        dy*2
                        dx*2
                        Repeat              ; déplacements verticaux
                            tracePixel()    ;
                            y1+1
                            If y1=y2:Break:EndIf
                            err-dx;
                            If err<0
                                x1+1 ;  // déplacement diagonal
                                err+dy  ;
                            EndIf       ;
                        ForEver         ;
                    EndIf               ;
                Else                    ; dy < 0 (et dx > 0)
                                        ; vecteur oblique dans le 4e cadran
                    If dx>=-dy
                        ; vecteur diagonal ou oblique proche de l’horizontale, dans le 8e octant
                        err=dx
                        dx*2
                        dy*2 ;  // e est positif
                        Repeat              ; déplacements horizontaux
                            tracePixel()    ;
                            x1+1
                            If x1=x2:Break:EndIf ;
                            err+dy
                            If err<0
                                y1-1 ;  // déplacement diagonal
                                err+dx  ;
                            EndIf       ;
                        ForEver         ;
                    Else                ; vecteur oblique proche de la verticale, dans le 7e octant
                        err=dy
                        dy*2
                        dx*2 ;  // e est négatif
                        Repeat              ; déplacements verticaux
                            tracePixel()    ;
                            y1-1
                            If y1=y2:Break:EndIf ;
                            err+dx
                            If err>0
                                x1+1 ;  // déplacement diagonal
                                err+dy  ;
                            EndIf       ;
                        ForEver         ;
                    EndIf               ;
                EndIf                   ;
            Else                        ; dy = 0 (et dx > 0)
                                        ; vecteur horizontal vers la droite
                Repeat
                    tracePixel() ;
                Until (x1=x1+1)=x2     ;
            EndIf                      ;
        Else                           ; dx < 0
            dy=y2-y1
            If dy<>0
                If dy>0
                    ; vecteur oblique dans le 2d quadran
                    If -dx>=dy
                        ; vecteur diagonal ou oblique proche de l’horizontale, dans le 4e octant
                        err=dx
                        dx*2
                        dy*2;  // e est négatif
                        Repeat              ; déplacements horizontaux
                            tracePixel()    ;
                            x1-1
                            If x1=x2:Break:EndIf ;
                            err+dy
                            If err>=0
                                y1+1 ;  // déplacement diagonal
                                err+dx  ;
                            EndIf       ;
                        ForEver         ;
                    Else
                        ; vecteur oblique proche de la verticale, dans le 3e octant
                        err=dy
                        dy*2
                        dx*2
                        Repeat              ; déplacements verticaux
                            tracePixel()    ;
                            y1+1
                            If y1=y2:Break:EndIf ;
                            err+dx
                            If err<=0
                                x1-1 ;  // déplacement diagonal
                                err+dy  ;
                            EndIf       ;
                        ForEver         ;
                    EndIf               ;
                Else                    ; dy < 0 (et dx < 0)
                                        ; vecteur oblique dans le 3e cadran
                    If dx<=dy
                        ; vecteur diagonal ou oblique proche de l’horizontale, dans le 5e octant
                        err=dx
                        dx*2
                        dy*2; est negatif
                        Repeat              ; déplacements horizontaux
                            tracePixel()    ;
                            x1-1
                            If x1=x2:Break:EndIf ;
                            err-dy
                            If err>=0
                                y1-1
                                err+dx  ;
                            EndIf       ;
                        ForEver         ;
                    Else                ; vecteur oblique proche de la verticale, dans le 6e octant
                        err=dy
                        dy*2
                        dx*2 ;  // e est négatif
                        Repeat              ; déplacements verticaux
                            tracePixel()    ;
                            y1-1
                            If y1=y2:Break:EndIf ;
                            err-dx
                            If err>=0
                                x1-1 ;  // déplacement diagonal
                                err+dy  ;
                            EndIf       ;
                        ForEver         ;
                    EndIf               ;
                EndIf                   ;
            Else                        ; dy = 0 (et dx < 0)
                                        ; vecteur horizontal vers la gauche
                Repeat
                    tracePixel() ;
                    x1-1
                Until x1=x2     ;
            EndIf               ;
        EndIf                   ;
    Else                        ; dx = 0
        dy=y2-y1
        If dy<>0
            If dy>0
                ; vecteur vertical croissant
                Repeat
                    tracePixel() ;
                    y1+1
                Until y1=y2     ;
            Else                ; dy < 0 (et dx = 0)
                                ; vecteur vertical décroissant
                Repeat
                    tracePixel() ;
                    y1-1
                Until y1=y2     ;
            EndIf               ;
        EndIf                   ;
    EndIf                       ;
                                ;f le pixel final (x2, y2) n’est pas tracé.
EndProcedure

Procedure EffacePoly()
    ForEach X()
        FreeList(x()\x())
    Next
    ClearMap(x())
EndProcedure

Procedure BresenhamPoly(List V.point())
    Protected pa.point,pb.point
    LastElement(V())
    pb\x=V()\x:pb\y=V()\y
    ForEach V()
        pa\x=V()\x
        pa\y=V()\y
        LineBresenham(pa\x,pa\y,pb\x,pb\y)
        pb\x=pa\x
        pb\y=pa\y
        If V()\y>BOT:BOT=V()\y:EndIf
        If V()\y<TOP:TOP=V()\y:EndIf
    Next
EndProcedure

;tracer un Polygone plein
Procedure DrawPolyFull()
    For pixelY=TOP To BOT
        seg.s=Str(pixely)
        If FindMapElement(x(),seg)
            SortList(x()\x(),#PB_Sort_Ascending)
            FirstElement(x()\x())
            Repeat
                x1=x()\x()
                If NextElement(x()\x())=0:Break:EndIf
                x2=x()\x()
                LineXY(x1,pixely,x2,pixely,#Red)
            Until NextElement(x()\x())=0
        EndIf 
    Next pixely
EndProcedure

If InitSprite()
  If InitKeyboard() And InitMouse()
    winMain = OpenWindow(#PB_Any,0,0,800,600,"Press [Esc] to close",#PB_Window_ScreenCentered | #PB_Window_SystemMenu)
    OpenWindowedScreen(WindowID(winMain), 0, 0,800,600, 1, 0, 0)
    SetFrameRate(60)
  EndIf
Else
  MessageRequester("","Unable to initsprite") :
EndIf
BresenhamPoly(V())
Repeat
  Delay(1)
  EventID = WindowEvent()
  ExamineKeyboard()
  ExamineMouse()
  ClearScreen(col)
  

  StartDrawing(ScreenOutput())
  drawPolyFull()
  Circle(MouseX(),MouseY(),5,#Blue)  
  StopDrawing()
  FlipBuffers()
Until KeyboardReleased(#PB_Key_Escape) Or EventID = #PB_Event_CloseWindow

Ollivier · **Inscription:** Ven 29/Juin/2007 17:50 **Messages:** 3220

Heureux de te revoir Thyphoon et... Sympa le double canular

(ça sent le pixel à tout faire)

Code:

@
@@    Cas n°1
@ @
@  @


@@
@ @@  Cas n°2
@   @@

Il est impossible de dicerner les cas 1 et 2.
Et quand, bien même l'on s'y attèle (par appartenance aux segments), il est impossible de dicerner les séries à 3 pixels ou plus, sans passer par la force brute.

Thyphoon

Ollivier a écrit:

Heureux de te revoir Thyphoon

Merci

... je suis jamais vraiment parti...mais je manque tellement de temps....

(Ne faites pas d'enfant c'est un piège :mrgreen:

)

Fig a écrit:

Voir les notes en tête de listing...
C'est rapide, fini le scan de chaque x de chaque ligne.

Toujours pas eu le temps de faire autre chose que juste tester rapidement ton code ... C'est impressionnant

faut vraiment que je regarde de plus prêt
Un grand merci pour le coup de main en tout cas.

Mesa · **Inscription:** Mer 14/Sep/2011 16:59 **Messages:** 880

J'ai trouvé ça dans mes archives mais je ne sais plus qui l'a créé.

M.

Code:

Structure Pt
  x.i
  y.i
EndStructure

Structure PtPair
  A.Pt
  B.Pt
EndStructure

Structure PtPairSlopeCache Extends PtPair
  yperx.d
EndStructure

Procedure MaxI(A, B)
  If A > B
    ProcedureReturn A
  EndIf
  ProcedureReturn B
EndProcedure

Procedure MinI(A, B)
  If A < B
    ProcedureReturn A
  EndIf
  ProcedureReturn B
EndProcedure

; Return the x of a line for a given y
Macro LineX(y, Line)
  (line\yperx * (y-Line\A\y) + Line\A\x)
EndMacro

; Whether a ray like this crosses a line segment
;  |-------------------->
; *a is the topmost point (smallest y), *b is the lowest point
Procedure XRayCrossesLine(x, y, *Line.PtPairSlopeCache)
  If y <= *line\A\y
    ProcedureReturn 0
  ElseIf y > *line\B\y
    ProcedureReturn 0
  ElseIf LineX(y, *Line) > x
    ProcedureReturn 1
  Else
    ProcedureReturn 0
  EndIf
EndProcedure

; Make sure *a\y < *b\y
Procedure CorrectPointOrder(*a.pt, *b.pt)
  If *a\y > *b\y
    Swap *a\x, *b\x
    Swap *a\y, *b\y
  EndIf
EndProcedure

; Precalc line slope
Procedure.d Slope(*a.pt, *b.pt)
  dx.i = (*b\x-*a\x)
  dy.i = (*b\y-*a\y)
  ProcedureReturn dx/dy
EndProcedure

; Make the lines conform to expectations
Procedure PrepLines(List Lines.PtPairSlopeCache())
  ForEach Lines()
    CorrectPointOrder(Lines()\A, Lines()\B)
    Lines()\yperx = Slope(Lines()\A, Lines()\B)
  Next
EndProcedure

; Convert a list of points into a list of lines
Procedure GetPolyLines(List Poly.pt(), List Lines.PtPairSlopeCache())
  FirstElement(Poly())
  Prev.pt = Poly()
  While NextElement(Poly())
    AddElement(Lines())
    Lines()\A = Prev
    Lines()\B = Poly()
    Prev = Poly()
  Wend
  ; Connect last point to first
  AddElement(lines())
  lines()\A = Prev
  FirstElement(Poly())
  lines()\B = Poly()
  ; Prep lines
  PrepLines(Lines())
EndProcedure

Procedure PtInPoly(x, y, List Lines.PtPairSlopeCache())
  Protected Intersections = 0
  FirstElement(Lines())
  ForEach Lines()
    Intersections + XRayCrossesLine(x, y, @Lines())
  Next
  ProcedureReturn Intersections & 1
EndProcedure

Procedure GetPolyExtents(List Poly.Pt(), *TopLeft.Pt, *BtmRight.Pt)
  ForEach Poly()
    *TopLeft\x = MinI(*TopLeft\x, Poly()\x)
    *TopLeft\y = MinI(*TopLeft\y, Poly()\y)
    *BtmRight\x = MaxI(*BtmRight\x, Poly()\x)
    *BtmRight\y = MaxI(*BtmRight\y, Poly()\y)
  Next
EndProcedure

Procedure FillPolygonWithCache(xoff, yoff, List Poly.Pt(), List Lines.PtPairSlopeCache(), color)
  GetPolyExtents(Poly(), TopLeft.Pt, BtmRight.Pt)
  w = BtmRight\x - TopLeft\x
  h = BtmRight\y - TopLeft\y
  For x = TopLeft\x To w
    For y = TopLeft\y To h
      If PtInPoly(x, y, Lines())
        Plot(x+xoff, y+yoff, color)
      EndIf
    Next
  Next
EndProcedure

Procedure FillPolygon(xoff, yoff, List Poly.Pt(), color=255)
  Protected NewList Lines.PtPairSlopeCache()
  GetPolyLines(Poly(), Lines())
  FillPolygonWithCache(xoff, yoff, Poly(), Lines(), color)
EndProcedure

Procedure OutlinePolygonWithCache(xoff, yoff, List Poly.Pt(), List Lines.PtPairSlopeCache(), color)
  ForEach Lines()
    LineXY(Lines()\A\x + xoff, Lines()\A\y + yoff, Lines()\B\x + xoff, Lines()\B\y + yoff, color)
  Next
EndProcedure

Procedure OutlinePolygon(xoff, yoff, List Poly.Pt(), color=0)
  Protected NewList Lines.PtPairSlopeCache()
  GetPolyLines(Poly(), Lines())
  OutlinePolygonWithCache(xoff, yoff, Poly(), Lines(), color)
EndProcedure

Procedure RenderPolygon(xoff, yoff, List Poly.Pt(), FillColor=255, OutlineColor=0)
  Protected NewList Lines.PtPairSlopeCache()
  GetPolyLines(Poly(), Lines())
  FillPolygonWithCache(xoff, yoff, Poly(), Lines(), FillColor)
  OutlinePolygonWithCache(xoff, yoff, Poly(), Lines(), OutlineColor)
EndProcedure

;- Test code:

Procedure MyPatternPainter(x, y, src, target)
  r = 255-(((x/4)&1) | ((y/4)&1))*255
  ProcedureReturn RGB(r, x*y, r)
EndProcedure

OpenWindow(0, 0, 0, 512, 384, "", #PB_Window_SystemMenu | #PB_Window_ScreenCentered | #PB_Window_SizeGadget)

Macro AddPt(l, _x, _y)
  AddElement(l)
  l\x = _x
  l\y = _y
EndMacro

NewList rect.pt()

AddPt(rect(), 10, 10)
AddPt(rect(), 125, 15)
AddPt(rect(), 120, 100)
AddPt(rect(), 15, 90)

NewList Star.Pt()
AddPt(Star(), 0, 13)
AddPt(Star(), 15, 13)
AddPt(Star(), 20, 0)
AddPt(Star(), 25, 13)
AddPt(Star(), 40, 13)
AddPt(Star(), 27, 22)
AddPt(Star(), 32, 35)
AddPt(Star(), 20, 27)
AddPt(Star(), 7, 35)
AddPt(Star(), 12, 22)

ForEach Star()
  Star()\x = Star()\x * 4 + 130
  Star()\y = Star()\y * 4 + 30
Next


w = 512
h = 384
CreateImage(0, w, h, 24)
t = ElapsedMilliseconds()
StartDrawing(ImageOutput(0))
  Box(0, 0, w, h, RGB(255, 255, 255))
 
  ; Show our box
  RenderPolygon(0, 0, rect(), RGB(255, 128, 32), RGB(128, 64, 16))
 
  ; Advanced: gradient fill (of star)
  DrawingMode(#PB_2DDrawing_Gradient)
  CircularGradient(200, 100, 100)
  RandomSeed(63)
  For I = 0 To 20
    GradientColor(I/20, RGB(Random(255), Random(255), Random(255)))
  Next
  FillPolygon(0, 0, star())
  DrawingMode(#PB_2DDrawing_Default)
  OutlinePolygon(0, 0, Star())
 
  ; Advanced: pattern fill (with custom callback)
  DrawingMode(#PB_2DDrawing_CustomFilter)
  CustomFilterCallback(@MyPatternPainter())
  FillPolygon(0, 200, rect())
  DrawingMode(#PB_2DDrawing_Default)
  OutlinePolygon(0, 200, rect(), RGB(0, 255, 0))

 
StopDrawing()
t = ElapsedMilliseconds()-t
; MessageRequester("", Str(t))

ImageGadget(0, 0, 0, 0, 0, ImageID(0))

Repeat
  Event = WaitWindowEvent()
Until Event = #PB_Event_CloseWindow

Demivec · **Inscription:** Sam 18/Sep/2010 18:13 **Messages:** 63

Mesa a écrit:

J'ai trouvé ça dans mes archives mais je ne sais plus qui l'a créé.

@Mesa: Trond l'a créé. Ici https://www.purebasic.fr/english/viewtopic.php?f=12&t=44074

Thyphoon

Merci Mesa et Demivec

C'est top ... Faut juste que j'arrive a trouver plus de 10 minutes a passer sur purebasic pour avancer un peu.

PureBasic

Un algo efficace pour remplir un polygone

Qui est en ligne