PureBasic

Forums PureBasic
Nous sommes le Jeu 13/Déc/2018 3:48

Heures au format UTC + 1 heure




Poster un nouveau sujet Répondre au sujet  [ 14 messages ] 
Auteur Message
 Sujet du message: Un algo efficace pour remplir un polygone
MessagePosté: Jeu 11/Oct/2018 8:23 
Hors ligne
Avatar de l’utilisateur

Inscription: Mer 25/Aoû/2004 6:31
Messages: 2564
Localisation: Eragny
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 ? :P

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


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Un algo efficace pour remplir un polygone
MessagePosté: Jeu 11/Oct/2018 16:22 
Hors ligne
Avatar de l’utilisateur

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:
Priority Level | Operators
---------------+---------------------------
8 (high) | ~, - (negative)
7 | <<, >>, %, !
6 | |, &
5 | *, /
4 | +, - (substraction)
3 | >, >=, =>, <, <=, =<, =, <>
2 | Not
1 (low) | And, Or, XOr

_________________
Il y a deux méthodes pour écrire des programmes sans erreurs. Mais il n’y a que la troisième qui marche.
Version de PB : 5.45LTS - 32 bits


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Un algo efficace pour remplir un polygone
MessagePosté: Jeu 11/Oct/2018 16:32 
Hors ligne
Avatar de l’utilisateur

Inscription: Mer 25/Aoû/2004 6:31
Messages: 2564
Localisation: Eragny
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 :P
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


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Un algo efficace pour remplir un polygone
MessagePosté: Jeu 11/Oct/2018 17:30 
Hors ligne
Avatar de l’utilisateur

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

_________________
Il y a deux méthodes pour écrire des programmes sans erreurs. Mais il n’y a que la troisième qui marche.
Version de PB : 5.45LTS - 32 bits


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Un algo efficace pour remplir un polygone
MessagePosté: Ven 12/Oct/2018 7:12 
Hors ligne
Avatar de l’utilisateur

Inscription: Mer 25/Aoû/2004 6:31
Messages: 2564
Localisation: Eragny
génial Merci ... Je vais étudier ton code ... :mrgreen:


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Un algo efficace pour remplir un polygone
MessagePosté: Ven 12/Oct/2018 11:35 
Hors ligne
Avatar de l’utilisateur

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

_________________
Il y a deux méthodes pour écrire des programmes sans erreurs. Mais il n’y a que la troisième qui marche.
Version de PB : 5.45LTS - 32 bits


Dernière édition par Fig le Sam 13/Oct/2018 18:12, édité 1 fois.

Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Un algo efficace pour remplir un polygone
MessagePosté: Ven 12/Oct/2018 14:16 
Hors ligne
Avatar de l’utilisateur

Inscription: Mer 25/Aoû/2004 6:31
Messages: 2564
Localisation: Eragny
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


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Un algo efficace pour remplir un polygone
MessagePosté: Dim 14/Oct/2018 15:33 
Hors ligne

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.


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Un algo efficace pour remplir un polygone
MessagePosté: Dim 14/Oct/2018 19:34 
Hors ligne
Avatar de l’utilisateur

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

_________________
Il y a deux méthodes pour écrire des programmes sans erreurs. Mais il n’y a que la troisième qui marche.
Version de PB : 5.45LTS - 32 bits


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Un algo efficace pour remplir un polygone
MessagePosté: Mar 16/Oct/2018 4:38 
Hors ligne

Inscription: Ven 29/Juin/2007 17:50
Messages: 3220
Heureux de te revoir Thyphoon et... Sympa le double canular :D (ç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.


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Un algo efficace pour remplir un polygone
MessagePosté: Mar 16/Oct/2018 12:20 
Hors ligne
Avatar de l’utilisateur

Inscription: Mer 25/Aoû/2004 6:31
Messages: 2564
Localisation: Eragny
Ollivier a écrit:
Heureux de te revoir Thyphoon

Merci :oops: ... 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 8O faut vraiment que je regarde de plus prêt
Un grand merci pour le coup de main en tout cas.


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Un algo efficace pour remplir un polygone
MessagePosté: Ven 19/Oct/2018 9:53 
Hors ligne

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


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Un algo efficace pour remplir un polygone
MessagePosté: Sam 20/Oct/2018 1:03 
Hors ligne
Avatar de l’utilisateur

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


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Un algo efficace pour remplir un polygone
MessagePosté: Sam 20/Oct/2018 17:20 
Hors ligne
Avatar de l’utilisateur

Inscription: Mer 25/Aoû/2004 6:31
Messages: 2564
Localisation: Eragny
Merci Mesa et Demivec 8) C'est top ... Faut juste que j'arrive a trouver plus de 10 minutes a passer sur purebasic pour avancer un peu. :P


Haut
 Profil  
Répondre en citant le message  
Afficher les messages postés depuis:  Trier par  
Poster un nouveau sujet Répondre au sujet  [ 14 messages ] 

Heures au format UTC + 1 heure


Qui est en ligne

Utilisateurs parcourant ce forum: Aucun utilisateur enregistré et 5 invités


Vous ne pouvez pas poster de nouveaux sujets
Vous ne pouvez pas répondre aux sujets
Vous ne pouvez pas éditer vos messages
Vous ne pouvez pas supprimer vos messages

Rechercher:
Aller à:  

 


Powered by phpBB © 2008 phpBB Group | Traduction par: phpBB-fr.com
subSilver+ theme by Canver Software, sponsor Sanal Modifiye