//Vector Library
//Michael Chang
//Dated 11/30/2005

vec origin2D=new vec();    //origin is 0,0
//--------------BEGINNING OF VECTOR CLASS OBJECT--------------
class vec
{
  float x;
  float y;
  vec()
  {//constructor with no arguments, gives you origin
    x=0;
    y=0;
  }
  vec(float x,float y)
  {//constructor with 2 arguments x and y
    this.x=x;
    this.y=y;
  }
  vec(vec s)
  {//constructor with vec as input. basically an assignment operator
    if(s==null)
      return;
    this.x=s.x;
    this.y=s.y;
  }  
  vec(vec s,vec t)
  {//constructs a vector from the difference of two vectors
    float dx=t.x-s.x;
    float dy=t.y-s.y;
    this.x=dx;
    this.y=dy;
  }
  vec(vec s,vec t,float k)
  {//constructs a vector from the difference of two vectors, then modifies it by k
    float dx=t.x-s.x;
    float dy=t.y-s.y;
    this.x=dx*k;
    this.y=dy*k;
  }

  //--------------BEGINNING OF VECTOR METHODS--------------  
  void disp(float ang,float magnitude)
  {//displacement. will offset this vector by an angle and distance
    ang=radians(ang);
    x+=cos(ang)*magnitude;
    y-=sin(ang)*magnitude;    
  }
  void rotate(float ang)
  {
    vec temp=new vec();
    temp.disp(ang()+ang,mag());
    x=temp.x;
    y=temp.y;
  }  
  void rotate(vec v,float ang)
  {
    vec cen=new vec(v);
    vec ori=new vec(v,this);
    ori.rotate(180+ang);
    cen.add(ori);
    this.x=cen.x;
    this.y=cen.y;
    return;
  }
  float ang()
  {//returns the angle between this vector and origin
    return getAng(this,origin2D);
  }
  float mag()
  {//returns the distance between this vector and origin
    return dist(origin2D,this);
  }
  //scalar operations
  void add(float s)
  {//addition operator
    x+=s;
    y+=s;
  }
  void sub(float s)
  {//subtraction operator
    x-=s;
    y-=s;
  }
  void mul(float s)
  {//multiplication operator
    x*=s;
    y*=s;
  }
  void div(float s)
  {//division operator. returns 0 when division by zero
    if(s==0)
      return;
    x/=s;
    y/=s;
  }
  void add(float x,float y)
  {//addition operator
    this.x+=x;
    this.y+=y;
  }
  void sub(float x,float y)
  {//subtraction operator
    this.x-=x;
    this.y-=y;
  }
  void mul(float x,float y)
  {//multiplication operator
    this.x*=x;
    this.y*=y;
  }
  void div(float x,float y)
  {//division operator. returns 0 when division by zero
    if(x==0||y==0)
      return;
    this.x/=x;
    this.y/=y;
  }  
  //vector operators
  void add(vec s)
  {//addition operator
    x+=s.x;
    y+=s.y;
  }
  void sub(vec s)
  {//subtraction operator
    x-=s.x;
    y-=s.y;
  }
  void mul(vec s)
  {//multiplication operator
    x*=s.x;
    y*=s.y;
  }
  void div(vec s)
  {//division operator. returns 0 when division by zero
    if(s.x==0||s.y==0)
      return;
    x/=s.x;
    y/=s.y;
  }  
}
//--------------END OF VECTOR OBJECT--------------
//--------------ALTERNATE METHODS OF CONSTRUCTING A VECTOR--------------
vec newVec(vec v,float ang,float magnitude)
{
  vec temp=new vec(v); 
  temp.disp(ang,magnitude);
  return temp;
}

vec newVec(float ang,float magnitude)
{
  ang=radians(ang);
  float tx=cos(ang)*magnitude;
  float ty=sin(ang)*magnitude*-1;
  vec temp=new vec(tx,ty);  
  return temp;
}
vec nv(float x,float y)
{
  return new vec(x,y);
}
vec nv(vec a,vec b)
{
  return new vec(a,b);
}
vec nv(vec v)
{
  return new vec(v.x,v.y);
}

//--------------USEFUL VECTOR TOOLS--------------
//Finds the midpoint between two positions in space
vec midPoint(vec a,vec b)
{
  vec d=new vec(a,b);
  d.mul(.5);
  vec dest=new vec(a);
  dest.add(d);
  //  d.sub(b);
  //  vec newVec=new vec(a);
  //  newVec.add(d);
  return dest;
}

