Code Golf: Calculating the intersection between Box and Line

Question

The challenge

Given you have the coordinates of a rectangle and a line in 2D space, and they may or may not intersect, write a function that calculates the intersection.

Here is an example of an intersection in glorious ASCII art:

    +-------------+
    |             |
    |             |
----*-------      |
    |             |
    |             |
    +-------------+

intersection between line and box is at '*'

The rectangle is axis aligned. So the function signature is something like this in pseudo code:

function calculateIntersection(Line l, Rectangle b)

Where the rectangle and the line has the following data:

Line: 
    Point from
    Point to
Rectangle:
    Point p // upper right corner
    int width
    int height

Here is one test, the line and rectangle should intersect:

Line:
    from 0,0
    to 2,2
Rectangle:
    from 1,0
    width 3
    height 3

Output: intersection is at 1,1

Answer 1

Since a rectangle is a polygon, you can just use the answer from this question: http://stackoverflow.com/questions/1119451/how-to-tell-if-a-line-intersects-a-polygon-in-c

Answer 2

Write the line segment (not line!) as y = m*x + b

    y2 - y1
m = -------
    x2 - x1

b = (-m * x) + y

Your box is nothing more than 4 line segments. Loop through those four line segments and check if one of them intersects with your single line segement: Rough pseudo code:

LineSegment {

  Point p1
  Point p2  
  double m
  double b

  // ...

  Point intersection(LineSegment that)  {

    if(this.p1 == that.p1 || this.p1 == that.p2) return this.p1
    if(this.p2 == that.p1 || this.p2 == that.p2) return this.p2

    xIntersection = (that.b - this.b) / (this.m - that.m)
    yIntersection = (this.m * xIntersection) + this.b

    Point p = new Point(xIntersection, yIntersection)
    if(!this.liesOnSegment(p) || !that.liesOnSegment(p)) return null
    return p 
  }
}

The 'liesOnSegment' function shouldn't pose a problem, I assume.

Answer 3

I have a solution for a similar problem: does a line intersect a rectangle's area anywhere? Here's my lightly-tested solution in C++ (508 characters):

#include <iostream>
#define P {a=*p++-'a';b=*p++-'a';}
#define S l[8]=l[a];l[a]=l[b];l[b]=l[8];
#define s {P S}
#define c {P if (l[a]>=l[b]) {S}}
#define g if(({P l[a]>=l[b];}))
#define h(d) {g d else p+=2;}
#define m {P *i++=l[a]-l[b];}
#define t {P l[a]*=l[b];}
main(void) {double l[17],*i=l;int j=8,a,b;while (j--)std::cin >> *i++;char*p=
"aaaaegfhdbcaeagafbhbjkmnjlopmknkolplpmnoacbdgahbcedf";m m c c m m m m m m h(s)
h(s) t t t t g g {c c g g g g j=0;}printf("Line is %sin rectangle\n", j?"not ":
"");}

The input format is lx0 ly0 lx1 ly0 rx0 ry0 rx1 ry1 (8 double-precision floats with whitespace in between). It can be tested with the following script:

#!/bin/sh
g++ line_rect_intersect.cpp -o line_rect_intersect
while read i ; do
    echo $i | ./line_rect_intersect
done<<heredoc
-1 -1 -.1 -.1 0 0 1 2
0.9 0.8 1.4 -.2 0 0 1 2
0.1 1.9 0.9 1.1 0 0 2 1
0.1 1.9 0.9 1.1 0 0 1 2
heredoc

This code is based off of a routine I wrote for my game OpenRider ( http://www.funsitelots.com/pub/openrider-0.1-win32.zip ):

bool LineReallyInBox(double l0x, double l0y, double l1x, double l1y, double r0x, double r0y, double r1x, double r1y)
{
   double j,k,m,n,p,q;
   double tmp;
   #define swap(a,b) {tmp=a; a=b; b=tmp;}
   if (r0x>r1x)
      swap(r0x, r1x);
   if (r0y>r1y)
      swap(r0y, r1y);
   j = l1y-l0y;
   k = l1x-l0x;
   m = r0x-l0x;
   n = r1x-l0x;
   p = r0y-l0y;
   q = r1y-l0y;
   if (j<0)
      swap(n,m);
   if (k<0)
      swap(p,q);
   if (j*m<=k*q && j*n>=k*p) {
      //The infinite-length line parallel to the line in question intersects, but we need to
      // make sure that the line terminated at the given points actually makes it to the rectangle
      //We do that by checking for intersection of the box of the line and the rectangle
      if (l0x>l1x)
         swap(l0x, l1x);
      if (l0y>l1y)
         swap(l0y, l1y);
      if (l0x<=r1x && l0y<=r1y && r0x<=l1x && r0y<=l1y)
         return true;
      return false;
   }
   return false;
   #undef swap
}