class Collision
{
  boolean testCollisions  (ArrayList cars)
  {
    for ( int i = 0, sz= cars.size(); i < sz-1; ++i ) {

      Car cur = (Car) cars.get(i);
      for ( int j = i+1; j < sz; ++j )
      {
        Car test = (Car) cars.get(j);
        if (collide (cur,test))
        {
          return true; 
        }
      }

    }

    return false;
  }

  float findCollisionTime (float noEvent, float event, ArrayList cars)
  {
    final float eps = 1e-7; 
    float middle = event;
    int iter =0;

    while (event-noEvent >= eps)
    {
      ++iter;
      middle = 0.5*(noEvent+event);
      for ( int i=0, sz = cars.size(); i < sz; ++i)
        ((Car)cars.get(i)).tmpUpdatePosFromTime(middle);

      if ( testCollisions(cars) )
        event = middle;  
      else
        noEvent = middle;
    }

    return event;
  }

  boolean collide ( Car cur, Car test )
  {
    pt[] border = cur.getCurrentBorder();

    for ( int i =0; i < cur.bordersize; ++i )
    {
      if ( allOnOtherSide (border[i], border[(i+1)%cur.bordersize], test.getCurrentBorder()) )
        return false;
    }
    return true; 
  }

  boolean allOnOtherSide ( pt a, pt b, pt[] testpts )
  {
    pt d = b.makeCopy();
    d.subPt (a);
    d.right();
    float c = d.dot(a);

    for ( int i= 0, sz = Array.getLength(testpts); i <  sz; ++i)
    {
      if (  d.dot(testpts[i]) - c <= 0 )
        return false;
    }

    return true;
  }

  void getCollisionPoints (ArrayList cars, ArrayList results)
  {
    //compute via edge intersection \
    int sz = cars.size();
    for ( int i =0; i < sz-1; ++i)
    {
      for ( int j = i+1; j < sz; ++j )
      {
        Car car1 = (Car) cars.get(i); 
        Car car2 = (Car) cars.get(j);

        pt upl1 = new pt(0,0), botr1 = new pt(0,0), upl2 = new pt(0,0), botr2 = new pt(0,0);
        pt[] pts1 = car1.getCurrentBorderWithRect (upl1, botr1);
        pt[] pts2 = car2.getCurrentBorderWithRect (upl2, botr2);

        if ( rectangleIntersect (upl1,botr1,upl2,botr2) )
        {
          boolean oneEventHandeld = false;
          for ( int k =0; k < car1.bordersize; ++k )
          {
            if (oneEventHandeld) break;

            for ( int l =0; l < car2.bordersize; ++l )
            {
              pt[] interresult = new pt[2];
              float[] locations = new float[2];
              int num = intersectEdges ( pts1[k], pts1[(k+1)%car1.bordersize], pts2[l], pts2[(l+1)%car2.bordersize], interresult, locations);
              if ( num == 2 )
                results.add ( interresult[0].add(interresult[1]).sca(0.5));

              if ( num == 1)
                results.add ( interresult[0] );

              if ( num > 0 )
              {
                results.add (car1);
                results.add (car2);
                // TODO
                if ( num > 1) 
                  results.add ( pts2[(l+1)%car2.bordersize].sub(pts2[l]).left().unit() );
                else
                {
                  float s = locations[0]; 
                  float t = locations[1];
                  if (s > 0.02 && s < 0.98)
                    results.add ( pts1[(k+1)%car1.bordersize].sub(pts1[k]).right().unit() );
                  else if ( t > 0.02 && t < 0.98 )
                    results.add ( pts2[(l+1)%car2.bordersize].sub(pts2[l]).left().unit() );
                  else
                  {
                    // point to point
                    println("bad animation");
                    results.add ( pts2[(l+1)%car2.bordersize].sub(pts2[l]).left().unit() );                       
                  }

                  oneEventHandeld = true;
                  break;

                }
              }                
            }
          }
        } 
      }
    }
  }

  boolean rectangleIntersect (pt upl1,pt botr1,pt upl2,pt botr2)
  {
    if ( upl1.x > botr2.x || botr2.x < upl1.x || upl1.y > botr2.y || botr1.y < upl2.y )
      return false;
    else
      return true; 
  }

