/*Remplit de couleur un polygone convexe. Tous les points sont décalé 
par(XOffset, YOffset).
"Convexe" signifie "uniforme en fonction de la ligne verticale" ; c'est-à-dire, 
que chaque ligne horizontale affichée à travers le polygone en tout point 
devrait croiser exactement deux cotés actifs(ni les lignes horizontales ni les 
cotés de longueur=zéro ne comptent comme cotés actifs; les deux sont acceptables n'importe où dans le polygone). Les cotés droit & gauche peuvent se croiser 
(polygones peuvent être non simples). Les Polygones qui ne sont pas convexes 
conformément à cette définition ne seront pas affichés correctement. (Certes, "convexe" est un terme inadéquat pour ce type de polygone, mais il est pratique
employez "uniforme-vertical" si vous préférez!)
*******************************************************************
NOTE: La routine d'affichage de bas niveau, DrawHorizontalLineList, doit 
être capable d'inverser les cotés, s'il est nécessaire de faire du cotés gauche
le coté correct. Elle doit également prévoir que le coté droit est spécifié dans 
le format +1 (la coordonnée X dépasse de 1 la coordonnée la plus élevée à 
afficher).En fonction de cela, elle diffère des routines d'affichage de bas
niveau présentées dans les listings précédents ; des modifications sont nécessaires pour pouvoir afficher des polygones uniformes-verticaux non simples
ce qui par la suite permet d'utiliser le test de Jim Kent sur les polygones
uniformes-verticaux.
*******************************************************************
Retourne 1 en cas de réussite, 0 si l'allocation de la mémoire a échoué.
  Testé avec Borland C++ 4.02 en modèle small par Jim Mischel 12/16/94.
*/

#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include "polygon.h"

/* Avance l'index de un point dans la liste des points, en
   bouclant à la fin de la liste */
#define INDEX_FORWARD(Index) \
   Index = (Index + 1) % VertexList->Length;

/* Recule l'index de un point dans la liste points,
   bouclant au début de la liste */
#define INDEX_BACKWARD(Index) \
   Index = (Index - 1 + VertexList->Length) % VertexList->Length;

/* Avance l'index de un point en avant ou en arrière dans la liste
   de points, en bouclant à la fin ou au début de la liste */
#define INDEX_MOVE(Index,Direction)                                  \
   if (Direction > 0)                                                \
      Index = (Index + 1) % VertexList->Length;                      \
   else                                                              \
      Index = (Index - 1 + VertexList->Length) % VertexList->Length;

extern void ScanEdge(int, int, int, int, int, int, struct HLine **);
extern void DrawHorizontalLineList(struct HLineList *, int);

int FillMonotoneVerticalPolygon(struct PointListHeader * VertexList,
      int Color, int XOffset, int YOffset)
{
   int i, MinIndex, MaxIndex, MinPoint_Y, MaxPoint_Y;
   int NextIndex, CurrentIndex, PreviousIndex;
   struct HLineList WorkingHLineList;
   struct HLine *EdgePointPtr;
   struct Point *VertexPtr;

   /* Pointe sur la liste de point */
   VertexPtr = VertexList->PointPtr;

   /* Parcourt la liste pour trouver le haut et le bas du polygone */
   if (VertexList->Length == 0)
      return(1);  /* rejette les polygones nuls */
   MaxPoint_Y = MinPoint_Y = VertexPtr[MinIndex = MaxIndex = 0].Y;
   for (i = 1; i < VertexList->Length; i++) {
      if (VertexPtr[i].Y < MinPoint_Y)
         MinPoint_Y = VertexPtr[MinIndex = i].Y; /* nouveau haut*/
      else if (VertexPtr[i].Y > MaxPoint_Y)
         MaxPoint_Y = VertexPtr[MaxIndex = i].Y; /* nouveau bas */
   }

   /* Paramètre le nombre de lignes d'affichage dans le polygone, sautant le cotés du       
      bas */
   if ((WorkingHLineList.Length = MaxPoint_Y - MinPoint_Y) <= 0)
      return(1);  /* rien n'est à afficher,  nous avons donc fini */
   WorkingHLineList.YStart = YOffset + MinPoint_Y;

   /* Récupère la mémoire dans laquelle stocker la liste de lignes que nous générons */
   if ((WorkingHLineList.HLinePtr =
         (struct HLine *) (malloc(sizeof(struct HLine) *
         WorkingHLineList.Length))) == NULL)
      return(0);  /* ne peut pas récupérer de la mémoire pour cette liste de lignes */

   /* Parcourt le premier cotés et stocke les points limites dans la liste */
   /* Pointeur initial pour stocker les coordonnées numérisées du premier cotés*/
   EdgePointPtr = WorkingHLineList.HLinePtr;
   /* Commence en haut du premier edge */
   PreviousIndex = CurrentIndex = MinIndex;
   /* Numérise chaque ligne du premier coté de haut en bas */
   do {
      INDEX_BACKWARD(CurrentIndex);
      ScanEdge(VertexPtr[PreviousIndex].X + XOffset,
            VertexPtr[PreviousIndex].Y,
            VertexPtr[CurrentIndex].X + XOffset,
            VertexPtr[CurrentIndex].Y, 1, 0, &EdgePointPtr);
      PreviousIndex = CurrentIndex;
   } while (CurrentIndex != MaxIndex);

   /* Parcourt le second coté et stocke les points limites dans la liste */
   EdgePointPtr = WorkingHLineList.HLinePtr;
   PreviousIndex = CurrentIndex = MinIndex;
   do {
      INDEX_FORWARD(CurrentIndex);
      ScanEdge(VertexPtr[PreviousIndex].X + XOffset,
            VertexPtr[PreviousIndex].Y,
            VertexPtr[CurrentIndex].X + XOffset,
            VertexPtr[CurrentIndex].Y, 0, 0, &EdgePointPtr);
      PreviousIndex = CurrentIndex;
   } while (CurrentIndex != MaxIndex);

   /* Affiche la liste de lignes représentant le polygone*/
   DrawHorizontalLineList(&WorkingHLineList, Color);

   /* Libère la mémoire de la liste de lignes et nous avons réussi */
   free(WorkingHLineList.HLinePtr);
   return(1);
}