Fit between two curves

I am trying to determine the fit between two curves (example shown below). Both curves are plotted here as a bunch of XY data points (not functions).

The curves represent the trajectories of two planes taxiing, and I'm trying to figure out how far apart they are on average. (axes are in x/y position in meters)

I've done correlation and RMSE, but neither of those is really what I want-- the two planes are travelling at different speeds, and thus one curve has many more data points than the other. So RMSE is sensitive to time, whereas I want deviation independent of time.

My next thought is to do some sort of integration, but I'm not sure how that would work as the curves crisscross frequently.

As you can see, the curves are pretty similar so I'm looking to get a small number as a result... probably around 0-5 meters.

What sort of analysis should I be doing here?

A close up of the turn:

• Your axes don't have labels. I realize it's in meters, but is that something like distance from the start of the runway versus altitude? – Iterator Aug 6 '11 at 2:48
• No, the planes are taxiing so there is no altitude. The axes are x and y position of the plane (in meters) in two-dimensional space. The zero point is arbitrary, and is based on the coordinate plane that my flight simulator is using. They could just as easily be longitude vs. latitude, but recording the data in meters using a local coordinate system gives me more precision. – Jeff Aug 6 '11 at 3:07
• By the way, is the comparison exploratory in nature, or is there a particular question you're trying to address? – Iterator Aug 6 '11 at 3:39
• More the latter, I guess. One of those curves is human data and the other is produced by a computational model I'm working on. Deviation from the human data is one measure of how good the model is at mimicking human pilots. – Jeff Aug 6 '11 at 3:47
• Do you need to measure the discrepancy between these two curves on an absolute basis or on a relative one? In the latter case you might, for instance, be willing to disregard a shift in the x- or y-directions. These curves might match closely indeed if the left one were shifted about 3 meters right. What about the possibility of overlooking arbitrary Euclidean motions, such as rotations? – whuber Aug 6 '11 at 18:33

This is kind of like the analysis of animal tracking data that I have to do in lab. My reflex would be something like this:

First define a linearized track as @Iterator suggested. I do this by defining a spline with somewhere between 3 and 20 control points. You can either fit the spline through all of your data or use something absolute like the physical shape of the taxi runway, or the optimal path that textbook-perfect taxi-ing would produce. Whatever you choose, let's call this the reference path.

Then densely sample that spline - find 100,000 points or so along the spline evenly spaced from beginning to end.

Next, for each point in time, and for each trajectory, determine two things: (x) the identity of point along the reference path that's closest to the XY position of the plane at that point in time, and (y) the euclidean distance between the instantaneous data point and that closest spline point. Plotting y as a function of x gives you a plot of distance between the plane and the reference path, by distance along that path.

If you define your reference path to be the spline through Plane A's trajectory, and make the plot described above for Plane B with respect to that path, you'll have a the distance between the planes as a function of their course along the track, independent of time.

Here's some commented code that does the trick. Works on my computer with the test data here.


% Script to determine distance between 2 paths as a function
% of distance along the first path
%
% Path 1 is used to fit a spline.  That spline is densely interpolated
% For a given point along path 2, path1 interpolation points are searched
% for the one with the lowest euclidean distance.  The distance to the
% nearest Path1 interpolation point ALONG path 1 is that path 2 points'
% "reference path distance", and the distance between the interpolation
% point and the path 2 point is the "reference path deviance"
%
% Because the points along path 1 aren't monotonically moving from the
% beginning of the path to the end, in order to fit a smooth spline over
% path 1, I have the user click spline control points over path 1.  A
% temporary spline is fit to the user's clicked points, and the temporary
% spline is used to break the path 1 data into small groups of data.  The
% centroid of each group is taken a control point for building a path 1
% spline.

%% Load data. path1 and path2 are each 2xn [x_data; y_data] %%

%% Plot raw data & get spline points from user %%
figure;  plot(path1(1,:),path1(2,:),'b'); % First path
hold on; plot(path2(1,:),path2(2,:),'r'); % Second path
[spl_x, spl_y] = getpts();                % Mouse-clicks to define spline
user_path = [spl_x'; spl_y'];             % Rearrange to same format as path1,2

%% Make spline from user points %%
n_xx = 100;                        % n_xx interp points for temporary spline
n_x = size(user_path,2);           % n_x samples, 2 values each
xx_t = linspace(0,1,n_xx);         % the interpolants
x_t  = linspace(0,1,n_x);          % the parameter for our parametric fn of time
yy_t = spline(x_t,user_path,xx_t); % yy is the points along the path at xx
plot( yy_t(1,:), yy_t(2,:), '.b', 'LineWidth', 4 );

%% Break path1 points into groups by nearest tmp spline interpolant %%
% For each path1 point, find the nearest temp spline point
TRI = delaunay( yy_t(1,:), yy_t(2,:) );
index = dsearch( yy_t(1,:), yy_t(2,:), TRI, path1(1,:), path1(2,:) );
path1_x = zeros(2,n_xx);  % make 1 path1 spline control point for each path1 point group

