python - 在不改变形状的情况下将线细分为线段

Question

假设我有一条由 N 个有序点（这里：N=5：a、b、c、d 和 e）组成的线，它将它细分为 N-1（这里：4）段。我打算将这条线细分为 M > N-1 段，同时满足两个要求：

1. 段的长度应尽可能相似
2. 线的形状不能改变

如果没有要求（2），我们可以简单地沿着原线的路径创建 M+1 个点，并完美地满足要求（1）：

import numpy as np
import scipy.interpolate
import matplotlib.pyplot as plt

XY  = np.asarray([[1,1],[2.5,3],[4,2.5],[7,3],[9,1]])

distance = np.zeros(5)
for i in range(4):
    distance[i+1] = np.sqrt((XY[i+1,0]-XY[i,0])**2+(XY[i+1,1]-XY[i,1])**2)
distance = np.cumsum(distance)
distance /= distance[-1]

# Get an interpolator for x
x_itp = scipy.interpolate.interp1d(distance,XY[:,0])
y_itp = scipy.interpolate.interp1d(distance,XY[:,1])

# Plot the original line
plt.scatter(XY[:,0],XY[:,1],color='b')
plt.plot(XY[:,0],XY[:,1],'b')

# Get 10 equidistant points
XY_new  = np.column_stack((
    x_itp(np.linspace(0,1,10)),
    y_itp(np.linspace(0,1,10)) ))

# Plot the new line
plt.scatter(XY_new[:,0],XY_new[:,1],color='r',marker='x')
plt.plot(XY_new[:,0],XY_new[:,1],'r--')

不幸的是，如果原始顶点不在这些新点中，则新分段线的形状会略有不同（切角）：

您对我如何创建满足这些要求的算法有任何建议或想法吗？

标签： pythonpython-3.xlineinterpolation

Answer 1

约束：

• 您无法在不丢失形状的情况下修改原始点
• 您不能在不丢失形状的情况下删除原始点
• 任何额外的点都需要在当前段上
• 应最小化 abs（segmentlenght 的差异 - 中值（segmentlength））的总和

你可以通过

1. 按长度排序所有段
2. 如果是原始片段，则将最长的片段分成两半，或者如果不是原始片段，则获取它所属的原始片段并将其拆分为另一个片段，然后将其当前已拆分为
3. 转到 1 直到 M 到达

通过按长度排序并将最长的部分减半，每一步都能让你更接近M. 通过重复此过程，您的分段长度会在每次新减半时变得更加均匀。

您需要使用字典跟踪哪些（新）段位于哪个（原始）段中 - fe：

{ old_seg_1: [new_seg_1, new_seg_2, ...], old_seg_2:[old_seg_2], ...}

如果最长的片段不是原始片段之一，您需要找到它属于哪些原始片段并将该原始片段拆分为另一个片段，然后它当前具有：

---

获得每个段需要多少拆分的基本 python 方法可能是：

import numpy as np
from pprint import pprint
XY  = np.asarray([[1,1],[2.5,3],[4,2.5],[7,3],[9,1]])

def dist(p1,p2):
    return np.sqrt(p2[0]**2-p1[0]**2)

segment = {}
distances = {}
for pos in range(len(XY)-1):
    dist = np.sqrt((XY[pos+1][0]-XY[pos][0])**2 + (XY[pos+1][1]-XY[pos][1])**2)
    segment[pos] = (XY[pos], XY[pos+1])
    distances[pos] = [1,dist]

print("Before:")
pprint(distances)

M = 9
seg_count = lambda w: sum(d[0] for d in distances.values())
seg_count_start = seg_count(distances)

while seg_count(distances) < M:
    keyyy, longest = max(distances.items(), key = lambda x: x[1][1] / x[1][0] )
    distances[keyyy][0] += 1


print("\nAfter:")
pprint(distances)

输出：

Before:
{0: [1, 2.5],
 1: [1, 1.5811388300841898],
 2: [1, 3.0413812651491097],
 3: [1, 2.8284271247461903]}

After:
{0: [2, 2.5],
 1: [2, 1.5811388300841898],
 2: [3, 3.0413812651491097],
 3: [2, 2.8284271247461903]}

现在，您可以使用 scipys 插值使用拆分量来细分所属部分。