How to find 3D coordinate of a 2D point based on a set of 3D points (possibly non-coplanar)?

Question

I have a set of 3D points (I'll call them "outer" points) and a 2D point ("inner" point).

I need to quickly calculate a "good" third coordinate for the inner point so that it would place the constructed 3D point as "close" to the outer points as possible. "Close" may be defined as a minimum sum of distances between the inner 3D point and the outer points or as a sum of differences in the Z-coordinates - I'm open to interpretations to make calculation faster.

My real-world problem is that I need to calculate elevation of way points inside tunnel based on their 2D-coordinates. A tunnel structure has a few (typically 2 but sometimes more) entry and exit points (my "outer" points) where I know not just latitude and longitude but also elevations. Based on this information I need to estimate elevation of points inside the tunnel.

The task is trivial for 1-3 entry points but I don't know how to approach it efficiently for more than 3 outer points.

Answer 1

Well, without knowing much more about the general problem the best I can do is probably what you already know, but I will show it anyway.

Given three entry or exit points $(x_1,y_1,z_1),\,(x_2,y_2,z_2),\,(x_3,y_3,z_3)$ first find the $\textbf{normal vector}$ of the plane containing them by taking the cross product of the two vectors $\langle x_2-x_1,y_2-y_1,z_2-z_1 \rangle$ and $\langle x_3-x_1,y_3-y_1,z_3-z_1 \rangle$ and call that cross-product vector $\langle a,b,c\rangle$.

Then the equation of the plane containing the three points is

\begin{equation} ax+by+cz=ax_1+by_1+cz_1 \end{equation}

For a way point $w=(w_1,w_2,w_3)$ one can compute the estimated value of the elevation $w_3$ by solving the following equation for $w_3$:

\begin{equation} aw_1+bw_2+cw_3=ax_1+by_1+cz_1 \end{equation}

I would pick sets of three maximally separated points for $(x_1,y_1,z_1),\,(x_2,y_2,z_2),\,(x_3,y_3,z_3)$ and if some other outer points were close to some of these three, swap that point out for one close to it and recompute $w_3$. Do this for any two points close together and take an average of the results.

Answer 2

I think a problem like this is better solved by making as good a model as you can of the way the real-life object is constructed, not by taking some mathematical abstraction.

The elevation of most points in a tunnel follows the elevation of a line painted down the center of the roadway within that tunnel. (This could be a fictional line, though in many cases an actual line is conveniently painted there.) On either side of the line the surface is at approximately the same elevation, but you may find the elevation increases or decreases as you travel along the line.

If there are more than two access points to the tunnel (one at each end), the additional access points are typically made via ramps that branch off from the main tunnel and then travel some distance until they finally emerge at the surface of the Earth. Each ramp can have its own slope independently of any other part of the tunnel.

If the given elevation of an "access point" is the elevation where the ramp emerges onto the surface, that elevation may not be the same as any nearby part of the tunnel. As long as the ramps at the access points are not very long, however, they are likely to be at elevations that are not too different from the elevations of the nearby points along the main roadway of the tunnel. They might be a few meters higher, but not hundreds of meters higher.

I believe the people who design tunnels generally do not care whether the center line of the tunnel lies all in one plane. They do care about the grade within the tunnel, that is, the slope of the center line. A reasonable model for a typical tunnel through a mountain with two access points is that the grade is constant throughout the tunnel. If the tunnel curves left or right at some point, it will more likely follow a helical path there, not a planar curve.

So the first thing I would do in modeling elevations within the tunnel is to "straighten out" your model of the tunnel to turn it into a two-dimensional problem instead of a three-dimensional one; but the two dimensions are not latitude and longitude, rather they are elevation and driving distance through the tunnel. For example, if the access points at the two extreme ends of the tunnel are $9$ km apart, but the driving distance between these points is $10$ km because of the way the tunnel turns left or right, lay out a straight line segment on the $x$ axis of a graph with one end of the segment at zero and the other at $10$ km, and plot the elevations in the $y$ direction.

Plot every other access point at the $x$ coordinate that represents the driving distance from the "zero" end of the tunnel to that access point. Provided that the ramps are very short compared to the length of the whole tunnel, a reasonable first approximation is that if there is an access point at distance $x$ with elevation $y$, the elevation of the main tunnel at distance $x$ is $y$. Between access points, a reasonable first approximation is that the grade is constant.

In other words, if you have $n+2$ access points (the two ends and $n$ intermediate access points) then the graph of the tunnel's elevation consists of $n+1$ straight line segments linearly interpolated between consecutive points among the $n+2$ plotted elevations of the access points.

You could make further refinements to the model given real-world knowledge of how tunnels are built. For example, you might observe that an intermediate access point is far above the straight-line path between the elevations of the access points immediately before and after it, the tunnel engineers will typically let the main roadway pass a few meters below the access point and make up the difference by increasing the grade of the ramp to the access point. (I don't know for a fact that it works this way; this is something you would have to get from real-world observations or from tunnel engineers themselves, either directly or via someone else who obtained that information.)

You might be able to refine the estimated elevations by finding out which directions of traffic in the tunnel have access to each access point. For example, an access point to an east-west tunnel that allows drivers to enter the tunnel in the westbound direction is likely to merge into the main roadway a few dozen meters west of the access point. You could estimate where that point was and plot the access point's elevation at the $x$ coordinate of the merge point rather than the $x$ coordinate of the point in the tunnel closest to the access point.

Another real-life observation is that when a tunnel crosses a river, its elevation is often lower in the middle than at any of the access points, because the tunnel is designed to pass below the bottom of the river.

But I think all these extra refinements would only change the estimated elevation of the tunnel's roadway by a few meters at any given point. The main source of error that you're trying to correct, following the surface elevation rather than following a reasonable grade for a tunnel, is corrected by a very simple 2-D linear interpolation. The main thing to "correct" after that would occur when tunnels pass under rivers, and for that you may just have to make a reasonable guess (e.g., put the tunnel $100$ meters under the surface of the middle $1/3$ of the river, if that is below all the access points, and let it slope upward from there).

Answer 3

Here's a solution I came up with so far.

Assume we have a number of more than 3D points $(x_i,y_i,z_i)$ and a 2D point $(x,y)$ we need to calculate $z$ for.

The idea is that the closer $(x,y)$ is to $(x_i,y_i)$, the closer $z$ should be to $z_i$.

So for each of the points $(x_i,y_i,z_i)$ we'll calculate proximity factor $$l_i=\frac{1}{((x_i-x)^2+(y_i-y)^2)^k}$$ and a total $$L=\sum_{i=0}^n l_i$$ I've found a good $k$ to be $1.5$ (cube of distance), but $1$ also works fine and makes calculations much cheaper.

Then we'll "weight" elevations of 3D-points on these proximity factors:

$$z=\sum_{i=0}^n \frac{z_i\cdot l_i}{L}$$

The closer $(x,y)$ get to $(x_i,y_i)$, the closer $z$ gets to $z_i$.