% there are n_xx bins for points in path1.  Determine the n_xx centroids
% of the groups of points falling in each of those bins.
for n = 1:n_xx
path1_x(:,n) = [ mean(path1(1, index==n)); ...
mean(path1(2, index==n))];
end

%% Use the centroids just obtained as control points for a 'path1 spline'. %%
n_xx = 1000;                        % we'll densely sample the path1 spline
n_x  = size(path1_x,2);             % although we have only 50 control points for path1 spline
xx_p1 = linspace(0, 1, n_xx);       % where to interpolate into path1 spline
x_p1   = linspace(0, 1, n_x);        % the parameter: distance along temporary spline
yy_p1 = spline(x_p1, path1_x, xx_p1); % spline x&y coordinates along path1
figure; plot( path1(1,:), path1(2,:), '.', 'MarkerSize', 10);
hold on; plot( yy_p1(1,:), yy_p1(2,:), '-');

%% 'Linearize' Path 2 by finding the nearest point along path1 spline for each path2 point. %%
TRI = delaunay( yy_p1(1,:), yy_p1(2,:) );
index = dsearch( yy_p1(1,:), yy_p1(2,:), TRI, path2(1,:), path2(2,:));

path2_dist_along = xx_p1(1,index);  % distance along the path1 spline for each path2 point
% is just the interpolation value of the
% path1 spline

% deviance is the euclidian distance between each path2 point and its
% closest path1_spline counterpart
path2_deviance = sqrt((path2(1,:) - yy_p1(1,index)).^2 + (path2(2,:) - yy_p1(2,index)).^2);

figure; plot(path2_dist_along, path2_deviance,'.');



My paths are not nice and even like yours :/ Animal tracking status-quo. So there is a work-around for fitting a spline to that somewhat messy raw data.

And here's the output of the script.

NB: if that were plotted as a line graph instead of a scatterplot, you would see that the points are not in order along the x axis, and the x axis isn't evenly sampled. This could be fixed by some combination of interpolating and smoothing I think, but the solution probably depends on exactly how you want your output to be formatted, so I didn't code it up.

I tried to make the code clear, but please let me know if anything is confusing. Fun question to work on, thanks.

• This sounds pretty good thanks, but I'm still a bit confused... Do I need to to define a spline function at all, if I'm merely comparing one line to another? Can't I simply use plane b's data points as the reference line? (Although a spline function would also be useful, under the assumption that even the human pilot is not perfectly on the centerline at all times). Also, how do you find the closest point on the reference line-- do you use brute force? Lastly, I am using matlab, so if you do have some code that would be greatly appreciated! – Jeff Aug 6 '11 at 4:01
• Ah, yes, maybe in your case you don't need a spline. I use splines because the animals I track make a lot of lateral movements and the main variable of interest for me is the linearized (almost 1-d) position along a curved track. Your traces look quite smooth already, so you may be able to use one plane's raw path in the way that I use a spline. I'll try to put some code up tomorrow. Brute force works great for finding the closest point. I've also used delaunay and dsearch – ImAlsoGreg Aug 6 '11 at 4:13
• You're both correct: adding a spline is unnecessary. It could help in smoothing the data if there are any local jitters, but I think that calculating the differentials on this data should be fine. @ImAlsoGreg has precisely the right intuition: animal tracking is very related to this. Maybe you have some plots that you could share to illustrate? I think it would help inspire Jeff as to why we're thinking of this as interesting to explore. :) – Iterator Aug 6 '11 at 5:15
• With @Jeff's comment about computer and human matching, I now think that the turning phase could be the most interesting thing possible (along with the possible decision path near takeoff). Humans may be making a ton of decisions, and where the gradients move in unexpected ways could be indicative of external factors that caught their attention. Such as something on the runway. :( – Iterator Aug 6 '11 at 5:18
• What is the resolution and error of your measurements? Are these from GPS? dGPS? Something else? A spline or other smoothing might come into play if the potential error is large relative to the desired error in tracking, for example. – cardinal Aug 6 '11 at 12:53

My suggestion is to rescale the points to be proportions of the length of the arc (the curve). At that point, you can look at interpolations, such as (0,0.01, ..., 1.00) of the arc length and compare the correlation, or whatnot.

However, a more interesting question might be the relationships between the gradient of movement, especially close to the turn. I think a plot of that could be very interesting.

• Good point about rescaling-- I wasn't sure how accurate that would be since technically the arc lengths are different because of small deviations. I'm not sure what you mean about 'gradient of movement' though? I've included a close-up shot of the turn... – Jeff Aug 6 '11 at 3:33
• I just meant a plot of the vectors $(\frac{\partial x}{\partial t},\frac{\partial y}{\partial t})$ at a sequence of timepoints. It might help to look at the plot from the Wikipedia entry on vector fields. – Iterator Aug 6 '11 at 3:37
• Not sure if my suggestion is just a wordier version of Iterator's. Let me know if it's the same idea I'll delete, thanks. Gradient as a function of distance along the path - yep that would be nice to see. – ImAlsoGreg Aug 6 '11 at 3:51
• Nope, not quite the same. Your answer is more fun, in fact. :) – Iterator Aug 6 '11 at 5:11