Subdivide a line into segments without changing its shape

user_8544328 0
Viewed 352

Assume that I have a line composed of N ordered points (here: N=5: a, b, c, d, and e) which subdivide it into N-1 (here: 4) segments. It is my intention to subdivide the line into M > N-1 segments, while honoring two requirements:

  1. The segments should be as similar in length to each other as possible
  2. The shape of the line mustn't be altered

enter image description here

Without requirement (2) we could simply create M+1 points along the path of the original line and honor requirement (1) perfectly:

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--')

Unfortunately, if the original vertices are not among these new points, the new segmented line would have a slightly different shape (cutting corners):

enter image description here

Do you have any suggestions or ideas on how I could create an algorithm which fulfills these requirements?

line interpolation python-3.x python
1 Answers

Constrains:

  • You cannot modify the original points without loosing the shape
  • You cannot remove original points without loosing the shape
  • any additional points need to be on current segments
  • the sum of the abs(differences of segmentslenght - median(segmentlength)) should be minimized

You could achieve this by

  1. ordering all segments by lenght
  2. split the longest in half if an orignal segment OR if not an original segment, get the original segment it belonged to and split it into one more segment then it currently has been split into
  3. goto 1 until M reached

By orderring by lenght and halving the longest segment every step gets you one closer to M. By repeating this process your segments length get more uniform wich each new halving.

Algo

You would need to keep track of which (new) segments lie in which (original) segment - f.e. using a dictionary:

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

If the longest segment is not one of the original ones, you need to find which original ones it belongs to and split that orignal one into one more segment then it currnently has:

Algo 2

A basic python approach to get how many splits each segment needs could be:

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)

Output:

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]}

Now you can use the amounts of splits to subdivide the belonging sections using scipys interpolation.

user_75053950
Related