将一条线细分为线段而不改变其形状

Question

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

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

如果没有要求（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--')

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

关于我如何创建满足这些要求的算法，您有什么建议或想法吗？

Answer 1

约束：

你不能在不丢失形状的情况下修改原始点
你不能在不丢失形状的情况下删除原始点
任何额外的点都需要在当前段上
绝对值的总和（段长的差异 - 中值（段长））应该最小化

您可以通过

实现

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

通过按长度排序并将最长的段减半，每一步都可以让您更接近 M。通过重复此过程，您的段长度会随着每次减半而变得更加均匀。

您需要跟踪哪些（新）段位于哪个（原始）段 - f.e。使用字典：

{ 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 插值来细分所属部分。

将一条线细分为线段而不改变其形状

Subdivide a line into segments without changing its shape

python

interpolation

line

python-3.x