algorithmmathc#-3.0linecomputational-geometry

Extending a line segment to fit into a bounding box


I have a line segment defined by two pointFs, along with a 2D bounding rectangle. I want to extend the line segment as much as possible in both directions so that the segment is flush with the walls of the bounding box. Here are some examples of what I'm trying to do:

enter image description here

Does anyone have any suggestions on how to do this?


Solution

  • 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.