延伸线段以适合边界框

Question

我有一个由两个 pointF 定义的线段，以及一个 2D 边界矩形。我想在两个方向上尽可能地延伸线段，以便该线段与边界框的壁齐平。以下是我想做的一些示例：

有人对如何做有任何建议吗这？

Answer 1

下面是 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()

它不会检查线段是否包含在矩形中，并且如果线段位于矩形外部，则也应该起作用（如果没有实际的线段交集，则返回 None -隐式）。

它基于矩形具有与轴平行的线段的假设。

Answer 2

将矩形定义为四条线。

找到您的线与四条线中每条线之间的交点。 （你的高中几何学怎么样？）

在这四个交点中，确定哪些点在矩形的边界内。 （找到 x 和 y 值都在矩形范围内的交点）。

您的算法还必须考虑到以下边缘情况：

• 该线与矩形的垂直或水平边缘平行
• 该线实际上与矩形的一个角相交。

Answer 3

一种选择是定义范围在某个变量 t 上的线段的参数表示，然后定义四个线性方程来定义盒子侧面的线（在所有方向上无限延伸）。这个想法是，当您检查段命中的位置时这些线，对于您可以延伸线段的每个方向，您将获得两个交点 - 一个用于水平交点，一个用于垂直交点。无论盒子里有哪一个，都将是您想要选择的。

为此，请计算通过在击中四个边界线之一的每个方向上延伸线段而形成的线的参数 t 值。我假设线段被参数化，使得 t ∈ [0, 1]。然后，您将获得（最多）四个与线与边界框相交处的参数相对应的 t 值 - 两个值 ≥ 1 表示线在一个方向上的延伸，两个值 ≤ 0 表示线在另一方向上的延伸。在这四个值中，您要选择 t ≥ 1 的值最小，t ≥ 0 的值最大（这些代表在撞墙之前在每个方向上延伸出最短距离的线的参数） 。获得这两个参数后，将 t 的值插回到原始参数化中，以生成所需的与墙壁的两个交点，然后将新线段定义为从第一个线段跨越到第二个线段。

请注意，该算法更一般地可用于延伸线段以填充任何凸多边形的边界，包括未轴对齐的矩形。您实际上不需要测试您找到的任何点是否包含在边界框中；您只需查看参数 t 的值即可了解哪些交点更接近线段的端点。

希望这有帮助！

Answer 4

我通过@tsveti_iko修改了代码，因为当 y_for_xmin 为“无穷大”时（如果 x2 - x1 为 0），int 转换无法正常工作，我遇到了一些问题

import math
extend_line(xmin, ymin, xmax, ymax, x1, y1, x2, y2):
        
        """
        Extend a line so that it reaches the walls of the bbox.

        Args:
            xmin(int): The very left coordinate of the bbox.
            ymin(int): The very top coordinate of the bbox.
            xmax(int): The very right coordinate of the bbox.
            ymax(int): The very bottom coordinate of the bbox.
            x1(int): The start x coordinate of the line.
            y1(int): The start y coordinate of the line.
            x2(int): The end x coordinate of the line.
            y2(int): The end y coordinate of the line.

        Returns:
            - (list): The start and end (x, y) coordinates of the extended line.
        """

        # If we imagine extending the line until it crosses the top wall of the 
        # bbox at point `(xmin, y_for_xmin)` and then imagine drawing 
        # perpendicular lines from each point `(x1, y1)`, `(x2, y2)` to the wall 
        # of the bbox, we end up with 2 perpendicular trianlges with the same 
        # angles - similar triangles. The rule of the similar triangles is that   
        # the side lengths of two similar triangles are proportional. 
        # That's how we get the equal ratios:
        # `| y_for_xmin - y1 | / | xmin - x1 | == | y2 - y1 | / | x2 - x1 |`
        # After we move some numbers from one to the other side of this equation, 
        # we get the value for `y_for_xmin`. That's where the line should cross 
        # the top wall of the bbox. We do the same for all other coordinates.
        # NOTE: These calculations are valid if one starts to draw a line from top 
        # to botton and from left to right. In case the direction is reverted, we 
        # need to switch the min and max for each point (x, y). We do that below.
        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)

        # The line is vertical
        if (x2 - x1) < (y2 - y1):
            # The line is drawn from right to left
            if x1 > x2:
                # Switch the min and max x coordinates for y, 
                # because the direction is from right (min) to left (max)
                y_for_xmin, y_for_xmax = y_for_xmax, y_for_xmin
        # The line is horizontal
        else:
            # The line is drawn from bottom to top
            if y1 > y2:
                # Switch the min and max y coordinates for x,
                # because the direction is from bottom (min) to top (max)
                x_for_ymin, x_for_ymax = x_for_ymax, x_for_ymin

        # The line is drawn from right to left
        if x1 > x2:
            # Get the maximal value for x1.
            # When `x_for_ymin < xmin`(line goes out of the 
            # bbox from the top), we clamp to xmin.
            x1 = max(max(int(x_for_ymin), xmin), x1)
        # The line is drawn from left to right
        else:
            # Get the minimal value for x1.
            # When `x_for_ymin < xmin`(line goes out of the 
            # bbox from the top), we clamp to xmin.
            if math.isinf(x_for_ymin):
                x1 = min(xmin,x1)
            else:
                x1 = min(max(int(x_for_ymin), xmin), x1)

        # Get the maximal value for x2.
        # When `x_for_ymax > xmax` (line goes out of the 
        # bbox from the bottom), we clamp to xmax.
        if math.isinf(x_for_ymax):
            x2 = max(xmax,x2)
        else:
            x2 = max(min(int(x_for_ymax), xmax), x2)

        # Get the minimal value for y1
        # When `y_for_xmin < ymin`(line goes out of the 
        # bbox from the left), we clamp to ymin.
        if math.isinf(y_for_xmin):
            y1 = min(ymin,ymax)
        else:
            y1 = min(max(int(y_for_xmin), ymin), ymax)


        # Get the minimal value for y2
        if math.isinf(y_for_xmin):
            y2 = ymax
        else:
            y2 = min(int(y_for_xmax), ymax)
        # Done
        return [x1, y1, x2, y2]

