TwistyPuzzleLib

import android.graphics.Path;

// This agrees with startAngle and sweepAngle arguments to Canvas.drawArc(), i.e. it is 0 at the +x

// axis, and grows clockwise to 2*PI.

    float theta = (float)Math.atan2(-dy,dx);

    if( theta<0 ) theta += 2*PI;

    return theta;

  private float[][] computeCircles(float[][] vertices, float[] angles)

    int length = vertices.length;

    float[][] output = new float[length][3];

    for(int vert=0; vert<length; vert++)

      {

      int next = vert<length-1 ? vert+1 : 0;

      float[] cv = vertices[vert];

      float[] nv = vertices[next];

      float currX = cv[0];

      float currY = cv[1];

      float nextX = nv[0];

      float nextY = nv[1];

      float angle = getAngle(angles,vert);

      computeCircle(currX,currY,nextX,nextY,angle,output[vert]);

      }

    return output;

    }

///////////////////////////////////////////////////////////////////////////////////////////////////

// Input: circle segment from point C=(cx,cy) to point N=(nx,ny) ; if angle==0, then it is a

// straight line. Otherwise it is a true circle segment. If O=(ox,oy) is the center of this circle

// and R>0 is its radius, then |angle| is the angle CON (in radians); if angle>0, then O is to the

// left of vector PC, otherwise it is to the right.

//

// Output: if angle!=0, output[0]=ox, output[1]=oy, output[2]=R.

// Otherwise we have a straight line y=ax+b and output[0]=a, output[1]=b and output[2]=0.

// [ special case when line is vertical, i.e. x=c: output=(c,0,-1) ]

  private void computeCircle(float cx, float cy, float nx, float ny, float angle, float[] output)

    {

    if( angle != 0 )

      {

      float ctg= 1.0f/((float)Math.tan(angle/2));

      float ox = 0.5f*(cx+nx) + ctg*0.5f*(cy-ny);

      float oy = 0.5f*(cy+ny) - ctg*0.5f*(cx-nx);

      float dx = ox-cx;

      float dy = oy-cy;

      float r = (float)Math.sqrt(dx*dx+dy*dy);

      output[0] = ox;

      output[1] = oy;

      output[2] = r;

      }

    else

      {

      float dx = nx-cx;

      float dy = ny-cy;

      if( dx*dx > 0.000001f )

        {

        output[0] = dy/dx;

        output[1] = (nx*cy-cx*ny)/dx;

        output[2] = 0;

        }

      else

        {

        output[0] = cx;

        output[1] =  0;

        output[2] = -1;

        }

      }

    }

///////////////////////////////////////////////////////////////////////////////////////////////////

  private float[][][] computeInnerVertices(float[][] circles, float[][] vertices, float[] radii, float corners,

                                           float[] strokes, float borders, float[][] corner_circles)

    {

    int prev, next, length = circles.length;

    float[][][] output = new float[length][2][2];

    for(int curr=0; curr<length; curr++)

      {

      float[] currC = corner_circles[curr];

      prev = curr==0 ? length-1 : curr-1;

      next = curr==length-1 ? 0 : curr+1;

      float radius = radii[curr]*corners + strokes[curr]*borders/2;

      computeCornerCircle(circles[prev],circles[curr], vertices[prev], vertices[curr], vertices[next], radius, currC );

      computeInnerVertex(circles[prev],currC,output[curr][0]);

      computeInnerVertex(circles[curr],currC,output[curr][1]);

      }

    return output;

    }

///////////////////////////////////////////////////////////////////////////////////////////////////

// Return the angle the vector tangent to the circle at point T='tangent_point' makes with the

// +x axis. (i.e. float from 0 to 2PI going clockwise, same format as in Canvas.drawArc).

// If the 'circle' is really a straight line, return the angle from O=other_point to T, two

// points which lie on this line.

// Otherwise, the direction of the vector points as we go from O to T (along the shorter arc).

// What to do when the two points are opposite on the circle and two arcs are equal? Go CCW.

//

// If C (cx,cy) is the center of the circle, compute vector CT = (vx,vy), then the perpendicular

// V'= (-vy,vx) and choose V' or -V' depending on which one forms angle of less than 90 degrees

