/*
 * ported from p bourke's triangulate.c
 * http://astronomy.swin.edu.au/~pbourke/terrain/triangulate/triangulate.c
 *
 * fjenett, 20th february 2005, offenbach-germany.
 * contact: http://www.florianjenett.de/
 *
 * Tom Carden, 22 January 2005, London
 * made more Java-like, but not extensively tested 
 * contact tom (at) tom-carden.co.uk
 *
 */

import java.util.Vector;
import java.util.Collections;
import java.util.HashSet;
import java.util.Comparator;

public class Triangulate {

  public static double EPSILON = 0.000001;

  /*
    Return TRUE if a point p is inside the circumcircle made up
    of the points in triangle t
    The circumcircle centre is returned in circle.x and circle.y and the radius r is circle.z
    NOTE: A point on the edge is inside the circumcircle
  */
  static boolean CircumCircle(Point3d p, Triangle t, Point3d circle) {
    
    double m1,m2,mx1,mx2,my1,my2;
    double dx,dy,rsqr,drsqr;

    /* Check for coincident points */
    if ( Math.abs(t.p1.y-t.p2.y) < EPSILON && Math.abs(t.p2.y-t.p3.y) < EPSILON )
    {
      System.out.println("CircumCircle: Points are coincident.");
      return false;
    }

    if ( Math.abs(t.p2.y-t.p1.y) < EPSILON ) {
      m2 = - (t.p3.x-t.p2.x) / (t.p3.y-t.p2.y);
      mx2 = (t.p2.x + t.p3.x) / 2.0;
      my2 = (t.p2.y + t.p3.y) / 2.0;
      circle.x = (t.p2.x + t.p1.x) / 2.0;
      circle.y = m2 * (circle.x - mx2) + my2;
    }
    else if ( Math.abs(t.p3.y-t.p2.y) < EPSILON ) {
      m1 = - (t.p2.x-t.p1.x) / (t.p2.y-t.p1.y);
      mx1 = (t.p1.x + t.p2.x) / 2.0;
      my1 = (t.p1.y + t.p2.y) / 2.0;
      circle.x = (t.p3.x + t.p2.x) / 2.0;
      circle.y = m1 * (circle.x - mx1) + my1;  
    }
    else {
      m1 = - (t.p2.x-t.p1.x) / (t.p2.y-t.p1.y);
      m2 = - (t.p3.x-t.p2.x) / (t.p3.y-t.p2.y);
      mx1 = (t.p1.x + t.p2.x) / 2.0;
      mx2 = (t.p2.x + t.p3.x) / 2.0;
      my1 = (t.p1.y + t.p2.y) / 2.0;
      my2 = (t.p2.y + t.p3.y) / 2.0;
      circle.x = (m1 * mx1 - m2 * mx2 + my2 - my1) / (m1 - m2);
      circle.y = m1 * (circle.x - mx1) + my1;
    }

    dx = t.p2.x - circle.x;
    dy = t.p2.y - circle.y;
    rsqr = dx*dx + dy*dy;
    circle.z = Math.sqrt(rsqr); // radius

    dx = p.x - circle.x;
    dy = p.y - circle.y;
    drsqr = dx*dx + dy*dy;

    return drsqr <= rsqr;
  }


  public static class XYZCompare implements Comparator {
    public int compare(Object o1, Object o2) {
      Point3d p1 = (Point3d)o1;
      Point3d p2 = (Point3d)o2;
      if (p1.x < p2.x) {
        return -1;
      }
      else if (p1.x > p2.x) {
        return 1;
      }
      else {
        return 0;
      }
    }
  }


  /*
    Triangulation subroutine
       Takes as input NV vertices in array pxyz
       Returned is a list of ntri triangular faces in the array v
       These triangles are arranged in a consistent clockwise order.
       The triangle array 'v' should be malloced to 3 * nv
       The vertex array pxyz must be big enough to hold 3 more points
       The vertex array must be sorted in increasing x values say
       
       qsort(p,nv,sizeof(XYZ),XYZCompare);
       
       int XYZCompare(void *v1,void *v2)
       {
         XYZ *p1,*p2;
         p1 = v1;
         p2 = v2;
         if (p1->x < p2->x)
           return(-1);
         else if (p1->x > p2->x)
           return(1);
         else
           return(0);
       }
     */