Answer 5

@andredor 算法的扩展版本，涵盖所有情况（也包括当线段不平行于轴时 - 例如当线段是对角线时）。详细解释该方法作为文档。

def extend_line(xmin, ymin, xmax, ymax, x1, y1, x2, y2):
    """
    Extend a line so that it reaches the walls of the bbox.

    Args:
        xmin(int): The very left coordinate of the bbox.
        ymin(int): The very top coordinate of the bbox.
        xmax(int): The very right coordinate of the bbox.
        ymax(int): The very bottom coordinate of the bbox.
        x1(int): The start x coordinate of the line.
        y1(int): The start y coordinate of the line.
        x2(int): The end x coordinate of the line.
        y2(int): The end y coordinate of the line.

    Returns:
        - (list): The start and end (x, y) coordinates of the extended line.
    """

    # If we imagine extending the line until it crosses the top wall of the 
    # bbox at point `(xmin, y_for_xmin)` and then imagine drawing 
    # perpendicular lines from each point `(x1, y1)`, `(x2, y2)` to the wall 
    # of the bbox, we end up with 2 perpendicular trianlges with the same 
    # angles - similar triangles. The rule of the similar triangles is that   
    # the side lengths of two similar triangles are proportional. 
    # That's how we get the equal ratios:
    # `| y_for_xmin - y1 | / | xmin - x1 | == | y2 - y1 | / | x2 - x1 |`
    # After we move some numbers from one to the other side of this equation, 
    # we get the value for `y_for_xmin`. That's where the line should cross 
    # the top wall of the bbox. We do the same for all other coordinates.
    # NOTE: These calculations are valid if one starts to draw a line from top 
    # to botton and from left to right. In case the direction is reverted, we 
    # need to switch the min and max for each point (x, y). We do that below.
    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)

    # The line is vertical
    if (x2 - x1) < (y2 - y1):
        # The line is drawn from right to left
        if x1 > x2:
            # Switch the min and max x coordinates for y, 
            # because the direction is from right (min) to left (max)
            y_for_xmin, y_for_xmax = y_for_xmax, y_for_xmin
    # The line is horizontal
    else:
        # The line is drawn from bottom to top
        if y1 > y2:
            # Switch the min and max y coordinates for x,
            # because the direction is from bottom (min) to top (max)
            x_for_ymin, x_for_ymax = x_for_ymax, x_for_ymin

    # The line is drawn from right to left
    if x1 > x2:
        # Get the maximal value for x1.
        # When `x_for_ymin < xmin`(line goes out of the 
        # bbox from the top), we clamp to xmin.
        x1 = max(max(int(x_for_ymin), xmin), x1)
    # The line is drawn from left to right
    else:
        # Get the minimal value for x1.
        # When `x_for_ymin < xmin`(line goes out of the 
        # bbox from the top), we clamp to xmin. 
        x1 = min(max(int(x_for_ymin), xmin), x1)

    # Get the maximal value for x2.
    # When `x_for_ymax > xmax` (line goes out of the 
    # bbox from the bottom), we clamp to xmax.
    x2 = max(min(int(x_for_ymax), xmax), x2)

    # Get the minimal value for y1
    # When `y_for_xmin < ymin`(line goes out of the 
    # bbox from the left), we clamp to ymin.
    y1 = min(max(int(y_for_xmin), ymin), ymax)

    # Get the minimal value for y2
    y2 = min(int(y_for_xmax), ymax)

    # Done
    return [x1, y1, x2, y2]