  int intersectEdges ( pt a0, pt a1, pt b0, pt b1, pt[] result, float[] locations)
  {
    pt delta = b0.sub(a0);
    pt d0 = a1.sub(a0);
    pt d1 = b1.sub(b0);

    float kross = d0.kross(d1);
    float sqrKross = kross * kross;
    float sqrLen0 = d0.sqrLen();
    float sqrLen1 = d1.sqrLen();
    final float sqrEps = 1e-8f;
    final float eps = 1e-4f;

    if ( sqrKross > sqrEps * sqrLen0 * sqrLen1 )
    {
      // lines are not parallel
      float s = delta.kross(d1) / kross;
      if ( s < -eps || s > 1+eps )
        return 0;

      float t = delta.kross(d0) / kross;
      if ( t < -eps || t > 1+eps )
        return 0;

      locations[0] = s;
      locations[1] = t;
      result[0] = a0.add( d0.sca(s));
      return 1;
    }

    // lines are parallel
    // test if coincident
    kross = delta.kross(d0);
    sqrKross = kross * kross;
    if ( sqrKross > sqrEps * sqrLen0 * delta.sqrLen() )
    {
      // kross not zero --> lines are different
      return 0;
    }

    float s0 = d0.dot(delta) / sqrLen0;
    float s1 = s0 + d0.dot(d1) / sqrLen0;
    float smin = min ( s0, s1); 
    float smax = max ( s0, s1);
    float[] s_hat = new float[2];

    int intersects = intersectInterval ( 0.0, 1.0, smin, smax, s_hat);
    for ( int i =0; i < intersects; ++i )
      result[i] = a0.add(d0.sca(s_hat[i]));
    return intersects;
  }

  int intersectInterval ( float x0, float x1, float y0, float y1, float[] res)
  {
    if ( x1 < y0 || x0 > y1 )
      return 0;
    if ( x1 > y0 ) {
      if ( x0 < y1 ) {
        if ( x0 < y0 ) 
          res[0] = y0;
        else
          res[0] = x0;
        if ( x1 > y1 )
          res[1] = y1;
        else
          res[1] = x1;
        return 2;
      } 
      else {
        // x0 == y1
        res[0] = x0;
        return 1;
      }
    }
    else {
      // x1 == y0
      res[0] = x1;
      return 1;
    }
  }

  void handleCollision ( Car ca, Car cb, pt p, pt n, float t )
  {
    if ( ca.curveControlled )
      ca.detachFromCurve(t);
    if ( cb.curveControlled )
      cb.detachFromCurve(t);

    // change velocity's
    float m = 10000;
    float I = 1.0/12.0 * m *( sq(carSprite.width) + sq(carSprite.height ) );

    float anglediff = ca.curangle - cb.curangle;
    while ( anglediff < 0 ) anglediff += PI/2;
    while ( anglediff > PI/2 ) anglediff -=PI/2;
    
    float e = 1.0;//0.5 + 0.5*cos(anglediff);

    pt r_a = p.sub(ca.center());
    pt r_b = p.sub(cb.center());

    pt k_r_a = r_a.makeCopy();
    k_r_a.left();
    pt k_r_b = r_b.makeCopy();
    k_r_b.left();


    pt p_dot_a = ca.curvelo.add(k_r_a.sca(ca.curanglevelo));
    pt p_dot_b = cb.curvelo.add(k_r_b.sca(cb.curanglevelo));

    pt v_ab = p_dot_a.sub( p_dot_b);
    pt w_1col = new pt ( 2.0/m, 0 );
    pt w_2col = new pt ( 0, 2.0/m );
    w_1col.addPt ( new pt( r_a.y * r_a.y / I, - r_a.x * r_a.y / I ) );
    w_1col.addPt ( new pt( r_b.y * r_b.y / I, - r_b.x * r_b.y / I ) );
    w_2col.addPt ( new pt( - r_a.x*r_a.y/I, r_a.x*r_a.x/I ) );
    w_2col.addPt ( new pt( - r_b.x*r_b.y/I, r_b.x*r_b.x/I ) );

    // invert w
    float detw = w_1col.x * w_2col.y - w_1col.y * w_2col.x; // same as kross
    float tmp = w_1col.x;
    w_1col.x = w_2col.y / detw;
    w_2col.y = tmp / detw;
    w_1col.y /= -detw;
    w_2col.x /= -detw;

    w_1col.mul(v_ab.x);
    w_2col.mul(v_ab.y);
    w_1col.addPt(w_2col);
    pt Q = w_1col.sca ( -(1.0+e) );

    ca.curvelo.addPt ( Q.sca(1.0/m));
    cb.curvelo.subPt ( Q.sca(1.0/m));
    ca.curanglevelo += r_a.kross(Q)/I;
    cb.curanglevelo -= r_b.kross(Q)/I;

   /*
   float v_rel = p_dot_a.sub(p_dot_b).dot(n);
     float eps = 1;
     
     float denom = 2.0/m + (n.dot ( new pt ( -r_a.y * r_a.kross(n), r_a.x * r_a.kross(n) ) ) + n.dot ( new pt ( -r_b.y * r_b.kross(n), r_b.x * r_b.kross(n) ) )) / I;
     float j = v_rel * ( -(1+eps)/denom);
     
     ca.curvelo.addPt ( n.sca( j/m ) );
     cb.curvelo.addPt ( n.sca( j/m ) );
     
     ca.curanglevelo += r_a.kross ( n.sca(j) ) / I;
     cb.curanglevelo += r_b.kross ( n.sca(j) ) / I;
     */
  }

}