How do I get distance between two curves that cannot be described with a polynomial?

Hi guys so I have a unique problem. I'm comparing the distance between two path planning algorithms and these are the results I get in the MATLAB figure. I want to compare the distance between the two paths and output a single graph that has the offset of the distance between the curves, but as you can see, I cannot really use fit with smoothingspline ("fit(X,Y,"smoothingspline")") because both plots cannot be described in a single equation, trust me, I have tried.

I also tried using movmean to average the functions but that made the two graphs fall apart even further sicne the X and Y values don't exactly line up. I figure I will need to use a 3rd dimension like time to orient it but I would like to avoid doing that. My last resort could be running computer vision to get a white space between the two and grab the area between them but that is not a very exact analysis.

[Robert U]

Hi Jacinth Gudetti,

you might want to clarify your question. From your description there are - at least for me - several ways to estimate the distance between the shown paths:

1. Residual distance - think of the path as e.g. traveled distance over time; at each time instant or traveled distance point the Euclidian distance between the two trajectories could be measured.
2. Local distance - for each point of a reference path (choose one of the trajectories as reference) the minimum distance to the second path can be calculated
3. Overal distance difference - for each point measured the overall travelled distance can be compared

Please, clarify what distance you would like to estimate. In order to get meaningful help, it is appreciated when sharing trajectory data (even it is only example data without revealing your study subject) and describe step-by-step the procedure you have in mind.

Kind regards,

Robert

[Sam Chak]

Hi @Jacinth Gudetti

I'm not exactly sure, but I think you will need some kinematics and calculus to find out which path is shorter or longer. As suggested by @Robert U, you should be able to think of the paths as some kinds of coordinates with respect to the time, t. You can do the polyfit for (t, ) and (t, ). For example:

Path #1:

,

,

Path #2:

,

,

Arc length:

The distance travelled from Point A to Point B for a particular path (in 2D) is given by

If possible try to provide the (t, , ) data for both paths. Here is an example:

https://www.mathworks.com/help/matlab/math/integration-to-find-arc-length.html