  //static int Triangulate ( int nv, Point3d pxyz[], Triangle v[] )
  static Vector triangulate ( Vector pxyz )
  {
    HashSet complete = new HashSet();
    Vector edges = new Vector();
    Vector triangles = new Vector();

    Collections.sort(pxyz, new XYZCompare());

    /*
    Find the maximum and minimum vertex bounds.
         This is to allow calculation of the bounding triangle
         */
    double xmin = ((Point3d)pxyz.get(0)).x;
    double ymin = ((Point3d)pxyz.get(0)).y;
    double xmax = xmin;
    double ymax = ymin;
    for (int i=1;i<pxyz.size();i++)
    {
      Point3d p = (Point3d)pxyz.get(i);
      if (p.x < xmin) xmin = p.x;
      if (p.x > xmax) xmax = p.x;
      if (p.y < ymin) ymin = p.y;
      if (p.y > ymax) ymax = p.y;
    }
    double dx = xmax - xmin;
    double dy = ymax - ymin;
    double dmax = (dx > dy) ? dx : dy;
    double xmid = (xmax + xmin) / 2.0;
    double ymid = (ymax + ymin) / 2.0;

    /*
      Set up the supertriangle
           This is a triangle which encompasses all the sample points.
           The supertriangle coordinates are added to the end of the
           vertex list. The supertriangle is the first triangle in
           the triangle list.
         */
    Triangle superTriangle = new Triangle();
    superTriangle.p1 = new Point3d( xmid - 2.0 * dmax, ymid - dmax, 0.0 );
    superTriangle.p2 = new Point3d( xmid, ymid + 2.0 * dmax, 0.0 );
    superTriangle.p3 = new Point3d(xmid + 2.0 * dmax, ymid - dmax, 0.0 );
    triangles.add(superTriangle);

    /*
      Include each point one at a time into the existing mesh
         */
    for (int i=0;i<pxyz.size();i++) {

      Point3d p = (Point3d)pxyz.get(i);
      edges.clear();

      /*
        Set up the edge buffer.
               If the point (xp,yp) lies inside the circumcircle then the
               three edges of that triangle are added to the edge buffer
               and that triangle is removed.
             */
      Point3d circle = new Point3d();
      for (int j = triangles.size()-1; j >= 0; j--) {
        Triangle t = (Triangle)triangles.get(j);
        if (complete.contains(t)) {
          continue;
        }
        boolean inside = CircumCircle( p, t, circle );
        if (circle.x + circle.z < p.x) {
          complete.add(t);
        }
        if (inside) {
          Edge e = new Edge();
          e.p1 = t.p1;
          e.p2 = t.p2;
          edges.add(e);
          e = new Edge();
          e.p1 = t.p2;
          e.p2 = t.p3;
          edges.add(e);
          e = new Edge();
          e.p1 = t.p3;
          e.p2 = t.p1;
          edges.add(e);
          triangles.remove(t);
        }
      }

      /*
        Tag multiple edges
        Note: if all triangles are specified anticlockwise then all
        interior edges are opposite pointing in direction.
      */
      for (int j=0;j<edges.size()-1;j++)
      {
        Edge e1 = (Edge)edges.get(j);
        //if ( !(edges[j].p1 < 0 && edges[j].p2 < 0) )
        for (int k=j+1;k<edges.size();k++)
        {
          Edge e2 = (Edge)edges.get(k);
          if ((e1.p1 == e2.p2) && (e1.p2 == e2.p1))
          {
            e1.p1 = null;
            e1.p2 = null;
            e2.p1 = null;
            e2.p2 = null;
          }
          /* Shouldn't need the following, see note above */
          if ((e1.p1 == e2.p1) && (e1.p2 == e2.p2))
          {
            e1.p1 = null;
            e1.p2 = null;
            e2.p1 = null;
            e2.p2 = null;
          }
        }
      }

      /*
        Form new triangles for the current point
        Skipping over any tagged edges.
        All edges are arranged in clockwise order.
       */
      for (int j=0;j<edges.size();j++) {
        Edge e = (Edge)edges.get(j);
        if (e.p1 == null || e.p2 == null) {
          continue;
        }
        Triangle t = new Triangle();
        t.p1 = e.p1;
        t.p2 = e.p2;
        t.p3 = p;
        triangles.add(t);
      }
    }


    /* 
     Remove triangles with supertriangle vertices
     These are triangles which have a vertex number greater than nv
    */
    for (int i=triangles.size()-1;i>=0;i--)
    {
      Triangle t = (Triangle)triangles.get(i);
      if (t.p1 == superTriangle.p1 || t.p2 == superTriangle.p1 || t.p3 == superTriangle.p1 ||
        t.p1 == superTriangle.p2 || t.p2 == superTriangle.p2 || t.p3 == superTriangle.p2 ||
        t.p1 == superTriangle.p3 || t.p2 == superTriangle.p3 || t.p3 == superTriangle.p3 ) {
        triangles.remove(t);
      }
    }

    return triangles;
  }

}