/*------------------------------------------------------------\
|                                                             |
| Tool    :                     RDS                           |
|                                                             |
| File    :                  Rut acces                        |
|                                                             |
| Authors :                Jacomme Ludovic                    |
|                                                             |
| Date    :                   01.08.93                        |
|                                                             |
\------------------------------------------------------------*/

/*------------------------------------------------------------\
|                                                             |
|                         Include Files                       |
|                                                             |
\------------------------------------------------------------*/

# include MPH_H
# include MUT_H
# include RDS_H
# include RPR_H
# include RFM_H
# include RUT_H
# include "rutacces.h"
# include "ruterror.h"
# include "math.h"

/*------------------------------------------------------------\
|                                                             |
|                           Constants                         |
|                                                             |
\------------------------------------------------------------*/
/*------------------------------------------------------------\
|                                                             |
|                            Types                            |
|                                                             |
\------------------------------------------------------------*/
/*------------------------------------------------------------\
|                                                             |
|                          Variables                          |
|                                                             |
\------------------------------------------------------------*/
/*------------------------------------------------------------\
|                                                             |
|                         Symmetry Table                      |
|                                                             |
\------------------------------------------------------------*/

  char RDS_SYMMETRY_TABLE[ RDS_MAX_TRANSF ][ RDS_MAX_TRANSF ] =

  {
    { RDS_NOSYM, RDS_ROT_P, RDS_SYMXY, RDS_ROT_M, RDS_SYM_X, RDS_SY_RM, RDS_SYM_Y, RDS_SY_RP },
    { RDS_ROT_P, RDS_SYMXY, RDS_ROT_M, RDS_NOSYM, RDS_SY_RP, RDS_SYM_X, RDS_SY_RM, RDS_SYM_Y },
    { RDS_SYMXY, RDS_ROT_M, RDS_NOSYM, RDS_ROT_P, RDS_SYM_Y, RDS_SY_RP, RDS_SYM_X, RDS_SY_RM },
    { RDS_ROT_M, RDS_NOSYM, RDS_ROT_P, RDS_SYMXY, RDS_SY_RM, RDS_SYM_Y, RDS_SY_RP, RDS_SYM_X },
    { RDS_SYM_X, RDS_SY_RM, RDS_SYM_Y, RDS_SY_RP, RDS_NOSYM, RDS_ROT_P, RDS_SYMXY, RDS_ROT_M },
    { RDS_SY_RM, RDS_SYM_Y, RDS_SY_RP, RDS_SYM_X, RDS_ROT_M, RDS_NOSYM, RDS_ROT_P, RDS_SYMXY },
    { RDS_SYM_Y, RDS_SY_RP, RDS_SYM_X, RDS_SY_RM, RDS_SYMXY, RDS_ROT_M, RDS_NOSYM, RDS_ROT_P },
    { RDS_SY_RP, RDS_SYM_X, RDS_SY_RM, RDS_SYM_Y, RDS_ROT_P, RDS_SYMXY, RDS_ROT_M, RDS_NOSYM }
  };

/*------------------------------------------------------------\
|                                                             |
|                       Privates variables                    |
|                                                             |
\------------------------------------------------------------*/

  static ptype_list *HEAD_RDSMODEL = (ptype_list *)NULL;
  static long        RdsIndexModel = 0;

/*------------------------------------------------------------\
|                                                             |
|                          Functions                          |
|                                                             |
\------------------------------------------------------------*/
/*------------------------------------------------------------\
|                                                             |
|                        Search Functions                     |
|                                                             |
\------------------------------------------------------------*/
/*------------------------------------------------------------\
|                                                             |
|                       Search Rds Figure                     |
|                                                             |
\------------------------------------------------------------*/

  rdsfig_list *searchrdsfig( Name )

    char *Name;
  {
    rdsfig_list *Figure;

    Name = namealloc( Name );

    for ( Figure  = HEAD_RDSFIG;
          Figure != (rdsfig_list *)NULL;
          Figure  = Figure->NEXT )
    {
      if ( Figure->NAME == Name ) break;
    }

    return( Figure );
  }

/*------------------------------------------------------------\
|                                                             |
|                        Search Rds Instance                  |
|                                                             |
\------------------------------------------------------------*/

  rdsins_list *searchrdsins( Figure, Name )

     rdsfig_list *Figure;
     char        *Name;
  {
    rdsins_list *Instance;

    Name = namealloc( Name );

    for ( Instance  = Figure->INSTANCE;
          Instance != (rdsins_list *)NULL;
          Instance  = Instance->NEXT )
    {
      if ( Instance->INSNAME == Name ) break;
    }

    return( Instance );
  }

/*------------------------------------------------------------\
|                                                             |
|                      getrdsmodellist                        |
|                                                             |
\------------------------------------------------------------*/

  ptype_list *getrdsmodellist( Figure )

    rdsfig_list *Figure;
  {
    ptype_list  *Head;
    ptype_list  *Stop;
    ptype_list  *Scan;
    ptype_list  *Search;
    rdsfig_list *Model;
    rdsins_list *Instance;

    if ( HEAD_RDSMODEL != (ptype_list *)NULL )
    {
      freeptype( HEAD_RDSMODEL );
      HEAD_RDSMODEL = (ptype_list *)NULL;
    }

    HEAD_RDSMODEL = addptype( HEAD_RDSMODEL, ++RdsIndexModel, (char*)Figure );
    Stop          = (ptype_list *)NULL;

    do
    {
      Head = HEAD_RDSMODEL;

      for ( Scan  = Head;
            Scan != Stop;
            Scan  = Scan->NEXT )
      {
        for ( Instance  = ((rdsfig_list *)(Scan->DATA))->INSTANCE;
              Instance != (rdsins_list *)NULL;
              Instance  = Instance->NEXT )
        {
          for ( Search  = HEAD_RDSMODEL;
                Search != (ptype_list *)NULL;
                Search  = Search->NEXT )
          {
            if (((rdsfig_list *)Search->DATA)->NAME == Instance->FIGNAME )
            {
              break;
            }
          }

          if ( Search == (ptype_list *)NULL )
          {
            Model = searchrdsfig( Instance->FIGNAME );

            if ( Model == (rdsfig_list *)NULL )
            {
              ruterror( RDS_MODEL_NOT_FOUND, Instance->FIGNAME );
            }

            HEAD_RDSMODEL = addptype( HEAD_RDSMODEL, ++RdsIndexModel, (char*)Model );
          }
        }
      }

      Stop = Head;
    }
    while ( Head != HEAD_RDSMODEL );

    return( HEAD_RDSMODEL );
  }