Answer 6

改进了 andredor 的代码 - 添加了线与顶部和底部或左侧和右侧边缘相交时的边缘情况。提供的代码用于处理测试算法。第一个点通过单击鼠标设置，第二个点随着当前鼠标指针位置不断更新。

int px = 100, py = 100;

void setup() {
  size(480, 640);
  background(102);
}

void draw() {
  stroke(255);
  rect(0, 0, 480, 640);
  stroke(100);

  if (mousePressed == true) {
    px = mouseX;
    py = mouseY;
  }
  extendLine(0, 0, 480, 640, px, py, mouseX, mouseY);
}

void extendLine(int xmin, int ymin, int xmax, int ymax, int x1, int y1, int x2, int y2) {
    if (y1 == y2) {
        line(xmin, y1, xmax, y1);
        return;
    }
    if(x1 == x2) {
        line(x1, ymin, x1, ymax);
        return;
    }

    int y_for_xmin = y1 + (y2 - y1) * (xmin - x1) / (x2 - x1);
    int y_for_xmax = y1 + (y2 - y1) * (xmax - x1) / (x2 - x1);

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

    if (ymin <= y_for_xmin && y_for_xmin <= ymax
     && ymin <= y_for_xmax && y_for_xmax <= ymax) {
       line(xmin, y_for_xmin, xmax, y_for_xmax);
       return;
    } else if (ymin <= y_for_xmin && y_for_xmin <= ymax) {
        if (xmin <= x_for_ymax && x_for_ymax <= xmax) {
            line(xmin, y_for_xmin, x_for_ymax, ymax);
            return;
        }
        else if(xmin <= x_for_ymin && x_for_ymin <= xmax) {
            line(xmin, y_for_xmin, x_for_ymin, ymin);
            return;
        }
    } else if (ymin <= y_for_xmax && y_for_xmax <= ymax){
        if (xmin <= x_for_ymin && x_for_ymin <= xmax){
            line(x_for_ymin, ymin, xmax, y_for_xmax);
            return;
        }
        if(xmin <= x_for_ymax && x_for_ymax <= xmax){
            line(x_for_ymax, ymax, xmax, y_for_xmax);
            return;
        }
    } else if (xmin <= x_for_ymin && x_for_ymin <= xmax
     && xmin <= x_for_ymax && x_for_ymax <= xmax) { 
         line(x_for_ymin, ymin, x_for_ymax, ymax);
         return;
    }
}

Answer 7

该脚本将适用于任何给定的线，无论它是如何绘制的

bbox_width = int(bbox_width)
bbox_height = int(bbox_height)

# BBox points
a----b
|    |
d----c

a = np.array([0, 0, 1])
b = np.array([bbox_width, 0, 1])
c = np.array([bbox_width, bbox_height, 1])
d = np.array([0, bbox_height, 1])

# Create lines out of points
lineab = np.cross(a, b)
linebc = np.cross(b, c)
linecd = np.cross(c, d)
lineda = np.cross(d, a)
bbox_lines = [lineab, linebc, linecd, lineda]

# Line inside bbox
x1, y1 = line.x.start, line.y.start # replace with start point of line
x2, y2 = line.x.end, line.y.end # replace with end point of line
line_start = np.array([x1, y1, 1])
line_end = np.array([x2, y2, 1])
line = np.cross(line_start, line_end)

concat_points = []
for b_l in bbox_lines:
    e = np.cross(b_l, line)
    if (0 <= e[0] / e[2] <= bbox_width) and (0 <= e[1] / e[2] <= bbox_height):
        concat_points.append((e[0] / e[2], e[1] / e[2]))
if concat_points:
    concat_points = sorted(concat_points, key=lambda tup: (tup[0], tup[1]))
    x1, y1 = concat_points[0][0], concat_points[0][1] # Concat point start
    x2, y2 = concat_points[1][0], concat_points[1][1] # Concat point end