Extend a line segment to bounding box

Question

I have two points a and b, and a bounding box at 0,0,w,h. Both points are within the bounding box. How do I extend the line segment created by a and b to find points c and d where the line intersects the box?

*c-------------*
| \            |
|  \           |
|   a          |
|    \         |
|     \        |
|      b       |
|       \      |
*--------d-----*

Answer 1

Get the equation for the line
For each (vertical) side take that X and solve for Y - check if Y is between the top and bottom.
If not then use the horizontal side's Y values and solve for 'X'

Answer 2

Ok, if you're getting it wrong, let's look at an example: Suppose w =6, and h = 5, and suppose the line segment is between (3,4) and (2,1).

y
^
|
6
5------------
4     x     |
3           |
2           |
1   x       |
0 1 2 3 4 5 6 -->x

Let's find the slope,

m = (y2-y1)/(x2-x1) = (4-1)/(3-2) = 3

Now the intercept c where, y = mx + c. Using the first point (2,1),

1 = 3*2 + c => c = -5.

Therefore, the equation of the line is y = 3x -5 or 3x - y - 5 = 0.

Now, plug in the value of the bounding lines using the boundary conditions y>=0 AND y<=5 and x>=0 AND x<=6

x = 0 => 3*0 - y - 5 = 0 => y = -5    --> Out of boundary
y = 0 => 3*x - 0 - 5 = 0 => x = 5/3   --> Within boundary (Intersects bottom line)
x = 6 => 3*6 - y - 5 = 0 => y = 13    --> Out of boundary
y = 5 => 3*x - 5 - 5 = 0 => x = 10/3  --> Within boundary (Intersects top line)

Answer 3

Since the line is straight we know that the gradient is:

gradient = (ax - bx) / (ay - by)

In fact, for any point X, Y on the line:

gradient = (X - bx) / (Y - by)

Rearranging we get the following expressions that allow us to find X given Y or Y given X:

X = (gradient * (Y - by)) + bx

Y = ((X - bx) / gradient) + by

We also have the bounds of the box, call them leftX, rightx, topy and bottomy.

We can work out the points at which the line intersects each of those bounds by using the above equations e.g.

Y = ((leftx - bx) / gradient) + by

gives some value for Y when X = leftx.

The real question is whether this line point is inside the box. In your example, we would get a value of Y larger than topy and so we can conclude that the line doesn't intersect with the left hand edge of the box.

Compute all four intersections points and you'll find only two of them are within the bounds of the box. Those are the two you need. Of course, in the special cases where your points C and D are actually the very corners of the box, your leftx solution will be the same point as your topy solution (in your example: could be leftx and bottomy if the line sloped the other way).

Answer 4

The best way to answer was, for me, to experiment with this topic, as it interests me.

I used Processing for the visual part (and its PVector, but it is trivial in its use here). Basically, it is Java code. I used Wikipedia's Line-line intersection article's formula.

int MARGIN = 10;
int POINT_SIZE = 7;

// Definition of the bouding box
float xMin, xMax;
float yMin, yMax;

// The two points inside the bounding box
// A PVector is just a pair of x and y coordinates
PVector pointA = new PVector();
PVector pointB = new PVector();

// The intersection points
PVector[] pointsI = new PVector[2];

void setup()
{
  size(800, 800);
  MakeBB();
  SetPoints();
  FindIntersections();
}

