#ifndef LIBTESS_H
#define LIBTESS_H


enum TessWindingRule {
  TESS_WINDING_ODD,
  TESS_WINDING_NONZERO,
  TESS_WINDING_POSITIVE,
  TESS_WINDING_NEGATIVE,
  TESS_WINDING_ABS_GEQ_TWO,
};

enum TessElementType {
  TESS_POLYGONS,
  TESS_CONNECTED_POLYGONS,
  TESS_BOUNDARY_CONTOURS,
};

enum TessOption {
  TESS_CONSTRAINED_DELAUNAY_TRIANGULATION,
  TESS_REVERSE_CONTOURS
};

typedef float TESSreal;
typedef int TESSindex;
typedef struct TESStesselator TESStesselator;
typedef struct TESSalloc TESSalloc;

#define TESS_UNDEF (~(TESSindex)0)

#define TESS_NOTUSED(v)                                                        \
  do {                                                                         \
    (void)(1 ? (void)0 : ((void)(v)));                                         \
  } while (0)

struct TESSalloc {
  void *(*memalloc)(void *userData, unsigned int size);
  void *(*memrealloc)(void *userData, void *ptr, unsigned int size);
  void (*memfree)(void *userData, void *ptr);
  void *userData;
  int meshEdgeBucketSize;
  int meshVertexBucketSize;
  int meshFaceBucketSize;
  int dictNodeBucketSize;
  int regionBucketSize;
  int extraVertices;
};

TESStesselator *tessNewTess(TESSalloc *alloc);

void tessDeleteTess(TESStesselator *tess);

void tessAddContour(TESStesselator *tess, int size, const void *pointer,
                    int stride, int count);

void tessSetOption(TESStesselator *tess, int option, int value);

int tessTesselate(TESStesselator *tess, int windingRule, int elementType,
                  int polySize, int vertexSize, const TESSreal *normal);

int tessGetVertexCount(TESStesselator *tess);

const TESSreal *tessGetVertices(TESStesselator *tess);

const TESSindex *tessGetVertexIndices(TESStesselator *tess);

int tessGetElementCount(TESStesselator *tess);

const TESSindex *tessGetElements(TESStesselator *tess);


#endif

#ifdef LIBTESS_IMPL
#include <assert.h>
#include <setjmp.h>
#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>

struct BucketAlloc *createBucketAlloc(TESSalloc *alloc, const char *name,
                                      unsigned int itemSize,
                                      unsigned int bucketSize);
void *bucketAlloc(struct BucketAlloc *ba);
void bucketFree(struct BucketAlloc *ba, void *ptr);
void deleteBucketAlloc(struct BucketAlloc *ba);

typedef void *DictKey;
typedef struct Dict Dict;
typedef struct DictNode DictNode;

Dict *dictNewDict(TESSalloc *alloc, void *frame,
                  int (*leq)(void *frame, DictKey key1, DictKey key2));

void dictDeleteDict(TESSalloc *alloc, Dict *dict);

DictNode *dictSearch(Dict *dict, DictKey key);
DictNode *dictInsertBefore(Dict *dict, DictNode *node, DictKey key);
void dictDelete(Dict *dict, DictNode *node);

#define dictKey(n) ((n)->key)
#define dictSucc(n) ((n)->next)
#define dictPred(n) ((n)->prev)
#define dictMin(d) ((d)->head.next)
#define dictMax(d) ((d)->head.prev)
#define dictInsert(d, k) (dictInsertBefore((d), &(d)->head, (k)))

struct DictNode {
  DictKey key;
  DictNode *next;
  DictNode *prev;
};

struct Dict {
  DictNode head;
  void *frame;
  struct BucketAlloc *nodePool;
  int (*leq)(void *frame, DictKey key1, DictKey key2);
};

typedef void *PQkey;
typedef int PQhandle;
typedef struct PriorityQHeap PriorityQHeap;

#define INV_HANDLE 0x0fffffff

typedef struct {
  PQhandle handle;
} PQnode;
typedef struct {
  PQkey key;
  PQhandle node;
} PQhandleElem;

struct PriorityQHeap {

  PQnode *nodes;
  PQhandleElem *handles;
  int size, max;
  PQhandle freeList;
  int initialized;

  int (*leq)(PQkey key1, PQkey key2);
};

typedef struct PriorityQ PriorityQ;

struct PriorityQ {
  PriorityQHeap *heap;

  PQkey *keys;
  PQkey **order;
  PQhandle size, max;
  int initialized;

  int (*leq)(PQkey key1, PQkey key2);
};

PriorityQ *pqNewPriorityQ(TESSalloc *alloc, int size,
                          int (*leq)(PQkey key1, PQkey key2));
void pqDeletePriorityQ(TESSalloc *alloc, PriorityQ *pq);

int pqInit(TESSalloc *alloc, PriorityQ *pq);
PQhandle pqInsert(TESSalloc *alloc, PriorityQ *pq, PQkey key);
PQkey pqExtractMin(PriorityQ *pq);
void pqDelete(PriorityQ *pq, PQhandle handle);

PQkey pqMinimum(PriorityQ *pq);
int pqIsEmpty(PriorityQ *pq);

typedef struct TESSmesh TESSmesh;
typedef struct TESSvertex TESSvertex;
typedef struct TESSface TESSface;
typedef struct TESShalfEdge TESShalfEdge;
typedef struct ActiveRegion ActiveRegion;

struct TESSvertex {
  TESSvertex *next;
  TESSvertex *prev;
  TESShalfEdge *anEdge;

  TESSreal coords[3];
  TESSreal s, t;
  int pqHandle;
  TESSindex n;
  TESSindex idx;
};

struct TESSface {
  TESSface *next;
  TESSface *prev;
  TESShalfEdge *anEdge;

  TESSface *trail;
  TESSindex n;
  char marked;
  char inside;
};

struct TESShalfEdge {
  TESShalfEdge *next;
  TESShalfEdge *Sym;
  TESShalfEdge *Onext;
  TESShalfEdge *Lnext;
  TESSvertex *Org;
  TESSface *Lface;

  ActiveRegion *activeRegion;
  int winding;
  int mark;
};

#define Rface Sym->Lface
#define Dst Sym->Org

#define Oprev Sym->Lnext
#define Lprev Onext->Sym
#define Dprev Lnext->Sym
#define Rprev Sym->Onext
#define Dnext Rprev->Sym
#define Rnext Oprev->Sym

struct TESSmesh {
  TESSvertex vHead;
  TESSface fHead;
  TESShalfEdge eHead;
  TESShalfEdge eHeadSym;

  struct BucketAlloc *edgeBucket;
  struct BucketAlloc *vertexBucket;
  struct BucketAlloc *faceBucket;
};

TESShalfEdge *tessMeshMakeEdge(TESSmesh *mesh);
int tessMeshSplice(TESSmesh *mesh, TESShalfEdge *eOrg, TESShalfEdge *eDst);
int tessMeshDelete(TESSmesh *mesh, TESShalfEdge *eDel);

TESShalfEdge *tessMeshAddEdgeVertex(TESSmesh *mesh, TESShalfEdge *eOrg);
TESShalfEdge *tessMeshSplitEdge(TESSmesh *mesh, TESShalfEdge *eOrg);
TESShalfEdge *tessMeshConnect(TESSmesh *mesh, TESShalfEdge *eOrg,
                              TESShalfEdge *eDst);

TESSmesh *tessMeshNewMesh(TESSalloc *alloc);
TESSmesh *tessMeshUnion(TESSalloc *alloc, TESSmesh *mesh1, TESSmesh *mesh2);
int tessMeshMergeConvexFaces(TESSmesh *mesh, int maxVertsPerFace);
void tessMeshDeleteMesh(TESSalloc *alloc, TESSmesh *mesh);
void tessMeshZapFace(TESSmesh *mesh, TESSface *fZap);

void tessMeshFlipEdge(TESSmesh *mesh, TESShalfEdge *edge);

#ifdef NDEBUG
#define tessMeshCheckMesh(mesh)
#else
void tessMeshCheckMesh(TESSmesh *mesh);
#endif

#ifdef NO_BRANCH_CONDITIONS

#define VertEq(u, v) (((u)->s == (v)->s) & ((u)->t == (v)->t))
#define VertLeq(u, v)                                                          \
  (((u)->s < (v)->s) | ((u)->s == (v)->s & (u)->t <= (v)->t))
#else
#define VertEq(u, v) ((u)->s == (v)->s && (u)->t == (v)->t)
#define VertLeq(u, v)                                                          \
  (((u)->s < (v)->s) || ((u)->s == (v)->s && (u)->t <= (v)->t))
#endif

#define EdgeEval(u, v, w) tesedgeEval(u, v, w)
#define EdgeSign(u, v, w) tesedgeSign(u, v, w)

#define TransLeq(u, v)                                                         \
  (((u)->t < (v)->t) || ((u)->t == (v)->t && (u)->s <= (v)->s))
#define TransEval(u, v, w) testransEval(u, v, w)
#define TransSign(u, v, w) testransSign(u, v, w)

#define EdgeGoesLeft(e) VertLeq((e)->Dst, (e)->Org)
#define EdgeGoesRight(e) VertLeq((e)->Org, (e)->Dst)
#define EdgeIsInternal(e) e->Rface && e->Rface->inside

#define ABS(x) ((x) < 0 ? -(x) : (x))
#define VertL1dist(u, v) (ABS(u->s - v->s) + ABS(u->t - v->t))

#define VertCCW(u, v, w) tesvertCCW(u, v, w)

int tesvertLeq(TESSvertex *u, TESSvertex *v);
TESSreal tesedgeEval(TESSvertex *u, TESSvertex *v, TESSvertex *w);
TESSreal tesedgeSign(TESSvertex *u, TESSvertex *v, TESSvertex *w);
TESSreal testransEval(TESSvertex *u, TESSvertex *v, TESSvertex *w);
TESSreal testransSign(TESSvertex *u, TESSvertex *v, TESSvertex *w);
int tesvertCCW(TESSvertex *u, TESSvertex *v, TESSvertex *w);
void tesedgeIntersect(TESSvertex *o1, TESSvertex *d1, TESSvertex *o2,
                      TESSvertex *d2, TESSvertex *v);
int tesedgeIsLocallyDelaunay(TESShalfEdge *e);

int tessComputeInterior(TESStesselator *tess);

struct ActiveRegion {
  TESShalfEdge *eUp;
  DictNode *nodeUp;
  int windingNumber;
  int inside;
  int sentinel;
  int dirty;
  int fixUpperEdge;
};

#define RegionBelow(r) ((ActiveRegion *)dictKey(dictPred((r)->nodeUp)))
#define RegionAbove(r) ((ActiveRegion *)dictKey(dictSucc((r)->nodeUp)))

struct TESStesselator {

  TESSmesh *mesh;
  int outOfMemory;

  TESSreal normal[3];
  TESSreal sUnit[3];
  TESSreal tUnit[3];

  TESSreal bmin[2];
  TESSreal bmax[2];

  int processCDT;
  int reverseContours;

  int windingRule;

  Dict *dict;
  PriorityQ *pq;
  TESSvertex *event;

  struct BucketAlloc *regionPool;

  TESSindex vertexIndexCounter;

  TESSreal *vertices;
  TESSindex *vertexIndices;
  int vertexCount;
  TESSindex *elements;
  int elementCount;

  TESSalloc alloc;

  jmp_buf env;
};

typedef struct BucketAlloc BucketAlloc;
typedef struct Bucket Bucket;

struct Bucket {
  Bucket *next;
};

struct BucketAlloc {
  void *freelist;
  Bucket *buckets;
  unsigned int itemSize;
  unsigned int bucketSize;
  const char *name;
  TESSalloc *alloc;
};

static int CreateBucket(struct BucketAlloc *ba) {
  size_t size;
  Bucket *bucket;
  void *freelist;
  unsigned char *head;
  unsigned char *it;

  size = sizeof(Bucket) + ba->itemSize * ba->bucketSize;
  bucket = (Bucket *)ba->alloc->memalloc(ba->alloc->userData, size);
  if (!bucket)
    return 0;
  bucket->next = 0;

  bucket->next = ba->buckets;
  ba->buckets = bucket;

  freelist = ba->freelist;
  head = (unsigned char *)bucket + sizeof(Bucket);
  it = head + ba->itemSize * ba->bucketSize;
  do {
    it -= ba->itemSize;

    *((void **)it) = freelist;

    freelist = (void *)it;
  } while (it != head);

  ba->freelist = (void *)it;

  return 1;
}

static void *NextFreeItem(struct BucketAlloc *ba) {
  return *(void **)ba->freelist;
}

struct BucketAlloc *createBucketAlloc(TESSalloc *alloc, const char *name,
                                      unsigned int itemSize,
                                      unsigned int bucketSize) {
  BucketAlloc *ba =
      (BucketAlloc *)alloc->memalloc(alloc->userData, sizeof(BucketAlloc));

  ba->alloc = alloc;
  ba->name = name;
  ba->itemSize = itemSize;
  if (ba->itemSize < sizeof(void *))
    ba->itemSize = sizeof(void *);
  ba->bucketSize = bucketSize;
  ba->freelist = 0;
  ba->buckets = 0;

  if (!CreateBucket(ba)) {
    alloc->memfree(alloc->userData, ba);
    return 0;
  }

  return ba;
}

void *bucketAlloc(struct BucketAlloc *ba) {
  void *it;

  if (!ba->freelist || !NextFreeItem(ba)) {
    if (!CreateBucket(ba))
      return 0;
  }

  it = ba->freelist;
  ba->freelist = NextFreeItem(ba);

  return it;
}

void bucketFree(struct BucketAlloc *ba, void *ptr) {
#ifdef CHECK_BOUNDS
  int inBounds = 0;
  Bucket *bucket;

  bucket = ba->buckets;
  while (bucket) {
    void *bucketMin = (void *)((unsigned char *)bucket + sizeof(Bucket));
    void *bucketMax = (void *)((unsigned char *)bucket + sizeof(Bucket) +
                               ba->itemSize * ba->bucketSize);
    if (ptr >= bucketMin && ptr < bucketMax) {
      inBounds = 1;
      break;
    }
    bucket = bucket->next;
  }

  if (inBounds) {

    *(void **)ptr = ba->freelist;
    ba->freelist = ptr;
  } else {
    printf("ERROR! pointer 0x%p does not belong to allocator '%s'\n", ba->name);
  }
#else

  *(void **)ptr = ba->freelist;
  ba->freelist = ptr;
#endif
}

void deleteBucketAlloc(struct BucketAlloc *ba) {
  TESSalloc *alloc = ba->alloc;
  Bucket *bucket = ba->buckets;
  Bucket *next;
  while (bucket) {
    next = bucket->next;
    alloc->memfree(alloc->userData, bucket);
    bucket = next;
  }
  ba->freelist = 0;
  ba->buckets = 0;
  alloc->memfree(alloc->userData, ba);
}

