0

I have a function f(x,z) that returns a height y in a terrain. I want to be able to determine where a line P intersects with the terrain.

A point P=[px,py,pz] along the line is defined as such: P = O + D*t, where O is the origin of the line, D is the direction and t is some distance travelled from the origin.

Is it possible to compute the intersection between the line and the terrain with this information? If yes, then how?

birgersp
  • 103
  • If you tell us more about what the function $f$ looks like and the domain of input values we might be able to help. As the question is stated now it's too general. And I suspect linear algebra is the wrong tag, unless $f$ is linear. – Ethan Bolker Oct 17 '17 at 13:57
  • I modified the tag to "numerical methods" instead, I think (and hope) it is more appropriate. The function f is not linear, and it is (in a sense) "unknown". – birgersp Oct 17 '17 at 14:11
  • In what sense "unknown". Do you have a formula (no matter how complicated)? A class of possible formulas? Just a table of values on a grid? A small numerical example would be best. Without that kind of information I doubt you'll get much help. – Ethan Bolker Oct 17 '17 at 16:50
  • The function retrieves height information about a terrain, and returns an interpolated value between the two nearest height samples. It's a function written in a computer program. By "unknown" I mean I don't really know how to explain it mathematically, and I guess it can't be really be analysed to help out here. I guess this means I would have to apply some kind of search algorithm to find the intersection point? – birgersp Oct 17 '17 at 16:55

1 Answers1

0

Perhaps I know enough now about the problem to venture a possible answer.

Step along the line at intervals $\Delta t$. At each point, check that the pair $(x,z)$ is in the terrain, then calculate whether the height at that point is less than or equal to $f(x,z)$.

You'd have to experiment to find the right granularity $\Delta t$.

You might be able to speed things up if you had good bounds in advance for deciding when $(x,z)$ was in the domain or a maximum possible value for $y$ that would mean you didn't have to calculate $f$.

Note: I've followed your notation, but it's a little odd. I'd expect $(x,y)$ to specify a point in the domain and $z$ the height above that point.

Ethan Bolker
  • 95,224
  • 7
  • 108
  • 199
  • Thanks. For now I'm using a binary search to find (approximately) a value for t where the line goes through the terrain. But I was thinking maybe there was some (feasible) way to find the exact value of t. Maybe there isn't, and your answer is as good as it gets. – birgersp Oct 18 '17 at 09:04