void draw()
{
  background(#DDFFFF);
  stroke(#FFFF00);
  fill(#8000FF);
  rect(xMin, yMin, xMax - xMin, yMax - yMin);

  noStroke();
  fill(#FF8000);
  ellipse(pointA.x, pointA.y, POINT_SIZE, POINT_SIZE);
  fill(#FF8000);
  ellipse(pointB.x, pointB.y, POINT_SIZE, POINT_SIZE);
  stroke(#FFFF00);
  strokeWeight(5);
  line(pointA.x, pointA.y, pointB.x, pointB.y);

  noStroke();
  fill(#FF0000);
  ellipse(pointsI[0].x, pointsI[0].y, POINT_SIZE * 2, POINT_SIZE * 2);
  fill(#FF0000);
  ellipse(pointsI[1].x, pointsI[1].y, POINT_SIZE * 2, POINT_SIZE * 2);
  stroke(#FF8000);
  strokeWeight(1);
  line(pointsI[0].x, pointsI[0].y, pointsI[1].x, pointsI[1].y);
}

void keyPressed()
{
  MakeBB();
  SetPoints();
  FindIntersections();
}

// Make bounding box
void MakeBB()
{
  xMin = (int) random(MARGIN, width/2);
  xMax = (int) random(width/2, width - MARGIN);
  yMin = (int) random(MARGIN, height/2);
  yMax = (int) random(height/2, height - MARGIN);
}

void SetPoints()
{
  pointA.x = (int) random(xMin, xMax);
  pointA.y = (int) random(yMin, yMax);
  pointB.x = (int) random(xMin, xMax);
  pointB.y = (int) random(yMin, yMax);
}

void FindIntersections()
{
  // The corners of the BB
  PVector pTL = new PVector(xMin, yMin);
  PVector pBL = new PVector(xMin, yMax);
  PVector pTR = new PVector(xMax, yMin);
  PVector pBR = new PVector(xMax, yMax);
  // The sides of the BB
  PVector pT = IntersectLines(pTL, pTR);
  PVector pB = IntersectLines(pBL, pBR);
  PVector pL = IntersectLines(pTL, pBL);
  PVector pR = IntersectLines(pTR, pBR);

  int i = 0;
  // Eliminates the intersection points out of the segments
  if (pT != null && pT.x >= xMin && pT.x <= xMax) pointsI[i++] = pT;
  if (pB != null && pB.x >= xMin && pB.x <= xMax) pointsI[i++] = pB;
  if (pL != null && pL.y >= yMin && pL.y <= yMax) pointsI[i++] = pL;
  if (pR != null && pR.y >= yMin && pR.y <= yMax) pointsI[i++] = pR;
}

// Compute intersection of the line made of pointA and pointB
// with the given line defined by two points
PVector IntersectLines(PVector p1, PVector p2)
{
  PVector pRes = new PVector();
  float v1 = pointA.x * pointB.y - pointA.y * pointB.x;
  float v2 = p1.x * p2.y - p1.y * p2.x;
  float d = (pointA.x - pointB.x) * (p1.y - p2.y) -
      (pointA.y - pointB.y) * (p1.x - p2.x);
  if (d == 0)
  {
    println("Ouch!");
    return null;
  }
  pRes.x = (v1 * (p1.x - p2.x) - (pointA.x - pointB.x) * v2) / d;
  pRes.y = (v1 * (p1.y - p2.y) - (pointA.y - pointB.y) * v2) / d;
  return pRes;
}

It is a quick hack, not optimized and all. But it works... :-)

Answer 5

Funny, last night, I realized that my solution was a bit too generic for the given problem... It is nice to have a generic solution, but for testing against vertical and horizontal lines only, the formulas can be much simpler.

So I wrote a simplified version and came here to show it... to see that the first answer, accepted answer, just stated that! I overlooked the hint, jumping at the more generic solution...

Anyway, as this can be of interest to other visitors, here is the alternative version:

void FindIntersections()
{
  // Test against the sides of the BB
  PVector pT = IntersectHorizontalSegment(yMin, xMin, xMax);
  PVector pB = IntersectHorizontalSegment(yMax, xMin, xMax);
  PVector pL = IntersectVecticalSegment(xMin, yMin, yMax);
  PVector pR = IntersectVecticalSegment(xMax, yMin, yMax);

  int i = 0;
  // Eliminates the non-intersecting solutions
  if (pT != null) pointsI[i++] = pT;
  if (pB != null) pointsI[i++] = pB;
  if (pL != null) pointsI[i++] = pL;
  if (pR != null) pointsI[i++] = pR;
}

PVector IntersectHorizontalSegment(float y, float xMin, float xMax)
{
  float d = pointA.y - pointB.y;
  if (d == 0)
    return null;  // Horizontal line doesn't intersect horizontal segment (unless they have same y)

  float x = -(pointA.x * pointB.y - pointA.y * pointB.x - y * (pointA.x - pointB.x)) / d;
  println("X: " + x);
  if (x < xMin || x > xMax)
    return null;  // Not in segement

  return new PVector(x, y);
}

PVector IntersectVecticalSegment(float x, float yMin, float yMax)
{
  float d = pointA.x - pointB.x;
  if (d == 0)
    return null;  // Vertical line doesn't intersect vertical segment (unless they have same x)

  float y = (pointA.x * pointB.y - pointA.y * pointB.x - x * (pointA.y - pointB.y)) / d;
  println("Y: " + y);
  if (y < yMin || y > yMax)
    return null;  // Not in segement

  return new PVector(x, y);
}

It does less object creations, which is a good thing. In a program calling intensively these routines, I would even avoid object creation altogether (passing around an object for results), as garbage collection can slow down a lot applications where framerate is important (having visible incidence).