0

Given point $A$, point $B$, and a line (segment), I am trying to find a point $I$ on the line so that the total cost of a path from $A$ to $I$ and then to $B$ is minimal. I can calculate this in a simple case when I am directly summing the Euclidean distances. However, I am not able to find a solution when the distance from $A$ to $I$ is weighted.

I have tried:

  • I have defined the point on the line (segment) as: $I = P + D t$, where $P$ is the origin of the line, $D$ is its direction, and $t \in [0,1]$.
  • I am trying to minimize $cost = weight . Dist(A, I) + Dist(I, B)$ with respect to $t$, where $Dist$ is Euclidean distance. For 2D the cost to minimize is: $cost=weight.\sqrt{(A_x-I_x)^2+(A_x-I_x)^2}+\sqrt{(B_x-I_x)^2+(B_x-I_x)^2}$
  • Calculating a differential of the cost gives an equation that I am not able to solve (using wxMaxima). $$ 0= \frac{-2 D_y(-D_y t-P_y+A_y)-2 D_x (-D_x t-P_x+A_x)).weight} {2\sqrt{(-D_y t-P_y+A_y)^2+(-D_x t-P_x+A_x)^2}} + \frac{-2 D_y (-D_y t-P_y+B_y)-2 D_x (-D_x t-P_x+B_x)} {2\sqrt{(-D_y t-P_y+B_y)^2+(-D_x t-P_x+B_x)^2}} $$

Is there any formula to find the point $I$?

Juraj Blaho
  • 101

1 Answers1

1

Let $y=ax+b$ is the equation of the segment. Then the cost function is $f(x)=w\sqrt{(x_A-x)^2+(y_A-ax-b)^2}+\sqrt{(x_B-x)^2+(y_B-ax-b)^2}$. Taking the derivative: $f'(x)=-w\frac{x_A-x+a(y_a-ax-b)}{\sqrt{(x_A-x)^2+(y_A-ax-b)^2}}-\frac{x_B-x+a(y_B-ax-b)}{\sqrt{(x_B-x)^2+(y_B-ax-b)^2}}$.
Solving $f'(x)=0$ will lead to $$w(x(1-a^2)+x_A+ay_A-ab)\sqrt{(x_B-x)^2+(y_B-ax-b)^2}=(x(a^2-1)-x_B-ay_B+ab)\sqrt{(x_A-x)^2+(y_A-ax-b)^2}$$ To solve the last equation, square both parts which will lead to quartic equation for $x$. I do not think you'll be able to get a nice formula for it but it's definitely solvable.

Vasili
  • 10,690