我有一个由两个
pointF
定义的线段,以及一个 2D 边界矩形。 我想在两个方向上尽可能地延伸线段,以便该线段与边界框的壁齐平。 以下是我正在尝试做的一些示例:
有人对如何做到这一点有任何建议吗?
这是一个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 -隐式)。
它基于矩形具有与轴平行的线段的假设。
将矩形定义为四条线。
找到您的线与四条线中每条线之间的交点。 (你高中几何学得怎么样?)
在这四个交点中,确定哪些点在矩形的边界内。 (找到 x 和 y 值都在矩形范围内的交点)。
您的算法还必须考虑到以下边缘情况:
一种选择是定义范围在某个变量 t 上的线段的参数表示,然后定义四个线性方程来定义盒子侧面的线(在所有方向上无限延伸)。 这个想法是,当您检查线段与这些线的位置时,对于您可以延伸线段的每个方向,您将获得两个交点 - 一个用于水平交点,一个用于垂直交点。 无论盒子里有哪一个,都将是您想要挑选的。
为此,请计算通过在击中四个边界线之一的每个方向上延伸线段而形成的线的参数 t 的值。 我假设线段被参数化,使得 t ∈ [0, 1]。 然后,您将获得(最多)四个 t 值,对应于线与边界框相交的参数 - 两个值 ≥ 1 表示线在一个方向上的延伸,两个值 ≤ 0 表示线在另一方向上的延伸。 在这四个值中,您要选择 t ≥ 1 的值最小,t ≥ 0 的值最大(这些代表在撞墙之前在每个方向上延伸出最短距离的线的参数) 。 获得这两个参数后,将 t 的值插回到原始参数化中,以生成所需的与墙壁的两个交点,然后将新线段定义为从第一个到第二个的线段。
请注意,此算法更一般地可用于延伸线段以填充任何凸多边形的边界,包括未轴对齐的矩形。 您实际上不需要测试您找到的任何点是否包含在边界框中;您只需查看参数 t 的值即可了解哪些交点更接近线段的端点。
希望这有帮助!
我通过@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]
@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]
改进了 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;
}
}
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(counting_line_start, counting_line_end)
concat_points = [] 对于 bbox_lines 中的 b_l: e = np.cross(b_l, 计数线) 如果 (0 <= e[0] / e[2] <= bbox_width) and (0 <= e[1] / e[2] <= bbox_height): concat_points.append((int(e[0] / e[2]), int(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 points end