// with vector TO = (tx,ty).

  private float computeDir(float[] circle, float[] tangent_point, float[] other_point)

    {

    if( circle[2]<=0 )

      {

      float dx = tangent_point[0] - other_point[0];

      float dy = tangent_point[1] - other_point[1];

      return computeAngle(dx,dy);

      }

    else

      {

      float vx = tangent_point[0] - circle[0];

      float vy = tangent_point[1] - circle[1];

      float tx = tangent_point[0] - other_point[0];

      float ty = tangent_point[1] - other_point[1];

      float ret= (-vy*tx+vx*ty >=0) ? computeAngle(-vy,vx) : computeAngle(vy,-vx);

      //android.util.Log.e("D", "tangent: "+tangent_point[0]+" "+tangent_point[1]+" other="+other_point[0]+" "+other_point[1]);

      //android.util.Log.e("D","circle: "+circle[0]+" "+circle[1]+" "+circle[2]+" ret="+ret);

      return ret;

      }

  private void findCircleIntersection(float x1,float y1, float r1, float x2, float y2, float r2,

                                      float nearx, float neary, float[] output )

        output[0] = ox1;

        output[1] = oy1;

        output[0] = ox2;

        output[1] = oy2;

      output[0] = nearx;

      output[1] = neary;

// circle1: center (x,y) radius r; line: y=ax+b (if c==0) or x=a (otherwise)

// Guaranteed to intersect in two points. Find the intersection. Which one? the one that's closer

// to (nearx,neary).

// (vx,vy) is the point of intersection of the (a,b,c) line and the line perpendicular to it

// passing through (x,y)

  private void findCircleLineIntersection(float x,float y, float r, float a, float b, float c,

                                          float nearx, float neary, float[] output )

    float vx,vy,m;

    float ox1,ox2,oy1,oy2;

    if( c==0 )

      vx = (x + a*(y-b)) / (a*a + 1);

      vy = (a*x + a*a*y + b) / (a*a + 1);

      m = a;

      vx = a;

      vy = y;

      m = 0;

      }

    float dx = x-vx;

    float dy = y-vy;

    float d = (float)Math.sqrt(dx*dx+dy*dy);

    float f = (float)Math.sqrt(r*r-d*d);

    float e = f / ((float)Math.sqrt(m*m+1));

    if( c==0 )

      {

      ox1 = vx - e;

      oy1 = vy - e*m;

      ox2 = vx + e;

      oy2 = vy + e*m;

      }

    else

      {

      ox1 = vx;

      oy1 = vy - f;

      ox2 = vx;

      oy2 = vy + f;

      }

    dx = nearx-ox1;

    dy = neary-oy1;

    float d1 = dx*dx+dy*dy;

    dx = nearx-ox2;

    dy = neary-oy2;

    float d2 = dx*dx+dy*dy;

    if( d1<d2 )

      {

      output[0] = ox1;

      output[1] = oy1;

      }

    else

      {

      output[0] = ox2;

      output[1] = oy2;

    // android.util.Log.e("D", "findCircleLineIntersection circle="+x+" "+y+" "+r+" line="+a+" "+b+" "+c+" result: "+output[0]+" "+output[1]);

// line1: y=a1x+b1 (if c1==0) or x=a1 (otherwise)

// line2: y=a2x+b2 (if c2==0) or x=a2 (otherwise)

// Guaranteed to intersect. Find the intersection point.

  private void findLineIntersection(float a1,float b1, float c1, float a2, float b2, float c2, float[] output )

    if( c1==0 && c2==0 )

      {

      if( a1==a2 ) android.util.Log.e("E", "1 error in findLineIntersection: lines parallel" );

      else

        {

        float x = (b2-b1)/(a1-a2);

        float y = a1*x+b1;

        output[0] = x;

        output[1] = y;

        }

      }

    else if( c1==0 )

      output[0] = a2;

      output[1] = a1*a2 + b1;

      }

    else if( c2==0 )

      {

      output[0] = a1;

      output[1] = a2*a1 + b2;

      }

    else

      {

      android.util.Log.e("E", "2 error in findLineIntersection: lines parallel" );

  private void computeIntersection(float[] circle1, float[] circle2, float[] point, float[] output)

    float x1 = circle1[0];

    float y1 = circle1[1];

    float r1 = circle1[2];

    float x2 = circle2[0];

    float y2 = circle2[1];

    float r2 = circle2[2];

    if( r1>0 && r2>0 ) findCircleIntersection(x1,y1,r1,x2,y2,r2,point[0],point[1],output);

    else

      {

           if( r1>0 ) findCircleLineIntersection(x1,y1,r1,x2,y2,r2,point[0],point[1],output);

      else if( r2>0 ) findCircleLineIntersection(x2,y2,r2,x1,y1,r1,point[0],point[1],output);

      else            findLineIntersection(x2,y2,r2,x1,y1,r1,output);

      }

    }

///////////////////////////////////////////////////////////////////////////////////////////////////

// Input: a circle (true or line) in usual format and two points on it.

//

// If it is a straight line, return a straight line which is parallel to it and moved by either

