Extending a line segment to fit into a bounding box

Here is an code example in python:

def extend(xmin, ymin, xmax, ymax, x1, y1, x2, y2):
    if y1 == y2:
        return (xmin, y1, xmax, y1)
    if x1 == x2:
        return (x1, ymin, x1, ymax)

    # based on (y - y1) / (x - x1) == (y2 - y1) / (x2 - x1)
    # => (y - y1) * (x2 - x1) == (y2 - y1) * (x - x1)
    y_for_xmin = y1 + (y2 - y1) * (xmin - x1) / (x2 - x1)
    y_for_xmax = y1 + (y2 - y1) * (xmax - x1) / (x2 - x1)

    x_for_ymin = x1 + (x2 - x1) * (ymin - y1) / (y2 - y1)
    x_for_ymax = x1 + (x2 - x1) * (ymax - y1) / (y2 - y1)

    if ymin <= y_for_xmin <= ymax:
        if xmin <= x_for_ymax <= xmax:
            return (xmin, y_for_xmin, x_for_ymax, ymax)
        if xmin <= x_for_ymin <= xmax:
            return (xmin, y_for_xmin, x_for_ymin, ymin)
    if ymin <= y_for_xmax <= ymax:
        if xmin <= x_for_ymin <= xmax:
            return (x_for_ymin, ymin, xmax, y_for_xmax)
        if xmin <= x_for_ymax <= xmax:
            return (x_for_ymax, ymax, xmax, y_for_xmax)

def test():
    assert (2, 1,  2, 5) == extend(1, 1,  5, 5,  2, 3,  2, 4)
    assert (1, 2,  4, 5) == extend(1, 1,  5, 5,  2, 3,  3, 4)
    assert (1, 3,  5, 3) == extend(1, 1,  5, 5,  3, 3,  4, 3)
    assert (1, 1,  5, 5) == extend(1, 1,  5, 5,  2, 2,  3, 3)
    assert (3, 1,  5, 5) == extend(1, 1,  5, 5,  3.5, 2,  4, 3)

if __name__ == '__main__':
    test()

It doesn't check that the segment is contained in the rectangle and should work also if it is exterior to it (returns None -implicit- if there is no actual segment intersection).

It is based on the assumption that the rectangle has the segments parallel with the axes.

Define the rectangle as four lines.

Find the intersection between your line and each of the four lines. (How's your highschool geometry?)

Of these four intersection points, determine which points are within the bounds of the rectangle. (find the intersection points where both the x and y values are within the rectangles range).

Your algorithm must also allow for the following edge cases:

• The line is parallel with either the vertical of horizontal edge of the rectangle
• The line actually intersects with a corner of the rectangle.

One option would be to define a parametric representation of the line segment ranging over some variable t, then to define four linear equations defining the lines on the side of the box (extended infinitely in all directions). The idea is that when you check where the segment hits these lines, for each direction you could extend the segment, you'll get two intersection points - one for the horizontal intersection and one for the vertical intersection. Whichever of these lies inside the box will be the one that you want to pick.

To do this, compute values of the parameter t of the line formed by extending the segment in each direction where you hit one of the four bounding lines. I assume that the line segment is parameterized such that t ∈ [0, 1]. You will then get (up to) four values of t corresponding to parameters where the line intersects the bounding box - two values ≥ 1 representing extensions of the line in one direction and two values ≤ 0 representing extensions of the line in the other direction. Of these four values, you want to choose the value of t ≥ 1 that's the smallest and the value of t ≥ 0 that's the greatest (these represent the parameters of the line that extend out the shortest distance in each direction before hitting the wall). Once you have these two parameters, plug the values of t back into the original parameterization to yield the two intersection points you want with the walls, then define the new line segment to be one that spans from the first of these to the second.

Note that this algorithm more generally can be used to extend the line segment to fill the bounds of any convex polygon, including rectangles that aren't axis-aligned. You never actually need to test whether any of the points you find are contained in the bounding box; you just look at the value of the parameter t to see which of the intersection points are closer to the endpoints of your segment.

Hope this helps!