python - 沿着离散线段均匀分布点的路径行走

Question

我正在尝试编写一个程序，给定一个指示路径的点列表并给定所需数量的标记，它应该沿着路径精确均匀地分布这些标记。碰巧路径是循环的，但给定一个任意点开始和结束我认为它根本不会影响算法。

第一步是总结线段的长度以确定路径的总长度，然后将其除以标记数以获得所需的标记之间的距离。很简单。

下一步是沿着路径行走，每次穿过标记之间的距离的偶数倍时，存储每个标记的坐标。

在我的代码中，遍历似乎是正确的，但标记的分布并不均匀，也没有完全遵循路径。我在 matplotlib 中创建了一个可视化来绘制标记着陆的位置以显示这一点(请参阅上一节)。

路径数据

point_data = [
 (53.8024, 50.4762), (49.5272, 51.8727), (45.0118, 52.3863), (40.5399, 53.0184), (36.3951, 54.7708),
 (28.7127, 58.6807), (25.5306, 61.4955), (23.3828, 65.2082), (22.6764, 68.3316), (22.6945, 71.535),
 (24.6674, 77.6427), (28.8279, 82.4529), (31.5805, 84.0346), (34.7024, 84.8875), (45.9183, 84.5739),
 (57.0529, 82.9846), (64.2141, 79.1657), (71.089, 74.802), (76.7944, 69.8429), (82.1092, 64.4783),
 (83.974, 63.3605), (85.2997, 61.5455), (85.7719, 59.4206), (85.0764, 57.3729), (82.0979, 56.0247),
 (78.878, 55.1062), (73.891, 53.0987), (68.7101, 51.7283), (63.6943, 51.2997), (58.6791, 51.7438),
 (56.1255, 51.5243), (53.8024, 50.4762), (53.8024, 50.4762)]

遍历

import math

number_of_points = 20

def euclid_dist(x1, y1, x2, y2):
  return ((x1-x2)**2 + (y1-y2)**2)**0.5

def move_point(x0, y0, d, theta_rad):
  return x0 + d*math.cos(theta_rad), y0 + d*math.sin(theta_rad)

total_dist = 0
for i in range(1, len(point_data), 1):
  x1, y1 = point_data[i - 1]
  x2, y2 = point_data[i]
  total_dist += euclid_dist(x1, y1, x2, y2)

dist_per_point = total_dist / number_of_points

length_left_over = 0  # distance left over from the last segment
# led_id = 0

results = []

for i in range(1, len(point_data), 1):
  x1, y1 = point_data[i - 1]
  x2, y2 = point_data[i]

  angle_rads  = math.atan2(y1-y2, x1-x2)
  extra_rotation = math.pi / 2  # 90deg
  angle_output = math.degrees((angle_rads + extra_rotation + math.pi) % (2*math.pi) - math.pi)
  length_of_segment = euclid_dist(x1, y1, x2, y2)
    
  distance_to_work_with = length_left_over + length_of_segment
  
  current_dist = dist_per_point - length_left_over

  while distance_to_work_with > dist_per_point:

    new_point = move_point(x1, y1, current_dist, angle_rads)
    results.append((new_point[0], new_point[1], angle_output))

    current_dist += dist_per_point
    
    distance_to_work_with -= dist_per_point

  length_left_over = distance_to_work_with

可视化代码

import matplotlib.pyplot as plt
from matplotlib import collections  as mc
import numpy as np

X = np.array([x for x, _, _ in results])
Y = np.array([y for _, y, _ in results])

plt.scatter(X, Y)

for i, (x, y) in enumerate(zip(X, Y)):
    plt.text(x, y, str(i), color="red", fontsize=12)

possible_colors = [(1, 0, 0, 1), (0, 1, 0, 1), (0, 0, 1, 1)]

lines = []
colors = []
for i in range(len(point_data) -1 , 0, -1):
  x1, y1 = point_data[i - 1]
  x2, y2 = point_data[i]
  lines.append(((x1, y1), (x2, y2)))
  colors.append(possible_colors[i % 3])

lc = mc.LineCollection(lines, colors = colors, linewidths=2)
fig, ax = plt.subplots()
ax.add_collection(lc)
ax.autoscale()
ax.margins(0.1)

plt.show()

可视化结果

Answer 1