Dict *dictNewDict(TESSalloc *alloc, void *frame,
                  int (*leq)(void *frame, DictKey key1, DictKey key2)) {
  Dict *dict = (Dict *)alloc->memalloc(alloc->userData, sizeof(Dict));
  DictNode *head;

  if (dict == NULL)
    return NULL;

  head = &dict->head;

  head->key = NULL;
  head->next = head;
  head->prev = head;

  dict->frame = frame;
  dict->leq = leq;

  if (alloc->dictNodeBucketSize < 16)
    alloc->dictNodeBucketSize = 16;
  if (alloc->dictNodeBucketSize > 4096)
    alloc->dictNodeBucketSize = 4096;
  dict->nodePool = createBucketAlloc(alloc, "Dict", sizeof(DictNode),
                                     alloc->dictNodeBucketSize);

  return dict;
}

void dictDeleteDict(TESSalloc *alloc, Dict *dict) {
  deleteBucketAlloc(dict->nodePool);
  alloc->memfree(alloc->userData, dict);
}

DictNode *dictInsertBefore(Dict *dict, DictNode *node, DictKey key) {
  DictNode *newNode;

  do {
    node = node->prev;
  } while (node->key != NULL && !(*dict->leq)(dict->frame, node->key, key));

  newNode = (DictNode *)bucketAlloc(dict->nodePool);
  if (newNode == NULL)
    return NULL;

  newNode->key = key;
  newNode->next = node->next;
  node->next->prev = newNode;
  newNode->prev = node;
  node->next = newNode;

  return newNode;
}

void dictDelete(Dict *dict, DictNode *node) {
  node->next->prev = node->prev;
  node->prev->next = node->next;
  bucketFree(dict->nodePool, node);
}

DictNode *dictSearch(Dict *dict, DictKey key) {
  DictNode *node = &dict->head;

  do {
    node = node->next;
  } while (node->key != NULL && !(*dict->leq)(dict->frame, key, node->key));

  return node;
}

#define INIT_SIZE 32

#define TRUE 1
#define FALSE 0

#ifdef FOR_TRITE_TEST_PROGRAM
#define LEQ(x, y) (*pq->leq)(x, y)
#else

#define LEQ(x, y) VertLeq((TESSvertex *)x, (TESSvertex *)y)
#endif

#define pqHeapMinimum(pq) ((pq)->handles[(pq)->nodes[1].handle].key)
#define pqHeapIsEmpty(pq) ((pq)->size == 0)

PriorityQHeap *pqHeapNewPriorityQ(TESSalloc *alloc, int size,
                                  int (*leq)(PQkey key1, PQkey key2)) {
  PriorityQHeap *pq =
      (PriorityQHeap *)alloc->memalloc(alloc->userData, sizeof(PriorityQHeap));
  if (pq == NULL)
    return NULL;

  pq->size = 0;
  pq->max = size;
  pq->nodes = (PQnode *)alloc->memalloc(alloc->userData,
                                        (size + 1) * sizeof(pq->nodes[0]));
  if (pq->nodes == NULL) {
    alloc->memfree(alloc->userData, pq);
    return NULL;
  }

  pq->handles = (PQhandleElem *)alloc->memalloc(
      alloc->userData, (size + 1) * sizeof(pq->handles[0]));
  if (pq->handles == NULL) {
    alloc->memfree(alloc->userData, pq->nodes);
    alloc->memfree(alloc->userData, pq);
    return NULL;
  }

  pq->initialized = FALSE;
  pq->freeList = 0;
  pq->leq = leq;

  pq->nodes[1].handle = 1;
  pq->handles[1].key = NULL;
  return pq;
}

void pqHeapDeletePriorityQ(TESSalloc *alloc, PriorityQHeap *pq) {
  alloc->memfree(alloc->userData, pq->handles);
  alloc->memfree(alloc->userData, pq->nodes);
  alloc->memfree(alloc->userData, pq);
}

static void FloatDown(PriorityQHeap *pq, int curr) {
  PQnode *n = pq->nodes;
  PQhandleElem *h = pq->handles;
  PQhandle hCurr, hChild;
  int child;

  hCurr = n[curr].handle;
  for (;;) {
    child = curr << 1;
    if (child < pq->size &&
        LEQ(h[n[child + 1].handle].key, h[n[child].handle].key)) {
      ++child;
    }

    assert(child <= pq->max);

    hChild = n[child].handle;
    if (child > pq->size || LEQ(h[hCurr].key, h[hChild].key)) {
      n[curr].handle = hCurr;
      h[hCurr].node = curr;
      break;
    }
    n[curr].handle = hChild;
    h[hChild].node = curr;
    curr = child;
  }
}

static void FloatUp(PriorityQHeap *pq, int curr) {
  PQnode *n = pq->nodes;
  PQhandleElem *h = pq->handles;
  PQhandle hCurr, hParent;
  int parent;

  hCurr = n[curr].handle;
  for (;;) {
    parent = curr >> 1;
    hParent = n[parent].handle;
    if (parent == 0 || LEQ(h[hParent].key, h[hCurr].key)) {
      n[curr].handle = hCurr;
      h[hCurr].node = curr;
      break;
    }
    n[curr].handle = hParent;
    h[hParent].node = curr;
    curr = parent;
  }
}

void pqHeapInit(PriorityQHeap *pq) {
  int i;

  for (i = pq->size; i >= 1; --i) {
    FloatDown(pq, i);
  }
  pq->initialized = TRUE;
}

PQhandle pqHeapInsert(TESSalloc *alloc, PriorityQHeap *pq, PQkey keyNew) {
  int curr;
  PQhandle free;

  curr = ++pq->size;
  if ((curr * 2) > pq->max) {
    if (!alloc->memrealloc) {
      return INV_HANDLE;
    } else {
      PQnode *saveNodes = pq->nodes;
      PQhandleElem *saveHandles = pq->handles;

      pq->max <<= 1;
      pq->nodes = (PQnode *)alloc->memrealloc(
          alloc->userData, pq->nodes,
          (size_t)((pq->max + 1) * sizeof(pq->nodes[0])));
      if (pq->nodes == NULL) {
        pq->nodes = saveNodes;
        return INV_HANDLE;
      }
      pq->handles = (PQhandleElem *)alloc->memrealloc(
          alloc->userData, pq->handles,
          (size_t)((pq->max + 1) * sizeof(pq->handles[0])));
      if (pq->handles == NULL) {
        pq->handles = saveHandles;
        return INV_HANDLE;
      }
    }
  }

  if (pq->freeList == 0) {
    free = curr;
  } else {
    free = pq->freeList;
    pq->freeList = pq->handles[free].node;
  }

  pq->nodes[curr].handle = free;
  pq->handles[free].node = curr;
  pq->handles[free].key = keyNew;

  if (pq->initialized) {
    FloatUp(pq, curr);
  }
  assert(free != INV_HANDLE);
  return free;
}

PQkey pqHeapExtractMin(PriorityQHeap *pq) {
  PQnode *n = pq->nodes;
  PQhandleElem *h = pq->handles;
  PQhandle hMin = n[1].handle;
  PQkey min = h[hMin].key;

  if (pq->size > 0) {
    n[1].handle = n[pq->size].handle;
    h[n[1].handle].node = 1;

    h[hMin].key = NULL;
    h[hMin].node = pq->freeList;
    pq->freeList = hMin;

    if (--pq->size > 0) {
      FloatDown(pq, 1);
    }
  }
  return min;
}

void pqHeapDelete(PriorityQHeap *pq, PQhandle hCurr) {
  PQnode *n = pq->nodes;
  PQhandleElem *h = pq->handles;
  int curr;

  assert(hCurr >= 1 && hCurr <= pq->max && h[hCurr].key != NULL);

  curr = h[hCurr].node;
  n[curr].handle = n[pq->size].handle;
  h[n[curr].handle].node = curr;

  if (curr <= --pq->size) {
    if (curr <= 1 || LEQ(h[n[curr >> 1].handle].key, h[n[curr].handle].key)) {
      FloatDown(pq, curr);
    } else {
      FloatUp(pq, curr);
    }
  }
  h[hCurr].key = NULL;
  h[hCurr].node = pq->freeList;
  pq->freeList = hCurr;
}

PriorityQ *pqNewPriorityQ(TESSalloc *alloc, int size,
                          int (*leq)(PQkey key1, PQkey key2)) {
  PriorityQ *pq =
      (PriorityQ *)alloc->memalloc(alloc->userData, sizeof(PriorityQ));
  if (pq == NULL)
    return NULL;

  pq->heap = pqHeapNewPriorityQ(alloc, size, leq);
  if (pq->heap == NULL) {
    alloc->memfree(alloc->userData, pq);
    return NULL;
  }

  pq->keys =
      (PQkey *)alloc->memalloc(alloc->userData, size * sizeof(pq->keys[0]));
  if (pq->keys == NULL) {
    pqHeapDeletePriorityQ(alloc, pq->heap);
    alloc->memfree(alloc->userData, pq);
    return NULL;
  }

  pq->size = 0;
  pq->max = size;
  pq->initialized = FALSE;
  pq->leq = leq;

  return pq;
}

void pqDeletePriorityQ(TESSalloc *alloc, PriorityQ *pq) {
  assert(pq != NULL);
  if (pq->heap != NULL)
    pqHeapDeletePriorityQ(alloc, pq->heap);
  if (pq->order != NULL)
    alloc->memfree(alloc->userData, pq->order);
  if (pq->keys != NULL)
    alloc->memfree(alloc->userData, pq->keys);
  alloc->memfree(alloc->userData, pq);
}

#define LT(x, y) (!LEQ(y, x))
#define GT(x, y) (!LEQ(x, y))
#define Swap(a, b)                                                             \
  if (1) {                                                                     \
    PQkey *tmp = *a;                                                           \
    *a = *b;                                                                   \
    *b = tmp;                                                                  \
  } else

int pqInit(TESSalloc *alloc, PriorityQ *pq) {
  PQkey **p, **r, **i, **j, *piv;
  struct {
    PQkey **p, **r;
  } Stack[50], *top = Stack;
  unsigned int seed = 2016473283;

  pq->order = (PQkey **)alloc->memalloc(
      alloc->userData, (size_t)((pq->size + 1) * sizeof(pq->order[0])));

  if (pq->order == NULL)
    return 0;

  p = pq->order;
  r = p + pq->size - 1;
  for (piv = pq->keys, i = p; i <= r; ++piv, ++i) {
    *i = piv;
  }

  top->p = p;
  top->r = r;
  ++top;
  while (--top >= Stack) {
    p = top->p;
    r = top->r;
    while (r > p + 10) {
      seed = seed * 1539415821 + 1;
      i = p + seed % (r - p + 1);
      piv = *i;
      *i = *p;
      *p = piv;
      i = p - 1;
      j = r + 1;
      do {
        do {
          ++i;
        } while (GT(**i, *piv));
        do {
          --j;
        } while (LT(**j, *piv));
        Swap(i, j);
      } while (i < j);
      Swap(i, j);
      if (i - p < r - j) {
        top->p = j + 1;
        top->r = r;
        ++top;
        r = i - 1;
      } else {
        top->p = p;
        top->r = i - 1;
        ++top;
        p = j + 1;
      }
    }

    for (i = p + 1; i <= r; ++i) {
      piv = *i;
      for (j = i; j > p && LT(**(j - 1), *piv); --j) {
        *j = *(j - 1);
      }
      *j = piv;
    }
  }
  pq->max = pq->size;
  pq->initialized = TRUE;
  pqHeapInit(pq->heap);

#ifndef NDEBUG
  p = pq->order;
  r = p + pq->size - 1;
  for (i = p; i < r; ++i) {
    assert(LEQ(**(i + 1), **i));
  }
#endif

  return 1;
}

PQhandle pqInsert(TESSalloc *alloc, PriorityQ *pq, PQkey keyNew) {
  int curr;

  if (pq->initialized) {
    return pqHeapInsert(alloc, pq->heap, keyNew);
  }
  curr = pq->size;
  if (++pq->size >= pq->max) {
    if (!alloc->memrealloc) {
      return INV_HANDLE;
    } else {
      PQkey *saveKey = pq->keys;

      pq->max <<= 1;
      pq->keys = (PQkey *)alloc->memrealloc(
          alloc->userData, pq->keys, (size_t)(pq->max * sizeof(pq->keys[0])));
      if (pq->keys == NULL) {
        pq->keys = saveKey;
        return INV_HANDLE;
      }
    }
  }
  assert(curr != INV_HANDLE);
  pq->keys[curr] = keyNew;

  return -(curr + 1);
}

PQkey pqExtractMin(PriorityQ *pq) {
  PQkey sortMin, heapMin;

  if (pq->size == 0) {
    return pqHeapExtractMin(pq->heap);
  }
  sortMin = *(pq->order[pq->size - 1]);
  if (!pqHeapIsEmpty(pq->heap)) {
    heapMin = pqHeapMinimum(pq->heap);
    if (LEQ(heapMin, sortMin)) {
      return pqHeapExtractMin(pq->heap);
    }
  }
  do {
    --pq->size;
  } while (pq->size > 0 && *(pq->order[pq->size - 1]) == NULL);
  return sortMin;
}

PQkey pqMinimum(PriorityQ *pq) {
  PQkey sortMin, heapMin;

  if (pq->size == 0) {
    return pqHeapMinimum(pq->heap);
  }
  sortMin = *(pq->order[pq->size - 1]);
  if (!pqHeapIsEmpty(pq->heap)) {
    heapMin = pqHeapMinimum(pq->heap);
    if (LEQ(heapMin, sortMin)) {
      return heapMin;
    }
  }
  return sortMin;
}

int pqIsEmpty(PriorityQ *pq) {
  return (pq->size == 0) && pqHeapIsEmpty(pq->heap);
}

void pqDelete(PriorityQ *pq, PQhandle curr) {
  if (curr >= 0) {
    pqHeapDelete(pq->heap, curr);
    return;
  }
  curr = -(curr + 1);
  assert(curr < pq->max && pq->keys[curr] != NULL);

  pq->keys[curr] = NULL;
  while (pq->size > 0 && *(pq->order[pq->size - 1]) == NULL) {
    --pq->size;
  }
}

#define TRUE 1
#define FALSE 0

typedef struct {
  TESShalfEdge e, eSym;
} EdgePair;

