/* triangle.h - Don Yang (uguu.org)

   07/14/01
                                                                           */

#ifndef TRIANGLE_H__
#define TRIANGLE_H__


#define MIN_VERTEX_DISTANCE_2    10
#define COLINEAR_EPSILON         0.00001

#define TRIANGLE_EDGE1           1
#define TRIANGLE_EDGE2           2
#define TRIANGLE_EDGE3           4
#define TRIANGLE_WALL1           8
#define TRIANGLE_WALL2           16
#define TRIANGLE_WALL3           32
#define TRIANGLE_PATH            64
#define TRIANGLE_GOAL            128

/* Triangle list */
typedef struct _tlist
{
   void *t;
   struct _tlist *next;

} TList;

/* Vertex definition (linked list) */
typedef struct _vertex
{
   int id;                 /* Unique consequtive ID */
   double x, y;            /* Position */
   struct _vertex *next;   /* Pointer to next node */
   TList *tlist;           /* List of triangles using this vertex */

} Vertex;

/* Triangle definition (BST sorted by x) */
typedef struct _triangle
{
   int id;                          /* Update counter / subset id */
   int flags;                       /* Attributes */
   double key;                      /* Sort key */

   Vertex *v[3];                    /* Vertices */
   double cx, cy;                   /* Circumcircle position */
   double cr2;                      /* Circumcircle radius (squared) */

   struct _triangle *left, *right;  /* Pointers to subtrees */
   struct _triangle *n[3];          /* Pointer to neighbors */

} Triangle;

/* Exports */
extern int Edge1[3], Edge2[3];

/* Functions */
int AddTriangle(Triangle **root, Triangle **n, Vertex *v[3]);
int AddVertex(Vertex **list, Vertex **v, double x, double y);
void Apply(Triangle *root, void (*op)(Triangle*));
void AssignVertexID(Vertex *list);
int CountTriangles(Triangle *root);
void DeleteTriangle(Triangle **root, Triangle *d);
void DeleteTriangleList(Triangle **root);
void DeleteVertex(Vertex **list, Vertex *d);
void DeleteVertexList(Vertex **list);
int Enclosed(Vertex *v[3], Vertex *point);


#endif