//
// Line intersection.
// Requires prototype.js 1.6.1 or higher.
//
// Usage:
// 
//   Intersect.lines( [[0,0],[1,1]], [[0,1],[1,0]] ) -->  [0.5, 0.5]
//
// Other examples:
// http://www.kevlindev.com/gui/math/intersection/Intersection.js
// http://workshop.evolutionzone.com/2007/09/10/code-2d-line-intersection/
// http://processingjs.org/learning/custom/intersect
//

// define class (no instance methods):

var Intersect = Class.create();

// Add class methods:

Object.extend(Intersect, {
  NO: 0,         // for now, return '0' whenever there is
  COLLINEAR: 0,  // no intersect. maybe in the future we will distinguish.

  /**
   * Intersect.lines(lineA, lineB) -> Array
   * - lineA (Array): a line in the form [[x,y],[x,y]]
   * - lineB (Array): a line in the form [[x,y],[x,y]]
   * Intersects two lines, returning [x,y] array of the intersecting point.
   * If there is no intersection, 0 is returned.
   * Adapted from http://processingjs.org/learning/custom/intersect
   **/
  lines: function(lineA, lineB) {
    var x, y; // return vars

		var [x1, y1] = lineA[0];
		var [x2, y2] = lineA[1];
		var [x3, y3] = lineB[0];
		var [x4, y4] = lineB[1];

		var a1, a2, b1, b2, c1, c2;
		var r1, r2 , r3, r4;
		var denom, offset, num;

		// Compute a1, b1, c1, where line joining points 1 and 2
		// is "a1 x + b1 y + c1 = 0".
		a1 = y2 - y1;
		b1 = x1 - x2;
		c1 = (x2 * y1) - (x1 * y2);

		// Compute r3 and r4.
		r3 = ((a1 * x3) + (b1 * y3) + c1);
		r4 = ((a1 * x4) + (b1 * y4) + c1);

		// Check signs of r3 and r4. If both point 3 and point 4 lie on
		// same side of line 1, the line segments do not intersect.
		if ((r3 != 0) && (r4 != 0) && Intersect.sameSign(r3, r4)) {
		  return Intersect.NO;
		}

		// Compute a2, b2, c2
		a2 = y4 - y3;
		b2 = x3 - x4;
		c2 = (x4 * y3) - (x3 * y4);

		// Compute r1 and r2
		r1 = (a2 * x1) + (b2 * y1) + c2;
		r2 = (a2 * x2) + (b2 * y2) + c2;

		// Check signs of r1 and r2. If both point 1 and point 2 lie
		// on same side of second line segment, the line segments do
		// not intersect.
		if ((r1 != 0) && (r2 != 0) && (Intersect.sameSign(r1, r2))) {
		  return Intersect.NO;
		}

		// Line segments intersect: compute intersection point.
		denom = (a1 * b2) - (a2 * b1);

		if (denom == 0) {
		  return Intersect.COLLINEAR;
		}

		if (denom < 0) { offset = -denom / 2; } 
		else           { offset = denom / 2; }

		// The denom/2 is to get rounding instead of truncating. It
		// is added or subtracted to the numerator, depending upon the
		// sign of the numerator.
		num = (b1 * c2) - (b2 * c1);
		if (num < 0) { x = (num - offset) / denom; } 
		else         { x = (num + offset) / denom; }

		num = (a2 * c1) - (a1 * c2);
		if (num < 0) { y = ( num - offset) / denom; } 
		else         { y = (num + offset) / denom;  }

		// lines intersect
		return [x, y];
	},


  /**
   * Intersect.lines(line, rect) -> Array
   * - line (Array): a line in the form [[x,y],[x,y]]
   * - rect (Array): a rectangle in the form [[x,y],[x,y]]
   * Intersects a line with a rectangle, returning an array of all the 
   * intersecting points. 
   **/
  lineWithRect: function(line, rect) {
    var results = [];

    var [a1, a2] = line;
    var [r1, r2] = rect;

    var minx,miny,maxx,maxy;
    minx = Math.min(r1[0], r2[0]);
    maxx = Math.max(r1[0], r2[0]);
    miny = Math.min(r1[1], r2[1]);
    maxy = Math.max(r1[1], r2[1]);

    var intersection;

    // bottom edge
    intersection = Intersect.lines([[minx,miny],[maxx,miny]], line);
    if (intersection) results.push(intersection);

    // right edge
    intersection = Intersect.lines([[maxx,miny],[maxx,maxy]], line);
    if (intersection) results.push(intersection);

    // top edge
    intersection = Intersect.lines([[minx,maxy],[maxx,maxy]], line);
    if (intersection) results.push(intersection);

    // left edge
    intersection = Intersect.lines([[minx,miny],[minx,maxy]], line);
    if (intersection) results.push(intersection);

    return results;
  },

  sameSign: function(a, b) { return (( a * b) >= 0); }

});