static TESShalfEdge *MakeEdge(TESSmesh *mesh, TESShalfEdge *eNext) {
  TESShalfEdge *e;
  TESShalfEdge *eSym;
  TESShalfEdge *ePrev;
  EdgePair *pair = (EdgePair *)bucketAlloc(mesh->edgeBucket);
  if (pair == NULL)
    return NULL;

  e = &pair->e;
  eSym = &pair->eSym;

  if (eNext->Sym < eNext) {
    eNext = eNext->Sym;
  }

  ePrev = eNext->Sym->next;
  eSym->next = ePrev;
  ePrev->Sym->next = e;
  e->next = eNext;
  eNext->Sym->next = eSym;

  e->Sym = eSym;
  e->Onext = e;
  e->Lnext = eSym;
  e->Org = NULL;
  e->Lface = NULL;
  e->winding = 0;
  e->activeRegion = NULL;
  e->mark = 0;

  eSym->Sym = e;
  eSym->Onext = eSym;
  eSym->Lnext = e;
  eSym->Org = NULL;
  eSym->Lface = NULL;
  eSym->winding = 0;
  eSym->activeRegion = NULL;
  eSym->mark = 0;

  return e;
}

static void Splice(TESShalfEdge *a, TESShalfEdge *b) {
  TESShalfEdge *aOnext = a->Onext;
  TESShalfEdge *bOnext = b->Onext;

  aOnext->Sym->Lnext = b;
  bOnext->Sym->Lnext = a;
  a->Onext = bOnext;
  b->Onext = aOnext;
}

static void MakeVertex(TESSvertex *newVertex, TESShalfEdge *eOrig,
                       TESSvertex *vNext) {
  TESShalfEdge *e;
  TESSvertex *vPrev;
  TESSvertex *vNew = newVertex;

  assert(vNew != NULL);

  vPrev = vNext->prev;
  vNew->prev = vPrev;
  vPrev->next = vNew;
  vNew->next = vNext;
  vNext->prev = vNew;

  vNew->anEdge = eOrig;

  e = eOrig;
  do {
    e->Org = vNew;
    e = e->Onext;
  } while (e != eOrig);
}

static void MakeFace(TESSface *newFace, TESShalfEdge *eOrig, TESSface *fNext) {
  TESShalfEdge *e;
  TESSface *fPrev;
  TESSface *fNew = newFace;

  assert(fNew != NULL);

  fPrev = fNext->prev;
  fNew->prev = fPrev;
  fPrev->next = fNew;
  fNew->next = fNext;
  fNext->prev = fNew;

  fNew->anEdge = eOrig;
  fNew->trail = NULL;
  fNew->marked = FALSE;

  fNew->inside = fNext->inside;

  e = eOrig;
  do {
    e->Lface = fNew;
    e = e->Lnext;
  } while (e != eOrig);
}

static void KillEdge(TESSmesh *mesh, TESShalfEdge *eDel) {
  TESShalfEdge *ePrev, *eNext;

  if (eDel->Sym < eDel) {
    eDel = eDel->Sym;
  }

  eNext = eDel->next;
  ePrev = eDel->Sym->next;
  eNext->Sym->next = ePrev;
  ePrev->Sym->next = eNext;

  bucketFree(mesh->edgeBucket, eDel);
}

static void KillVertex(TESSmesh *mesh, TESSvertex *vDel, TESSvertex *newOrg) {
  TESShalfEdge *e, *eStart = vDel->anEdge;
  TESSvertex *vPrev, *vNext;

  e = eStart;
  do {
    e->Org = newOrg;
    e = e->Onext;
  } while (e != eStart);

  vPrev = vDel->prev;
  vNext = vDel->next;
  vNext->prev = vPrev;
  vPrev->next = vNext;

  bucketFree(mesh->vertexBucket, vDel);
}

static void KillFace(TESSmesh *mesh, TESSface *fDel, TESSface *newLface) {
  TESShalfEdge *e, *eStart = fDel->anEdge;
  TESSface *fPrev, *fNext;

  e = eStart;
  do {
    e->Lface = newLface;
    e = e->Lnext;
  } while (e != eStart);

  fPrev = fDel->prev;
  fNext = fDel->next;
  fNext->prev = fPrev;
  fPrev->next = fNext;

  bucketFree(mesh->faceBucket, fDel);
}

TESShalfEdge *tessMeshMakeEdge(TESSmesh *mesh) {
  TESSvertex *newVertex1 = (TESSvertex *)bucketAlloc(mesh->vertexBucket);
  TESSvertex *newVertex2 = (TESSvertex *)bucketAlloc(mesh->vertexBucket);
  TESSface *newFace = (TESSface *)bucketAlloc(mesh->faceBucket);
  TESShalfEdge *e;

  if (newVertex1 == NULL || newVertex2 == NULL || newFace == NULL) {
    if (newVertex1 != NULL)
      bucketFree(mesh->vertexBucket, newVertex1);
    if (newVertex2 != NULL)
      bucketFree(mesh->vertexBucket, newVertex2);
    if (newFace != NULL)
      bucketFree(mesh->faceBucket, newFace);
    return NULL;
  }

  e = MakeEdge(mesh, &mesh->eHead);
  if (e == NULL)
    return NULL;

  MakeVertex(newVertex1, e, &mesh->vHead);
  MakeVertex(newVertex2, e->Sym, &mesh->vHead);
  MakeFace(newFace, e, &mesh->fHead);
  return e;
}

int tessMeshSplice(TESSmesh *mesh, TESShalfEdge *eOrg, TESShalfEdge *eDst) {
  int joiningLoops = FALSE;
  int joiningVertices = FALSE;

  if (eOrg == eDst)
    return 1;

  if (eDst->Org != eOrg->Org) {

    joiningVertices = TRUE;
    KillVertex(mesh, eDst->Org, eOrg->Org);
  }
  if (eDst->Lface != eOrg->Lface) {

    joiningLoops = TRUE;
    KillFace(mesh, eDst->Lface, eOrg->Lface);
  }

  Splice(eDst, eOrg);

  if (!joiningVertices) {
    TESSvertex *newVertex = (TESSvertex *)bucketAlloc(mesh->vertexBucket);
    if (newVertex == NULL)
      return 0;

    MakeVertex(newVertex, eDst, eOrg->Org);
    eOrg->Org->anEdge = eOrg;
  }
  if (!joiningLoops) {
    TESSface *newFace = (TESSface *)bucketAlloc(mesh->faceBucket);
    if (newFace == NULL)
      return 0;

    MakeFace(newFace, eDst, eOrg->Lface);
    eOrg->Lface->anEdge = eOrg;
  }

  return 1;
}

int tessMeshDelete(TESSmesh *mesh, TESShalfEdge *eDel) {
  TESShalfEdge *eDelSym = eDel->Sym;
  int joiningLoops = FALSE;

  if (eDel->Lface != eDel->Rface) {

    joiningLoops = TRUE;
    KillFace(mesh, eDel->Lface, eDel->Rface);
  }

  if (eDel->Onext == eDel) {
    KillVertex(mesh, eDel->Org, NULL);
  } else {

    eDel->Rface->anEdge = eDel->Oprev;
    eDel->Org->anEdge = eDel->Onext;

    Splice(eDel, eDel->Oprev);
    if (!joiningLoops) {
      TESSface *newFace = (TESSface *)bucketAlloc(mesh->faceBucket);
      if (newFace == NULL)
        return 0;

      MakeFace(newFace, eDel, eDel->Lface);
    }
  }

  if (eDelSym->Onext == eDelSym) {
    KillVertex(mesh, eDelSym->Org, NULL);
    KillFace(mesh, eDelSym->Lface, NULL);
  } else {

    eDel->Lface->anEdge = eDelSym->Oprev;
    eDelSym->Org->anEdge = eDelSym->Onext;
    Splice(eDelSym, eDelSym->Oprev);
  }

  KillEdge(mesh, eDel);

  return 1;
}

TESShalfEdge *tessMeshAddEdgeVertex(TESSmesh *mesh, TESShalfEdge *eOrg) {
  TESShalfEdge *eNewSym;
  TESShalfEdge *eNew = MakeEdge(mesh, eOrg);
  if (eNew == NULL)
    return NULL;

  eNewSym = eNew->Sym;

  Splice(eNew, eOrg->Lnext);

  eNew->Org = eOrg->Dst;
  {
    TESSvertex *newVertex = (TESSvertex *)bucketAlloc(mesh->vertexBucket);
    if (newVertex == NULL)
      return NULL;

    MakeVertex(newVertex, eNewSym, eNew->Org);
  }
  eNew->Lface = eNewSym->Lface = eOrg->Lface;

  return eNew;
}

TESShalfEdge *tessMeshSplitEdge(TESSmesh *mesh, TESShalfEdge *eOrg) {
  TESShalfEdge *eNew;
  TESShalfEdge *tempHalfEdge = tessMeshAddEdgeVertex(mesh, eOrg);
  if (tempHalfEdge == NULL)
    return NULL;

  eNew = tempHalfEdge->Sym;

  Splice(eOrg->Sym, eOrg->Sym->Oprev);
  Splice(eOrg->Sym, eNew);

  eOrg->Dst = eNew->Org;
  eNew->Dst->anEdge = eNew->Sym;
  eNew->Rface = eOrg->Rface;
  eNew->winding = eOrg->winding;
  eNew->Sym->winding = eOrg->Sym->winding;

  return eNew;
}

TESShalfEdge *tessMeshConnect(TESSmesh *mesh, TESShalfEdge *eOrg,
                              TESShalfEdge *eDst) {
  TESShalfEdge *eNewSym;
  int joiningLoops = FALSE;
  TESShalfEdge *eNew = MakeEdge(mesh, eOrg);
  if (eNew == NULL)
    return NULL;

  eNewSym = eNew->Sym;

  if (eDst->Lface != eOrg->Lface) {

    joiningLoops = TRUE;
    KillFace(mesh, eDst->Lface, eOrg->Lface);
  }

  Splice(eNew, eOrg->Lnext);
  Splice(eNewSym, eDst);

  eNew->Org = eOrg->Dst;
  eNewSym->Org = eDst->Org;
  eNew->Lface = eNewSym->Lface = eOrg->Lface;

  eOrg->Lface->anEdge = eNewSym;

  if (!joiningLoops) {
    TESSface *newFace = (TESSface *)bucketAlloc(mesh->faceBucket);
    if (newFace == NULL)
      return NULL;

    MakeFace(newFace, eNew, eOrg->Lface);
  }
  return eNew;
}

void tessMeshZapFace(TESSmesh *mesh, TESSface *fZap) {
  TESShalfEdge *eStart = fZap->anEdge;
  TESShalfEdge *e, *eNext, *eSym;
  TESSface *fPrev, *fNext;

  eNext = eStart->Lnext;
  do {
    e = eNext;
    eNext = e->Lnext;

    e->Lface = NULL;
    if (e->Rface == NULL) {

      if (e->Onext == e) {
        KillVertex(mesh, e->Org, NULL);
      } else {

        e->Org->anEdge = e->Onext;
        Splice(e, e->Oprev);
      }
      eSym = e->Sym;
      if (eSym->Onext == eSym) {
        KillVertex(mesh, eSym->Org, NULL);
      } else {

        eSym->Org->anEdge = eSym->Onext;
        Splice(eSym, eSym->Oprev);
      }
      KillEdge(mesh, e);
    }
  } while (e != eStart);

  fPrev = fZap->prev;
  fNext = fZap->next;
  fNext->prev = fPrev;
  fPrev->next = fNext;

  bucketFree(mesh->faceBucket, fZap);
}

TESSmesh *tessMeshNewMesh(TESSalloc *alloc) {
  TESSvertex *v;
  TESSface *f;
  TESShalfEdge *e;
  TESShalfEdge *eSym;
  TESSmesh *mesh =
      (TESSmesh *)alloc->memalloc(alloc->userData, sizeof(TESSmesh));
  if (mesh == NULL) {
    return NULL;
  }

  if (alloc->meshEdgeBucketSize < 16)
    alloc->meshEdgeBucketSize = 16;
  if (alloc->meshEdgeBucketSize > 4096)
    alloc->meshEdgeBucketSize = 4096;

  if (alloc->meshVertexBucketSize < 16)
    alloc->meshVertexBucketSize = 16;
  if (alloc->meshVertexBucketSize > 4096)
    alloc->meshVertexBucketSize = 4096;

  if (alloc->meshFaceBucketSize < 16)
    alloc->meshFaceBucketSize = 16;
  if (alloc->meshFaceBucketSize > 4096)
    alloc->meshFaceBucketSize = 4096;

  mesh->edgeBucket = createBucketAlloc(alloc, "Mesh Edges", sizeof(EdgePair),
                                       alloc->meshEdgeBucketSize);
  mesh->vertexBucket = createBucketAlloc(
      alloc, "Mesh Vertices", sizeof(TESSvertex), alloc->meshVertexBucketSize);
  mesh->faceBucket = createBucketAlloc(alloc, "Mesh Faces", sizeof(TESSface),
                                       alloc->meshFaceBucketSize);

  v = &mesh->vHead;
  f = &mesh->fHead;
  e = &mesh->eHead;
  eSym = &mesh->eHeadSym;

  v->next = v->prev = v;
  v->anEdge = NULL;

  f->next = f->prev = f;
  f->anEdge = NULL;
  f->trail = NULL;
  f->marked = FALSE;
  f->inside = FALSE;

  e->next = e;
  e->Sym = eSym;
  e->Onext = NULL;
  e->Lnext = NULL;
  e->Org = NULL;
  e->Lface = NULL;
  e->winding = 0;
  e->activeRegion = NULL;

  eSym->next = eSym;
  eSym->Sym = e;
  eSym->Onext = NULL;
  eSym->Lnext = NULL;
  eSym->Org = NULL;
  eSym->Lface = NULL;
  eSym->winding = 0;
  eSym->activeRegion = NULL;

  return mesh;
}

TESSmesh *tessMeshUnion(TESSalloc *alloc, TESSmesh *mesh1, TESSmesh *mesh2) {
  TESSface *f1 = &mesh1->fHead;
  TESSvertex *v1 = &mesh1->vHead;
  TESShalfEdge *e1 = &mesh1->eHead;
  TESSface *f2 = &mesh2->fHead;
  TESSvertex *v2 = &mesh2->vHead;
  TESShalfEdge *e2 = &mesh2->eHead;

  if (f2->next != f2) {
    f1->prev->next = f2->next;
    f2->next->prev = f1->prev;
    f2->prev->next = f1;
    f1->prev = f2->prev;
  }

  if (v2->next != v2) {
    v1->prev->next = v2->next;
    v2->next->prev = v1->prev;
    v2->prev->next = v1;
    v1->prev = v2->prev;
  }

  if (e2->next != e2) {
    e1->Sym->next->Sym->next = e2->next;
    e2->next->Sym->next = e1->Sym->next;
    e2->Sym->next->Sym->next = e1;
    e1->Sym->next = e2->Sym->next;
  }

  alloc->memfree(alloc->userData, mesh2);
  return mesh1;
}