/*------------------------------------------------------------\
|                                                             |
|                    Apply Rds Symmetry                       |
|                                                             |
\------------------------------------------------------------*/

  void applyrdssym( X, Y, Dx, Dy, Xins, Yins, Sym )

     long  *X;
     long  *Y; 
     long  *Dx;
     long  *Dy;
     long  Xins;
     long  Yins;
     char  Sym;
  {
    long  OldX;
    long  OldY;
    long  OldDx;
    long  OldDy;

    OldX  = *X;
    OldY  = *Y;
    OldDx = *Dx;
    OldDy = *Dy;

    switch ( Sym ) 
    {
      case RDS_NOSYM : *X += Xins;
                       *Y += Yins;

                     break;

      case RDS_SYM_X : *X  = Xins - OldX - OldDx;
                       *Y += Yins;
      
                     break;

      case RDS_SYM_Y : *X += Xins ;
                       *Y  = Yins - OldY - OldDy;
      
                     break;

      case RDS_SYMXY : *X  = Xins - OldX - OldDx;
                       *Y  = Yins - OldY - OldDy;
      
                     break;

      case RDS_ROT_P : *X  = Xins - OldY - OldDy;
                       *Y  = Yins + OldX;
                       *Dx = OldDy;
                       *Dy = OldDx;

                     break;

      case RDS_ROT_M : *X  = Xins + OldY;
                       *Y  = Yins - OldX - OldDx;
                       *Dx = OldDy;
                       *Dy = OldDx;
      
                     break;

      case RDS_SY_RP : *X  = Xins + OldY;
                       *Y  = Yins + OldX;
                       *Dx = OldDy;
                       *Dy = OldDx;

                     break;

      case RDS_SY_RM : *X  = Xins - OldY - OldDy;
                       *Y  = Yins - OldX - OldDx;
                       *Dx = OldDy;
                       *Dy = OldDx;

                     break;
    }
  }

/*------------------------------------------------------------\
|                                                             |
|                         applyrdsmode                        |
|                                                             |
\------------------------------------------------------------*/

  void applyrdsmode( Figure, Mode )

    rdsfig_list *Figure;
    char         Mode;
  {
    char          Layer; 
    rdsrec_list  *Rectangle;
    rdsrec_list  *InsRec;
    rdsrec_list **Previous;
    rdsins_list  *Instance;
    rdsfig_list  *Model;

    if ( Figure->MODE == Mode ) return;

    if ( Mode == 'P' )
    {
      for ( Layer = 0; Layer < RDS_MAX_LAYER; Layer++ )
      {
        Rectangle =  Figure->LAYERTAB[ Layer ];
        Previous  = &Figure->LAYERTAB[ Layer ];

        while ( Rectangle != (rdsrec_list *)NULL )
        {
          if ( ( IsRdsConnector( Rectangle ) ) ||
               ( IsRdsFigure( Rectangle    ) ) ||
               ( ( IsRdsSegment( Rectangle ) &&
                 ( ( Layer == RDS_TPOLY ) ||
                   ( Layer == RDS_TALU1 ) ||
                   ( Layer == RDS_TALU2 ) ||
                   ( Layer == RDS_TALU3 ) ) ) ) )
          {
            Previous  = &Rectangle->NEXT;
            Rectangle = Rectangle->NEXT;
          }
          else 
          {
            *Previous = Rectangle->NEXT;
            freerdsrec( Rectangle, Figure->SIZE );
            Rectangle = *Previous;
          }
        }
      }

      while ( Figure->INSTANCE != (rdsins_list *)NULL )
      {
        delrdsins( Figure, Figure->INSTANCE->INSNAME );
      }
    }
    else
    if ( Mode == 'V' )
    {
      for ( Instance  = Figure->INSTANCE;
            Instance != (rdsins_list *)NULL;
            Instance  = Instance->NEXT )
      {
        Model = searchrdsfig( Instance->FIGNAME );

        if ( Model == (rdsfig_list *)NULL )
        {
          ruterror( RDS_MODEL_NOT_FOUND, Instance->FIGNAME );
        }
        
        for ( Layer = 0; Layer < RDS_MAX_LAYER; Layer++ )
        {
          for ( Rectangle  = Model->LAYERTAB[ Layer ];
                Rectangle != (rdsrec_list *)NULL;
                Rectangle  = Rectangle->NEXT )
          {
            if ( ( IsRdsConnector( Rectangle ) ) ||
                 ( Layer == RDS_ABOX           ) ||
                 ( ( IsRdsSegment( Rectangle ) &&
                 ( ( Layer == RDS_TPOLY ) ||
                   ( Layer == RDS_TALU1 ) ||
                   ( Layer == RDS_TALU2 ) ||
                   ( Layer == RDS_TALU3 ) ) ) ) )
            {
               InsRec = 

                 addrdsinsrec( Instance, 
                               ( Layer == RDS_ABOX ) 
                             ? Instance->INSNAME : Rectangle->NAME,
                               Layer,
                               Rectangle->X, Rectangle->Y,
                               Rectangle->DX, Rectangle->DY );

              ClearRdsFigRec( InsRec );
              
              if ( IsRdsConnector( Rectangle ) ) 
              {
                SetRdsConnector( InsRec );
                SetRdsConInter( InsRec );
              }
              else
              if ( IsRdsSegment( Rectangle ) )
              {
                SetRdsSegment( InsRec );
              }
              else
              {
                SetRdsInstance( InsRec );
              }

              applyrdssym( &InsRec->X, &InsRec->Y, &InsRec->DX, &InsRec->DY,
                           Instance->X, Instance->Y, Instance->TRANSF );
            }
          }
        }
      }
    }
    else
    if ( Mode == 'A' )
    {
      for ( Instance  = Figure->INSTANCE;
            Instance != (rdsins_list *)NULL;
            Instance  = Instance->NEXT )
      {
        for ( Layer = 0; Layer < RDS_MAX_LAYER; Layer++ )
        {
          while ( Instance->LAYERTAB[ Layer ] != (rdsrec_list *)NULL )
          {
            delrdsinsrec( Instance, Instance->LAYERTAB[ Layer ] );
          }
        }
      }
    }

    Figure->MODE = Mode;
  }

