如何连接点和吸收动量？
How to connect points and absorbing momentum?
我目前正在使用像 this. The device receives a list of 2D points which is then displayed. Internally there's a galvanometer 这样的表演激光设备，它控制反射镜以投射激光点。
假设我要显示 5 个激光点（A、B、C、D、E）。由于激光设备不喜欢在短时间间隔内行进很远的距离，因此必须添加中间点，称为消隐点（激光在沿着这些消隐点行进时关闭）。这个程序达到了不给检流计太大压力的目的。
我目前正在使用简单的 Nearest Neighbor algorithm 计算 5 个点之间的 "shortest path"，最后是直线空白线（下图中的红色虚线）。
我通过这个优化已经取得了很好的效果。但我想更进一步。振镜在移动时具有一定的物理动量。急转弯时，例如从 C->D 和 D->E 行进，它确实强调了激光设备。
所以我正在考虑通过引入弯曲的消隐线而不是直的消隐线来吸收一些这种物理动量（与上图中的最后一张图 "Solution?" 比较）。
知道如何实现吗？
指向一些算法资源 and/or 一些伪代码或 C# 会有所帮助。谢谢！
正如其他人提到的，您想为此使用某种三次样条插值。
一旦知道访问每个关键点的时间以及每个点的速度，就可以计算以所选速度通过关键点的分段三次 Hermite 样条。参见：https://en.wikipedia.org/wiki/Cubic_Hermite_spline
由于您对速度没有任何特殊要求，您可能想使用经典的三次样条（是的，这些东西的名称不明确）：http://mathworld.wolfram.com/CubicSpline.html 这种形式的样条决定了速度确保一阶导数（速度）和二阶导数（加速度）在整个路径上平滑变化。
由于您对到达每个关键点的确切时间也没有任何特殊要求，您可能希望为整个路径设置最大时间，然后选择关键点的时间以最小化最大加速度或类似的东西。我没有真正简单的方法来做到这一点。我会尝试的是：
最初，使关键点之间的时间与这些点之间的距离成正比。然后，应用几轮：
- 调整每段时间，使关键点的切向加速度为0
- 重新计算样条
不过，如果没有这些优化轮次，您可能会非常高兴 -- 最初的猜测不会太糟糕。
我认为你正在处理的是 Traveling-Salesman-Problem(TSP) (here the slide of a Phd course which talk about how to try to solve it) 并且最小化激光器上的应力的路径是最小化力和移动它所需的力的变化的路径因此它是曲率最小的路径，所以我认为最好的办法是用圆弧圆角化 3 对点之间的路径。
可以找到有关如何计算通过 3 个点的圆的参数的示例 here
我的 C# 不是很流利，所以我会在 Python 中添加一个实现，希望你也觉得它有用。
我的想法是，对于点 A、B、C 的每个三元组，我找到经过这 3 个点的圆弧，该圆弧将是连接 B 和 C 的路径。
我还没有时间测试这个，所以可能有一些错误的标志。
# Initial points
points = [(1,1),(2,3),(5,3),(-4.1),(12,3)]
#List of point in the order find by the solution of the TSP
spl = tsp_solve(points) # generic function to solve the TSP
# Append the first two point of the list so that I can iterate over the list
# and parse every triplet of points in the same way.
spl = spl + spl[:2]
# The list where will be added every path that connect the points
paths = []
# For each tirplets of sequential points
for A,B,C in zip(spl[:-2],spl[1:-1],spl[2:]):
# Calculate the angular coefficent of the two line that pass on A,B and B,C
coeff_ab = (B[1] - A[1]) / (B[0] - A[0])
coeff_bc = (C[1] - B[1]) / (C[0] - B[0])
# If the two line have the same coeff then all the 3 point are on the same line
# and therfore the best path is that line.
if(coeff_ab == coeff_bc):
offset_y = A[1] - coeff_ab * A[0]
delta_x = C[0] - B[0]
paths.append({"type":"Line","coeff":coeff_ab,"offset_y":offset_y,"deta_x":delta_x})
continue
# Calculate the x of the center of the circle
center_x = coeff_ab *coeff_bc *(C[0]-A[0])
center_x += coeff_ab *(B[0]+C[0])
center_x -= coeff_bc *(A[0]+B[0])
center_x /= 2*(coeff_ab - coeff_bc)
# Calculate the y of the center of the circle
center_y = (A[1]+B[1)/2
center_y -= (center_x - (A[0] + B[0])/2)
center_y /= coeff_bc
radius = sqrt(center_x**2 + center_y**2)
paths.append({"type":"Circle","Radius":radius,"center_x":center_x,"center_y":center_y})
# Function To Calculate the X and Y of the lines and circles.
def calculate_circle_x(circle,time):
"""Function that return the x of a circle at a given time"""
time = time + circle["time_off"]
return circle["radius"] * cos(2*pi*time) + circle["center_x"]
def calculate_circle_y(circle,time):
"""Function that return the y of a circle at a given time"""
time = time + circle["time_off"]
return circle["radius"] * sin(2*pi*time) + circle["center_y"]
def calculate_line_x(line,time):
"""Function that return the x of a line at a given time"""
time = (line['delta_x']*time) + line["time_off"]
return time
def calculate_line_y(line,time):
"""Function that return the y of a line at a given time"""
time = (line['delta_x']*time) + line["time_off"]
return time * line["coeff"] + line['offset_y']
def calculate_x(obj,time):
"""Function that return the x of whatever it's passed"""
if(obj['type'] == 'Circle'):
return calculate_circle_x(obj,time)
else:
return calculate_line_x(obj,time)
def calculate_y(obj,time):
"""Function that return the y of whatever it's passed"""
if(obj['type'] == 'Circle'):
return calculate_circle_y(obj,time)
else:
return calculate_line_y(obj,time)
# Calculate some sample of the global path to plot it or do whatever with it.
number_of_sample = 100000
path_points = []
number_of_paths = len(paths)
# Calculate some time equidistant point's sample
for i in range(number_of_sample):
# Calculate the global time
global_time = i*number_of_paths/number_of_sample
# Calculate in which path the point it is
path_number = int(global_time)
# Calculate which time of the path it is
local_time = global_time - path_number
path = paths[path_number]
# Calculate the sampled point
new_point = (calculate_x(path,local_time),calculate_y(path,local_time))
# Add the sampled point to the path_points list
path_points.append(new_point)
# Print the result of the path point sampled.
print(path_points)
现在您已经掌握了分数或至少有了关于如何计算分数的示例，您可以将其转换为 C#。我试着对它进行了很多评论，这样你即使不知道也能理解它 Python.
我目前正在使用像 this. The device receives a list of 2D points which is then displayed. Internally there's a galvanometer 这样的表演激光设备，它控制反射镜以投射激光点。
假设我要显示 5 个激光点（A、B、C、D、E）。由于激光设备不喜欢在短时间间隔内行进很远的距离，因此必须添加中间点，称为消隐点（激光在沿着这些消隐点行进时关闭）。这个程序达到了不给检流计太大压力的目的。
我目前正在使用简单的 Nearest Neighbor algorithm 计算 5 个点之间的 "shortest path"，最后是直线空白线（下图中的红色虚线）。
我通过这个优化已经取得了很好的效果。但我想更进一步。振镜在移动时具有一定的物理动量。急转弯时，例如从 C->D 和 D->E 行进，它确实强调了激光设备。
所以我正在考虑通过引入弯曲的消隐线而不是直的消隐线来吸收一些这种物理动量（与上图中的最后一张图 "Solution?" 比较）。
知道如何实现吗？
指向一些算法资源 and/or 一些伪代码或 C# 会有所帮助。谢谢！
正如其他人提到的，您想为此使用某种三次样条插值。
一旦知道访问每个关键点的时间以及每个点的速度，就可以计算以所选速度通过关键点的分段三次 Hermite 样条。参见：https://en.wikipedia.org/wiki/Cubic_Hermite_spline
由于您对速度没有任何特殊要求，您可能想使用经典的三次样条（是的，这些东西的名称不明确）：http://mathworld.wolfram.com/CubicSpline.html 这种形式的样条决定了速度确保一阶导数（速度）和二阶导数（加速度）在整个路径上平滑变化。
由于您对到达每个关键点的确切时间也没有任何特殊要求，您可能希望为整个路径设置最大时间，然后选择关键点的时间以最小化最大加速度或类似的东西。我没有真正简单的方法来做到这一点。我会尝试的是：
最初，使关键点之间的时间与这些点之间的距离成正比。然后，应用几轮：
- 调整每段时间，使关键点的切向加速度为0
- 重新计算样条
不过，如果没有这些优化轮次，您可能会非常高兴 -- 最初的猜测不会太糟糕。
我认为你正在处理的是 Traveling-Salesman-Problem(TSP) (here the slide of a Phd course which talk about how to try to solve it) 并且最小化激光器上的应力的路径是最小化力和移动它所需的力的变化的路径因此它是曲率最小的路径，所以我认为最好的办法是用圆弧圆角化 3 对点之间的路径。
可以找到有关如何计算通过 3 个点的圆的参数的示例 here
我的 C# 不是很流利，所以我会在 Python 中添加一个实现，希望你也觉得它有用。
我的想法是，对于点 A、B、C 的每个三元组，我找到经过这 3 个点的圆弧，该圆弧将是连接 B 和 C 的路径。
我还没有时间测试这个，所以可能有一些错误的标志。
# Initial points
points = [(1,1),(2,3),(5,3),(-4.1),(12,3)]
#List of point in the order find by the solution of the TSP
spl = tsp_solve(points) # generic function to solve the TSP
# Append the first two point of the list so that I can iterate over the list
# and parse every triplet of points in the same way.
spl = spl + spl[:2]
# The list where will be added every path that connect the points
paths = []
# For each tirplets of sequential points
for A,B,C in zip(spl[:-2],spl[1:-1],spl[2:]):
# Calculate the angular coefficent of the two line that pass on A,B and B,C
coeff_ab = (B[1] - A[1]) / (B[0] - A[0])
coeff_bc = (C[1] - B[1]) / (C[0] - B[0])
# If the two line have the same coeff then all the 3 point are on the same line
# and therfore the best path is that line.
if(coeff_ab == coeff_bc):
offset_y = A[1] - coeff_ab * A[0]
delta_x = C[0] - B[0]
paths.append({"type":"Line","coeff":coeff_ab,"offset_y":offset_y,"deta_x":delta_x})
continue
# Calculate the x of the center of the circle
center_x = coeff_ab *coeff_bc *(C[0]-A[0])
center_x += coeff_ab *(B[0]+C[0])
center_x -= coeff_bc *(A[0]+B[0])
center_x /= 2*(coeff_ab - coeff_bc)
# Calculate the y of the center of the circle
center_y = (A[1]+B[1)/2
center_y -= (center_x - (A[0] + B[0])/2)
center_y /= coeff_bc
radius = sqrt(center_x**2 + center_y**2)
paths.append({"type":"Circle","Radius":radius,"center_x":center_x,"center_y":center_y})
# Function To Calculate the X and Y of the lines and circles.
def calculate_circle_x(circle,time):
"""Function that return the x of a circle at a given time"""
time = time + circle["time_off"]
return circle["radius"] * cos(2*pi*time) + circle["center_x"]
def calculate_circle_y(circle,time):
"""Function that return the y of a circle at a given time"""
time = time + circle["time_off"]
return circle["radius"] * sin(2*pi*time) + circle["center_y"]
def calculate_line_x(line,time):
"""Function that return the x of a line at a given time"""
time = (line['delta_x']*time) + line["time_off"]
return time
def calculate_line_y(line,time):
"""Function that return the y of a line at a given time"""
time = (line['delta_x']*time) + line["time_off"]
return time * line["coeff"] + line['offset_y']
def calculate_x(obj,time):
"""Function that return the x of whatever it's passed"""
if(obj['type'] == 'Circle'):
return calculate_circle_x(obj,time)
else:
return calculate_line_x(obj,time)
def calculate_y(obj,time):
"""Function that return the y of whatever it's passed"""
if(obj['type'] == 'Circle'):
return calculate_circle_y(obj,time)
else:
return calculate_line_y(obj,time)
# Calculate some sample of the global path to plot it or do whatever with it.
number_of_sample = 100000
path_points = []
number_of_paths = len(paths)
# Calculate some time equidistant point's sample
for i in range(number_of_sample):
# Calculate the global time
global_time = i*number_of_paths/number_of_sample
# Calculate in which path the point it is
path_number = int(global_time)
# Calculate which time of the path it is
local_time = global_time - path_number
path = paths[path_number]
# Calculate the sampled point
new_point = (calculate_x(path,local_time),calculate_y(path,local_time))
# Add the sampled point to the path_points list
path_points.append(new_point)
# Print the result of the path point sampled.
print(path_points)
现在您已经掌握了分数或至少有了关于如何计算分数的示例，您可以将其转换为 C#。我试着对它进行了很多评论，这样你即使不知道也能理解它 Python.