这里的关键是根据距离路径起点的累积距离(跨段)为我们要沿路径分布的每个点找到路径上的段。然后，根据该点在路径上的线段两端点之间的距离对该点进行插值。以下代码使用 numpy 数组处理和列表理解的混合来完成此操作:

    point_data = [
        (53.8024, 50.4762), (49.5272, 51.8727), (45.0118, 52.3863), (40.5399, 53.0184), (36.3951, 54.7708),
        (28.7127, 58.6807), (25.5306, 61.4955), (23.3828, 65.2082), (22.6764, 68.3316), (22.6945, 71.535),
        (24.6674, 77.6427), (28.8279, 82.4529), (31.5805, 84.0346), (34.7024, 84.8875), (45.9183, 84.5739),
        (57.0529, 82.9846), (64.2141, 79.1657), (71.089, 74.802), (76.7944, 69.8429), (82.1092, 64.4783),
        (83.974, 63.3605), (85.2997, 61.5455), (85.7719, 59.4206), (85.0764, 57.3729), (82.0979, 56.0247),
        (78.878, 55.1062), (73.891, 53.0987), (68.7101, 51.7283), (63.6943, 51.2997), (58.6791, 51.7438),
        (56.1255, 51.5243), (53.8024, 50.4762), (53.8024, 50.4762)
    ]

    number_of_points = 20

    def euclid_dist(x1, y1, x2, y2):
        return ((x1-x2)**2 + (y1-y2)**2)**0.5

    # compute distances between segment end-points (padded with 0. at the start)
    # I am using the OP supplied function and list comprehension, but this
    # can also be done using numpy
    dist_between_points = [0.] + [euclid_dist(p0[0], p0[1], p1[0], p1[1])
                                  for p0, p1 in zip(point_data[:-1], point_data[1:])]
    cum_dist_to_point = np.cumsum(dist_between_points)
    total_dist = sum(dist_between_points)

    cum_dist_per_point = np.linspace(0., total_dist, number_of_points, endpoint=False)
    # find the segment that the points will be in
    point_line_segment_indices = np.searchsorted(cum_dist_to_point, cum_dist_per_point, side='right').astype(int)
    # then do linear interpolation for the point based on distance between the two end points of the segment
    #   d0s: left end-point cumulative distances from start for segment containing point
    #   d1s: right end-point cumulative distances from start for segment containing point
    #   alphas: the interpolation distance in the segment
    #   p0s: left end-point for segment containing point
    #   p1s: right end-point for segment containing point    
    d0s = cum_dist_to_point[point_line_segment_indices - 1]
    d1s = cum_dist_to_point[point_line_segment_indices]
    alphas = (cum_dist_per_point - d0s) / (d1s - d0s)
    p0s = [point_data[segment_index - 1] for segment_index in point_line_segment_indices]
    p1s = [point_data[segment_index] for segment_index in point_line_segment_indices]
    results = [(p0[0] + alpha * (p1[0] - p0[0]), p0[1] + alpha * (p1[1] - p0[1]))
               for p0, p1, alpha in zip(p0s, p1s, alphas)]

数组 cum_dist_to_point 是沿路径从起点到 point_data 中每个点的累积(跨段)距离，数组 cum_dist_per_point 是我们想要沿路径均匀分布的点数沿路径的累积距离。请注意，我们使用 np.searchsorted 来识别路径上的段(通过从开始的累积距离)，该点距起点的给定距离位于该点所在的位置。根据文档，搜索排序:

Find the indices into a sorted array (first argument) such that, if the corresponding elements in the second argument were inserted before the indices, the order would be preserved.

然后，使用 OP 的绘图函数(由于 results 不再具有角度分量而略有修改):

def plot_me(results):
    X = np.array([x for x, _ in results])
    Y = np.array([y for _, y in results])

    plt.scatter(X, Y)

    for i, (x, y) in enumerate(zip(X, Y)):
        plt.text(x, y, str(i), color="red", fontsize=12)

    possible_colors = [(1, 0, 0, 1), (0, 1, 0, 1), (0, 0, 1, 1)]

    lines = []
    colors = []
    for i in range(len(point_data) -1, 0, -1):
        x1, y1 = point_data[i - 1]
        x2, y2 = point_data[i]
        lines.append(((x1, y1), (x2, y2)))
        colors.append(possible_colors[i % 3])

    lc = mc.LineCollection(lines, colors=colors, linewidths=2)
    fig, ax = plt.subplots()
    ax.add_collection(lc)
    ax.autoscale()
    ax.margins(0.1)

    plt.show()

我们有:

    plot_me(results)