/*------------------------------------------------------------\
|                                                             |
|                    Flatten Functions                        |
|                                                             |
\------------------------------------------------------------*/
/*------------------------------------------------------------\
|                                                             |
|                    Flatten Rds Figure                       |
|                                                             |
\------------------------------------------------------------*/
 
  void flattenrdsfig( Figure, InsName, Concat )

    rdsfig_list *Figure;
    char        *InsName;
    char         Concat;
  {
    rdsins_list *Instance;
    rdsfig_list *Model;
    rdsrec_list *NewRec;
    rdsrec_list *ScanRec;
    rdsins_list *ScanIns;
    char         Layer;
    long         Xins;
    long         Yins;
    long         Dxins;

    Instance = searchrdsins( Figure, InsName );

    if ( Instance == (rdsins_list *)NULL ) return;

    Model = searchrdsfig( Instance->FIGNAME );

    if ( Model == (rdsfig_list *)NULL )
    {
      ruterror( RDS_MODEL_NOT_FOUND, Instance->FIGNAME );
    }
        
    for ( Layer = 0; Layer < RDS_MAX_LAYER; Layer++ )
    {
      if ( Layer == RDS_ABOX ) continue;

      for ( ScanRec  = Model->LAYERTAB[ Layer ];
            ScanRec != (rdsrec_list *)NULL;
            ScanRec  = ScanRec->NEXT )
      {
        NewRec = addrdsfigrec( Figure, 
                               ScanRec->NAME, Layer,
                               ScanRec->X, ScanRec->Y,
                               ScanRec->DX, ScanRec->DY );

        SetRdsMbkType( NewRec, GetRdsMbkType( ScanRec ) );

        if ( IsRdsConnector( NewRec ) ) SetRdsSegment( NewRec );

        applyrdssym( &NewRec->X, &NewRec->Y, &NewRec->DX, &NewRec->DY,
                     Instance->X, Instance->Y, Instance->TRANSF );
      }
    }

    for ( ScanIns  = Model->INSTANCE;
          ScanIns != (rdsins_list *)NULL;
          ScanIns  = ScanIns->NEXT )
    {
      Xins  = ScanIns->X;
      Yins  = ScanIns->Y;
      Dxins = 0;

      applyrdssym( &Xins, &Yins, &Dxins, &Dxins,
                   Instance->X, Instance->Y, Instance->TRANSF );

      addrdsins( Figure, ScanIns->FIGNAME, 
                 Concat == RDS_NO ? 
                 ScanIns->INSNAME : concatname( InsName, ScanIns->INSNAME ),
                 RDS_SYMMETRY_TABLE[ ScanIns->TRANSF ][ Instance->TRANSF ],
                 Xins, Yins );
    }

    delrdsins( Figure, InsName );
  }

/*------------------------------------------------------------\
|                                                             |
|                   rflatten Rds Figure                       |
|                                                             |
\------------------------------------------------------------*/

  void rflattenrdsfig( Figure, Concat, Catal )
  
    rdsfig_list *Figure;
    char         Concat;
    char         Catal;
  {
    rdsins_list *Instance;

    Instance = Figure->INSTANCE;

    while ( Instance != (rdsins_list *)NULL )
    {
      if ( ( Catal == RDS_NO                      ) ||     
           ( ! incatalog( Instance->FIGNAME )     ) || 
           ( incatalogdelete( Instance->FIGNAME ) ) )
      {
        flattenrdsfig( Figure, Figure->INSTANCE->INSNAME, Concat );

        Instance = Figure->INSTANCE;
      }
      else
      {
        Instance = Instance->NEXT;
      }
    }
  }

/*------------------------------------------------------------\
|                                                             |
|                          Tools                              |
|                                                             |
\------------------------------------------------------------*/
/***********
*
*                        QUICKSORT
*
* Cette procedure sert a trier un tableau d'entiers dans l'ordre croissant.
*
***/
static void quicksort(tab, deb, fin)
long tab[];
unsigned        deb, fin;
{
register long   m, aux;
register unsigned       i, j;

        i = deb;
        j = fin;
        m = tab[(deb+fin) >> 1];                         /* on repere le milieu du tableau */
        do {
                while (tab[i] < m)
                        i++;
                while (tab[j] > m)
                        j--;
                if ( i <= j ) {
                        aux = tab[i];
                        tab[i] = tab[j];
                        tab[j] = aux;
                        i++;
                        j--;
                }
        } while (i <= j);
        if (deb < j)
                quicksort(tab, deb, j);
        if (i < fin)
                quicksort(tab, i, fin);

        return;
}


/***********
*
*                        SIMPLIFICATION
*
*        Cette fonction est utilisee pour oter toutes les valeurs qui existent en
*        double (ou en triple...) dans un tableau deja trie (ordre croissant).
*        On va utiliser 2 index : un pour la lecture, l'autre pour l'ecriture.
*               On stocke le premier element (ce qui revient a commencer a lire a
*                partir du 2eme element.
*               POUR tous les elements du tableau FAIRE
*                Si l'element lu est different du dernier element a avoir ete stocke
*                Alors le sauver
*               FPOUR
*
*        ENTREE : l'adresse du tableau
*                       la longueur de cette zone (i.e nombre d'elements du tableau)
*        RETOUR : le nombre d'elements differents du tableau maintenant remanie.
*
***/
static int      simplification(tab, tab_lg)
long    tab[];
unsigned        tab_lg;
{
register i, j;  /* i indice de lecture, j celui d'ecriture */
               /* remarque : j indexe l'element qui vient d'etre sauve */
        j = 0;
        for (i = 1; i < tab_lg; i++) /* on scanne toutes les valeurs     */
                if (tab[i] != tab[j])
                        tab[++j] = tab[i]; /* et on sauve si necessaire         */
        return(j + 1);
}

/***********
*
*                        AJOUTE
*
*        Cette fonction realise l'insertion d'une valeur dans un        tableau d'entier.
*        Elle ne travaille reellement que sur un segment de ce pseudo-tableau.  Elle
*        insere cette valeur parmi celles deja presentes dans la zone. Tri par ordre
*        croissant.
*
*       ENTREE : l'adresse du debut de la zone dans laquelle on insere la valeur.
*                        taille de la zone.
*                        la valeur a inserer.
*       RETOUR : aucune
*
***/

static void ajoute(tab, tab_lg, val)
type_i  tab[];
type_l  tab_lg;
type_i  val;
{
register int    i, j;

        for (i = 0; i < tab_lg; i++) {
                if (tab[i] == (type_i) - 1) { /* ici, la valeur est mise a la fin de la zone            */
                        tab[i] = val;
                        break;
                }
                if (tab[i] > val) {                    /* Ici, la valeur doit etre inseree */
                        for (j = i + 1; j < tab_lg; j++)     /* On cherche la 1ere valeur a -1 dans la zone.  */
                                if (tab[j] == (type_i) - 1)
                                        break;
                        for ( ; j > i; j--)                  /* Des qu'on l'a, on peut commencer a redescendre */
                                tab[j] = tab[j-1];           /* les valeurs pour ceder la place a la nouvelle. */
                        tab[i] = val;
                        break;
                }
        }
        return;
}

/***********
*
*			 OTE_DOUBLONS
*
*	 Cette fonction est utilisee pour oter toutes les valeurs qui existent
*	 en double dans un tableau trie par ordre croissant. En fait, on va se
*	 borner a remplacer les doublons par -1.	On evitera simplement de les
*	 interpreter par la suite lorsqu'on construira les pseudo-rectangles.
*
*	ENTREE : Adresse du debut de la zone dans laquelle on insere la valeur
*			 La taille de la zone
*	RETOUR : Aucune
*
***/

