0

Sort of like a more advanced version of this question.

Given a continuous 2D or higher function $f(x, y)$ corresponding to speed of getting through that point and two points $\vec{a}, \vec{b}$ to travel between, find the quickest route through.

For simplicity, assume that the metric of speed is meters per second and the unit of distance meters.

Note: The amount of time this will take isn't needed as a result. If it can be obtained though, all the better.

This is for a programming project of an alternative to A* search for GPS navigation. (Not a school project, just a personal project.)

Example: Imagine a pool full of oil and water that somehow are able to not move at all and fill the space from the top to the bottom. What is the quickest way to get through it, assuming that swimming through oil is only half as fast?

Lightning Creations
  • 1
  • @hardmath I'm going to be fed in a bitmap image probably, so I don't know how I would convert into geometric shapes. How I would make it continuous I guess is a whole separate ordeal, but I don't understand what you really mean with this. – Lightning Creations Aug 16 '18 at 01:53
  • You described the setup as a 2D flow, so I assumed you have a geometric region (like a rectangle, or perhaps a circle) in which the flow rate and density vary. Perhaps you have in mind the equations for 2D Navier-Stokes that should be satisfied in a model, but how you go from a bitmap image to some fluid motion/density values is beyond the scope of what Math.SE can reasonably hope to offer advice about. – hardmath Aug 16 '18 at 01:59
  • @hardmath No, that's something that I'm going to figure out. The point is that it's not some conglomerate of shapes, more of a map of how fast something would be able to move through any infinitesimal point on this surface. – Lightning Creations Aug 16 '18 at 02:08
  • I guess the word "fluid" led me to thinking of a motion in the fluid against which (or with which) an object would have relative speed. Perhaps you have in mind that at a particular point there is a given speed that an object would move, regardless of the direction in which it was moving there. – hardmath Aug 16 '18 at 04:14
  • I'm going to go ahead and add an example to the question that hopefully clarifies this. – Lightning Creations Aug 16 '18 at 13:12
  • 1
    Optimal path problems are pretty standard actually, they lead to Hamilton-Jacobi type PDEs. – Ian Aug 16 '18 at 13:19
  • @hardmath Edited. – Lightning Creations Aug 16 '18 at 13:34
  • This is a standard calculus of variation problem where you seek to choose $y(x)$ such that the $\int^b_a \frac{ds}{f(x,y)}$ is a minimum. Write $ds=dx \sqrt{(1+y'^2)}$ and use the standard Lagrange equations. – user121049 Aug 16 '18 at 16:40
  • @user121049 Yay, math going straight over my head. Could you maybe explain this a bit more? Maybe even put it in an answer? – Lightning Creations Aug 16 '18 at 16:52
  • @user121049 Now understanding your thing just a bit more, and it looks like the path selected requires a line that has only one y for each x, which doesn't correspond with most roads, which this algorithm is geared toward. Example, an S shape. That crosses itself in the X axis, and would require multiple outputs of the function for one input. If there's a variation of this that works for this sort of problem, I would appreciate it. – Lightning Creations Aug 16 '18 at 19:09
  • 1
    @LightningCreations Up until the $ds=dx \sqrt{1+y'^2}$ part, everything user121049 said applies to your context, even if neither $x$ nor $y$ can be chosen to be a function of the other. The idea is instead to parametrize the curve by some third variable (generally either arclength or time) and still get an Euler-Lagrange equation. – Ian Aug 16 '18 at 22:52
  • I still don't know what that is. Will look it up when I get a chance. – Lightning Creations Aug 19 '18 at 18:16

0 Answers0