CODEWITHSUNDEEP
pythonmath3d
user-2147482637
user-2147482637

Reputation: 2163

How to redistribute points evenly over a curve

I have some arbitrary curve in 3 dimensions made up of a list of XYZ cartesian points. The points are not evenly distributed (theres a time factor). How can I 'rebuild' the curve with a given number of points that should make up the curve. I see this done in 3D modeling programs so im pretty sure its possible, I just dont know how.

enter image description here

Based on the answer, i needed it in python so i started working to convert interparc into python. I got as far as the linear interpolation. It is probably inefficient and has redundancies, but maybe it will be useful to someone http://pastebin.com/L9NFvJyA

Upvotes: 6

Views: 7865

Answers (5)

adam.hendry
adam.hendry

Reputation: 5653

As a followup, interparc assumes your points are listed in path order (i.e. the points go from start to end tracing the curve). If using real world data, this may not be the case.

If you happen to know the connectivity of your points (i.e. which points connect to form a chord), you can use libigl to sort the points in path order:

import igl

path, _, _ = igl.edges_to_path(edges)  # edges = N x 2 array of point indices

points = points[path]

# Now use `interparc`...

If you don't know the connectivity, you could try using pykdtree:

  • Create an empty N X 2 array called edges
  • Pick a random point in the points dataset (say index 5 of points)
  • Use a KDTree to find the indices of the two nearest neighbors in the data
  • Store the pairs of indices in edges (i.e. if points[5] is connected to points[10] and points[3], you'd do something like:
edges = np.append(edges, [[5, 10], [5, 3]], axis=0)
  • Pop points 5, 10, and 3 from points and continue continue the algorithm at points 10 and 3 until there are no more points left.

The above is just an idea.

Upvotes: 0

FFC
FFC

Reputation: 355

First of all, thank you to Mr. John D'Errico for interparc. What a great job!

I too was facing this problem but am not familiar with the MATLAB engine API. Given that, I tried to convert part of the interparc Matlab code to Python (just including the linear interpolant because it would be enough to address my problem).

And so here is my code; hope it can help all the pythonics seeking something similar:

import numpy as np

def interpcurve(N,pX,pY):
#equally spaced in arclength
N=np.transpose(np.linspace(0,1,N))

#how many points will be uniformly interpolated?
nt=N.size

#number of points on the curve
n=pX.size
pxy=np.array((pX,pY)).T
p1=pxy[0,:]
pend=pxy[-1,:]
last_segment= np.linalg.norm(np.subtract(p1,pend))
epsilon= 10*np.finfo(float).eps

#IF the two end points are not close enough lets close the curve
if last_segment > epsilon*np.linalg.norm(np.amax(abs(pxy),axis=0)):
    pxy=np.vstack((pxy,p1))
    nt = nt + 1
else:
    print('Contour already closed')

pt=np.zeros((nt,2))

#Compute the chordal arclength of each segment.
chordlen = (np.sum(np.diff(pxy,axis=0)**2,axis=1))**(1/2)
#Normalize the arclengths to a unit total
chordlen = chordlen/np.sum(chordlen)
#cumulative arclength
cumarc = np.append(0,np.cumsum(chordlen))

tbins= np.digitize(N,cumarc) # bin index in which each N is in

#catch any problems at the ends
tbins[np.where(tbins<=0 | (N<=0))]=1
tbins[np.where(tbins >= n | (N >= 1))] = n - 1      

s = np.divide((N - cumarc[tbins]),chordlen[tbins-1])
pt = pxy[tbins,:] + np.multiply((pxy[tbins,:] - pxy[tbins-1,:]),(np.vstack([s]*2)).T)

return pt

Upvotes: 8

user85109
user85109

Reputation:

I'd use interparc, a tool of mine designed to do exactly that. It fits a spline through a general space curve in 2 or more dimensions, then chooses points that are equally spaced in terms of distance along that curve. In the case of a cubic spline, the solution uses an odesolver to do what must be a numerical integration so it is a bit slower, but it is still reasonably fast. In many cases, a simple linear interpolation (as I used here) will be entirely adequate, and extremely fast.

The curve may be completely general, even crossing over itself. I'll give a simple example for a 3-d space curve:

t = linspace(0,1,500).^3;
x = sin(2*pi*t);
y = sin(pi*t);
z = cos(3*x + y);
plot3(x,y,z,'o')
grid on
box on
view(-9,12)

enter image description here

xyzi = interparc(100,x,y,z,'lin');
plot3(xyzi(:,1),xyzi(:,2),xyzi(:,3),'o')
box on
grid on
view(-9,12)

enter image description here

Upvotes: 11

BlueRaja - Danny Pflughoeft
BlueRaja - Danny Pflughoeft

Reputation: 86116

Your "curve" is a bunch of line-segments that connect a bunch of points. Each line-segment has a length; the total length of your curve is the sum of these line-segments' lengths.

So calculate d = totalCurveLength / (numberOfPoints - 1), and split the curve into (numberOfPoints - 1) chunks of length d.

Upvotes: 2

user2565677
user2565677

Reputation: 905

Not sure I'm following, but instead of storing the actual data, maybe store the delta from point to point, then rebuild the curve from the deltas, so there wouldn't be any empty spots? This would, however, change the shape of the curve.

Upvotes: 0

Related Questions