static int CountFaceVerts(TESSface *f) {
  TESShalfEdge *eCur = f->anEdge;
  int n = 0;
  do {
    n++;
    eCur = eCur->Lnext;
  } while (eCur != f->anEdge);
  return n;
}

int tesvertCCW(TESSvertex *u, TESSvertex *v, TESSvertex *w) {

  return (u->s * (v->t - w->t) + v->s * (w->t - u->t) + w->s * (u->t - v->t)) >=
         0;
}

int tessMeshMergeConvexFaces(TESSmesh *mesh, int maxVertsPerFace) {
  TESShalfEdge *e, *eNext, *eSym;
  TESShalfEdge *eHead = &mesh->eHead;
  TESSvertex *va, *vb, *vc, *vd, *ve, *vf;
  int leftNv, rightNv;

  for (e = eHead->next; e != eHead; e = eNext) {
    eNext = e->next;
    eSym = e->Sym;
    if (!eSym)
      continue;

    if (!e->Lface || !e->Lface->inside)
      continue;
    if (!eSym->Lface || !eSym->Lface->inside)
      continue;

    leftNv = CountFaceVerts(e->Lface);
    rightNv = CountFaceVerts(eSym->Lface);
    if ((leftNv + rightNv - 2) > maxVertsPerFace)
      continue;

    va = e->Lprev->Org;
    vb = e->Org;
    vc = e->Sym->Lnext->Dst;

    vd = e->Sym->Lprev->Org;
    ve = e->Sym->Org;
    vf = e->Lnext->Dst;

    if (VertCCW(va, vb, vc) && VertCCW(vd, ve, vf)) {
      if (e == eNext || e == eNext->Sym) {
        eNext = eNext->next;
      }
      if (!tessMeshDelete(mesh, e))
        return 0;
    }
  }

  return 1;
}

void tessMeshFlipEdge(TESSmesh *mesh, TESShalfEdge *edge) {
  TESShalfEdge *a0 = edge;
  TESShalfEdge *a1 = a0->Lnext;
  TESShalfEdge *a2 = a1->Lnext;
  TESShalfEdge *b0 = edge->Sym;
  TESShalfEdge *b1 = b0->Lnext;
  TESShalfEdge *b2 = b1->Lnext;

  TESSvertex *aOrg = a0->Org;
  TESSvertex *aOpp = a2->Org;
  TESSvertex *bOrg = b0->Org;
  TESSvertex *bOpp = b2->Org;

  TESSface *fa = a0->Lface;
  TESSface *fb = b0->Lface;

  assert(EdgeIsInternal(edge));
  assert(a2->Lnext == a0);
  assert(b2->Lnext == b0);

  a0->Org = bOpp;
  a0->Onext = b1->Sym;
  b0->Org = aOpp;
  b0->Onext = a1->Sym;
  a2->Onext = b0;
  b2->Onext = a0;
  b1->Onext = a2->Sym;
  a1->Onext = b2->Sym;

  a0->Lnext = a2;
  a2->Lnext = b1;
  b1->Lnext = a0;

  b0->Lnext = b2;
  b2->Lnext = a1;
  a1->Lnext = b0;

  a1->Lface = fb;
  b1->Lface = fa;

  fa->anEdge = a0;
  fb->anEdge = b0;

  if (aOrg->anEdge == a0)
    aOrg->anEdge = b1;
  if (bOrg->anEdge == b0)
    bOrg->anEdge = a1;

  assert(a0->Lnext->Onext->Sym == a0);
  assert(a0->Onext->Sym->Lnext == a0);
  assert(a0->Org->anEdge->Org == a0->Org);

  assert(a1->Lnext->Onext->Sym == a1);
  assert(a1->Onext->Sym->Lnext == a1);
  assert(a1->Org->anEdge->Org == a1->Org);

  assert(a2->Lnext->Onext->Sym == a2);
  assert(a2->Onext->Sym->Lnext == a2);
  assert(a2->Org->anEdge->Org == a2->Org);

  assert(b0->Lnext->Onext->Sym == b0);
  assert(b0->Onext->Sym->Lnext == b0);
  assert(b0->Org->anEdge->Org == b0->Org);

  assert(b1->Lnext->Onext->Sym == b1);
  assert(b1->Onext->Sym->Lnext == b1);
  assert(b1->Org->anEdge->Org == b1->Org);

  assert(b2->Lnext->Onext->Sym == b2);
  assert(b2->Onext->Sym->Lnext == b2);
  assert(b2->Org->anEdge->Org == b2->Org);

  assert(aOrg->anEdge->Org == aOrg);
  assert(bOrg->anEdge->Org == bOrg);

  assert(a0->Oprev->Onext->Org == a0->Org);
}

#ifdef DELETE_BY_ZAPPING

void tessMeshDeleteMesh(TESSalloc *alloc, TESSmesh *mesh) {
  TESSface *fHead = &mesh->fHead;

  while (fHead->next != fHead) {
    tessMeshZapFace(fHead->next);
  }
  assert(mesh->vHead.next == &mesh->vHead);

  alloc->memfree(alloc->userData, mesh);
}

#else

void tessMeshDeleteMesh(TESSalloc *alloc, TESSmesh *mesh) {
  deleteBucketAlloc(mesh->edgeBucket);
  deleteBucketAlloc(mesh->vertexBucket);
  deleteBucketAlloc(mesh->faceBucket);

  alloc->memfree(alloc->userData, mesh);
}

#endif

#ifndef NDEBUG

void tessMeshCheckMesh(TESSmesh *mesh) {
  TESSface *fHead = &mesh->fHead;
  TESSvertex *vHead = &mesh->vHead;
  TESShalfEdge *eHead = &mesh->eHead;
  TESSface *f, *fPrev;
  TESSvertex *v, *vPrev;
  TESShalfEdge *e, *ePrev;

  for (fPrev = fHead; (f = fPrev->next) != fHead; fPrev = f) {
    assert(f->prev == fPrev);
    e = f->anEdge;
    do {
      assert(e->Sym != e);
      assert(e->Sym->Sym == e);
      assert(e->Lnext->Onext->Sym == e);
      assert(e->Onext->Sym->Lnext == e);
      assert(e->Lface == f);
      e = e->Lnext;
    } while (e != f->anEdge);
  }
  assert(f->prev == fPrev && f->anEdge == NULL);

  for (vPrev = vHead; (v = vPrev->next) != vHead; vPrev = v) {
    assert(v->prev == vPrev);
    e = v->anEdge;
    do {
      assert(e->Sym != e);
      assert(e->Sym->Sym == e);
      assert(e->Lnext->Onext->Sym == e);
      assert(e->Onext->Sym->Lnext == e);
      assert(e->Org == v);
      e = e->Onext;
    } while (e != v->anEdge);
  }
  assert(v->prev == vPrev && v->anEdge == NULL);

  for (ePrev = eHead; (e = ePrev->next) != eHead; ePrev = e) {
    assert(e->Sym->next == ePrev->Sym);
    assert(e->Sym != e);
    assert(e->Sym->Sym == e);
    assert(e->Org != NULL);
    assert(e->Dst != NULL);
    assert(e->Lnext->Onext->Sym == e);
    assert(e->Onext->Sym->Lnext == e);
  }
  assert(e->Sym->next == ePrev->Sym && e->Sym == &mesh->eHeadSym &&
         e->Sym->Sym == e && e->Org == NULL && e->Dst == NULL &&
         e->Lface == NULL && e->Rface == NULL);
}

#endif

int tesvertLeq(TESSvertex *u, TESSvertex *v) { return VertLeq(u, v); }

TESSreal tesedgeEval(TESSvertex *u, TESSvertex *v, TESSvertex *w) {

  TESSreal gapL, gapR;

  assert(VertLeq(u, v) && VertLeq(v, w));

  gapL = v->s - u->s;
  gapR = w->s - v->s;

  if (gapL + gapR > 0) {
    if (gapL < gapR) {
      return (v->t - u->t) + (u->t - w->t) * (gapL / (gapL + gapR));
    } else {
      return (v->t - w->t) + (w->t - u->t) * (gapR / (gapL + gapR));
    }
  }

  return 0;
}

TESSreal tesedgeSign(TESSvertex *u, TESSvertex *v, TESSvertex *w) {

  TESSreal gapL, gapR;

  assert(VertLeq(u, v) && VertLeq(v, w));

  gapL = v->s - u->s;
  gapR = w->s - v->s;

  if (gapL + gapR > 0) {
    return (v->t - w->t) * gapL + (v->t - u->t) * gapR;
  }

  return 0;
}

TESSreal testransEval(TESSvertex *u, TESSvertex *v, TESSvertex *w) {

  TESSreal gapL, gapR;

  assert(TransLeq(u, v) && TransLeq(v, w));

  gapL = v->t - u->t;
  gapR = w->t - v->t;

  if (gapL + gapR > 0) {
    if (gapL < gapR) {
      return (v->s - u->s) + (u->s - w->s) * (gapL / (gapL + gapR));
    } else {
      return (v->s - w->s) + (w->s - u->s) * (gapR / (gapL + gapR));
    }
  }

  return 0;
}

TESSreal testransSign(TESSvertex *u, TESSvertex *v, TESSvertex *w) {

  TESSreal gapL, gapR;

  assert(TransLeq(u, v) && TransLeq(v, w));

  gapL = v->t - u->t;
  gapR = w->t - v->t;

  if (gapL + gapR > 0) {
    return (v->s - w->s) * gapL + (v->s - u->s) * gapR;
  }

  return 0;
}

#define RealInterpolate(a, x, b, y)                                            \
  (a = (a < 0) ? 0 : a, b = (b < 0) ? 0 : b,                                   \
   ((a <= b) ? ((b == 0) ? ((x + y) / 2) : (x + (y - x) * (a / (a + b))))      \
             : (y + (x - y) * (b / (a + b)))))

#ifndef FOR_TRITE_TEST_PROGRAM
#define Interpolate(a, x, b, y) RealInterpolate(a, x, b, y)
#else

extern int RandomInterpolate;

double Interpolate(double a, double x, double b, double y) {
  printf("*********************%d\n", RandomInterpolate);
  if (RandomInterpolate) {
    a = 1.2 * drand48() - 0.1;
    a = (a < 0) ? 0 : ((a > 1) ? 1 : a);
    b = 1.0 - a;
  }
  return RealInterpolate(a, x, b, y);
}

#endif

#define Swap(a, b)                                                             \
  if (1) {                                                                     \
    TESSvertex *t = a;                                                         \
    a = b;                                                                     \
    b = t;                                                                     \
  } else

void tesedgeIntersect(TESSvertex *o1, TESSvertex *d1, TESSvertex *o2,
                      TESSvertex *d2, TESSvertex *v)

{
  TESSreal z1, z2;

  if (!VertLeq(o1, d1)) {
    Swap(o1, d1);
  }
  if (!VertLeq(o2, d2)) {
    Swap(o2, d2);
  }
  if (!VertLeq(o1, o2)) {
    Swap(o1, o2);
    Swap(d1, d2);
  }

  if (!VertLeq(o2, d1)) {

    v->s = (o2->s + d1->s) / 2;
  } else if (VertLeq(d1, d2)) {

    z1 = EdgeEval(o1, o2, d1);
    z2 = EdgeEval(o2, d1, d2);
    if (z1 + z2 < 0) {
      z1 = -z1;
      z2 = -z2;
    }
    v->s = Interpolate(z1, o2->s, z2, d1->s);
  } else {

    z1 = EdgeSign(o1, o2, d1);
    z2 = -EdgeSign(o1, d2, d1);
    if (z1 + z2 < 0) {
      z1 = -z1;
      z2 = -z2;
    }
    v->s = Interpolate(z1, o2->s, z2, d2->s);
  }

  if (!TransLeq(o1, d1)) {
    Swap(o1, d1);
  }
  if (!TransLeq(o2, d2)) {
    Swap(o2, d2);
  }
  if (!TransLeq(o1, o2)) {
    Swap(o1, o2);
    Swap(d1, d2);
  }

  if (!TransLeq(o2, d1)) {

    v->t = (o2->t + d1->t) / 2;
  } else if (TransLeq(d1, d2)) {

    z1 = TransEval(o1, o2, d1);
    z2 = TransEval(o2, d1, d2);
    if (z1 + z2 < 0) {
      z1 = -z1;
      z2 = -z2;
    }
    v->t = Interpolate(z1, o2->t, z2, d1->t);
  } else {

    z1 = TransSign(o1, o2, d1);
    z2 = -TransSign(o1, d2, d1);
    if (z1 + z2 < 0) {
      z1 = -z1;
      z2 = -z2;
    }
    v->t = Interpolate(z1, o2->t, z2, d2->t);
  }
}

TESSreal inCircle(TESSvertex *v, TESSvertex *v0, TESSvertex *v1,
                  TESSvertex *v2) {
  TESSreal adx, ady, bdx, bdy, cdx, cdy;
  TESSreal abdet, bcdet, cadet;
  TESSreal alift, blift, clift;

  adx = v0->s - v->s;
  ady = v0->t - v->t;
  bdx = v1->s - v->s;
  bdy = v1->t - v->t;
  cdx = v2->s - v->s;
  cdy = v2->t - v->t;

  abdet = adx * bdy - bdx * ady;
  bcdet = bdx * cdy - cdx * bdy;
  cadet = cdx * ady - adx * cdy;

  alift = adx * adx + ady * ady;
  blift = bdx * bdx + bdy * bdy;
  clift = cdx * cdx + cdy * cdy;

  return alift * bcdet + blift * cadet + clift * abdet;
}

int tesedgeIsLocallyDelaunay(TESShalfEdge *e) {
  return inCircle(e->Sym->Lnext->Lnext->Org, e->Lnext->Org,
                  e->Lnext->Lnext->Org, e->Org) < 0;
}

#ifdef FOR_TRITE_TEST_PROGRAM
extern void DebugEvent(TESStesselator *tess);
#else
#define DebugEvent(tess)
#endif

#define MAX(x, y) ((x) >= (y) ? (x) : (y))
#define MIN(x, y) ((x) <= (y) ? (x) : (y))

#define AddWinding(eDst, eSrc)                                                 \
  (eDst->winding += eSrc->winding, eDst->Sym->winding += eSrc->Sym->winding)

static void SweepEvent(TESStesselator *tess, TESSvertex *vEvent);
static void WalkDirtyRegions(TESStesselator *tess, ActiveRegion *regUp);
static int CheckForRightSplice(TESStesselator *tess, ActiveRegion *regUp);

static int EdgeLeq(TESStesselator *tess, ActiveRegion *reg1, ActiveRegion *reg2)