[John D'Errico]

@Robert U and @Sam Chak have made excellent points. The distance you want to compute will be hugely important. In fact, you may not think of the difference as being pertinent, but it can be so. Unfortunately, you don't provide any data, and you don't tell us yet what you want to do. My guess is you have not gotten past the point where you decided you wanted to see the distance, to realize there are issues.

For example, you are thinking you want to see the distance between the curves plotted. But, plotted as a function of what? For example, you might decide to take equally spaced points along curve 1, and plot the distance to the nearest point on curve 2. In fact, that is NOT a symmetric relationship. So if you stated with points on curve 2, the plot of the distance to the nearest point on curve 1 need not look the same as the previous plot you would have generated!

As well, there are good reasons why a simple smoothing spline failed, because this is not in itself a functional relationship, but what one might call an implicit function, or perhaps a space curve.

Finally, if these are curves that were generated as a function of time, then it might be correct to compute the distance to the corresponding point on the other curve, but sampled at the same time. That will result in a more well-posed curve, since now you are plotting a simply computed distance as a function of time.

Lacking any data, I won't make some up, but I can show how to solve the problem, and even indicate the issues between the various methods you might employ if you are willing to post some data in an attached file. Attach it to a comment, or to your original question by editing the question. Then use the paper clip to attach your data in a .mat file.

In fact, I even have code written (on the file exchange) to compute the distance, which in fact, does require some interesting calculus to do the work when you are working with splines.

[Jacinth Gudetti]

Unfortunately I'm not allowed to show any data for this project but I can say it's a path planning data set starting from the same point on the right where the data begins and ends on the top left. The data is just a series of (x,y) coordinates. the problem is the x and y coordinates are not really aligned with the other data set so I have to generalize the curves

[Robert U]

If it is just about the total length travelled, I do not think there is a need for generalization. You can assume that the way travelled between coordinates is piecewise linear and add all the linear way elements.

If in any case that would be an estimation that is too rough, you can choose other trajectory assumptions ending up in polynomials that must be described by transition conditions for smooth curves (i doubt that is really necessary) and add a lot of complexity to the trajectory that usually does not lead to a much improved accuracy.

BTW: You did not answer any other question concerning the task you would like to tackle.

Kind regards,

Robert

[Jacinth Gudetti]

@Sam Chak @Robert U @John D'Errico I have taken some more time to analyze my problem and I believe time should not be considered. rather I think it should be a function of perpendicular distance from the planned (red) path to the actual (blue) path. Time may in fact complicate matters even further as what I am looking for is for the algorithm's accuracy to stay close to the red line rather than anything with respect to time.

Answer 1

[Sam Chak]

Hi @Jacinth Gudetti

Here is an example. Say, there are two paths: one is an onion-shaped path and the other is a circular path.

The onion-shaped path with a center at (, ) can be described with

, and ,

while the cicular path with a radius r and the same center is given by

, and .

t = 0:pi/50:2*pi;
r = 1;
xc = 2;
yc = 3;

% Onion-shaped path
x1 = r*(cos(t)).^3 + xc;
y1 = r*sin(t) + yc;
h1 = plot(x1, y1, xc, yc, 'o');
daspect([1, 1, 1])
f1 = @(t) sqrt((-3*((cos(t)).^2).*sin(t)).^2 + cos(t).^2);
len1 = integral(f1, 0, 2*pi)

hold on

% Circular path
x2 = r*cos(t) + xc;
y2 = r*sin(t) + yc;
h2 = plot(x2, y2, xc, yc, 'o');
daspect([1, 1, 1])
f2 = @(t) sqrt(sin(t).^2 + cos(t).^2);
len2 = integral(f2, 0, 2*pi)

hold off

Results:

len1 = 5.8290

len2 = 6.2832

The onion-shaped path is shorter than the circular path. You can also verify that circumference for the circle is .

Also check out @John D'Errico's amazing works on the File Exchange.

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

[Sam Chak]

Here is another example, a kind of C-shaped path:

t = linspace(0, 7, 701);
x1 = 0.002778*t.^7 - 0.06944*t.^6 + 0.6861*t.^5 - 3.403*t.^4 + 8.844*t.^3 - 11.03*t.^2 + 3.967*t + 1;
y1 = 0.00119*t.^7 - 0.025*t.^6 + 0.1917*t.^5 - 0.625*t.^4 + 0.6833*t.^3 + 0.15*t.^2 - 0.3762*t + 1;
h1 = plot(x1, y1);
daspect([1, 1, 1])

f1 = @(t) sqrt((3.967 - 22.06*t + 26.532*t.^2 - 13.612*t.^3 + 3.4305*t.^4 - 0.41664*t.^5 + 0.019446*t.^6).^2 + (-0.3762 + 0.3*t + 2.0499*t.^2 - 2.5*t.^3 + 0.9585*t.^4 - 0.15*t.^5 + 0.00833*t.^6).^2);
len1 = integral(f1, 0, 7)

Result:

len1 = 8.3340

[John D'Errico]

What @Sam Chak wrote should get you started. If not, you can look at my distance2curve tool, on the file exchange. It can be used to find the closest point along a general path in the plane, represented as a set of piecewise linear segments, or as a cubic spline of some forms.

Given two curves, then you could simply compute the distance from each point on curve 1 to the second curve. I even show an example of doing something like that in the examples for the code as I recall.

[Jacinth Gudetti]

As I explained I can't compare point to point because the X and Y coordinates aren't exactly synced. I need to compare the perpendiculare distance to the curves

[Sam Chak]

Hi @Jacinth Gudetti

Thanks for your reply. You have mentioned about finding the perpendicular distance from the planned (red) path to the actual (blue) path. Since the path is described by the coordinates of the points, then there are multiple straight line segments to construct the curve. In a 2D space, I can think of 4 situations listed below:

1. Intersecting lines
2. Intersecting and perpendicular lines
3. Parallel lines (non-intersecting)
4. Skew lines (non-intersecting and non-parallel)

Can you sketch a simple diagram of the "perpendicular distances" that arise in such situations?

This is important because it is necessary to get a clearer picture before simply plugging in the perpendicular distance formula:

(not mentioning that there maybe the nearest and the farthest perpendicular distances).

[Jacinth Gudetti]

Hi thanks for your reply! I think I have an idea of what I want to do. I think what I could do is this kind of algorithm:

For every p in the planned path array:

for every a in the actual array:

get the distance from a to p

do checks to get 2 shortest distances and corresponding a coordinates (a1 and a2)

end

d1 = distance from p to a1

d2 = distance from p to a2

d3 = point_to_line(p, a1, a2)

%final distance is minimum of d1, d2, d3

d = min(d1,d2,d3)

plot on a graph with x corresponding to index for p

end

Source for point_to_line:

Is there a function in MATLAB that calculates the shortest distance from a point to a line? - (mathworks.com)

[Jacinth Gudetti]

This is a shortest distance from point to point analysis but I have the 2 edge cases where distance to a1 or a2 are closest accounted for as well although that probably needs more refining. I'll have to experiment with the point_to_line function. Here's the code for point_to_line in case the link is broken:

function d = point_to_line(pt, v1, v2)

a = v1 - v2;

b = pt - v2;

d = norm(cross(a,b)) / norm(a);

[Jacinth Gudetti]

Alright, so I solved the problem! Here is my code, p and a correspond to the planned path of the vehicle and the actual path the vehicle actually travelled:

******************************************************************************************************************

planned = [l1x, l1y];

actual = [l2x, l2y];

for p = 0:1024

display("Trial #: " + p)

d1 = 50;

d2 = 50;

a1x = 0; a1y = 0;

a2x = 0; a2y = 0;

for a = 0:1024

d = distance([l1x(p),l1y(p)], [l2x(a),l2y(a)]);

if(d < d1)

d1 = d;

a1x = l2x(a);

a1y = l2y(a);

continue;

end

if(d < d2)

d2 = d;

a2x = l2x(a);

a2y = l2y(a);

end

end

d3 = point_to_line([l1x(p), l1y(p), 0], [a1x, a1y, 0], [a2x, a2y, 0]);

d_f(p) = min([d1,d2,d3]);

hold on;

end

hold off;

figure();

plot([0:1024],d_f(0:1024));

hold off;

function d = point_to_line(pt, v1, v2)

a = v1 - v2;

b = pt - v2;

d = norm(cross(a,b)) / norm(a);

end

******************************************************************************************************************

[Sam Chak]

Hi @Jacinth Gudetti

Nothing works without steadfastness in pursuing what you desire. Kudos to you!