# Intersection between a 3D grid and flight path.

3 views (last 30 days)
Daniel Fry on 3 May 2021
Answered: Star Strider on 3 May 2021
Hello everyone,
I have data containing the latitude, longitude and altitude of a flight path sampled at 1 sec intervals in an [n,3] array.
flightPath = [-28.0206900000000,153.379210000000,12300;
-28.0196195409287,153.378420816824,12275.0494706551;
-28.0185513756236,153.377632629300,12250.3161326183;
-28.0174853947211,153.376845339494,12225.7886651166;
-28.0164214888577,153.376058849472,12201.4557473769]; % etc
I also have a rectangular grid structure within the 3d space this flight path exists, defined simply as:
lat = linspace(latMin,latMax,latDivisions);
lng = linspace(lngMin,lngMax,lngDivisions);
alt = linspace(altMin,altMax,altDivisions);
I want to find every area within this grid structure that the flight path enters. I know I could simply check which grid area each coordinate lies within, however the sample rate would have to be infinitely small to ensure no areas are missed and this is not feasible as I have nearly a million paths to process.
I was wondering if it would be possible to represent the flight path with an equation and then find which faces of the grid the path intersects with. It is not important if the equation representing the flight path is not exact (so long as it could be converted to discrete [lat,lng,alt] positions later) as the purpose of this work is to create a 'truth data set' which can be used to determine the accuracy of sampling using different structures.
Any other ideas are more than welcome!

KSSV on 3 May 2021
flightPath = [-28.0206900000000,153.379210000000,12300;
-28.0196195409287,153.378420816824,12275.0494706551;
-28.0185513756236,153.377632629300,12250.3161326183;
-28.0174853947211,153.376845339494,12225.7886651166;
-28.0164214888577,153.376058849472,12201.4557473769];
lat = linspace(latMin,latMax,latDivisions);
lng = linspace(lngMin,lngMax,lngDivisions);
alt = linspace(altMin,altMax,altDivisions);
[lat,lng,alt] = ndgrid(lat,lng,alt) ;
P = [lat(:) lng(:) alt(:)] ;
idx = knnsearch(P,flightPath) ;
P(idx,:)

Star Strider on 3 May 2021
I am not exactly certain what you want. This will give the latitude and longitude grid intersections, computed using linear regression on each segment of the flight path. You can then extract from those values other information. (This uses the automatically-generated 'XTick' and 'YTick' values to describe the grid, you can obviously use whatever values you want, providing they are monotonically increasing.)
This also does not use the altitude information. If you want the altitude information at each intersection, use an appropriate interpolation function, such as interp2. I did not do that as part of this code.
flightPath = [-28.0206900000000,153.379210000000,12300;
-28.0196195409287,153.378420816824,12275.0494706551;
-28.0185513756236,153.377632629300,12250.3161326183;
-28.0174853947211,153.376845339494,12225.7886651166;
-28.0164214888577,153.376058849472,12201.4557473769]; % etc
figure
plot(flightPath(:,1), flightPath(:,2),'.-')
grid
hold on
xt = get(gca,'XTick');
yt = get(gca,'YTick');
for k = 1:size(flightPath,1)-1
% sprintf('\n\t\t — k = %2d —\n',k)
[xtk,idxx] = mink(abs(xt-flightPath(k,1)),2); % Indices of Closest Latitude Grid Values To Position
xtv(k,:) = xt(idxx); % Closest Latitude Grid Values To Position
[ytk,idxy] = mink(abs(yt-flightPath(k,2)),2); % Indices Of Closest Longitude Grid Values To Position
ytv(k,:) = yt(idxy); % Closest Longitude Grid Values To Position
B = [flightPath([k k+1],1) ones(2,1)] \ flightPath([k k+1],2); % Linear Regression Coefficients
latisx(k,:) = (ytv(k,:)-B(2))/B(1); % Latitude Grid Intersections
lonisx(k,:) = [latisx(k,:); ones(1,2)].' * B; % Longitude Grid Intersections
plot(latisx(k,:), lonisx(k,:), 'sr', 'MarkerSize',10) % Plot Intersections
end
hold off
legend('Flight Path','Grid Intersections', 'Location','best') .