// |move| to the 'left' (if move<0) or |move| to the right (otherwise).

// 'left' or 'right' are defined: we are looking from point1 towards point2.

//

// If it is a true circle, then return a true circle which has the same center and radius either

// smaller by |move| or larger by |move| - depending on:

// if we're looking from point1 towards point2 (along the shorter arc) - notice on which side, left

// or right of the vector of movement anchored at point1, the outside of the circle is.

//

// Make the radius smaller iff:

// it is on the left and move<0 or it is on the right and move>0.

  private float[] moveCircle(float[] circle, float[] point1, float[] point2, float move)

    {

    float radius = circle[2];

    if( radius>0 )

      {

      float vx = point2[0]-point1[0];

      float vy = point2[1]-point1[1];

      float wx = circle[0]-point1[0];

      float wy = circle[1]-point1[1];

      boolean left = (wx*vy <= wy*vx);

      float m = left ? move : -move;

      return new float[] {circle[0],circle[1],radius+m};

      }

    else

      {

      if( radius==0 )

        {

        float a = circle[0];

        float m = point2[0]>point1[0] ? -move : move;

        float f = m*((float)Math.sqrt(a*a+1));

        return new float[] {circle[0],circle[1]+f,0};

        }

      else

        {

        float m = point2[1]>point1[1] ? move : -move;

        return new float[] {circle[0]+m,0,-1};

        }

      }

// Compute the 3-tuple describing a 'corner_circle' (i.e. the one which actually makes the corner

// of the sticker round). Format similar to the one in computeCircle() but:

// 1. here if radius=0 then it is a 'nothing', empty circle of radius 0 and not a line

// 2. there is the 4th float: 0 means 'this corner circle's center is inside the sticker (so outside

// of the circle is outside of the sticker), 1 - otherwise. We need this knowledge later on when

// blacking out the outsides of the round corners.

  private void computeCornerCircle(float[] prev_edge_circle, float[] curr_edge_circle,

                                   float[] pvert, float[] cvert, float[] nvert, float radius, float[] output)

    {

    if( radius<=0 )

      {

      output[0] = cvert[0];

      output[1] = cvert[1];

      output[2] = 0;

      output[3] = 0; // ??

      }

    else

      {

      float pdir = computeDir(prev_edge_circle,cvert,pvert);

      float cdir = computeDir(curr_edge_circle,cvert,nvert);

/*

      boolean pl = (cdir<pdir-PI || (cdir>pdir && cdir<pdir+PI));

      boolean cl = (pdir<cdir-PI || (pdir>cdir && pdir<cdir+PI));

      android.util.Log.e("D", "prev edge circle: "+prev_edge_circle[0]+" "+prev_edge_circle[1]+" "+prev_edge_circle[2]);

      android.util.Log.e("D", "from: "+cvert[0]+" "+cvert[1]);

      android.util.Log.e("D", "to  : "+pvert[0]+" "+pvert[1]);

      android.util.Log.e("D", "dir : "+pdir+" left: "+pl);

      android.util.Log.e("D", "curr edge circle: "+curr_edge_circle[0]+" "+curr_edge_circle[1]+" "+curr_edge_circle[2]);

      android.util.Log.e("D", "from: "+cvert[0]+" "+cvert[1]);

      android.util.Log.e("D", "to  : "+nvert[0]+" "+nvert[1]);

      android.util.Log.e("D", "dir : "+cdir+" left: "+cl);

*/

      float tmp = Math.abs(pdir-cdir);

      float diff= Math.abs(PI-tmp);

      if( diff > (17*PI/18) )  // the two consecutive edges are 'almost' parallel, do not round the corner

        {

        output[0] = cvert[0];

        output[1] = cvert[1];

        output[2] = 0;

        output[3] = 0;

        }

      else

        {

        boolean pleft = (cdir<pdir-PI || (cdir>pdir && cdir<pdir+PI));

        boolean cleft = (pdir<cdir-PI || (pdir>cdir && pdir<cdir+PI));

        float[] moved_prev_edge = moveCircle(prev_edge_circle, cvert, pvert, pleft ? radius : -radius);

        float[] moved_curr_edge = moveCircle(curr_edge_circle, cvert, nvert, cleft ? radius : -radius);

        computeIntersection(moved_curr_edge,moved_prev_edge,cvert,output);

        output[2] = radius;

        output[3] = pleft ? 0:1;

/*

        android.util.Log.e("D", "computeCornerCircle pdir="+pdir+" cdir="+cdir);

        android.util.Log.e("D", "prev edge circ: "+prev_edge_circle[0]+" "+prev_edge_circle[1]+" "+prev_edge_circle[2]+" pleft="+pleft);

        android.util.Log.e("D", "moved_prev: "+moved_prev_edge[0]+" "+moved_prev_edge[1]+" "+moved_prev_edge[2]);

        android.util.Log.e("D", "curr edge circ: "+curr_edge_circle[0]+" "+curr_edge_circle[1]+" "+curr_edge_circle[2]+" cleft="+cleft);

        android.util.Log.e("D", "moved_curr: "+moved_curr_edge[0]+" "+moved_curr_edge[1]+" "+moved_curr_edge[2]);

        android.util.Log.e("D", "pvert: "+pvert[0]+" "+pvert[1]);

        android.util.Log.e("D", "cvert: "+cvert[0]+" "+cvert[1]);

        android.util.Log.e("D", "nvert: "+nvert[0]+" "+nvert[1]);

        android.util.Log.d("D", "intersection: "+output[0]+" "+output[1]);

*/

        }

      }

    }

///////////////////////////////////////////////////////////////////////////////////////////////////

// input:

// 1) a 3-tuple representing circles (or possibly a degenerate circle, i.e. straight line)

// in the same format as described in the output of 'computeCircle()'

// 2) another 3-tuple describing the connecting 'corner_circle'. This time if its radius>0, then

// it is a proper corner_circle which makes the respecting corner round. Otherwise the circle is

// not there and the corner stays sharp.

//

// Compute the tangent point (vx,vy) where circle and corner circle touch.

// Output: output[0]=vx, output[1]=vy.

  private void computeInnerVertex(float[] edge_circle, float[] corner_circle, float[] output)

    float cx = corner_circle[0];

    float cy = corner_circle[1];

    float cr = corner_circle[2];

    float ex = edge_circle[0];

    float ey = edge_circle[1];

    float er = edge_circle[2];

    if( er>0 )  // the edge is curved, i.e. edge_circle is a true circle segment and not a line.

      {

      float dx = ex-cx;

      float dy = ey-cy;

      float len = (float)Math.sqrt(dx*dx + dy*dy);

      if( len>0 )

        {

        float b = cr/len;

        if( len<er ) b = -b;  // the corner circle can be inside the edge circle,

                              // then we need to subtract, or outside - then add.

        output[0] = cx + b*dx;

        output[1] = cy + b*dy;

        }

      else

        {

        android.util.Log.e("D", "error in computeInnerVertex: len=0");

        }

      }

    else if( er==0 )  // non-vertical line

      {

      float tmp = ex*ex+1;

      output[0] = (ex*(cy-ey)+cx)/tmp;

      output[1] = (ex*(cx+ex*cy)+ey)/tmp;

      }

    else   // vertical line

      output[0] = ex;

      output[1] = cy;

    //android.util.Log.e("D", "corner c: "+cx+" "+cy+" "+cr+" edge c: "+ex+" "+ey+" "+er+" output: "+output[0]+" "+output[1]);

// black out the outside of the round corner. It is guaranteed to be outside of the sticker.

  private void blackOutCorner(Canvas canvas, Paint paint, int left, int bott, float[] vert1,

                              float[] vert2, float[] vert, float[] circle)

    float v1x = left+(0.5f+vert1[0])*mTexHeight;

    float v1y = bott-(0.5f-vert1[1])*mTexHeight;

    float v2x = left+(0.5f+vert2[0])*mTexHeight;

    float v2y = bott-(0.5f-vert2[1])*mTexHeight;

    float vx  = left+(0.5f+vert[0])*mTexHeight;

    float vy  = bott-(0.5f-vert[1])*mTexHeight;

    float ox  = left+(0.5f+circle[0])*mTexHeight;

    float oy  = bott-(0.5f-circle[1])*mTexHeight;

    float or  = circle[2]*mTexHeight;

    float dx = vx-ox;

    float dy = vy-oy;

    float d  = (float)Math.sqrt(dx*dx+dy*dy);

    float v3x = ox + or*dx/d;

    float v3y = oy + or*dy/d;

    Path path = new Path();

    path.moveTo(v1x,v1y);

    path.lineTo(v3x,v3y);

    path.lineTo(v2x,v2y);

    path.lineTo(vx,vy);

    path.close();

    canvas.drawLine(v1x,v1y,vx,vy,paint);

    canvas.drawLine(v2x,v2y,vx,vy,paint);

    paint.setStrokeWidth(1);

    paint.setStyle(Paint.Style.FILL_AND_STROKE);

    canvas.drawPath(path, paint);

    paint.setStyle(Paint.Style.STROKE);

    }