//Finds the average position in an array of points in space
vec avg(vec v[])
{
  vec total=new vec();
  for(int i=0;i<v.length;i++)
  {
    total.add(v[i]);
  }
  total.div(v.length);
  return total;
}

//Using point a as origin, this returns the angle between a and b.
float getAng(vec a,vec b)
{
  float ang=atan2(-1*(b.y-a.y),b.x-a.x);
  ang=degrees(ang);
  if(b.y>a.y)
    return ang=360+ang;
  if(b.y==a.y&&b.x>a.x)
    return ang=0;    
  if(b.y==a.y&&b.x<a.x)
    return ang=180;
  return ang;
}

//Returns the distances between two points in space
float dist(vec a,vec b)
{
  if(a==null||b==null)
    return 0;
  return dist(a.x,a.y,b.x,b.y);
}

//Returns an interpolated point between two points in space, given a ratio
vec lerp(vec a,vec b,float k)
{
  vec n=new vec();
  n.x=lerp(a.x,b.x,k);
  n.y=lerp(a.y,b.y,k);
  return n;
}

//Wraps a point in space from 0 to canvas edge, given a buffer
vec wrap(vec v,float buff)
{
  if(v.x<0-buff)
    v=nv(width/2,height/2);
  if(v.x>width+buff)
    v=nv(width/2,height/2);
  if(v.y<0-buff)
    v=nv(width/2,height/2);
  if(v.y>height+buff)
    v=nv(width/2,height/2);
  return v;
}

//Constrains a point in space from 0 to canvas edge, given a buffer
vec constrain(vec v,float buff)
{
  vec temp=new vec(v);
  temp.x=constrain(temp.x,-buff,width+buff);
  temp.y=constrain(temp.y,-buff,height+buff);
  return temp;
}

//Appends a vector point at the end of a list of vectors
vec[] append(vec v[],vec nv)
{
  vec temp[]=new vec[v.length+1];
  System.arraycopy(v,0,temp,0,v.length);
  temp[v.length]=new vec(nv);
  return temp;  
}

//A segment is an object consisting of two points. This makes a line...
class seg
{
  vec a;
  vec b;
  seg()
  {
    a=new vec();
    b=new vec();
  }
  seg(vec a,vec b)
  {
    this.a=new vec(a);
    this.b=new vec(b);
  }
  float mag()
  {
    return dist(a,b);
  }
}

//Sedgwick's Line Intersection algorithm
//Will return 1 if p1 to p2 to p3 is found to be rotating counter clockwise
int CCW(vec p1, vec p2, vec p3)
{
  float dx1, dx2, dy1, dy2;
  dx1 = p2.x - p1.x; 
  dy1 = p2.y - p1.y;
  dx2 = p3.x - p1.x; 
  dy2 = p3.y - p1.y;
  if (dx1*dy2 > dy1*dx2) return +1;
  if (dx1*dy2 < dy1*dx2) return -1;
  if ((dx1*dx2 < 0) || (dy1*dy2 < 0)) return -1;
  if ((dx1*dx1+dy1*dy1) < (dx2*dx2+dy2*dy2)) 
    return +1;
  return 0;
}

//Given lines A1A2, B1B2, this returns true if they are intersecting
boolean intersect(vec a1, vec a2, vec b1, vec b2)
{  
  return
    ((CCW(a1, a2, b1) != CCW(a1, a2, b2))
    && (CCW(b1, b2, a1) != CCW(b1, b2, a2)));
}

//Given line segment A and B, returns true if found intersecting
boolean intersect(seg a,seg b)
{  
  if(a==null||b==null)
    return false;
  vec a1=a.a;
  vec a2=a.b;
  vec b1=b.a;
  vec b2=b.b;
  return intersect(a1,a2,b1,b2);
}

//Given line segment A and B, returns the point of intersection
vec intersectPoint(seg a,seg b)
{
  vec n=new vec();
  float x1=a.a.x;
  float x2=a.b.x;
  float x3=b.a.x;
  float x4=b.b.x;
  float y1=a.a.y;
  float y2=a.b.y;
  float y3=b.a.y;
  float y4=b.b.y;
  float nd=((y4-y3)*(x2-x1))-((x4-x3)*(y2-y1));
  if(nd==0)
    return a.a;
  float mnx=(((x4-x3)*(y1-y3))-((y4-y3)*(x1-x3)))   /   nd;
  //  float mny=(((x2-x1)*(y1-y3))-((y2-y1)*(x1-x3)))   /   nd;
  float nx=x1+mnx*(x2-x1);
  float ny=y1+mnx*(y2-y1);
  n=new vec(nx,ny);
  return n;
}