static void ote_doublons(tab, tab_lg)
type_i	tab[];
type_l	tab_lg;
{
	register int	i;

	if (tab_lg == 2)
		return;					 /* si il n'y a que 2 valeurs, il n'y a rien a faire */
	for (i = 1; i < tab_lg - 2; i++)
		if (tab[i] == tab[i+1]) {	 /* Si les 2 valeurs sont identiques				 */
			tab[i] = (type_i) - 1;
			tab[i+1] = (type_i) - 1;
		}
	return;
}


/***********
*
*			 DO_V_RECTANGLE & DO_H_RECTANGLE
*
*	 Ces fonctions servent a former les rectangles avec leurs coordonnees
*	 non pas reelles mais exprimees en fonction de leur position relative
*	 par rapport aux autres. En clair, on recupere les cordonnees reelles
*	 dans les pseudo-tableaux xtab et ytab.
*
*	ENTREE : Pseudo-tableau de reception des pseudo-coordonnees des rectangles
*			 Indice d'ecriture dans ce pseudo-tableau
*			 Indice dans xtab (ou ytab) de l'abcisse gauche (ou ordonnee basse)
*			 Pseudo-tableau des aretes horizontales (ou verticales)
*			 Indice de debut de lecture dans le precedent tableau
*			 Indice de fin de lecture dans le precedent tableau
*	RETOUR : Nombre de rectangles deja inscrit dans le 1er tableau (c'est donc
*				 la valeur de l'indice en sortie).
*
***/

static type_l do_v_rectangle(rect_tab, idx, gauche, pos_tab, deb, fin)
rect_t	rect_tab[];
type_l	idx;
type_i	gauche;
type_i	pos_tab[];
type_l	deb;
type_l	fin;
{
	register int	i, j;

	register type_i bas, haut;
	register int	deja_vu;

	i = deb;
	do {
		deja_vu = 0;
		bas = pos_tab[i++];
		while (pos_tab[i] == (type_i) - 1) 
			i++;		 /* on passe les eventuels -1 */
		haut = pos_tab[i++];

		/* on va verifier s'il n'existe pas deja un rectangle de meme hauteur qui soit */
		/* accole, a gauche, a celui qu'on cherche a former. Dans ce cas, on ne ferait */
		/* qu'un rectangle de ces 2 la -> unification.								 */
		for (j = 0; j < idx; j++)
			if ( rect_tab[j].r_d == gauche && rect_tab[j].r_b == bas && rect_tab[j].r_h == haut ) {
				rect_tab[j].r_d++;
				deja_vu = 1;
				break;
			}
		if (deja_vu) 
			continue;			/* si on vient justement d'elargir un rectangle, on n'en */
		/* cree pas un nouveau, on passe aux aretes suivantes.	 */

		rect_tab[idx].r_g = gauche;
		rect_tab[idx].r_d = gauche + 1;
		rect_tab[idx].r_b = bas;
		rect_tab[idx].r_h = haut;
		idx++;
	} while (i < fin);

	return(idx);			/* on renvoie l'indice du nouveau poste de libre. */
}


static type_l do_h_rectangle(rect_tab, idx, bas, pos_tab, deb, fin)
rect_t	rect_tab[];
type_l	idx;
type_i	bas;
type_i	pos_tab[];
type_l	deb;
type_l	fin;
{
	register int	i, j;
	register type_i gauche, droite;
	register int	deja_vu;

	i = deb;
	do {
		deja_vu = 0;
		gauche = pos_tab[i++];
		while (pos_tab[i] == (type_i) - 1) 
			i++;	 /* on passe les eventuels -1 */
		droite = pos_tab[i++];

		/* on va verifier s'il n'existe pas deja un rectangle de meme largeur qui	soit */
		/* accole en dessous de celui qu'on cherche a former. Dans ce cas, on ne ferait */
		/* qu'un rectangle de ces 2 la -> unification.									*/
		for (j = 0; j < idx; j++)
			if ( rect_tab[j].r_h == bas && rect_tab[j].r_g == gauche && rect_tab[j].r_d == droite ) {
				rect_tab[j].r_h++;
				deja_vu = 1;
				break;
			}
		if (deja_vu) 
			continue;		/* si on vient justement de rehausser un rectangle, on n'en */
		/* cree pas un nouveau, on passe aux aretes suivantes.		*/

		rect_tab[idx].r_g = gauche;
		rect_tab[idx].r_d = droite;
		rect_tab[idx].r_b = bas;
		rect_tab[idx].r_h = bas + 1;
		idx++;
	} while (i < fin);

	return(idx);			/* on renvoie l'indice du nouveau poste de libre. */
}


/***********
*
*			 D2RDS
*
*	 Cette fonction prend un tableau de structures qui decrivent des	diagonales
*	 de rectangles et produit les rectangles correspondant dans la base RDS.
*	 Les deux 1eres paires decrivent la 1ere diagonale et ainsi de suite.
*
*	ENTREE : Layer de la liste ou il faut inserer les nouveaux rectangles
*			 Tableau de structures contenant les coordonnees des diagonales
*			 Taille du tableau
*	RETOUR : Liste des rdsrec_listtangles pointee par HeadFigureRds->layertab[layer]
*
***/

void diag2rec(model, layer, coord_tab, coord_numb)
rdsfig_list *model;
char	layer;
coord_t	coord_tab[];
unsigned	coord_numb;
{
        rdsrec_list *Rec;
	register unsigned int	i, j;
	register long	x, y, dx, dy;

	for (i = 0; i < coord_numb; i += 2) {
		j = i + 1;
		x	 = coord_tab[i].X;	 
		y	 = coord_tab[i].Y;
		dx = coord_tab[j].X - x; 
		dy = coord_tab[j].Y - y;
		if (CheckPhysicalGridAligned(x)
				|| CheckPhysicalGridAligned(y)
				|| CheckPhysicalGridAligned(dx)
				|| CheckPhysicalGridAligned(dy)) {
			fprintf(stderr, "*** rds warning ***\nPolygon with points not ");
			fprintf(stderr, "aligned on the physical grid found in %s\n", model->NAME);
			fprintf(stderr, "%ld %ld %ld %ld\n", x, y, dx, dy);
                        Rec = addrdsfigrec(model, NULL, layer, x, y, dx, dy );
                        if ( layer == RDS_ABOX ) SetRdsFigure( Rec );
                	roundrdsrec( Rec );
		} else
                {
			Rec = addrdsfigrec(model, NULL, layer, x, y, dx, dy );
                        if ( layer == RDS_ABOX ) SetRdsFigure( Rec );
                        roundrdsrec( Rec );
                }
	}
}