///////////////////////////////////////////////////////////////////////////////////////////////////

// draw a circle segment from vert1 to vert2. 'circle' describes the center and radius of the segment.

  private void drawCircleSegment(Canvas canvas, Paint paint, int left, int bottom, float[] vert1, float[] vert2, float[] circle)

    {

    float v1x = (0.5f+vert1[0])*mTexHeight;

    float v1y = (0.5f-vert1[1])*mTexHeight;

    float v2x = (0.5f+vert2[0])*mTexHeight;

    float v2y = (0.5f-vert2[1])*mTexHeight;

    float R = circle[2]*mTexHeight;

    if( R>0 )

      {

      float oX = (0.5f+circle[0])*mTexHeight;

      float oY = (0.5f-circle[1])*mTexHeight;

      float startA = computeAngle(oX-v1x, oY-v1y) + PI;

      float stopA  = computeAngle(oX-v2x, oY-v2y) + PI;

      float sweepA = stopA-startA;

      while( sweepA<-PI ) sweepA += 2*PI;

      while( sweepA> PI ) sweepA -= 2*PI;

      //sweepA = -sweepA;

      startA *= 180/PI;

      sweepA *= 180/PI;

//android.util.Log.e("D", "drawing arc ox="+oX+" oy="+oY+" R="+R+" startA="+startA+" sweepA="+sweepA+" stopA="+(stopA*(180/PI)));

//android.util.Log.e("D", "drawing arc v1="+v1x+" , "+v1y+" v2="+v2x+" , "+v2y+" tex: "+mTexHeight);

      canvas.drawArc( left+oX-R, bottom-oY-R, left+oX+R, bottom-oY+R, startA, sweepA, false, paint);

//android.util.Log.e("D", "drawing line from "+v1x+" , "+v1y+" to "+v2x+" , "+v2y);

      canvas.drawLine( left+v1x, bottom-v1y, left+v2x, bottom-v2y, paint);

    }

/*

///////////////////////////////////////////////////////////////////////////////////////////////////

  private void printCircle(float[] circle, String marker)

    {

    String str = "";

    if( circle[2]>0 ) str=" true circle "+circle[0]+" "+circle[1]+" "+circle[2];

    else              str=" line "+circle[0]+" "+circle[1]+" "+circle[2];

    if( circle.length>3 ) str+= (circle[3]==0 ? " INSIDE" : " OUTSIDE");

    android.util.Log.e("D", marker+" "+str);

  private void printVertices(float[][] v, String marker)

    {

    String str = (v[0][0]+","+v[0][1]+" "+v[1][0]+","+v[1][1]);

    android.util.Log.e("D", marker+" "+str);

    }

*/

///////////////////////////////////////////////////////////////////////////////////////////////////

  private void drawEdge(Canvas canvas, Paint paint, int left, int bottom, float[] strokes,

    float[][]     edge_circles = computeCircles(vertices,angles);

    float[][]   corner_circles = new float[length][4];

    float[][][] inner_vertices = computeInnerVertices(edge_circles,vertices,radii,corners,strokes,borders,corner_circles);

    //for(int c=0; c<edge_circles.length; c++) printCircle(edge_circles[c], "EDGE "+c);

    //for(int c=0; c<corner_circles.length; c++) printCircle(corner_circles[c], "CORNER "+c);

    //for(int c=0; c<inner_vertices.length; c++) printVertices(inner_vertices[c], "VERTICES "+c);

    for(int curr=0; curr<length; curr++)

      int next = curr==length-1 ? 0 : curr+1;

      float currStroke = borders*strokes[curr]*mTexHeight;

      float radius     = corner_circles[next][2]*mTexHeight;

      if( currStroke>0 )

        paint.setStrokeWidth(currStroke);

        drawCircleSegment( canvas, paint, left, bottom, inner_vertices[curr][1], inner_vertices[next][0], edge_circles[curr]);

      if( radius>0 )

        {

        float nextStroke = borders*strokes[next]*mTexHeight;

        if( nextStroke<currStroke ) paint.setStrokeWidth(nextStroke);

        drawCircleSegment( canvas, paint, left, bottom, inner_vertices[next][0], inner_vertices[next][1], corner_circles[next]);

        if( corner_circles[next][3]==0 )

          blackOutCorner( canvas, paint, left, bottom, inner_vertices[next][0], inner_vertices[next][1], vertices[next], corner_circles[next] );

        }

///////////////////////////////////////////////////////////////////////////////////////////////////

    //android.util.Log.d("D", "DRAW ROUNDED POLYGONS");

      drawEdge(canvas, paint, left, bottom, strokes[l], vertices[l], ang, radii[l], borders, corners);