//Given line segment A and B, returns the point of intersection
//Alternate method
vec intersectPoint2(seg a,seg b)
{
  vec n=new vec();
  float A1=a.a.x-a.b.x;
  float B1=a.a.y-a.b.y;
  float C1=A1*a.a.x+B1*a.a.y;
  float A2=b.a.x-b.b.x;
  float B2=b.a.y-b.b.y;
  float C2=A2*b.a.x+B2*b.a.y;
  float det=(A1*B2)-(A2*B1);
  if(det==0)
  {
    return new vec();
  }
  else
  {
    n.x=((B2*C1 - B1*C2)/det);
    n.y=((A1*C2 - A2*C1)/det);
  }
  return n;
}

//Normalizes an angle between 0 and 360
float normalize(float a)
{
  if(a>360)
    return a%360;
  if(a<0)
    return 360+(a%360);
  return a;
}

//Wraps a number from mini to maxi
float wrap(float n,float mini,float maxi)
{
  n=n%maxi;
  if(n<mini)
    return maxi-(mini-n);
  if(n>maxi)
    return mini+(n-maxi);
  return n;
}



void ellipse(vec p,float r)
{
  ellipse(p.x,p.y,r,r);
}
void line(vec a,vec b)
{
  line(a.x,a.y,b.x,b.y);
}
void println(vec v)
{
  println("point: "+v.x+","+v.y);
}
void curvevec3ex(vec v)
{
  curveVertex(v.x,v.y);
}
void bezier(vec a,vec b,vec c,vec d)
{
  bezier(a.x,a.y,b.x,b.y,c.x,c.y,d.x,d.y);
}
vec bezierPoint(vec a,vec b,vec c,vec d,float t)
{
  float nx=bezierPoint(a.x,b.x,c.x,d.x,t);
  float ny=bezierPoint(a.y,b.y,c.y,d.y,t);  
  //  float ny=bezierPoint(a.z,b.z,c.z,d.z,t);    
  return new vec(nx,ny);
}
void vertex(vec v)
{
  vertex(v.x,v.y);
}
void translate(vec v)
{
  translate(v.x,v.y);
}

void drawArrow(vec p1,vec p2)
{
  vec corner=new vec(0,0);
  vec bLeft=new vec(newVec(140,6));
  vec bRight=new vec(newVec(220.0,6.0));
  float heading=radians(360-getAng(p1,p2));  
  pushMatrix();
  //  line(p1.x,p1.y,p2.x,p2.y);
  translate(p2.x,p2.y);
  rotate(heading);
  beginShape(POLYGON);
  vertex(corner.x,corner.y);
  vertex(bLeft.x,bLeft.y);
  vertex(bRight.x,bRight.y);
  endShape();
  popMatrix();
}
void drawArrowL(vec p1,vec p2)
{
  vec corner=new vec(0,0);
  vec bLeft=newVec(140,6);
  float d=cos(degrees(140))*6;
  vec center=newVec(0,d);
  //  vec bRight=new vec(newVec(220.0,6.0));
  float heading=radians(360-getAng(p1,p2));  
  pushMatrix();
  //  line(p1.x,p1.y,p2.x,p2.y);
  translate(p2.x,p2.y);
  rotate(heading);
  beginShape(POLYGON);
  vertex(corner);
  vertex(bLeft);
  vertex(center);
  endShape();
  popMatrix();
}






void stippleLine(vec loc[],float k)
{
  boolean switcher=true;
  vec nvtl=null;
  vec nvt=null;
  for(float i=0;i<=1;i+=k/100)
  {  
    nvtl=nvt;
    nvt=findNormalPoint(loc,i);
    switcher=!switcher;
    if(switcher&&i>0)
      line(nvtl,nvt);
  }  
}


vec findNormalPoint(vec loc[],float k)
{
  if(loc==null||loc.length==0)
    return new vec();
  if(loc.length==1)
    return loc[0];
  float totalD=0;
  for(int i=1;i<loc.length;i++)
    totalD+=dist(loc[i-1],loc[i]);


  float searchDistance=totalD*k;
  float curDistance=0;
  vec nvec3=new vec();
  for(int i=0;i<=loc.length-1;i++)
  {
    float nd=dist(loc[i],loc[i+1]);
    if(curDistance+nd>searchDistance)
    {
      float distanceLeft=searchDistance-curDistance;
      float k2=distanceLeft/nd;
      nvec3=lerp(loc[i],loc[i+1],k2);
      break;
    }
    else
      curDistance+=nd;
  }
  return nvec3;
}