/***********
*
*			 DO_DIAGONALE
*
*	 Cette fonction prend un tableau de structures qui decrivent tous les rectangles
*	 necessaire a la reconstitution du polygone.	Ces	structures ne contiennent pas
*	 les coordonnees reelles des sommets.	Elles ne font qu'indiquer ou on peut con-
*	 vertir les coordonnees fictives en coordonnees reelles. On va donc les chercher
*	 dans les pseudo-tableaux xtab et ytab. La fonction cree et remplit	un	tableau
*	 de structures coord_t dans lequel on trouve decrits les rectangles avec des co-
*	 ordonnees reelles : les deux 1eres entrees du tableau concernent	la	diagonale
*	 du 1er rectangle (le point en bas a gauche et celui en haut a droite) et	ainsi
*	 de suite.
*
*	ENTREE : Pseudo-tableau de structures contenant les coordonnees fictives des rectangles
*			 Taille du pseudo-tableau
*			 Table de conversion abcisse fictive >> abcisse reelle
*			 Table de conversion ordonnee fictive >> ordonnee reelle
*	RETOUR : Tableau de structures coord_t
*
***/

static coord_t *do_diagonale(rect_tab, nb_rect, xtab, ytab)
rect_t	rect_tab[];
type_l	nb_rect;
long	xtab[], ytab[];
{
	register int	i, j;
	register coord_t	*tab;

	tab = (coord_t * )malloc(nb_rect * 2 * sizeof(coord_t));
	if (tab == (coord_t * )NULL) {
		ruterror( RDS_NOT_ENOUGH_MEMORY, "do_diagonale");
		return((coord_t * )NULL);
	}

	for (i = 0; i < nb_rect; i++) {
		j = 2 * i;
		tab[j].X	 = xtab[rect_tab[i].r_g];
		tab[j].Y	 = ytab[rect_tab[i].r_b];
		tab[j+1].X = xtab[rect_tab[i].r_d];
		tab[j+1].Y = ytab[rect_tab[i].r_h];
	}
	return(tab);
}


/***********
*
*			 P2D
*
*	 Cette fonction prend la description d'un polygone et transforme	celui-ci
*	 en un ensemble de diagonales de rectangles equivalent.
*
*	ENTREE: - coord_tab est un pointeur sur un tableau contenant les paires de
*			coordonnees.
*			- coord_numb est le nombre de coordonnees contenues dans ce pseudo-
*			tableau.
*			Permet de borner la zone utilisee pour stocker les coordonnees.
*			- Facteur de grossissement : pour changer de systeme	de	coordon-
*			neees.
*			- Adresse d'un pointeur de coord_t
*			- Pointeur sur un unsigned
*
*	RETOUR:	Un pointeur sur un tableau de paires	de	coordonnees	destines a
*			 remplacer le polygone. Ce tableau ne contient que les coordonnees
*			 des diagonales de ces rectangles.
*			 NULL si manque d'espace memoire
*
*	REMARQUES IMPORTANTES :
*		1- Le polygone decrit par le tableau	de	coordonnees	coord_tab	DOIT
*		 etre rectangle (il ne DOIT y avoir que des angles	a	90'	dans	le
*		 dessin.
*		2- on va supposer que ce tableau contient n+1 couples	de	coordonnees
*		 si le polygone a n sommets. Le 1er et le dernier couple sont	iden-
*		 tiques (ils ferment le polygone).
*		3- xtab et ytab contiennent les coordonnees reelles du polygone. Dans
*		 tout l'algorithme, on utilisera des coordonnees fictives qui seront
*		 en fait des index sur xtab et ytab, et permettront de retrouver les
*		 coordonnees reelles, a la fin, pour produire les rectangles finaux.
*		4- Pour economiser l'espace memoire, on va supposer qu'il n'y aura pas
*		 plus de 65535 abcisses ou ordonnees differentes ( 2^16 de chaque au
*		 maximum ). Ce qui permet de definir nb_x et nb_y comme type_i, donc
*		 comme unsigned short.
*		 - pos_h et pos_v sont 2 tableaux qui contiennent les positions verti-
*		 cales	(resp. horiz.) des	aretes	horizontales (resp. vert.)	dans
*		 chaque colonne (resp. ligne) du	dessin.	Ces	positions	sont	des
*		 index dans ytab (resp. xtab) dont les valeurs sont	obligatoirement
*		 comprises entre 0 et nb_y (resp. nb_x).	On definit donc	pos_h	et
*		 pos_v comme des tableaux contenant des "type_i".
*		 - index_h et index_v sont 2 tableaux qui permettent	d'indexer	pos_h
*		 et pos_v.	Ils montrent ou se trouve la 1ere arete de	chacune	des
*		 colonnes (resp. lignes). Une fois le polygone decoupe	en	morceaux
*		 elementaires (on utilise un maillage fait de toutes les abcisses et
*		 ordonnees differentes),	on obtient generalement (toujours ?)	plus
*		 d'aretes horizontales (resp. vert.) qu'il	n'y a d'abcisses	(resp.
*		 d'ordonnees) differentes : si le dessin a n+1 ordonnees differentes
*		 cela fait n lignes (comprendre intervalles), on a donc au minimum n
*		 aretes pour monter	+	n	pour descendre (pour un dessin simple, du
*		 genre carre, pyramide maya, escalier...). On en conclut que si on a
*		 65535 ordonnees differentes (=2^16), on aura au minimum 2 fois plus
*		 d'aretes verticales. Ce qui veut dire que pos_v aurait	dans ce cas
*		 plus de 130 000 entrees. Donc il faut que index_h et index_v soient
*		 des tableaux d'entiers longs pour pouvoir indexer correctement dans
*		 ces cas la. On en fera des tableaux de type_l, ce type_l etant plus
*		 "grand" que le type_i (comprendre la : "permettant de composer	des
*		 entiers plus grands").	Neanmoins, il parait raisonnable de definir
*		 type_l comme "unsigned short", la probabilite d'avoir plus de 65535
*		 aretes horizontales (resp. vert) au total me paraissant faible.
*		 - col et lig sont 2 tableaux qui permettent de savoir combien	d'are-
*		 tes horizontales (resp. vert) se trouvent dans chaque colonne (resp
*		 ligne) du dessin. Si on a n ordonnees differentes, on ne peut avoir
*		 plus de n aretes horizontales dans une colonne puisqu'au minimum si
*		 on a n aretes horizontales on a n ordonnees	differentes.	Le	seul
*		 probleme qu'on peut avoir est quand une arete	est	parcourue	dans
*		 les 2 sens. Cela arrive quand on a un trou dans le dessin, on	cree
*		 un fil qu'on parcourt dans un sens pour aller parcourir le bord	du
*		 trou, et dans l'autre pour rejoindre le parcours exterieur. Donc la
*		 on aurait 2 aretes pour une ordonnee unique dans la	meme	colonne.
*		 Mais en fait, le parcours interieur implique au moins une	ordonnee
*		 pour laquelle il n'y a pas d'arete correspondante dans la preceden-
*		 te colonne.	Comme il parait fortement improbable d'avoir plus de
*		 65535 ordonnees (ou abcisses) differentes, on definit des	tableaux
*		 de type_c ou type_c est du type unsigned short.
*		 - On remarque que	type_c < type_i < type_l.	 Peut-etre	faudrait-il
*		 prevoir des tests pour ne pas depasser la capacite	d'accueil	d'un
*		 de ces types (unsigned short actuellement) et demander une nouvelle
*		 compilation de ce module avec des nouvelles definitions?
*		 En tout cas, il est vraisemblable qu'il faudra d'abord agrandir	le
*		 type "type_l" avant les autres.
*
***/