{
  TESSvertex *event = tess->event;
  TESShalfEdge *e1, *e2;
  TESSreal t1, t2;

  e1 = reg1->eUp;
  e2 = reg2->eUp;

  if (e1->Dst == event) {
    if (e2->Dst == event) {

      if (VertLeq(e1->Org, e2->Org)) {
        return EdgeSign(e2->Dst, e1->Org, e2->Org) <= 0;
      }
      return EdgeSign(e1->Dst, e2->Org, e1->Org) >= 0;
    }
    return EdgeSign(e2->Dst, event, e2->Org) <= 0;
  }
  if (e2->Dst == event) {
    return EdgeSign(e1->Dst, event, e1->Org) >= 0;
  }

  t1 = EdgeEval(e1->Dst, event, e1->Org);
  t2 = EdgeEval(e2->Dst, event, e2->Org);
  return (t1 >= t2);
}

static void DeleteRegion(TESStesselator *tess, ActiveRegion *reg) {
  if (reg->fixUpperEdge) {

    assert(reg->eUp->winding == 0);
  }
  reg->eUp->activeRegion = NULL;
  dictDelete(tess->dict, reg->nodeUp);
  bucketFree(tess->regionPool, reg);
}

static int FixUpperEdge(TESStesselator *tess, ActiveRegion *reg,
                        TESShalfEdge *newEdge)

{
  assert(reg->fixUpperEdge);
  if (!tessMeshDelete(tess->mesh, reg->eUp))
    return 0;
  reg->fixUpperEdge = FALSE;
  reg->eUp = newEdge;
  newEdge->activeRegion = reg;

  return 1;
}

static ActiveRegion *TopLeftRegion(TESStesselator *tess, ActiveRegion *reg) {
  TESSvertex *org = reg->eUp->Org;
  TESShalfEdge *e;

  do {
    reg = RegionAbove(reg);
  } while (reg->eUp->Org == org);

  if (reg->fixUpperEdge) {
    e = tessMeshConnect(tess->mesh, RegionBelow(reg)->eUp->Sym,
                        reg->eUp->Lnext);
    if (e == NULL)
      return NULL;
    if (!FixUpperEdge(tess, reg, e))
      return NULL;
    reg = RegionAbove(reg);
  }
  return reg;
}

static ActiveRegion *TopRightRegion(ActiveRegion *reg) {
  TESSvertex *dst = reg->eUp->Dst;

  do {
    reg = RegionAbove(reg);
  } while (reg->eUp->Dst == dst);
  return reg;
}

static ActiveRegion *AddRegionBelow(TESStesselator *tess,
                                    ActiveRegion *regAbove,
                                    TESShalfEdge *eNewUp)

{
  ActiveRegion *regNew = (ActiveRegion *)bucketAlloc(tess->regionPool);
  if (regNew == NULL)
    longjmp(tess->env, 1);

  regNew->eUp = eNewUp;
  regNew->nodeUp = dictInsertBefore(tess->dict, regAbove->nodeUp, regNew);
  if (regNew->nodeUp == NULL)
    longjmp(tess->env, 1);
  regNew->fixUpperEdge = FALSE;
  regNew->sentinel = FALSE;
  regNew->dirty = FALSE;

  eNewUp->activeRegion = regNew;
  return regNew;
}

static int IsWindingInside(TESStesselator *tess, int n) {
  switch (tess->windingRule) {
  case TESS_WINDING_ODD:
    return (n & 1);
  case TESS_WINDING_NONZERO:
    return (n != 0);
  case TESS_WINDING_POSITIVE:
    return (n > 0);
  case TESS_WINDING_NEGATIVE:
    return (n < 0);
  case TESS_WINDING_ABS_GEQ_TWO:
    return (n >= 2) || (n <= -2);
  }

  assert(FALSE);

  return (FALSE);
}

static void ComputeWinding(TESStesselator *tess, ActiveRegion *reg) {
  reg->windingNumber = RegionAbove(reg)->windingNumber + reg->eUp->winding;
  reg->inside = IsWindingInside(tess, reg->windingNumber);
}

static void FinishRegion(TESStesselator *tess, ActiveRegion *reg)

{
  TESShalfEdge *e = reg->eUp;
  TESSface *f = e->Lface;

  f->inside = reg->inside;
  f->anEdge = e;
  DeleteRegion(tess, reg);
}

static TESShalfEdge *FinishLeftRegions(TESStesselator *tess,
                                       ActiveRegion *regFirst,
                                       ActiveRegion *regLast)

{
  ActiveRegion *reg, *regPrev;
  TESShalfEdge *e, *ePrev;

  regPrev = regFirst;
  ePrev = regFirst->eUp;
  while (regPrev != regLast) {
    regPrev->fixUpperEdge = FALSE;
    reg = RegionBelow(regPrev);
    e = reg->eUp;
    if (e->Org != ePrev->Org) {
      if (!reg->fixUpperEdge) {

        FinishRegion(tess, regPrev);
        break;
      }

      e = tessMeshConnect(tess->mesh, ePrev->Lprev, e->Sym);
      if (e == NULL)
        longjmp(tess->env, 1);
      if (!FixUpperEdge(tess, reg, e))
        longjmp(tess->env, 1);
    }

    if (ePrev->Onext != e) {
      if (!tessMeshSplice(tess->mesh, e->Oprev, e))
        longjmp(tess->env, 1);
      if (!tessMeshSplice(tess->mesh, ePrev, e))
        longjmp(tess->env, 1);
    }
    FinishRegion(tess, regPrev);
    ePrev = reg->eUp;
    regPrev = reg;
  }
  return ePrev;
}

static void AddRightEdges(TESStesselator *tess, ActiveRegion *regUp,
                          TESShalfEdge *eFirst, TESShalfEdge *eLast,
                          TESShalfEdge *eTopLeft, int cleanUp)

{
  ActiveRegion *reg, *regPrev;
  TESShalfEdge *e, *ePrev;
  int firstTime = TRUE;

  e = eFirst;
  do {
    assert(VertLeq(e->Org, e->Dst));
    AddRegionBelow(tess, regUp, e->Sym);
    e = e->Onext;
  } while (e != eLast);

  if (eTopLeft == NULL) {
    eTopLeft = RegionBelow(regUp)->eUp->Rprev;
  }
  regPrev = regUp;
  ePrev = eTopLeft;
  for (;;) {
    reg = RegionBelow(regPrev);
    e = reg->eUp->Sym;
    if (e->Org != ePrev->Org)
      break;

    if (e->Onext != ePrev) {

      if (!tessMeshSplice(tess->mesh, e->Oprev, e))
        longjmp(tess->env, 1);
      if (!tessMeshSplice(tess->mesh, ePrev->Oprev, e))
        longjmp(tess->env, 1);
    }

    reg->windingNumber = regPrev->windingNumber - e->winding;
    reg->inside = IsWindingInside(tess, reg->windingNumber);

    regPrev->dirty = TRUE;
    if (!firstTime && CheckForRightSplice(tess, regPrev)) {
      AddWinding(e, ePrev);
      DeleteRegion(tess, regPrev);
      if (!tessMeshDelete(tess->mesh, ePrev))
        longjmp(tess->env, 1);
    }
    firstTime = FALSE;
    regPrev = reg;
    ePrev = e;
  }
  regPrev->dirty = TRUE;
  assert(regPrev->windingNumber - e->winding == reg->windingNumber);

  if (cleanUp) {

    WalkDirtyRegions(tess, regPrev);
  }
}

static void SpliceMergeVertices(TESStesselator *tess, TESShalfEdge *e1,
                                TESShalfEdge *e2)

{
  if (!tessMeshSplice(tess->mesh, e1, e2))
    longjmp(tess->env, 1);
}

static void VertexWeights(TESSvertex *isect, TESSvertex *org, TESSvertex *dst,
                          TESSreal *weights)

{
  TESSreal t1 = VertL1dist(org, isect);
  TESSreal t2 = VertL1dist(dst, isect);

  weights[0] = (TESSreal)0.5 * t2 / (t1 + t2);
  weights[1] = (TESSreal)0.5 * t1 / (t1 + t2);
  isect->coords[0] += weights[0] * org->coords[0] + weights[1] * dst->coords[0];
  isect->coords[1] += weights[0] * org->coords[1] + weights[1] * dst->coords[1];
  isect->coords[2] += weights[0] * org->coords[2] + weights[1] * dst->coords[2];
}

static void GetIntersectData(TESStesselator *tess, TESSvertex *isect,
                             TESSvertex *orgUp, TESSvertex *dstUp,
                             TESSvertex *orgLo, TESSvertex *dstLo)

{
  TESSreal weights[4];
  TESS_NOTUSED(tess);

  isect->coords[0] = isect->coords[1] = isect->coords[2] = 0;
  isect->idx = TESS_UNDEF;
  VertexWeights(isect, orgUp, dstUp, &weights[0]);
  VertexWeights(isect, orgLo, dstLo, &weights[2]);
}

static int CheckForRightSplice(TESStesselator *tess, ActiveRegion *regUp)

{
  ActiveRegion *regLo = RegionBelow(regUp);
  TESShalfEdge *eUp = regUp->eUp;
  TESShalfEdge *eLo = regLo->eUp;

  if (VertLeq(eUp->Org, eLo->Org)) {
    if (EdgeSign(eLo->Dst, eUp->Org, eLo->Org) > 0)
      return FALSE;

    if (!VertEq(eUp->Org, eLo->Org)) {

      if (tessMeshSplitEdge(tess->mesh, eLo->Sym) == NULL)
        longjmp(tess->env, 1);
      if (!tessMeshSplice(tess->mesh, eUp, eLo->Oprev))
        longjmp(tess->env, 1);
      regUp->dirty = regLo->dirty = TRUE;

    } else if (eUp->Org != eLo->Org) {

      pqDelete(tess->pq, eUp->Org->pqHandle);
      SpliceMergeVertices(tess, eLo->Oprev, eUp);
    }
  } else {
    if (EdgeSign(eUp->Dst, eLo->Org, eUp->Org) <= 0)
      return FALSE;

    RegionAbove(regUp)->dirty = regUp->dirty = TRUE;
    if (tessMeshSplitEdge(tess->mesh, eUp->Sym) == NULL)
      longjmp(tess->env, 1);
    if (!tessMeshSplice(tess->mesh, eLo->Oprev, eUp))
      longjmp(tess->env, 1);
  }
  return TRUE;
}

static int CheckForLeftSplice(TESStesselator *tess, ActiveRegion *regUp)

{
  ActiveRegion *regLo = RegionBelow(regUp);
  TESShalfEdge *eUp = regUp->eUp;
  TESShalfEdge *eLo = regLo->eUp;
  TESShalfEdge *e;

  assert(!VertEq(eUp->Dst, eLo->Dst));

  if (VertLeq(eUp->Dst, eLo->Dst)) {
    if (EdgeSign(eUp->Dst, eLo->Dst, eUp->Org) < 0)
      return FALSE;

    RegionAbove(regUp)->dirty = regUp->dirty = TRUE;
    e = tessMeshSplitEdge(tess->mesh, eUp);
    if (e == NULL)
      longjmp(tess->env, 1);
    if (!tessMeshSplice(tess->mesh, eLo->Sym, e))
      longjmp(tess->env, 1);
    e->Lface->inside = regUp->inside;
  } else {
    if (EdgeSign(eLo->Dst, eUp->Dst, eLo->Org) > 0)
      return FALSE;

    regUp->dirty = regLo->dirty = TRUE;
    e = tessMeshSplitEdge(tess->mesh, eLo);
    if (e == NULL)
      longjmp(tess->env, 1);
    if (!tessMeshSplice(tess->mesh, eUp->Lnext, eLo->Sym))
      longjmp(tess->env, 1);
    e->Rface->inside = regUp->inside;
  }
  return TRUE;
}

static int CheckForIntersect(TESStesselator *tess, ActiveRegion *regUp)

{
  ActiveRegion *regLo = RegionBelow(regUp);
  TESShalfEdge *eUp = regUp->eUp;
  TESShalfEdge *eLo = regLo->eUp;
  TESSvertex *orgUp = eUp->Org;
  TESSvertex *orgLo = eLo->Org;
  TESSvertex *dstUp = eUp->Dst;
  TESSvertex *dstLo = eLo->Dst;
  TESSreal tMinUp, tMaxLo;
  TESSvertex isect, *orgMin;
  TESShalfEdge *e;

  assert(!VertEq(dstLo, dstUp));
  assert(EdgeSign(dstUp, tess->event, orgUp) <= 0);
  assert(EdgeSign(dstLo, tess->event, orgLo) >= 0);
  assert(orgUp != tess->event && orgLo != tess->event);
  assert(!regUp->fixUpperEdge && !regLo->fixUpperEdge);

  if (orgUp == orgLo)
    return FALSE;

  tMinUp = MIN(orgUp->t, dstUp->t);
  tMaxLo = MAX(orgLo->t, dstLo->t);
  if (tMinUp > tMaxLo)
    return FALSE;

  if (VertLeq(orgUp, orgLo)) {
    if (EdgeSign(dstLo, orgUp, orgLo) > 0)
      return FALSE;
  } else {
    if (EdgeSign(dstUp, orgLo, orgUp) < 0)
      return FALSE;
  }

  DebugEvent(tess);

  tesedgeIntersect(dstUp, orgUp, dstLo, orgLo, &isect);

  assert(MIN(orgUp->t, dstUp->t) <= isect.t);
  assert(isect.t <= MAX(orgLo->t, dstLo->t));
  assert(MIN(dstLo->s, dstUp->s) <= isect.s);
  assert(isect.s <= MAX(orgLo->s, orgUp->s));

  if (VertLeq(&isect, tess->event)) {

    isect.s = tess->event->s;
    isect.t = tess->event->t;
  }

  orgMin = VertLeq(orgUp, orgLo) ? orgUp : orgLo;
  if (VertLeq(orgMin, &isect)) {
    isect.s = orgMin->s;
    isect.t = orgMin->t;
  }

  if (VertEq(&isect, orgUp) || VertEq(&isect, orgLo)) {

    (void)CheckForRightSplice(tess, regUp);
    return FALSE;
  }

  if ((!VertEq(dstUp, tess->event) &&
       EdgeSign(dstUp, tess->event, &isect) >= 0) ||
      (!VertEq(dstLo, tess->event) &&
       EdgeSign(dstLo, tess->event, &isect) <= 0)) {

    if (dstLo == tess->event) {

      if (tessMeshSplitEdge(tess->mesh, eUp->Sym) == NULL)
        longjmp(tess->env, 1);
      if (!tessMeshSplice(tess->mesh, eLo->Sym, eUp))
        longjmp(tess->env, 1);
      regUp = TopLeftRegion(tess, regUp);
      if (regUp == NULL)
        longjmp(tess->env, 1);
      eUp = RegionBelow(regUp)->eUp;
      FinishLeftRegions(tess, RegionBelow(regUp), regLo);
      AddRightEdges(tess, regUp, eUp->Oprev, eUp, eUp, TRUE);
      return TRUE;
    }
    if (dstUp == tess->event) {

      if (tessMeshSplitEdge(tess->mesh, eLo->Sym) == NULL)
        longjmp(tess->env, 1);
      if (!tessMeshSplice(tess->mesh, eUp->Lnext, eLo->Oprev))
        longjmp(tess->env, 1);
      regLo = regUp;
      regUp = TopRightRegion(regUp);
      e = RegionBelow(regUp)->eUp->Rprev;
      regLo->eUp = eLo->Oprev;
      eLo = FinishLeftRegions(tess, regLo, NULL);
      AddRightEdges(tess, regUp, eLo->Onext, eUp->Rprev, e, TRUE);
      return TRUE;
    }

    if (EdgeSign(dstUp, tess->event, &isect) >= 0) {
      RegionAbove(regUp)->dirty = regUp->dirty = TRUE;
      if (tessMeshSplitEdge(tess->mesh, eUp->Sym) == NULL)
        longjmp(tess->env, 1);
      eUp->Org->s = tess->event->s;
      eUp->Org->t = tess->event->t;
    }
    if (EdgeSign(dstLo, tess->event, &isect) <= 0) {
      regUp->dirty = regLo->dirty = TRUE;
      if (tessMeshSplitEdge(tess->mesh, eLo->Sym) == NULL)
        longjmp(tess->env, 1);
      eLo->Org->s = tess->event->s;
      eLo->Org->t = tess->event->t;
    }

    return FALSE;
  }

  if (tessMeshSplitEdge(tess->mesh, eUp->Sym) == NULL)
    longjmp(tess->env, 1);
  if (tessMeshSplitEdge(tess->mesh, eLo->Sym) == NULL)
    longjmp(tess->env, 1);
  if (!tessMeshSplice(tess->mesh, eLo->Oprev, eUp))
    longjmp(tess->env, 1);
  eUp->Org->s = isect.s;
  eUp->Org->t = isect.t;
  eUp->Org->pqHandle = pqInsert(&tess->alloc, tess->pq, eUp->Org);
  if (eUp->Org->pqHandle == INV_HANDLE) {
    pqDeletePriorityQ(&tess->alloc, tess->pq);
    tess->pq = NULL;
    longjmp(tess->env, 1);
  }
  GetIntersectData(tess, eUp->Org, orgUp, dstUp, orgLo, dstLo);
  RegionAbove(regUp)->dirty = regUp->dirty = regLo->dirty = TRUE;
  return FALSE;
}

