/* Remplit de couleur un polygone de forme arbitraire décrit par VertexList.
 Si le premier et le dernier point de VertexList ne sont pas les mêmes, le parcours autour du polygone est automatiquement fermé. Tous les points sont déplacés par (XOffset, YDffset). Retourne 1 en cas de succès, 0 si l'allocation de la mémoire a échoué. Testé avec Borland C++.

Si la forme du polygone est déjà connue, un processus plus rapide peut être activé en spécifiant la forme comme suit: "convexe" - un élastique étiré autour du polygone devrait toucher tous les points dans l'ordre; "non convexe" - le polygone ne se coupe pas lui-même, il n'a pas besoin d'être convexe; "complexe" - le polygone se coupe lui-même, ou coupe toute sorte de polygones. Complexe fonctionnera pour tous les polygones; convexe est plus rapide. De mauvais résultats peuvent être obtenus si convexe est spécifié pour un polygone non convexe ou complexe.

Définissez CONVEX-CODE-LINKED si le code de remplissage rapide de polygone convexe de l'article de Février 1991 est lié. Sinon, les polygones convexes sont traités par le code de remplissage de polygone complexe.
Les polygones non convexes sont considérés comme complexes dans cette implémentation. Reportez-vous au texte concernant le traitement plus rapide des polygones non convexes.

    #include    <stdio.h>
    #include    <math.h>
    #ifdef      -TURBOC-
    #include    <alloc.h>
    #else       /* msc */
    #include    <malloc.h>
    #endif
    #include    "polygon.h"

#define SWAP(a,b) {temp= a; a= b; b = temp;}

struct EdgeState t
struct EdgeState *NextEdge;
int X;
int StartY;
int WholePixeIXMove:
int XDirection;
int ErrorTerm;
int ErrorTermAdjUp;
int ErrorTermAdjDown;
int Count;

extern  void DrawHorizoritalLineSeg(int, int, int, int);
extern  int FillMonotoneVerticalPolygon(struct PointListHeader
int, int, int);
extern int PolygonIsMonotoneVertical(-struct PointListHeader 
static void BuildGET(struct PointListHeader *, struct EdgeState
int, int);
static void MoveXSortedToAET(int)
static void ScanOutAET(int)
static  void AdvanceAET(void);
static  vold XSortAET(void):

/* Pointeurs sur les tables GET et les AET 
static struct EdgeState *GETPtr, *AETPtr:

int FîllPolygon(struct PointListHeader * VertexList. lnt Color, 
int PolygonShape, int XOffset, int YOffset)
{
struct EdgeState *EdgeTableBuffer; int CurrentY;


#ifdef CONVEX-CODE-LINKED
/* Les polygones convexes passent à travers le remplisseur rapide de polygone convexe
if((PolygonShape = CONVEX) Il
PolygonIsMonotoneVertical(VertexList"
return(FillMonotoneVerticalPolygon(VertexList, Color, XOffset.
YOffset";
#endif
/*Il faut au minimum 3 points pour afficher n'importe quel pixel; rejette les polygones qui sont garantis être invisibles
if   (VertexList->Length < 3)
return(l);
/*Récupère suffisamment de mémoire pour stocker complètement la table des bords
if   ((EdgeTableBuffer =
      (struct EdgeState *) (malloc(sizeof(struct EdgeState) *
     VertexList->Lengt))) - NULL)
return(0); /* n'a pas assez de mémoire pour la table
/*Construit la table GET */
BuildGET(VertexList, EdgeTableBuffer, XOffset, YOffset);
/*Parcourt les côtés du polygone, ligne d'affichage par ligne d'affichage, à condition qu'un coté au moins reste dans l'une des tables GET ou AET 
AETPtr = NULL;             /* initialise la table AET pour la vider 
CurrentY = GETPtr->StartY;      /* commence au point du haut du polygone
 while "GETPtr 1= NULL) Il (AETPtr 1= NULL" {
                     MoveXSortedToAET(CurrentY);     /*met à jour AET pour cette
                                                              ligne d'affichage */ 
                     ScanOutAET(CurrentY. Color);      /*affiche cette ligne 
                                                          d'affichage dans AET*/
                     AdvanceAET();                     /*avance les cotés AET 
                                                         d'une ligne d'affichage */
                     XSortAET();                      /*re-trie en fonction de X */
                     CurrentY++;                      /*passe à la prochaine ligne
                                                        d'affichage */

/* Libère la mémoire que nous avons allouée et nous avons terminé
free(EdgeTableBuffer);
return(l);
}

/* Crée une GET dans le tampon pointé par NextFreeEdgeStruc dans la liste de points. Les extrémités des cotés sont permutés, si nécessaire, pour garantir que tous les cotés vont de haut en bas La table GET est triée au préalable en ordre ascendant de la cordonnée Y de départ puis triée en ordre ascendant de la coordonnée X de départ à l'intérieur des cotés qui ont des coordonnées Y communes. */

static void BuildGET(struct PointListHeader * VertexList,
struct EdgeState * NextFreeEdgeStruc, int XOffset, int YOffset)
}

