#include <stdio.h>
#include <malloc.h>
#include <math.h>
#include <string.h>
#include <assert.h>
#include "rtmp_dlist.h"


#define FT_SHAKE      0.01     /* ft coords adjustment range */
#define FT_AFFINE_EPS 0.0001   /* this dist point-to-facet fails affine test */
#define FT_HULL_EPS   0.01     /* this dist outside hull fails hull test */

#define AVAILABLE 1
#define TAKEN     0

#ifndef RAND_MAX
#define RAND_MAX 2147483647 /* 2^31 - 1 */
#endif

extern int convex_hull();

/*************************************************/
/*    vertex and facet classification indices    */
/*************************************************/

#define CLASS_UNKNOWN -1
#define BENEATH  0        /* vertex and all ascendants part of new hull */
#define BEYOND   1        /* vertex and all ascendants not in new hull */
#define MIXED    2        /* otherwise */


/***************************************/
/*    statistics kept for each face    */
/***************************************/

/* Nstats are defined by:
        basis      => dimension orthogonal vectors
	coords     => min-distance-to-origin point
	inside_vec => vector to hull inside .. meaningful for facets
*/

typedef struct nstats
{
  float **basis;
  float *coords;
  float *inside_vec;
}
Nstats;


/*******************************************************/
/*    each node of the convex hull tree is an Nface    */
/*******************************************************/

typedef struct nface
{
  int dimension;                /* 0 = vertex .. up to (SPACE_DIMENSION - 1) */
  Nstats *stats;                /* face specifics.. form depends on dimension */
  DLIST ascendants;             /* >dim: may be many.. added, deleted at will */
  struct nface **descendants;   /* <dim: fixed number depends on dimension */
  struct nface *new_ascendant;  /* ascendant due to pt now being processed */

  DLIST facets;                 /* shortcut verts to facets */
  DLIST points;                 /* shortcut facets to verts */
  int class;                    /* classification wrt new vert */
  int marker;                   /* allows tree coverage w/out backtracking */
  int ident;                    /* for debugging */
}
Nface;


typedef struct nface_stack
{
    Nface *head;
    struct nface_stack *next;
    int bottom;
} 
Nface_Stack;