static void WalkDirtyRegions(TESStesselator *tess, ActiveRegion *regUp)

{
  ActiveRegion *regLo = RegionBelow(regUp);
  TESShalfEdge *eUp, *eLo;

  for (;;) {

    while (regLo->dirty) {
      regUp = regLo;
      regLo = RegionBelow(regLo);
    }
    if (!regUp->dirty) {
      regLo = regUp;
      regUp = RegionAbove(regUp);
      if (regUp == NULL || !regUp->dirty) {

        return;
      }
    }
    regUp->dirty = FALSE;
    eUp = regUp->eUp;
    eLo = regLo->eUp;

    if (eUp->Dst != eLo->Dst) {

      if (CheckForLeftSplice(tess, regUp)) {

        if (regLo->fixUpperEdge) {
          DeleteRegion(tess, regLo);
          if (!tessMeshDelete(tess->mesh, eLo))
            longjmp(tess->env, 1);
          regLo = RegionBelow(regUp);
          eLo = regLo->eUp;
        } else if (regUp->fixUpperEdge) {
          DeleteRegion(tess, regUp);
          if (!tessMeshDelete(tess->mesh, eUp))
            longjmp(tess->env, 1);
          regUp = RegionAbove(regLo);
          eUp = regUp->eUp;
        }
      }
    }
    if (eUp->Org != eLo->Org) {
      if (eUp->Dst != eLo->Dst && !regUp->fixUpperEdge &&
          !regLo->fixUpperEdge &&
          (eUp->Dst == tess->event || eLo->Dst == tess->event)) {

        if (CheckForIntersect(tess, regUp)) {

          return;
        }
      } else {

        (void)CheckForRightSplice(tess, regUp);
      }
    }
    if (eUp->Org == eLo->Org && eUp->Dst == eLo->Dst) {

      AddWinding(eLo, eUp);
      DeleteRegion(tess, regUp);
      if (!tessMeshDelete(tess->mesh, eUp))
        longjmp(tess->env, 1);
      regUp = RegionAbove(regLo);
    }
  }
}

static void ConnectRightVertex(TESStesselator *tess, ActiveRegion *regUp,
                               TESShalfEdge *eBottomLeft)

{
  TESShalfEdge *eNew;
  TESShalfEdge *eTopLeft = eBottomLeft->Onext;
  ActiveRegion *regLo = RegionBelow(regUp);
  TESShalfEdge *eUp = regUp->eUp;
  TESShalfEdge *eLo = regLo->eUp;
  int degenerate = FALSE;

  if (eUp->Dst != eLo->Dst) {
    (void)CheckForIntersect(tess, regUp);
  }

  if (VertEq(eUp->Org, tess->event)) {
    if (!tessMeshSplice(tess->mesh, eTopLeft->Oprev, eUp))
      longjmp(tess->env, 1);
    regUp = TopLeftRegion(tess, regUp);
    if (regUp == NULL)
      longjmp(tess->env, 1);
    eTopLeft = RegionBelow(regUp)->eUp;
    FinishLeftRegions(tess, RegionBelow(regUp), regLo);
    degenerate = TRUE;
  }
  if (VertEq(eLo->Org, tess->event)) {
    if (!tessMeshSplice(tess->mesh, eBottomLeft, eLo->Oprev))
      longjmp(tess->env, 1);
    eBottomLeft = FinishLeftRegions(tess, regLo, NULL);
    degenerate = TRUE;
  }
  if (degenerate) {
    AddRightEdges(tess, regUp, eBottomLeft->Onext, eTopLeft, eTopLeft, TRUE);
    return;
  }

  if (VertLeq(eLo->Org, eUp->Org)) {
    eNew = eLo->Oprev;
  } else {
    eNew = eUp;
  }
  eNew = tessMeshConnect(tess->mesh, eBottomLeft->Lprev, eNew);
  if (eNew == NULL)
    longjmp(tess->env, 1);

  AddRightEdges(tess, regUp, eNew, eNew->Onext, eNew->Onext, FALSE);
  eNew->Sym->activeRegion->fixUpperEdge = TRUE;
  WalkDirtyRegions(tess, regUp);
}

#define TOLERANCE_NONZERO FALSE

static void ConnectLeftDegenerate(TESStesselator *tess, ActiveRegion *regUp,
                                  TESSvertex *vEvent)

{
  TESShalfEdge *e, *eTopLeft, *eTopRight, *eLast;
  ActiveRegion *reg;

  e = regUp->eUp;
  if (VertEq(e->Org, vEvent)) {

    assert(TOLERANCE_NONZERO);
    SpliceMergeVertices(tess, e, vEvent->anEdge);
    return;
  }

  if (!VertEq(e->Dst, vEvent)) {

    if (tessMeshSplitEdge(tess->mesh, e->Sym) == NULL)
      longjmp(tess->env, 1);
    if (regUp->fixUpperEdge) {

      if (!tessMeshDelete(tess->mesh, e->Onext))
        longjmp(tess->env, 1);
      regUp->fixUpperEdge = FALSE;
    }
    if (!tessMeshSplice(tess->mesh, vEvent->anEdge, e))
      longjmp(tess->env, 1);
    SweepEvent(tess, vEvent);
    return;
  }

  assert(TOLERANCE_NONZERO);
  regUp = TopRightRegion(regUp);
  reg = RegionBelow(regUp);
  eTopRight = reg->eUp->Sym;
  eTopLeft = eLast = eTopRight->Onext;
  if (reg->fixUpperEdge) {

    assert(eTopLeft != eTopRight);
    DeleteRegion(tess, reg);
    if (!tessMeshDelete(tess->mesh, eTopRight))
      longjmp(tess->env, 1);
    eTopRight = eTopLeft->Oprev;
  }
  if (!tessMeshSplice(tess->mesh, vEvent->anEdge, eTopRight))
    longjmp(tess->env, 1);
  if (!EdgeGoesLeft(eTopLeft)) {

    eTopLeft = NULL;
  }
  AddRightEdges(tess, regUp, eTopRight->Onext, eLast, eTopLeft, TRUE);
}

static void ConnectLeftVertex(TESStesselator *tess, TESSvertex *vEvent)

{
  ActiveRegion *regUp, *regLo, *reg;
  TESShalfEdge *eUp, *eLo, *eNew;
  ActiveRegion tmp;

  tmp.eUp = vEvent->anEdge->Sym;

  regUp = (ActiveRegion *)dictKey(dictSearch(tess->dict, &tmp));
  regLo = RegionBelow(regUp);
  if (!regLo) {

    return;
  }
  eUp = regUp->eUp;
  eLo = regLo->eUp;

  if (EdgeSign(eUp->Dst, vEvent, eUp->Org) == 0) {
    ConnectLeftDegenerate(tess, regUp, vEvent);
    return;
  }

  reg = VertLeq(eLo->Dst, eUp->Dst) ? regUp : regLo;

  if (regUp->inside || reg->fixUpperEdge) {
    if (reg == regUp) {
      eNew = tessMeshConnect(tess->mesh, vEvent->anEdge->Sym, eUp->Lnext);
      if (eNew == NULL)
        longjmp(tess->env, 1);
    } else {
      TESShalfEdge *tempHalfEdge =
          tessMeshConnect(tess->mesh, eLo->Dnext, vEvent->anEdge);
      if (tempHalfEdge == NULL)
        longjmp(tess->env, 1);

      eNew = tempHalfEdge->Sym;
    }
    if (reg->fixUpperEdge) {
      if (!FixUpperEdge(tess, reg, eNew))
        longjmp(tess->env, 1);
    } else {
      ComputeWinding(tess, AddRegionBelow(tess, regUp, eNew));
    }
    SweepEvent(tess, vEvent);
  } else {

    AddRightEdges(tess, regUp, vEvent->anEdge, vEvent->anEdge, NULL, TRUE);
  }
}

static void SweepEvent(TESStesselator *tess, TESSvertex *vEvent)

{
  ActiveRegion *regUp, *reg;
  TESShalfEdge *e, *eTopLeft, *eBottomLeft;

  tess->event = vEvent;
  DebugEvent(tess);

  e = vEvent->anEdge;
  while (e->activeRegion == NULL) {
    e = e->Onext;
    if (e == vEvent->anEdge) {

      ConnectLeftVertex(tess, vEvent);
      return;
    }
  }

  regUp = TopLeftRegion(tess, e->activeRegion);
  if (regUp == NULL)
    longjmp(tess->env, 1);
  reg = RegionBelow(regUp);
  eTopLeft = reg->eUp;
  eBottomLeft = FinishLeftRegions(tess, reg, NULL);

  if (eBottomLeft->Onext == eTopLeft) {

    ConnectRightVertex(tess, regUp, eBottomLeft);
  } else {
    AddRightEdges(tess, regUp, eBottomLeft->Onext, eTopLeft, eTopLeft, TRUE);
  }
}

static void AddSentinel(TESStesselator *tess, TESSreal smin, TESSreal smax,
                        TESSreal t)

{
  TESShalfEdge *e;
  ActiveRegion *reg = (ActiveRegion *)bucketAlloc(tess->regionPool);
  if (reg == NULL)
    longjmp(tess->env, 1);

  e = tessMeshMakeEdge(tess->mesh);
  if (e == NULL)
    longjmp(tess->env, 1);

  e->Org->s = smax;
  e->Org->t = t;
  e->Dst->s = smin;
  e->Dst->t = t;
  tess->event = e->Dst;

  reg->eUp = e;
  reg->windingNumber = 0;
  reg->inside = FALSE;
  reg->fixUpperEdge = FALSE;
  reg->sentinel = TRUE;
  reg->dirty = FALSE;
  reg->nodeUp = dictInsert(tess->dict, reg);
  if (reg->nodeUp == NULL)
    longjmp(tess->env, 1);
}

static void InitEdgeDict(TESStesselator *tess)

{
  TESSreal w, h;
  TESSreal smin, smax, tmin, tmax;

  tess->dict = dictNewDict(&tess->alloc, tess,
                           (int (*)(void *, DictKey, DictKey))EdgeLeq);
  if (tess->dict == NULL)
    longjmp(tess->env, 1);

  w = (tess->bmax[0] - tess->bmin[0]) + (TESSreal)0.01;
  h = (tess->bmax[1] - tess->bmin[1]) + (TESSreal)0.01;

  smin = tess->bmin[0] - w;
  smax = tess->bmax[0] + w;
  tmin = tess->bmin[1] - h;
  tmax = tess->bmax[1] + h;

  AddSentinel(tess, smin, smax, tmin);
  AddSentinel(tess, smin, smax, tmax);
}

static void DoneEdgeDict(TESStesselator *tess) {
  ActiveRegion *reg;
  int fixedEdges = 0;

  while ((reg = (ActiveRegion *)dictKey(dictMin(tess->dict))) != NULL) {

    if (!reg->sentinel) {
      assert(reg->fixUpperEdge);
      assert(++fixedEdges == 1);
    }
    assert(reg->windingNumber == 0);
    DeleteRegion(tess, reg);
  }
  dictDeleteDict(&tess->alloc, tess->dict);
}

static void RemoveDegenerateEdges(TESStesselator *tess)

{
  TESShalfEdge *e, *eNext, *eLnext;
  TESShalfEdge *eHead = &tess->mesh->eHead;

  for (e = eHead->next; e != eHead; e = eNext) {
    eNext = e->next;
    eLnext = e->Lnext;

    if (VertEq(e->Org, e->Dst) && e->Lnext->Lnext != e) {

      SpliceMergeVertices(tess, eLnext, e);
      if (!tessMeshDelete(tess->mesh, e))
        longjmp(tess->env, 1);
      e = eLnext;
      eLnext = e->Lnext;
    }
    if (eLnext->Lnext == e) {

      if (eLnext != e) {
        if (eLnext == eNext || eLnext == eNext->Sym) {
          eNext = eNext->next;
        }
        if (!tessMeshDelete(tess->mesh, eLnext))
          longjmp(tess->env, 1);
      }
      if (e == eNext || e == eNext->Sym) {
        eNext = eNext->next;
      }
      if (!tessMeshDelete(tess->mesh, e))
        longjmp(tess->env, 1);
    }
  }
}

static int InitPriorityQ(TESStesselator *tess)