int 1-, StartX-, StartY.  EndX, EndY, DeltaY. DeltaX.  Width, temp:
    struct EdgeState *NewEdgePtr;
struct EdgeState *FollowingEdge, **FollowingEdgeLink;
 struct Point *VertexPtr;

/* Parcourt la liste de points et met tous les cotés qui ont une hauteur non nulle dans GET, triée en ordre ascendant des coordonnées Y de départ */
VertexPtr -      VertexList->PointPtr;   /* pointe sur la liste des points 
GETPtr = NULL;          /* initialise la table GET pour la vider 
for (i = 0; i < VertexList->Length, i++) {

/* Calcule la hauteur et la largeur d'un coté
StartX = VertexPtr[i],X + XOffset;
StartY =VertexPtr[il.Y + YOffset;

/* Le coté part du point courant au précédent */ 
if (i == 0) {
/* Revient en arrière en fin de liste */ 
EndX=VertexPtr[VertexList->Lenght-1].X+Xoffset ;
EndY=VertexPtr[VertexList->Lenght-1]Y+YOffset
}else{
EndX - VertexPtr[i-l].X + XOffset;
EndY - VertexPtr[i-1].Y + YOffset;
}

/*S'assure que le coté va de haut en bas
if  (StartY > EndY) {
SWAP(StartX, EndX);
SWAP(StartY.  EndY);
}
/*Saute s'il ne s'agit pas d'un coté actif ( de hauteur 0)
if  ((DeltaY = EndY - StartY) != 0) {
/* Alloue de l'espace pour l'info de ce coté, et remplit la structure */
NewEdgePtr = NextFreeEdgeStruc++;
NewEdgePtr->Xdirection = /* direction dans laquelle X se déplace
             ((DeltaX = EndX - StartX) > 0) ? 1 : -1;
Width = abs(DeltaX);
NewEdgePtr->X = StartX;
NewEdgePtr->StartY = StartY;
NewEdgePtr->Count = DeltaY ;
NewEdgePtr->ErrorTermAdjDown = DeltaY;
if (DeltaX >- 0) /* terme d'erreur initial allant de G->D */
NewEdgePtr->ErrorTerm - 0;
else               /* terme d'erreur allant de D->G */
NewEdgePtr->ErrorTerm = DeltaY + 1:
if (DeltaY >- Width) { /* coté principal Y */
NewEdgePtr->WholePixeIXMove = 0 ;
NewEdgePtr->ErrorTermAdjUp = Width;
}else {                     /* coté principal X*/
NewEdgePtr->WholePixelXMove -
(Width / DeltaY)* NewEdgePtr-->-Xdirection;
NewEdgePtr->ErrorTermAdjUp = Width % DeltaY;
}
/* Effectue un lien entre le nouveau coté et GET afin que la liste des cotés reste triée en fonction de la coordonnée Y, et en fonction de la coordonnée X pour tous les cotés de même coordonnée Y 
FollowingEdgeLink = &GETPtr ;
for (;;) {

FollowingEdge = *FollowingEdgeLink;

if((FollowingEdge = NULL) Il
(FollowingEdge->StartY > StartY)II
((FollowingEdge->StartY == StartY)
(FollowingEdge->X >= StartX))) {
NewEdgePtr->NextEdge = FollowingEdge;
*FollowingEdgeLink = NewEdgePtr;
break;
}

/* Trie tous les cotés de la table EAT dans l'ordre ascendant de la coordonnée X courante */
static void XSortAET() {
struct EdgeState *CurrentEdge, **CurrentEdgePtr, *TempEdge: 
int SwapOccurred;

/* Parcourt AET et permute tout coté adjacent pour lequel le deuxième coté est à une cordonnée X inférieure à celle du premier coté. Répète jusqu'à ce plus aucune permutation ne soit nécessaire */
if (AETPtr != NULL) {
do {
swapOccurred = 0;
currentEdgePtr = &AETPtr;
while ((CurrentEdge = *CurrentEdgePtr)->NextEdge != NULL) {
if   (CurrentEdge->X > CurrentEdge->NextEdge->X) {
/* Le deuxième coté a une coordonnée X inférieure à celle du premier; permutez-les dans AET */
TempEdge = CurrentEdge->Next-Edge->NextEdge;
*CurrentEdgePtr = CurrentEdge->NextEdge: 
CurrentEdge->NextEdge->NextEdge = CurrentEdge; 
CurrentEdge->NextEdge = TempEdge;
SwapOccurred = 1;
              }
          CurrentEdgePtr=&(*CurrentEdgePtr)->NextEdge ;
        }
      }while (SwapOccured != 0) ;
     }
    }
