public class Tools2D
{
    
    static float area2(Point2D A,Point2D B,Point2D C){
        return (A.x-C.x)*(B.y-C.y)-(A.y-C.y)*(B.x-C.x);
    }
    
    static boolean insideTriangle(Point2D A,Point2D B,Point2D C,Point2D P){
        return Tools2D.area2(A,B,P) >=0 && Tools2D.area2(B,C,P) >=0 && Tools2D.area2(C,A,P) >=0;
    }
    
    static void triangulate(Point2D[] P, Triangle[] tr){
        //P contains all n polygon vertices in CCW order.
        //The resulting triangles will be stored in array tr.
        //This array tr must have length n-2.
        int n=P.length, j =n-1,iA=0,iB=0,iC=0;
        int[] next=new int[n];
        for (int i=0;i<n;i++){
            next[j]=i;
            j=i;
        }
        for (int k=0;k<n-2;k++){
            //Find a suitable triangle, consisting of two edges
            //and an internal diagonal
            Point2D A,B,C;
            boolean triaFound=false;
            int count=0;
            while (!triaFound && ++count<n){
                iB=next[iA]; iC=next[iB];
                A=P[iA]; B=P[iB]; C=P[iC];
                if(Tools2D.area2(A,B,C)>=0){
                    //edges AB and BC; diagonal AC.
                    //Test to see if no other polygon vertex
                    //lies within triangle ABC.
                    j=next[iC];
                    while(j!=iA && !insideTriangle(A,B,C,P[j]))
                       j=next[j];
                    if(j==iA){
                        //Triangle ABC contains no other vertex:
                        tr[k]=new Triangle(A,B,C);
                        next[iA]=iC;
                        triaFound=true;
                    }
                }
                iA=next[iA];
            }
            if(count==n){
                System.out.println("Not a simple polygon or vertex sequence not counter clockwise");
                System.exit(1);
            }
        }
    } 
    
    static float distance2(Point2D P,Point2D Q){
        float dx=P.x-Q.x,
              dy=P.y-Q.y;
        return dx*dx+dy*dy;
    }
}