Locating a point along a curve some distance away from an initial point.

So I have a curve, but I don't have the equation for this curve, just a set of data points. Given an initial point on this curve I want to find another point along this curve at a specified distance away.

As of right now my idea at a solution method involves defining a region in front of the initial point, calucating the distance between every point in this region and my initial point, selecting the 2 points that are closest to my desired distance away, and interpolating between those to points. However this is exteremely inefficient, and would take ages to run in my larger simulation.

Is there a more efficient way to do this?

Answer 1

[John D'Errico]

Easy, peasy. That is, assuming you are asking about a distance in terms of arclength along the curve. If not, then the answer is of course different. Still entirely possible to solve, but completely different.

Use my interparc tool, combined with my arclength tool. They are both on the file exchange. (Links provided below.)

x = linspace(0,2*pi,20);
y = sin(x);

Find a new point at a distance of 2 units along the curve. Use a spline to interpolate the points. The total arclength of the curve is 7.6403... units.

L = arclength(x,y,'spline')
L =
       7.6403

The first point on the curve lies at arclength 0. Interparc uses a relative arclength.

format long g
xy = interparc(2/L,x,y,'spline')
xy =
          1.66061053630525         0.995974772830712

So that point lies at a distance along the curve of 2 units.

plot(x,y,'o',xy(1),xy(2),'r*')

Or, suppose I have some other point on the curve, and I want to find a new point that lies exactly 2 units further along the curve? Use my distance2curve utility first, as we need to locate it on the curve in terpms of arclength.

x0 = 3;
y0 = sin(x0);

So (x0,y0) should lie along the curve. But where does it lie in terms of arclenth along that curve from the start?

[xyc,d0,t0] = distance2curve([x;y]',[x0,y0],'spline')
xyc =
          2.99999755728184         0.141117541012307
d0 =
       3.4717712602551e-06
t0 =
         0.473835095624448

So the point lies on the curve, but it did not lie EXACTLY on the spline itself. No matter, as it was only a tiny amount off. The closest point on the spline is very close. There are two neighbors to that point, located at a distance of 2 units along the spline interpolant.

xyneighbors = interparc(t0 + [-2/L,2/L],x,y,'spline')
xyneighbors =
          1.28471554283348         0.959412594091491
          4.60259974918216        -0.993988748347396

So the green star is on the curve. The pair of red stars lie at a distance of 2 units along the curve in either direction.

No loops, searches, or iteration is required. (Well, no explicit loops or any work on your part.)

Note that if extreme efficiency is required, you can use all of those tools with linear interpolation instead of a spline. They will all be highly efficient then, although the results will be somewhat less accurate when based on a piecewise linear interpolant.

Find the tools I have used on the file exchange, here:

https://www.mathworks.com/matlabcentral/fileexchange/34869-distance2curve

https://www.mathworks.com/matlabcentral/fileexchange/34874-interparc

https://www.mathworks.com/matlabcentral/fileexchange/34871-arclength

[Alexander Khair]

It worked great, thank you!

[John D'Errico]

I want to make sure that I interpreted your question correctly though. The tools I describe work with distance along the curve, as if we have an ant walking along the curve, stopping at a specific distance measured along the curve. (Do ants carry pedometers? Would an ant get a pedometer screed up do to using 6 legs, instead of 2 legs? These are clearly fundamentally important questions in life.)

Anyway, this is different from finding a seond point that is a fixed distance away in the plane. Thus, consider the curve I created first, a sinewave. Now given the point at (0,0) can I find a second point that is a distance of exactly 2 units away from the first? So now I am not worried about a distance measured by following along the curve itself, but purely a distance.

We can write this alternative question as a system of two nonlinear equations. So we have one equation...

y = sin(x)

and a second equation

(x - 0)^2 + (y-0)^2 = x^2 + y^2 = 2^2

The latter equation is that of a circle of radius 2, centered at (0,0). Any point on the perimeter of a circle lies at a distance of exactly the radius of the circle. (I've drawn the problem below using Wolfram Alpha, since my own MATLAB license will be very busy for the next 16 hours.)

We can try to solve it by eliminating one variable,

x^2 + (sin(x))^2 = 4

but that surely won't have an analytical solution. We could easily enough use a tool like vpasolve or better yet, fzero, to solve it though. However we solve it, this problem is subtly different from that of the one I solved in my answer. Actually, there is an even better solution method that I can suggest for this variation of your problem, that would use Doug Schwarz's intersections tool, also from the file exchange.

Anyway, a numerical solution of those equations will yield x=1.74024, not x = 1.66061053630525, as my other solution came up with. The difference lies in how you measure distance.

[Alexander Khair]

You interpreted the problem correctly. The solution you presented was exactly what I was looking for.

The problem I’m working with involves taking the portion of a rigid body that crosses an oscillating beam and fitting that length to the curve of the beam.

I need to discretize it to calculate strains, stresses, and forces to push it back. I’m already iterating through the whole simulation on a small time step, and to have to find 50 or so of these points each time there’s any penetration would have really decreased efficiency.

I still have a lot of work to get everything incorporated into my larger model, but the preliminary test run using your method work very nicely.

Thanks again for the help. Your answers were very detailed and extremely easy to follow.

[John D'Errico]

Great!

[bahar gharehpapagh]

dear John D'Errico

If the problem is about points of a 2d curve that exist just coordinates, how can we find points with a defined distance from those coordinates? I handle it by locating circles on the points and finding intersection points. Is there another efficient method?

[Biraj Khanal]

This is so good! Thanks @John D'Errico!!!