/* Avance chaque coté d'une ligne d'affichage dans AET.
Supprime tous les cotés qui ont été entièrement parcourus .*/ 
static void AdvanceAET() {
struct EdgeState *CurrentEdge, **CurrentEdgePtr;

/* Décompte et supprime ou avance chaque coté dans AET */
CurrentEdgePtr = &AETPtr;
while ((CurrentEdge = *CurrentEdgePtr) != NULL)
/* Décompte une ligne d'affichage pour ce coté*/ 
if ((--(CurrentEdge->Count" == 0) {
/* Ce coté est termine, supprimez-le de l'AET */
*CurrentEdgePtr = CurrentEdge->NextEdge; 
} else {
/* Avance la coordonnée X du coté d'un minimum */
CurrentEdge->X += CurrentEdge->WholePixelXMove; 
/* Détermine s'il est temps d'avancer X de un. */
if((CurrentEdge->ErrorTerm +=
CurrentEdge->ErrorTermAdjUp) > 0) {
CurrentEdge->X += CurrentEdge->XDirection:
CurrentEdge->ErrorTerm -= CurrentEdge->ErrorTermAdjDown:
}
CurrentEdgePtr = &CurrentEdge->NextEdge;
               }
             }
          }

/* Déplace tous les cotés qui commencent à la coordonnée Y spécifiée de GET à AET, tout en gardant le tri sur X d'AET.
static vold MoveXSortedToAET(int YToMove) {
struct EdgeState *AETEdge, **AETEdgePtr, *TempEdge; 
int CurrentX;

/* La table GET est triée sur Y. Tout coté commençant à la coordonnée Y désirée sera le premier dans GET, aussi nous passerons les cotés de GET à AET jusqu'à ce que le premier coté gauche dans GET ne dépasse pas la cordonnée Y. De plus, la table GET est triée sur X à l'intérieur de chaque cordonnée Y, si bien que chaque coté successif que nous ajouterons dans AET est garanti être placé après celui qui vient d'être ajouté dans AET.*/
AETEdgePtr = &AETPtr;
While((GETPtr !-=NULL) && (GETPtr->StartY == YtoMove)) }
CurrentX = GETPtr->X;
/* Effectue un lien entre le nouveau coté et AET afin que la table AET reste triée sur la coordonnée X */
for (;;) {
AETEdge = *AETEdgePtr;
if((AETEdge - NULL) II(AETEdge->X >- Current)) { 
TempEdge = GETPtr->NextEdge; 
*AETEdgePtr = GETPtr; /* effectue un lien entre le coté et la table AET*/
 GETPtr->NextEdge = AETEdge:
AETEdgePtr = &GETPtr->NextEdge;
GETPtr = TempEdge; /* supprime le lien entre le coté et la table GET */ 
break;
}else {
AETEdgePtr - &AETEdge->NextEdge;
  }
 }
}
/* Remplit la ligne d'affichage décrite par l'AET courante à la coordonnée Y spécifiée Y dans la couleur spécifiée, en appliquant la règle de remplissage pair/impair */ 
static void ScanOutAET(int YToScan, int Color)
int LeftX:
struct EdgeState *CurrentEdge;

/* Parcourt la table AET, en affichant des segments de ligne à chaque intersection d'une paire de cotés. Le pixel le plus proche ou à droite des cotés gauches est affichés, puis le pixel de gauche le plus proche et non sur le coté droit est affiché */
CurrentEdge - AETPtr:
while (CurrentEdge 1= NULL)
LeftX = CurrentEdge->X:
CurrentEdge = CurrentEdge->NextEdge;
DrawHorizontalLineSeg(YToScan, LeftX, CurrentEdge->X-1, Color);
CurrentEdge = CurrentEdge->NextEdge;
 }
}