TODO optimize: reduce Vector3 creation (each operation) by using instance cache (or by using x,y instead of vector) May be future inspiration : http://www.realtimerendering.com/intersections.html http://www.kevlindev.com/gui/math/intersection/index.htm http://cse.csusb.edu/tong/courses/cs621/notes/intersect.php http://www.gamasutra.com/view/feature/3383/simpleintersectiontestsforgames.php

class IntersectionFinderXY implements IntersectionFinder {
 //with double approximation, use zeroEpsilon for test
 static const zeroEpsilon = 0.0001;

 // cache to avoid re-alloc
 var _v0 = new Vector3.zero();
 var _v1 = new Vector3.zero();
 var _v2 = new Vector3.zero();
 var _mm0 = new MinMax();
 var _mm1 = new MinMax();


//  double length2(Vector3 p0, Vector3 p1) {
//    var x = p1.x - p0.x;
//    var y = p1.y - p0.y;
//    return x*x + y*y;
//  }

 /// implementation from http://stackoverflow.com/questions/563198/how-do-you-detect-where-two-line-segments-intersect
 /// based on Andre LeMothe's ["Tricks of the Windows Game Programming Gurus"](http://rads.stackoverflow.com/amzn/click/0672323699).
 bool segment_segment(Vector3 sa1, Vector3 sa2, Vector3 sb1, Vector3 sb2, Vector4 acol) {
   var sa_x, sa_y, sb_x, sb_y;
   sa_x = sa2.x - sa1.x;     sa_y = sa2.y - sa1.y;
   sb_x = sb2.x - sb1.x;     sb_y = sb2.y - sb1.y;

   var u = (sa_x * sb_y - sb_x * sa_y);
   // u == 0 if segment are parallele, with double approximation, use 0.0001
   //if (u < zeroEpsilon && u > -zeroEpsilon ) return false;
   if (u == 0) return false;

   var s = ( sa_x * (sa1.y - sb1.y) - sa_y * (sa1.x - sb1.x)) / u;
   var t = ( sb_x * (sa1.y - sb1.y) - sb_y * (sa1.x - sb1.x)) / u;

   if (s >= 0 && s <= 1 && t >= 0 && t <= 1) {
     acol.x = sa1.x + (t * sa_x);
     acol.y = sa1.y + (t * sa_y);
     //acol.z = sa1.z;
     acol.w = t;
     return  true;
   }
   return false;
 }


 bool segment_sphere(Vector3 s1, Vector3 s2, Vector3 c, double r){

   var s1c = _v0;
   s1c.setFrom(c).sub(s1);
   var s = _v1;
   s.setFrom(s2).sub(s1);
   var sl2 = s.length2;
   var sp;
   if (sl2 == 0.0) {
     sp = s1;
   } else {
     double u = (s1c.x * s.x + s1c.y *s.y) / sl2; // s1c.dot(s)
     sp = (u < 0.0)? s1 : (u > 1.0) ? s2 : s.scale(u).add(s1);
   }
   var cs = _v2;
   cs.setFrom(c).sub(sp);
   double l2 = cs.length2;

   if (l2 > r * r)
     return false;

//    double l = math.sqrt(l2);
//    var t = (r - l) / l;
//    var coll = cs.scale(t).add(c);
//    ccol.setValues(coll.x, coll.y, coll.z, t);
   return true;

 }

 bool sphere_sphere(Vector3 ca, double ra, Vector3 cb, double rb) {
   var threshold = ra + rb;

   // Get the Cathetus
   var dx = (ca.x - cb.x);
   var dy = (ca.y - cb.y);

   // Calculate the distance
   var dis2 = dx * dx + dy * dy;

   // Returns whether the distance between the two particles is smaller then the sum of both radi
   return (threshold * threshold >= dis2);
 }

 bool aabb_aabb( Aabb3 b1, Aabb3 b2 ) {
   return ( b1.min.x <= b2.max.x) && ( b1.min.y <= b2.max.y )
       && ( b1.max.x >= b2.min.x ) && ( b1.max.y >= b2.min.y);
 }


 // use SAT check intersection (first againts the longer poly (nb of edge))
 // [a] and [b] should be clockwise concave polygone
 bool poly_poly(List<Vector3> a, List<Vector3> b) {
   var separated = false;

   separated = _poly_poly0(a, b);
   separated = separated || _poly_poly0(b, a);
   return !separated;
 }

 bool _poly_poly0(List<Vector3> a, List<Vector3> b) {
   var axis = _v0;
   MinMax amm = _mm0;
   MinMax bmm = _mm1;

   var separated = false;
   for (var i = 0; (!separated) && (i < a.length); i++) {
     // axis is the left normal of the side
     axis.setFrom(a[(i+1) % a.length]).sub(a[i]);
     var t = axis.x;
     axis.x = - axis.y;
     axis.y = t;

     extractMinMaxProjection(a, axis, amm);
     extractMinMaxProjection(b, axis, bmm);
     separated = isSeparated(amm.min, amm.max, bmm.min, bmm.max);
   }
   return separated;
 }
}