--- ray/src/common/triangulate.c	2014/01/24 02:22:49	2.3
+++ ray/src/common/triangulate.c	2021/04/19 20:37:04	2.7
@@ -1,11 +1,13 @@
 #ifndef lint
-static const char RCSid[] = "$Id: triangulate.c,v 2.3 2014/01/24 02:22:49 greg Exp $";
+static const char RCSid[] = "$Id: triangulate.c,v 2.7 2021/04/19 20:37:04 greg Exp $";
 #endif
 /*
  *  triangulate.c
  *  
  *  Adapted by Greg Ward on 1/23/14.
- *  Copyright 2014 Anyhere Software. All rights reserved.
+ *  Fixes for polygons with seams/holes and co-linear vertices added
+ *  by Nathaniel Jones on 12/21/16.
+ *  Copyright 2016 Anyhere Software. All rights reserved.
  *
  */
 
@@ -32,13 +34,13 @@ static const char RCSid[] = "$Id: triangulate.c,v 2.3 
 #define false	0
 #endif
 
-static const double EPSILON = 0.0000000001;
+#define EPSILON		0.0000000001
 
 static int
 polySnip(const Vert2_list *contour, int u, int v, int w, int n, int *V)
 {
   int p;
-  double Ax, Ay, Bx, By, Cx, Cy, Px, Py;
+  double Ax, Ay, Bx, By, Cx, Cy, Px, Py, cross;
 
   Ax = contour->v[V[u]].mX;
   Ay = contour->v[V[u]].mY;
@@ -49,13 +51,17 @@ polySnip(const Vert2_list *contour, int u, int v, int 
   Cx = contour->v[V[w]].mX;
   Cy = contour->v[V[w]].mY;
 
-  if ( EPSILON > (((Bx-Ax)*(Cy-Ay)) - ((By-Ay)*(Cx-Ax))) ) return false;
+  cross = ((Bx - Ax)*(Cy - Ay)) - ((By - Ay)*(Cx - Ax));
+  if (cross < EPSILON)
+  	return cross > -EPSILON ? -1 : false; /* Negative if colinear points */
 
   for (p=0;p<n;p++)
   {
     if( (p == u) | (p == v) | (p == w) ) continue;
     Px = contour->v[V[p]].mX;
     Py = contour->v[V[p]].mY;
+    if ((Px == Ax) & (Py == Ay) || (Px == Bx) & (Py == By) ||
+		(Px == Cx) & (Py == Cy)) continue; /* Handle donuts */
     if (insideTriangle(Ax,Ay,Bx,By,Cx,Cy,Px,Py)) return false;
   }
 
@@ -77,6 +83,9 @@ polyAlloc(int nv)
 	return pnew;
 }
 
+/*
+  Area is positive if vertices listed counter-clockwise, negative if clockwise
+ */
 double
 polyArea(const Vert2_list *contour)
 {
@@ -99,7 +108,6 @@ insideTriangle(double Ax, double Ay,
                       double Bx, double By,
                       double Cx, double Cy,
                       double Px, double Py)
-
 {
   double ax, ay, bx, by, cx, cy, apx, apy, bpx, bpy, cpx, cpy;
   double cCROSSap, bCROSScp, aCROSSbp;
@@ -115,7 +123,7 @@ insideTriangle(double Ax, double Ay,
   cCROSSap = cx*apy - cy*apx;
   bCROSScp = bx*cpy - by*cpx;
 
-  return ((aCROSSbp >= 0.0) && (bCROSScp >= 0.0) && (cCROSSap >= 0.0));
+  return ((aCROSSbp >= 0.0) & (bCROSScp >= 0.0) & (cCROSSap >= 0.0));
 };
 
 int
@@ -123,7 +131,7 @@ polyTriangulate(const Vert2_list *contour, tri_out_t *
 {
   /* allocate and initialize list of Vertices in polygon */
 
-  int nv, m, u, v, w, count;
+  int nv, u, v, w, count, result;
   int *V;
 
   if ( contour->nv < 3 ) return false;
@@ -133,41 +141,44 @@ polyTriangulate(const Vert2_list *contour, tri_out_t *
 
   /* we want a counter-clockwise polygon in V */
 
-  if ( 0.0 < polyArea(contour) )
+  if ( polyArea(contour) > 0.0 )
     for (v=0; v<contour->nv; v++) V[v] = v;
   else
-    for(v=0; v<contour->nv; v++) V[v] = (contour->nv-1)-v;
+    for (v=0; v<contour->nv; v++) V[v] = (contour->nv-1)-v;
 
   nv = contour->nv;
 
   /*  remove nv-2 Vertices, creating 1 triangle every time */
   count = 2*nv;   /* error detection */
 
-  for(m=0, v=nv-1; nv>2; )
+  v = nv-1;
+  while (nv > 2)
   {
     /* if we loop, it is probably a non-simple polygon */
-    if (0 >= count--)
+    if (count-- <= 0)
     {
       /* Triangulate: ERROR - probable bad polygon */
+      free(V);
       return false;
     }
 
     /* three consecutive vertices in current polygon, <u,v,w> */
-    u = v  ; if (nv <= u) u = 0;     /* previous */
-    v = u+1; if (nv <= v) v = 0;     /* new v    */
-    w = v+1; if (nv <= w) w = 0;     /* next     */
+    u = v  ; u *= (nv > u);     /* previous */
+    v = u+1; v *= (nv > v);     /* new v    */
+    w = v+1; w *= (nv > w);     /* next     */
 
-    if ( polySnip(contour,u,v,w,nv,V) )
+    result = polySnip(contour, u, v, w, nv, V);
+    if (result > 0) /* successfully found a triangle */
     {
-      int a,b,c,s,t;
-
-      /* true names of the vertices */
-      a = V[u]; b = V[v]; c = V[w];
-
       /* output Triangle */
-      if (!(*cb)(contour, a, b, c)) return false;
- 
-      m++;
+      if (!(*cb)(contour, V[u], V[v], V[w])) {
+      	free(V);
+      	return false;
+      }
+    }
+    if (result) /* successfully found a triangle or three consecutive colinear points */
+    {
+      int s,t;
 
       /* remove v from remaining polygon */
       for(s=v,t=v+1;t<nv;s++,t++) V[s] = V[t]; nv--;