将线段延长以适应边界框

Question

将线段延长以适应边界框

algorithmmathc#-3.0linecomputational-geometry

9

我有两个PointF定义的线段和一个二维边界矩形。我想将线段尽可能地向两个方向延伸，以使线段与边界框的墙壁相齐。以下是一些示例：

有没有人有关于如何做到这一点的建议？

- AMH

4

盒子的边是否始终平行于x和y轴？还是有时候会倾斜一些角度？ - Jean-François Corbett

图片链接不正确。 - Andrei

6个回答

4

将矩形定义为四条线。

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

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

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

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

- Andrew Shepherd

2

我修改了@tsveti_iko的代码，因为当y_for_xmin为“无穷大”（如果x2-x1为0）时，整数转换不起作用。

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]

- Tycon

2

一种选项是定义一个参数表示线段，该线段在某个变量t上范围内变化，然后定义四条线性方程来定义盒子两侧的线（在所有方向上无限延伸）。想法是当你检查线段与这些线的相交点时，对于每个方向你可以延长线段，你会得到两个交点-一个为水平交点，一个为垂直交点。任何一个在盒子内的交点都是你想选择的。

为了实现这个功能，需要计算线段在每个方向上延伸时与四条边界线相交的参数 t 的值。假设线段被参数化，使得 t ∈ [0,1]。你将获得（最多）四个 t 值，分别对应于线段与边框相交的参数，其中两个值 ≥ 1 表示向一侧延伸的线段的扩展，而两个值 ≤ 0 则表示向另一侧延伸的线段的扩展。在这四个值中，你需要选择 t ≥ 1 的最小值和 t ≥ 0 的最大值（它们分别表示在撞墙前沿着每个方向延伸的线段的参数）。一旦你获得了这两个参数，就将 t 的值带回原始参数化公式中，得到你想要与墙相交的两个点，然后定义新的线段从第一个点到第二个点。

请注意，这种算法更普遍地可以用于扩展线段以填充任何凸多边形的边界，包括非轴对齐的矩形。你实际上不需要测试找到的任何点是否包含在边框内；你只需查看参数 t 的值，以确定哪些相交点更接近线段的端点。

希望这有所帮助！

- templatetypedef

1

一种扩展版的@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]

- tsveti_iko

0

改进了andredor的代码 - 添加了当线段与顶部和底部或左侧和右侧边缘相交时的边界情况。提供的代码是为了测试该算法而编写的Processing代码。第一个点由单击鼠标设置，第二个点会随着当前鼠标指针位置的更新而不断更新。

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;
    }
}

- rohanr22

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- andredor · Accepted Answer

这里是一个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）。

此代码基于矩形的线段与坐标轴平行的假设。