{
  PriorityQ *pq;
  TESSvertex *v, *vHead;
  int vertexCount = 0;

  vHead = &tess->mesh->vHead;
  for (v = vHead->next; v != vHead; v = v->next) {
    vertexCount++;
  }

  vertexCount += MAX(8, tess->alloc.extraVertices);

  pq = tess->pq = pqNewPriorityQ(&tess->alloc, vertexCount,
                                 (int (*)(PQkey, PQkey))tesvertLeq);
  if (pq == NULL)
    return 0;

  vHead = &tess->mesh->vHead;
  for (v = vHead->next; v != vHead; v = v->next) {
    v->pqHandle = pqInsert(&tess->alloc, pq, v);
    if (v->pqHandle == INV_HANDLE)
      break;
  }
  if (v != vHead || !pqInit(&tess->alloc, pq)) {
    pqDeletePriorityQ(&tess->alloc, tess->pq);
    tess->pq = NULL;
    return 0;
  }

  return 1;
}

static void DonePriorityQ(TESStesselator *tess) {
  pqDeletePriorityQ(&tess->alloc, tess->pq);
}

static int RemoveDegenerateFaces(TESStesselator *tess, TESSmesh *mesh)

{
  TESSface *f, *fNext;
  TESShalfEdge *e;

  for (f = mesh->fHead.next; f != &mesh->fHead; f = fNext) {
    fNext = f->next;
    e = f->anEdge;
    assert(e->Lnext != e);

    if (e->Lnext->Lnext == e) {

      AddWinding(e->Onext, e);
      if (!tessMeshDelete(tess->mesh, e))
        return 0;
    }
  }
  return 1;
}

int tessComputeInterior(TESStesselator *tess)

{
  TESSvertex *v, *vNext;

  RemoveDegenerateEdges(tess);
  if (!InitPriorityQ(tess))
    return 0;
  InitEdgeDict(tess);

  while ((v = (TESSvertex *)pqExtractMin(tess->pq)) != NULL) {
    for (;;) {
      vNext = (TESSvertex *)pqMinimum(tess->pq);
      if (vNext == NULL || !VertEq(vNext, v))
        break;

      vNext = (TESSvertex *)pqExtractMin(tess->pq);
      SpliceMergeVertices(tess, v->anEdge, vNext->anEdge);
    }
    SweepEvent(tess, v);
  }

  tess->event = ((ActiveRegion *)dictKey(dictMin(tess->dict)))->eUp->Org;
  DebugEvent(tess);
  DoneEdgeDict(tess);
  DonePriorityQ(tess);

  if (!RemoveDegenerateFaces(tess, tess->mesh))
    return 0;
  tessMeshCheckMesh(tess->mesh);

  return 1;
}

#define Dot(u, v) (u[0] * v[0] + u[1] * v[1] + u[2] * v[2])

#if defined(FOR_TRITE_TEST_PROGRAM) || defined(TRUE_PROJECT)
static void Normalize(TESSreal v[3]) {
  TESSreal len = v[0] * v[0] + v[1] * v[1] + v[2] * v[2];

  assert(len > 0);
  len = sqrtf(len);
  v[0] /= len;
  v[1] /= len;
  v[2] /= len;
}
#endif

#define ABS(x) ((x) < 0 ? -(x) : (x))

static int LongAxis(TESSreal v[3]) {
  int i = 0;

  if (ABS(v[1]) > ABS(v[0])) {
    i = 1;
  }
  if (ABS(v[2]) > ABS(v[i])) {
    i = 2;
  }
  return i;
}

static int ShortAxis(TESSreal v[3]) {
  int i = 0;

  if (ABS(v[1]) < ABS(v[0])) {
    i = 1;
  }
  if (ABS(v[2]) < ABS(v[i])) {
    i = 2;
  }
  return i;
}

static void ComputeNormal(TESStesselator *tess, TESSreal norm[3]) {
  TESSvertex *v, *v1, *v2;
  TESSreal c, tLen2, maxLen2;
  TESSreal maxVal[3], minVal[3], d1[3], d2[3], tNorm[3];
  TESSvertex *maxVert[3], *minVert[3];
  TESSvertex *vHead = &tess->mesh->vHead;
  int i;

  v = vHead->next;
  for (i = 0; i < 3; ++i) {
    c = v->coords[i];
    minVal[i] = c;
    minVert[i] = v;
    maxVal[i] = c;
    maxVert[i] = v;
  }

  for (v = vHead->next; v != vHead; v = v->next) {
    for (i = 0; i < 3; ++i) {
      c = v->coords[i];
      if (c < minVal[i]) {
        minVal[i] = c;
        minVert[i] = v;
      }
      if (c > maxVal[i]) {
        maxVal[i] = c;
        maxVert[i] = v;
      }
    }
  }

  i = 0;
  if (maxVal[1] - minVal[1] > maxVal[0] - minVal[0]) {
    i = 1;
  }
  if (maxVal[2] - minVal[2] > maxVal[i] - minVal[i]) {
    i = 2;
  }
  if (minVal[i] >= maxVal[i]) {

    norm[0] = 0;
    norm[1] = 0;
    norm[2] = 1;
    return;
  }

  maxLen2 = 0;
  v1 = minVert[i];
  v2 = maxVert[i];
  d1[0] = v1->coords[0] - v2->coords[0];
  d1[1] = v1->coords[1] - v2->coords[1];
  d1[2] = v1->coords[2] - v2->coords[2];
  for (v = vHead->next; v != vHead; v = v->next) {
    d2[0] = v->coords[0] - v2->coords[0];
    d2[1] = v->coords[1] - v2->coords[1];
    d2[2] = v->coords[2] - v2->coords[2];
    tNorm[0] = d1[1] * d2[2] - d1[2] * d2[1];
    tNorm[1] = d1[2] * d2[0] - d1[0] * d2[2];
    tNorm[2] = d1[0] * d2[1] - d1[1] * d2[0];
    tLen2 = tNorm[0] * tNorm[0] + tNorm[1] * tNorm[1] + tNorm[2] * tNorm[2];
    if (tLen2 > maxLen2) {
      maxLen2 = tLen2;
      norm[0] = tNorm[0];
      norm[1] = tNorm[1];
      norm[2] = tNorm[2];
    }
  }

  if (maxLen2 <= 0) {

    norm[0] = norm[1] = norm[2] = 0;
    norm[ShortAxis(d1)] = 1;
  }
}

static void CheckOrientation(TESStesselator *tess) {
  TESSreal area;
  TESSface *f, *fHead = &tess->mesh->fHead;
  TESSvertex *v, *vHead = &tess->mesh->vHead;
  TESShalfEdge *e;

  area = 0;
  for (f = fHead->next; f != fHead; f = f->next) {
    e = f->anEdge;
    if (e->winding <= 0)
      continue;
    do {
      area += (e->Org->s - e->Dst->s) * (e->Org->t + e->Dst->t);
      e = e->Lnext;
    } while (e != f->anEdge);
  }
  if (area < 0) {

    for (v = vHead->next; v != vHead; v = v->next) {
      v->t = -v->t;
    }
    tess->tUnit[0] = -tess->tUnit[0];
    tess->tUnit[1] = -tess->tUnit[1];
    tess->tUnit[2] = -tess->tUnit[2];
  }
}

#ifdef FOR_TRITE_TEST_PROGRAM
extern int RandomSweep;
#define S_UNIT_X (RandomSweep ? (2 * drand48() - 1) : 1.0)
#define S_UNIT_Y (RandomSweep ? (2 * drand48() - 1) : 0.0)
#else
#if defined(SLANTED_SWEEP)

#define S_UNIT_X (TESSreal)0.50941539564955385
#define S_UNIT_Y (TESSreal)0.86052074622010633
#else
#define S_UNIT_X (TESSreal)1.0
#define S_UNIT_Y (TESSreal)0.0
#endif
#endif

void tessProjectPolygon(TESStesselator *tess) {
  TESSvertex *v, *vHead = &tess->mesh->vHead;
  TESSreal norm[3];
  TESSreal *sUnit, *tUnit;
  int i, first, computedNormal = FALSE;

  norm[0] = tess->normal[0];
  norm[1] = tess->normal[1];
  norm[2] = tess->normal[2];
  if (norm[0] == 0 && norm[1] == 0 && norm[2] == 0) {
    ComputeNormal(tess, norm);
    computedNormal = TRUE;
  }
  sUnit = tess->sUnit;
  tUnit = tess->tUnit;
  i = LongAxis(norm);

#if defined(FOR_TRITE_TEST_PROGRAM) || defined(TRUE_PROJECT)

  Normalize(norm);

  sUnit[i] = 0;
  sUnit[(i + 1) % 3] = S_UNIT_X;
  sUnit[(i + 2) % 3] = S_UNIT_Y;

  w = Dot(sUnit, norm);
  sUnit[0] -= w * norm[0];
  sUnit[1] -= w * norm[1];
  sUnit[2] -= w * norm[2];
  Normalize(sUnit);

  tUnit[0] = norm[1] * sUnit[2] - norm[2] * sUnit[1];
  tUnit[1] = norm[2] * sUnit[0] - norm[0] * sUnit[2];
  tUnit[2] = norm[0] * sUnit[1] - norm[1] * sUnit[0];
  Normalize(tUnit);
#else

  sUnit[i] = 0;
  sUnit[(i + 1) % 3] = S_UNIT_X;
  sUnit[(i + 2) % 3] = S_UNIT_Y;

  tUnit[i] = 0;
  tUnit[(i + 1) % 3] = (norm[i] > 0) ? -S_UNIT_Y : S_UNIT_Y;
  tUnit[(i + 2) % 3] = (norm[i] > 0) ? S_UNIT_X : -S_UNIT_X;
#endif

  for (v = vHead->next; v != vHead; v = v->next) {
    v->s = Dot(v->coords, sUnit);
    v->t = Dot(v->coords, tUnit);
  }
  if (computedNormal) {
    CheckOrientation(tess);
  }

  first = 1;
  for (v = vHead->next; v != vHead; v = v->next) {
    if (first) {
      tess->bmin[0] = tess->bmax[0] = v->s;
      tess->bmin[1] = tess->bmax[1] = v->t;
      first = 0;
    } else {
      if (v->s < tess->bmin[0])
        tess->bmin[0] = v->s;
      if (v->s > tess->bmax[0])
        tess->bmax[0] = v->s;
      if (v->t < tess->bmin[1])
        tess->bmin[1] = v->t;
      if (v->t > tess->bmax[1])
        tess->bmax[1] = v->t;
    }
  }
}

#define AddWinding(eDst, eSrc)                                                 \
  (eDst->winding += eSrc->winding, eDst->Sym->winding += eSrc->Sym->winding)

int tessMeshTessellateMonoRegion(TESSmesh *mesh, TESSface *face) {
  TESShalfEdge *up, *lo;

  up = face->anEdge;
  assert(up->Lnext != up && up->Lnext->Lnext != up);

  for (; VertLeq(up->Dst, up->Org); up = up->Lprev)
    ;
  for (; VertLeq(up->Org, up->Dst); up = up->Lnext)
    ;
  lo = up->Lprev;

  while (up->Lnext != lo) {
    if (VertLeq(up->Dst, lo->Org)) {

      while (lo->Lnext != up &&
             (EdgeGoesLeft(lo->Lnext) ||
              EdgeSign(lo->Org, lo->Dst, lo->Lnext->Dst) <= 0)) {
        TESShalfEdge *tempHalfEdge = tessMeshConnect(mesh, lo->Lnext, lo);
        if (tempHalfEdge == NULL)
          return 0;
        lo = tempHalfEdge->Sym;
      }
      lo = lo->Lprev;
    } else {

      while (lo->Lnext != up &&
             (EdgeGoesRight(up->Lprev) ||
              EdgeSign(up->Dst, up->Org, up->Lprev->Org) >= 0)) {
        TESShalfEdge *tempHalfEdge = tessMeshConnect(mesh, up, up->Lprev);
        if (tempHalfEdge == NULL)
          return 0;
        up = tempHalfEdge->Sym;
      }
      up = up->Lnext;
    }
  }

  assert(lo->Lnext != up);
  while (lo->Lnext->Lnext != up) {
    TESShalfEdge *tempHalfEdge = tessMeshConnect(mesh, lo->Lnext, lo);
    if (tempHalfEdge == NULL)
      return 0;
    lo = tempHalfEdge->Sym;
  }

  return 1;
}

int tessMeshTessellateInterior(TESSmesh *mesh) {
  TESSface *f, *next;

  for (f = mesh->fHead.next; f != &mesh->fHead; f = next) {

    next = f->next;
    if (f->inside) {
      if (!tessMeshTessellateMonoRegion(mesh, f))
        return 0;
    }
  }
  return 1;
}

typedef struct EdgeStackNode EdgeStackNode;
typedef struct EdgeStack EdgeStack;

struct EdgeStackNode {
  TESShalfEdge *edge;
  EdgeStackNode *next;
};

struct EdgeStack {
  EdgeStackNode *top;
  struct BucketAlloc *nodeBucket;
};

int stackInit(EdgeStack *stack, TESSalloc *alloc) {
  stack->top = NULL;
  stack->nodeBucket =
      createBucketAlloc(alloc, "CDT nodes", sizeof(EdgeStackNode), 512);
  return stack->nodeBucket != NULL;
}

void stackDelete(EdgeStack *stack) { deleteBucketAlloc(stack->nodeBucket); }

int stackEmpty(EdgeStack *stack) { return stack->top == NULL; }

void stackPush(EdgeStack *stack, TESShalfEdge *e) {
  EdgeStackNode *node = (EdgeStackNode *)bucketAlloc(stack->nodeBucket);
  if (!node)
    return;
  node->edge = e;
  node->next = stack->top;
  stack->top = node;
}

TESShalfEdge *stackPop(EdgeStack *stack) {
  TESShalfEdge *e = NULL;
  EdgeStackNode *node = stack->top;
  if (node) {
    stack->top = node->next;
    e = node->edge;
    bucketFree(stack->nodeBucket, node);
  }
  return e;
}

void tessMeshRefineDelaunay(TESSmesh *mesh, TESSalloc *alloc) {

  TESSface *f;
  EdgeStack stack;
  TESShalfEdge *e;
  int maxFaces = 0, maxIter = 0, iter = 0;

  stackInit(&stack, alloc);

  for (f = mesh->fHead.next; f != &mesh->fHead; f = f->next) {
    if (f->inside) {
      e = f->anEdge;
      do {
        e->mark = EdgeIsInternal(e);
        if (e->mark && !e->Sym->mark)
          stackPush(&stack, e);
        e = e->Lnext;
      } while (e != f->anEdge);
      maxFaces++;
    }
  }

  maxIter = maxFaces * maxFaces;

  while (!stackEmpty(&stack) && iter < maxIter) {
    e = stackPop(&stack);
    e->mark = e->Sym->mark = 0;
    if (!tesedgeIsLocallyDelaunay(e)) {
      TESShalfEdge *edges[4];
      int i;
      tessMeshFlipEdge(mesh, e);

      edges[0] = e->Lnext;
      edges[1] = e->Lprev;
      edges[2] = e->Sym->Lnext;
      edges[3] = e->Sym->Lprev;
      for (i = 0; i < 4; i++) {
        if (!edges[i]->mark && EdgeIsInternal(edges[i])) {
          edges[i]->mark = edges[i]->Sym->mark = 1;
          stackPush(&stack, edges[i]);
        }
      }
    }
    iter++;
  }

  stackDelete(&stack);
}

