//Sedgwick's Line Intersection algorithm
//Will return 1 if p1 to p2 to p3 is found to be rotating counter clockwise
int CCW(vec2 p1, vec2 p2, vec2 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(vec2 a1, vec2 a2, vec2 b1, vec2 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;
  vec2 a1=a.a;
  vec2 a2=a.b;
  vec2 b1=b.a;
  vec2 b2=b.b;
  return intersect(a1,a2,b1,b2);
}