void poly2diag(coord_tab, coord_numb, scale, new_coord_tab, new_coord_numb)
coord_t	 coord_tab[];
unsigned	coord_numb;
double	scale;
coord_t	 **new_coord_tab;
unsigned	*new_coord_numb;
{
	register int	i, h, v;				 /* compteurs a tout faire	*/

	long	x1, y1, x2, y2;				/* auxiliaires (de coordonnees) en tout genre */

	long	*tab;							/* pseudo-tableau auxiliaire */
	long	*xtab, *ytab;					/* pseudo-tableaux des differentes coordonnees*/
	type_i nb_x, nb_y;					/* tailles des 2 tableaux et egalement nombres d'abcisses et d'ordonnees significatives. */
	type_c * col, *lig;					/* pseudo-tableaux contenant respectivement les nombres d'aretes par ligne, par colonne. */
	type_l * index_h, *index_v;			/* pseudo-tableaux permettant d'indexer les tableaux contenant les positions des aretes. */
	type_i * pos_h, *pos_v;				/* pseudo-tableaux contenant les aretes classees par colonne (ligne) et dans l'ordre	 */
	/* croissant des ordonnees (abcisses).													 */
	rect_t * v_rect, *h_rect;			/* pseudo-tableaux contenant les rectangles presque formes (coordonnees fictives).		 */
	coord_t * nct;						 /* tableau contenant les paires de coordonnees resultantes : celles qui forment les		*/
	/* diagonales.																			 */
	coord_t	 * coordonnees;				/* Si on doit faire une mise a l'echelle, ce tableau recevra les nouvelles coordonnees	 */
	/* et si ce n'est pas le cas il servira a pointer directement coord_tab.				 */
	short	bool = 0;					 /* Indique si coordonnees pointe sur une autre zone que coord_tab (si on a alloue une	*/
	/* nouvelle zone pour y ranger les coordonnees mises a l'echelle.						*/

	/*																													 */
	/* On regarde d'abord si le polygone a decouper n'est pas deja un rectangle, auquel cas le probleme est vite resolu.	 */
	/*																													 */
	if (coord_numb == 5) {
		nct = (coord_t * )malloc(2 * sizeof(coord_t));
		*new_coord_tab = nct;
		*new_coord_numb = 0;
		if (nct == (coord_t * )NULL) {
			ruterror( RDS_NOT_ENOUGH_MEMORY, "p2d(nct)");
			EXIT(1);
		}
		*new_coord_numb = 2;
		if (scale == 1.0) {
			nct[0].X = coord_tab[0].X;
			nct[0].Y = coord_tab[0].Y;
			nct[1].X = coord_tab[2].X;
			nct[1].Y = coord_tab[2].Y;
		} else {
			nct[0].X = (long)floor(((double)coord_tab[0].X * scale) + .5);
			nct[0].Y = (long)floor(((double)coord_tab[0].Y * scale) + .5);
			nct[1].X = (long)floor(((double)coord_tab[2].X * scale) + .5);
			nct[1].Y = (long)floor(((double)coord_tab[2].Y * scale) + .5);
		}
	}

	/*																			*/
	/* On fait la mise a l'echelle ? Seulement si necessaire.					 */
	/*																			*/
	if (scale == 1.0)
		coordonnees = coord_tab;
	else {
		coordonnees = (coord_t * )malloc(coord_numb * sizeof(coord_t));
		if (coordonnees == (coord_t * )NULL) {
			ruterror( RDS_NOT_ENOUGH_MEMORY, "p2d(coordonnees)");
			EXIT(1);
		}
		bool = 1;														/* On vient d'allouer une nouvelle zone pour coordonnees*/
		for (i = 0; i < coord_numb; i++) {							 /* On recopie les valeurs du tableau passe en parametre */
			coordonnees[i].X = (long)floor(((double)coord_tab[i].X * scale) + .5);	/* en les mettant a l'echelle de la base RDS.			 */
			coordonnees[i].Y = (long)floor(((double)coord_tab[i].Y * scale) + .5);
		}
	}

	/*																			*/
	/* On extrait de la liste des coordonnees toutes les valeurs significatives */
	/*																			*/
	tab = (long *)malloc(coord_numb * sizeof(long));		/* on alloue un tableau auxiliaire pour y stocker */
	if (tab == (long *)NULL) {								/* temporairement les abcisses et les ordonnees.	*/
		ruterror( RDS_NOT_ENOUGH_MEMORY, "p2d(tab)");
		if (bool) 
			free((char *)coordonnees);
		EXIT(1);
	}

	for (i = 0; i < coord_numb; i++)						/* On commence par les abcisses										*/
		tab[i] = coordonnees[i].X;

	quicksort(tab, 0, coord_numb - 1);					 /* On les trie														 */
	nb_x = simplification(tab, coord_numb);				/* On ne garde que les valeurs significatives						*/
	xtab = (long *)malloc(nb_x * sizeof(long));			 /* On alloue un pseudo-tableau pour y ranger les valeurs definitives */
	if (xtab == (long *)NULL) {
		ruterror( RDS_NOT_ENOUGH_MEMORY, "p2d(xtab)");
		if (bool) 
			free((char *)coordonnees);				/* traine pas d'imprecision : si la techno employee n'est pas assez	*/
		free((char *)tab);									/* precise (ex: 50 * 0.001 = 0 si caste en long)					 */
		EXIT(1);
	}
	/* On recopie ces valeurs definitives dans le nouveau tableau	 */
	(void)memcpy((char *)xtab, (char *)tab, (int)nb_x * sizeof(long));


	for (i = 0; i < coord_numb; i++)						/* Puis on s'occupe des ordonnees de la meme facon					 */
		tab[i] = coordonnees[i].Y;

	quicksort(tab, 0, coord_numb - 1);
	nb_y = simplification(tab, coord_numb);
	ytab = (long *)malloc(nb_y * sizeof(long));
	if (ytab == (long *)NULL) {
		ruterror( RDS_NOT_ENOUGH_MEMORY, "p2d(ytab)");
		if (bool) 
			free((char *)coordonnees);
		free((char *)tab);
		free((char *)xtab);
		EXIT(1);
	}
	/* On recopie ces valeurs definitives dans le nouveau tableau	 */
	(void)memcpy((char *)ytab, (char *)tab, (int)nb_y * sizeof(long));

	free((char * )tab);

	/*																			 */
	/* Calcul du nombre d'aretes, formant le polygone, pour chaque ligne et		*/
	/* chaque colonne.															 */
	/*																			 */
	col = (type_c * )calloc(nb_x - 1, sizeof(type_c));		 /* on prepare le pseudo-tableau pour repertorier les aretes	*/
	if (col == (type_c * )NULL) {							/* horizontales contenues dans chaque colonne du dessin.	 */
		ruterror( RDS_NOT_ENOUGH_MEMORY, "p2d(col)");
		if (bool) 
			free((char *)coordonnees);
		free((char *)xtab); 
		free((char *)ytab);
		EXIT(1);
	}
	lig = (type_c * )calloc(nb_y - 1, sizeof(type_c));		 /* idem pour les aretes verticales contenues dans chaque ligne.	*/
	if (lig == (type_c * )NULL) {
		ruterror( RDS_NOT_ENOUGH_MEMORY, "p2d(lig)");
		if (bool) 
			free((char *)coordonnees);
		free((char *)xtab); 
		free((char *)ytab);
		free((char *)col);
		EXIT(1);
	}
	x1 = coordonnees[0].X;							/* initialisation des 1eres coordonnees */
	y1 = coordonnees[0].Y;							/* (le point 1 = P1)					*/
	h = v = 0;
	while (xtab[h] != x1) 
		h++;	/* on positionne h et v pour demarrer a partir de la 1ere coordonnee du tableau coordonnees */
	while (ytab[v] != y1) 
		v++;
	for ( i = 0; i < coord_numb - 1; i++) {
		x2 = coordonnees[i+1].X;				/* initialisation des coordonnees suivantes (le point 2 = P2) */
		y2 = coordonnees[i+1].Y;
		if ( x1 < x2 )								/* ------ si P1 a gauche de P2 --------- */
			while ( xtab[h] < x2 )
				col[h++]++;
		else if ( x1 > x2 )						 /* ------ si P1 a droite de P2 --------- */
			while ( xtab[h] > x2 )
				col[--h]++;
		else if ( y1 < y2 )						 /* ------ si P1 au dessous de P2 ------- */
			while ( ytab[v] < y2 )
				lig[v++]++;
		else if ( y1 > y2 )						 /* ------ si P1 au dessus de P2 -------- */
			while ( ytab[v] > y2 )
				lig[--v]++;
		x1 = x2;							/* P2 devient P1 */
		y1 = y2;
	}

	/*																			 */
	/* Preparation de 2 tableaux qui vont servir a indexer 2 tableaux contenant	*/
	/* les aretes classees par colonnes et par lignes							*/
	/*																			 */
	index_h = (type_l * )calloc(nb_x, sizeof(type_l));			 /* reservation de la place en memoire	*/
	if (index_h == (type_l * )NULL) {
		ruterror( RDS_NOT_ENOUGH_MEMORY, "p2d(index_h)");
		if (bool) 
			free((char *)coordonnees);
		free((char *)xtab); 
		free((char *)ytab);
		free((char *)col); 
		free((char *)lig);
		EXIT(1);
	}
	index_v = (type_l * )calloc(nb_y, sizeof(type_l));			 /* reservation de la place en memoire	*/
	if (index_v == (type_l * )NULL) {
		ruterror( RDS_NOT_ENOUGH_MEMORY, "p2d(index_v)");
		if (bool) 
			free((char *)coordonnees);
		free((char *)xtab); 
		free((char *)ytab);
		free((char *)col); 
		free((char *)lig);
		free((char *)index_h);
		EXIT(1);
	}
	index_h[0] = index_v[0] = 0;
	for (i = 1; i < nb_x; i++)					 /* ce tableau indexe le debut de chaque colonne. */
		index_h[i] = index_h[i-1] + col[i-1];
	for (i = 1; i < nb_y; i++)
		index_v[i] = index_v[i-1] + lig[i-1];		 /* celui-ci de chaque ligne dans pos_v */

	/*																			 */
	/* Mise en place des aretes horizontales et verticales dans les pseudo-		*/
	/* tableaux pos_h et pos_v.													*/
	/* Exemple : pos_h va contenir a la suite des couples d'indices de ytab		*/
	/* Chaque couple permet de positionner une arete (horizontale) verticalement */
	/* dans une certaine colonne du dessin. On determine de quelle colonne il	*/
	/* s'agit grace a index_h. Chaque entree de index_h indique (avec l'indice	 */
	/* qu'elle contient) a quel endroit de pos_h on change de colonne.			 */
	/*																			 */
	pos_h = (type_i * )malloc(index_h[nb_x-1] * sizeof(type_i));				 /* reservation de la place en memoire */
	if (pos_h == (type_i * )NULL) {
		ruterror( RDS_NOT_ENOUGH_MEMORY, "p2d(pos_h)");
		if (bool) 
			free((char *)coordonnees);
		free((char *)xtab); 
		free((char *)ytab);
		free((char *)col); 
		free((char *)lig);
		free((char *)index_h); 
		free((char *)index_v);
		EXIT(1);
	}
	pos_v = (type_i * )malloc(index_v[nb_y-1] * sizeof(type_i));				 /* reservation de la place en memoire */
	if (pos_v == (type_i * )NULL) {
		ruterror( RDS_NOT_ENOUGH_MEMORY, "p2d(pos_v)");
		if (bool) 
			free((char *)coordonnees);
		free((char *)xtab); 
		free((char *)ytab);
		free((char *)col); 
		free((char *)lig);
		free((char *)index_h); 
		free((char *)index_v);
		free((char *)pos_h);
		EXIT(1);
	}
	for (i = 0; i < index_h[nb_x-1]; i++) 
		pos_h[i] = (type_i) - 1;				/* on initialise a -1 ces 2 tableaux */
	for (i = 0; i < index_v[nb_y-1]; i++) 
		pos_v[i] = (type_i) - 1;
	x1 = coordonnees[0].X;							/* initialisation des 1eres coordonnees (le point 1 = P1) */
	y1 = coordonnees[0].Y;
	h = v = 0;
	while (xtab[h] != x1) 
		h++;	 /* on positionne h et v pour demarrer a partir de la 1ere coordonnee du tableau coordonnees */
	while (ytab[v] != y1) 
		v++;
	for ( i = 0; i < coord_numb - 1; i++) {
		x2 = coordonnees[i+1].X;				/* initialisation des coordonnees suivantes (le point 2 = P2) */
		y2 = coordonnees[i+1].Y;
		if ( x1 < x2 )								/* ------ si P1 a gauche de P2 --------- */
			while ( xtab[h] < x2 ) {
				ajoute(&pos_h[index_h[h]], index_h[h+1] - index_h[h], (type_i)v);
				h++;
			}
		else if ( x1 > x2 )						 /* ------ si P1 a droite de P2 --------- */
			while ( xtab[h] > x2 ) {
				h--;
				ajoute(&pos_h[index_h[h]], index_h[h+1] - index_h[h], (type_i)v);
			}
		else if ( y1 < y2 )						 /* ------ si P1 au dessous de P2 ------- */
			while ( ytab[v] < y2 ) {
				ajoute(&pos_v[index_v[v]], index_v[v+1] - index_v[v], (type_i)h);
				v++;
			}
		else if ( y1 > y2 )						 /* ------ si P1 au dessus de P2 -------- */
			while ( ytab[v] > y2 ) {
				v--;
				ajoute(&pos_v[index_v[v]], index_v[v+1] - index_v[v], (type_i)h);
			}
		x1 = x2;							/* P2 devient P1 */
		y1 = y2;
	}

	/*																			*/
	/* Simplification des 2 pseudo-tableaux pos_h et pos_v.						 */
	/* Si une zone contient, par exemple, la sequence 1|2|2|3|5|6 dans le tableau */
	/* pos_h, cela signifie que dans la colonne, concernee par la zone, on a 3	*/
	/* rectangles : entre les ordonnees 1 et 2, 2 et 3, 5 et 6. Cela arrive quand */
	/* on rencontre un polygone avec un trou au milieu; pour le former avec un	*/
	/* seul contour (continu) on est obliger de dessiner un trait invisible qui	 */
	/* le coupe pour rejoindre le contour interieur, et pour fermer ce contour on */
	/* est oblige de repasser dans l'autre sens sur ce trait. On va donc simpli-	*/
	/* fier les 2 rectangles qui se touchent pour obtenir la sequence 1|3|5|6.	*/
	/*																			*/
	for (i = 0; i < nb_x - 1; i++)
		ote_doublons(&pos_h[index_h[i]], index_h[i+1] - index_h[i]);
	for (i = 0; i < nb_y - 1; i++)
		ote_doublons(&pos_v[index_v[i]], index_v[i+1] - index_v[i]);

	/*																			 */
	/* Calcul des rectangles en fonction des colonnes : rectangles verticaux	 */
	/*																			 */
	v_rect = (rect_t * )malloc(index_h[nb_x-1] / 2 * sizeof(rect_t));
	if (v_rect == (rect_t * )NULL) {
		ruterror( RDS_NOT_ENOUGH_MEMORY, "p2d(v_rect)");
		if (bool) 
			free((char *)coordonnees);
		free((char *)xtab); 
		free((char *)ytab);
		free((char *)col); 
		free((char *)lig);
		free((char *)index_h); 
		free((char *)index_v);
		free((char *)pos_h); 
		free((char *)pos_v);
		EXIT(1);
	}
	v = 0;								/* v sert a compter le nombre de rectangles verticaux */
	for (i = 0; i < nb_x - 1; i++)
		v = do_v_rectangle(v_rect, (type_l)v, (type_i)i, pos_h, index_h[i], index_h[i+1]);

	/*																			 */
	/* Calcul des rectangles en fonction des lignes : rectangles horizontaux	 */
	/*																			 */
	h_rect = (rect_t * )malloc(index_v[nb_y-1] / 2 * sizeof(rect_t));
	if (h_rect == (rect_t * )NULL) {
		ruterror( RDS_NOT_ENOUGH_MEMORY, "p2d(h_rect)");
		if (bool) 
			free((char *)coordonnees);
		free((char *)xtab); 
		free((char *)ytab);
		free((char *)col); 
		free((char *)lig);
		free((char *)index_h); 
		free((char *)index_v);
		free((char *)pos_h); 
		free((char *)pos_v);
		free((char *)v_rect);
		EXIT(1);
	}
	h = 0;								/* h sert a compter le nombre de rectangles horizontaux */
	for (i = 0; i < nb_y - 1; i++)
		h = do_h_rectangle(h_rect, (type_l)h, (type_i)i, pos_v, index_v[i], index_v[i+1]);

	/*																			 */
	/* Choix du meilleur decoupage et production des rectangles finaux.			*/
	/*																			 */
	if (h < v) {
		free((char *)v_rect);
		nct = do_diagonale(h_rect, (type_l)h, xtab, ytab);
		*new_coord_tab = nct;
		*new_coord_numb = 2 * h;
		if (nct == (coord_t * )NULL) {
			ruterror( RDS_NOT_ENOUGH_MEMORY, "p2d(nct)");
			if (bool) 
				free((char *)coordonnees);
			free((char *)xtab); 
			free((char *)ytab);
			free((char *)col); 
			free((char *)lig);
			free((char *)index_h); 
			free((char *)index_v);
			free((char *)pos_h); 
			free((char *)pos_v);
			free((char *)h_rect);
			EXIT(1);
		}
		free((char *)h_rect);
	} else {
		free((char *)h_rect);
		nct = do_diagonale(v_rect, (type_l)v, xtab, ytab);
		*new_coord_tab = nct;
		*new_coord_numb = 2 * v;
		if (nct == (coord_t * )NULL) {
			ruterror( RDS_NOT_ENOUGH_MEMORY, "p2d(nct)");
			if (bool) 
				free((char *)coordonnees);
			free((char *)xtab); 
			free((char *)ytab);
			free((char *)col); 
			free((char *)lig);
			free((char *)index_h); 
			free((char *)index_v);
			free((char *)pos_h); 
			free((char *)pos_v);
			free((char *)v_rect);
			EXIT(1);
		}
		free((char *)v_rect);
	}

	/*																			 */
	/* Liberation de la memoire													*/
	/*																			 */
	if (bool) 
		free((char *)coordonnees);
	free((char *)xtab); 
	free((char *)ytab);
	free((char *)col); 
	free((char *)lig);
	free((char *)index_h); 
	free((char *)index_v);
	free((char *)pos_h); 
	free((char *)pos_v);
}


/***********
*
*			 ISPOLREC
*
*	 Cette fonction prend la description d'un polygone et verifie si celui-ci est
*	 rectangle, c'est-a-dire si les seuls angles qui ce retrouvent sur le	dessin
*	 sont des angles droits (pas de fils a 45' ou autre).	Il suffit de	verifier
*	 qu'il n'y a qu'une seule coordonnee qui change a la fois ( les seules direc-
*	 tions permises sont donc N, E, S, W).
*
*	ENTREE : Tableau de structures contenant les coordonnees des points
*			 Taille du tableau
*	RETOUR : 1 le polygone est rectangle
*			 0 sinon
*
***/
int ispolyrec(coord_tab, coord_numb)
coord_t coord_tab[];
unsigned coord_numb;
{
register int i;

	for (i = 0; i < coord_numb - 1; i++)
		if (coord_tab[i].X != coord_tab[i+1].X &&
				coord_tab[i].Y != coord_tab[i+1].Y)
			return 0;
         
	return 1;
}
