1

I am currently working with a show laser device like this. The device receives a list of 2D points which is then displayed. Internally there's a galvanometer that controls the mirror for projecting the laser points.

Let's say I want to display 5 laser points (A, B, C, D, E). Since the laser device doesn't like to travel long distances within short time intervals, one has to add intermediate points, called blanking points (the laser is off while traveling along these blanking points). This procedure is fulfilling the purpose of not stressing the galvanometer too much.

I am currently calculating the "shortest path" in between the 5 points with a simple Nearest Neighbor algorithm, ending up with straight blanking lines (red dotted line in following illustration).

enter image description here

I achieve already quite good results with this optimization. But I want to go a step further. The galvanometer has some physical momentum when moving. When doing sharp turns, e.g. travelling from C->D and D->E, it does stress the laser device.

So I was thinking about absorbing some of this physical momentum by introducing curved blanking lines instead of straight blanking lines (cp. to last image in above illustration "Solution?").

Any idea how to achieve that?

Pointing to some algorithm resources and/or some pseudo-code or C# would be helpful. Thank you!

4

2 回答 2

3

正如其他人所提到的，您想为此使用某种三次样条插值。

一旦您知道访问每个关键点的时间以及每个点的速度，您就可以计算以所选速度通过关键点的分段三次 Hermite 样条。见：https ://en.wikipedia.org/wiki/Cubic_Hermite_spline

由于您对速度没有任何特殊要求，您可能想要使用经典的三次样条（是的，这些东西的名称不明确）： http: //mathworld.wolfram.com/CubicSpline.html 这种形式的样条确定速度以确保一阶导数（速度）和二阶导数（加速度）沿整个路径平滑变化。

由于您对到达每个关键点的确切时间也没有任何特殊要求，因此您可能希望设置整个路径的最长时间，然后选择关键点的时间以最小化最大加速度或类似的东西那。我没有一个非常简单的方法来做到这一点。我会尝试的是：

最初，使关键点之间的时间与这些点之间的距离成比例。然后，应用几轮：

  1. 调整每段花费的时间，使关键点的切向加速度为0。
  2. 重新计算样条

不过，如果没有这些优化回合，您可能会非常高兴——最初的猜测不会太糟糕。

于 2018-07-11T17:10:35.273 回答
2

我认为你正在处理的是一个旅行推销员问题（TSP）（这里是博士课程的幻灯片，讨论如何尝试解决它）和最小化激光压力的路径是一个最小化移动它所需的力和力的变化，因此它是具有最小曲率的路径，所以我认为最好的方法是用圆弧圆角化 3 对点之间的路径。

可以在此处找到有关如何计算通过 3 个点的圆的参数的示例

我对 C# 不是很流利，所以我将在 Python 中添加一个实现，希望你也觉得它有用。

这个想法是，对于点 A、B、CI 的每个三元组，找到通过这 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 也能理解它。

于 2018-07-11T20:32:24.527 回答