void tessMeshDiscardExterior(TESSmesh *mesh) {
  TESSface *f, *next;

  for (f = mesh->fHead.next; f != &mesh->fHead; f = next) {

    next = f->next;
    if (!f->inside) {
      tessMeshZapFace(mesh, f);
    }
  }
}

int tessMeshSetWindingNumber(TESSmesh *mesh, int value, int keepOnlyBoundary) {
  TESShalfEdge *e, *eNext;

  for (e = mesh->eHead.next; e != &mesh->eHead; e = eNext) {
    eNext = e->next;
    if (e->Rface->inside != e->Lface->inside) {

      e->winding = (e->Lface->inside) ? value : -value;
    } else {

      if (!keepOnlyBoundary) {
        e->winding = 0;
      } else {
        if (!tessMeshDelete(mesh, e))
          return 0;
      }
    }
  }
  return 1;
}

void *heapAlloc(void *userData, unsigned int size) {
  TESS_NOTUSED(userData);
  return malloc(size);
}

void *heapRealloc(void *userData, void *ptr, unsigned int size) {
  TESS_NOTUSED(userData);
  return realloc(ptr, size);
}

void heapFree(void *userData, void *ptr) {
  TESS_NOTUSED(userData);
  free(ptr);
}

static TESSalloc defaulAlloc = {
    heapAlloc, heapRealloc, heapFree, 0, 0, 0, 0, 0, 0, 0,
};

TESStesselator *tessNewTess(TESSalloc *alloc) {
  TESStesselator *tess;

  if (alloc == NULL)
    alloc = &defaulAlloc;

  tess = (TESStesselator *)alloc->memalloc(alloc->userData,
                                           sizeof(TESStesselator));
  if (tess == NULL) {
    return 0;
  }
  tess->alloc = *alloc;

  if (tess->alloc.meshEdgeBucketSize == 0)
    tess->alloc.meshEdgeBucketSize = 512;
  if (tess->alloc.meshVertexBucketSize == 0)
    tess->alloc.meshVertexBucketSize = 512;
  if (tess->alloc.meshFaceBucketSize == 0)
    tess->alloc.meshFaceBucketSize = 256;
  if (tess->alloc.dictNodeBucketSize == 0)
    tess->alloc.dictNodeBucketSize = 512;
  if (tess->alloc.regionBucketSize == 0)
    tess->alloc.regionBucketSize = 256;

  tess->normal[0] = 0;
  tess->normal[1] = 0;
  tess->normal[2] = 0;

  tess->bmin[0] = 0;
  tess->bmin[1] = 0;
  tess->bmax[0] = 0;
  tess->bmax[1] = 0;

  tess->reverseContours = 0;

  tess->windingRule = TESS_WINDING_ODD;
  tess->processCDT = 0;

  if (tess->alloc.regionBucketSize < 16)
    tess->alloc.regionBucketSize = 16;
  if (tess->alloc.regionBucketSize > 4096)
    tess->alloc.regionBucketSize = 4096;
  tess->regionPool =
      createBucketAlloc(&tess->alloc, "Regions", sizeof(ActiveRegion),
                        tess->alloc.regionBucketSize);

  tess->mesh = NULL;

  tess->outOfMemory = 0;
  tess->vertexIndexCounter = 0;

  tess->vertices = 0;
  tess->vertexIndices = 0;
  tess->vertexCount = 0;
  tess->elements = 0;
  tess->elementCount = 0;

  return tess;
}

void tessDeleteTess(TESStesselator *tess) {

  struct TESSalloc alloc = tess->alloc;

  deleteBucketAlloc(tess->regionPool);

  if (tess->mesh != NULL) {
    tessMeshDeleteMesh(&alloc, tess->mesh);
    tess->mesh = NULL;
  }
  if (tess->vertices != NULL) {
    alloc.memfree(alloc.userData, tess->vertices);
    tess->vertices = 0;
  }
  if (tess->vertexIndices != NULL) {
    alloc.memfree(alloc.userData, tess->vertexIndices);
    tess->vertexIndices = 0;
  }
  if (tess->elements != NULL) {
    alloc.memfree(alloc.userData, tess->elements);
    tess->elements = 0;
  }

  alloc.memfree(alloc.userData, tess);
}

static TESSindex GetNeighbourFace(TESShalfEdge *edge) {
  if (!edge->Rface)
    return TESS_UNDEF;
  if (!edge->Rface->inside)
    return TESS_UNDEF;
  return edge->Rface->n;
}

void OutputPolymesh(TESStesselator *tess, TESSmesh *mesh, int elementType,
                    int polySize, int vertexSize) {
  TESSvertex *v = 0;
  TESSface *f = 0;
  TESShalfEdge *edge = 0;
  int maxFaceCount = 0;
  int maxVertexCount = 0;
  int faceVerts, i;
  TESSindex *elements = 0;
  TESSreal *vert;

  if (polySize > 3) {
    if (!tessMeshMergeConvexFaces(mesh, polySize)) {
      tess->outOfMemory = 1;
      return;
    }
  }

  for (v = mesh->vHead.next; v != &mesh->vHead; v = v->next)
    v->n = TESS_UNDEF;

  for (f = mesh->fHead.next; f != &mesh->fHead; f = f->next) {
    f->n = TESS_UNDEF;
    if (!f->inside)
      continue;

    edge = f->anEdge;
    faceVerts = 0;
    do {
      v = edge->Org;
      if (v->n == TESS_UNDEF) {
        v->n = maxVertexCount;
        maxVertexCount++;
      }
      faceVerts++;
      edge = edge->Lnext;
    } while (edge != f->anEdge);

    assert(faceVerts <= polySize);

    f->n = maxFaceCount;
    ++maxFaceCount;
  }

  tess->elementCount = maxFaceCount;
  if (elementType == TESS_CONNECTED_POLYGONS)
    maxFaceCount *= 2;
  tess->elements = (TESSindex *)tess->alloc.memalloc(
      tess->alloc.userData, sizeof(TESSindex) * maxFaceCount * polySize);
  if (!tess->elements) {
    tess->outOfMemory = 1;
    return;
  }

  tess->vertexCount = maxVertexCount;
  tess->vertices = (TESSreal *)tess->alloc.memalloc(
      tess->alloc.userData, sizeof(TESSreal) * tess->vertexCount * vertexSize);
  if (!tess->vertices) {
    tess->outOfMemory = 1;
    return;
  }

  tess->vertexIndices = (TESSindex *)tess->alloc.memalloc(
      tess->alloc.userData, sizeof(TESSindex) * tess->vertexCount);
  if (!tess->vertexIndices) {
    tess->outOfMemory = 1;
    return;
  }

  for (v = mesh->vHead.next; v != &mesh->vHead; v = v->next) {
    if (v->n != TESS_UNDEF) {

      vert = &tess->vertices[v->n * vertexSize];
      vert[0] = v->coords[0];
      vert[1] = v->coords[1];
      if (vertexSize > 2)
        vert[2] = v->coords[2];

      tess->vertexIndices[v->n] = v->idx;
    }
  }

  elements = tess->elements;
  for (f = mesh->fHead.next; f != &mesh->fHead; f = f->next) {
    if (!f->inside)
      continue;

    edge = f->anEdge;
    faceVerts = 0;
    do {
      v = edge->Org;
      *elements++ = v->n;
      faceVerts++;
      edge = edge->Lnext;
    } while (edge != f->anEdge);

    for (i = faceVerts; i < polySize; ++i)
      *elements++ = TESS_UNDEF;

    if (elementType == TESS_CONNECTED_POLYGONS) {
      edge = f->anEdge;
      do {
        *elements++ = GetNeighbourFace(edge);
        edge = edge->Lnext;
      } while (edge != f->anEdge);

      for (i = faceVerts; i < polySize; ++i)
        *elements++ = TESS_UNDEF;
    }
  }
}

void OutputContours(TESStesselator *tess, TESSmesh *mesh, int vertexSize) {
  TESSface *f = 0;
  TESShalfEdge *edge = 0;
  TESShalfEdge *start = 0;
  TESSreal *verts = 0;
  TESSindex *elements = 0;
  TESSindex *vertInds = 0;
  int startVert = 0;
  int vertCount = 0;

  tess->vertexCount = 0;
  tess->elementCount = 0;

  for (f = mesh->fHead.next; f != &mesh->fHead; f = f->next) {
    if (!f->inside)
      continue;

    start = edge = f->anEdge;
    do {
      ++tess->vertexCount;
      edge = edge->Lnext;
    } while (edge != start);

    ++tess->elementCount;
  }

  tess->elements = (TESSindex *)tess->alloc.memalloc(
      tess->alloc.userData, sizeof(TESSindex) * tess->elementCount * 2);
  if (!tess->elements) {
    tess->outOfMemory = 1;
    return;
  }

  tess->vertices = (TESSreal *)tess->alloc.memalloc(
      tess->alloc.userData, sizeof(TESSreal) * tess->vertexCount * vertexSize);
  if (!tess->vertices) {
    tess->outOfMemory = 1;
    return;
  }

  tess->vertexIndices = (TESSindex *)tess->alloc.memalloc(
      tess->alloc.userData, sizeof(TESSindex) * tess->vertexCount);
  if (!tess->vertexIndices) {
    tess->outOfMemory = 1;
    return;
  }

  verts = tess->vertices;
  elements = tess->elements;
  vertInds = tess->vertexIndices;

  startVert = 0;

  for (f = mesh->fHead.next; f != &mesh->fHead; f = f->next) {
    if (!f->inside)
      continue;

    vertCount = 0;
    start = edge = f->anEdge;
    do {
      *verts++ = edge->Org->coords[0];
      *verts++ = edge->Org->coords[1];
      if (vertexSize > 2)
        *verts++ = edge->Org->coords[2];
      *vertInds++ = edge->Org->idx;
      ++vertCount;
      edge = edge->Lnext;
    } while (edge != start);

    elements[0] = startVert;
    elements[1] = vertCount;
    elements += 2;

    startVert += vertCount;
  }
}

void tessAddContour(TESStesselator *tess, int size, const void *vertices,
                    int stride, int numVertices) {
  const unsigned char *src = (const unsigned char *)vertices;
  TESShalfEdge *e;
  int i;

  if (tess->mesh == NULL)
    tess->mesh = tessMeshNewMesh(&tess->alloc);
  if (tess->mesh == NULL) {
    tess->outOfMemory = 1;
    return;
  }

  if (size < 2)
    size = 2;
  if (size > 3)
    size = 3;

  e = NULL;

  for (i = 0; i < numVertices; ++i) {
    const TESSreal *coords = (const TESSreal *)src;
    src += stride;

    if (e == NULL) {

      e = tessMeshMakeEdge(tess->mesh);
      if (e == NULL) {
        tess->outOfMemory = 1;
        return;
      }
      if (!tessMeshSplice(tess->mesh, e, e->Sym)) {
        tess->outOfMemory = 1;
        return;
      }
    } else {

      if (tessMeshSplitEdge(tess->mesh, e) == NULL) {
        tess->outOfMemory = 1;
        return;
      }
      e = e->Lnext;
    }

    e->Org->coords[0] = coords[0];
    e->Org->coords[1] = coords[1];
    if (size > 2)
      e->Org->coords[2] = coords[2];
    else
      e->Org->coords[2] = 0;

    e->Org->idx = tess->vertexIndexCounter++;

    e->winding = tess->reverseContours ? -1 : 1;
    e->Sym->winding = tess->reverseContours ? 1 : -1;
  }
}

void tessSetOption(TESStesselator *tess, int option, int value) {
  switch (option) {
  case TESS_CONSTRAINED_DELAUNAY_TRIANGULATION:
    tess->processCDT = value > 0 ? 1 : 0;
    break;
  case TESS_REVERSE_CONTOURS:
    tess->reverseContours = value > 0 ? 1 : 0;
    break;
  }
}

int tessTesselate(TESStesselator *tess, int windingRule, int elementType,
                  int polySize, int vertexSize, const TESSreal *normal) {
  TESSmesh *mesh;
  int rc = 1;

  if (tess->vertices != NULL) {
    tess->alloc.memfree(tess->alloc.userData, tess->vertices);
    tess->vertices = 0;
  }
  if (tess->elements != NULL) {
    tess->alloc.memfree(tess->alloc.userData, tess->elements);
    tess->elements = 0;
  }
  if (tess->vertexIndices != NULL) {
    tess->alloc.memfree(tess->alloc.userData, tess->vertexIndices);
    tess->vertexIndices = 0;
  }

  tess->vertexIndexCounter = 0;

  if (normal) {
    tess->normal[0] = normal[0];
    tess->normal[1] = normal[1];
    tess->normal[2] = normal[2];
  }

  tess->windingRule = windingRule;

  if (vertexSize < 2)
    vertexSize = 2;
  if (vertexSize > 3)
    vertexSize = 3;

  if (setjmp(tess->env) != 0) {

    return 0;
  }

  if (!tess->mesh) {
    return 0;
  }

  tessProjectPolygon(tess);

  if (!tessComputeInterior(tess)) {
    longjmp(tess->env, 1);
  }

  mesh = tess->mesh;

  if (elementType == TESS_BOUNDARY_CONTOURS) {
    rc = tessMeshSetWindingNumber(mesh, 1, TRUE);
  } else {
    rc = tessMeshTessellateInterior(mesh);
    if (rc != 0 && tess->processCDT != 0)
      tessMeshRefineDelaunay(mesh, &tess->alloc);
  }
  if (rc == 0)
    longjmp(tess->env, 1);

  tessMeshCheckMesh(mesh);

  if (elementType == TESS_BOUNDARY_CONTOURS) {
    OutputContours(tess, mesh, vertexSize);
  } else {
    OutputPolymesh(tess, mesh, elementType, polySize, vertexSize);
  }

  tessMeshDeleteMesh(&tess->alloc, mesh);
  tess->mesh = NULL;

  if (tess->outOfMemory)
    return 0;
  return 1;
}

int tessGetVertexCount(TESStesselator *tess) { return tess->vertexCount; }

const TESSreal *tessGetVertices(TESStesselator *tess) { return tess->vertices; }

const TESSindex *tessGetVertexIndices(TESStesselator *tess) {
  return tess->vertexIndices;
}

int tessGetElementCount(TESStesselator *tess) { return tess->elementCount; }

const int *tessGetElements(TESStesselator *tess) { return tess->elements; }

#endif