Finding the y-coordinate of the intersection of two functions when all x-coordinates are unknown

functionslinear algebrapython

Part 1

I have 2 lines defined by 4 points in a plane: $\overline{(x_1, y_1), (x_2, y_2)}$ and $\overline{(x_3, y_3), (x_4, y_4)}$.

I would like to find the $y$-coordinate of the intersection point with only the following information:

  • I know the values $y_1, y_2, y_3, y_4$.
  • I know that $x_1 = x_3$ and $x_2 = x_4$.
  • I know the two lines do in fact intersect (which means we can assume without loss of generality that $y_1 \ge y_3$ and $y_2 \le y_4$).

All the formulas I've been able to find, however, require the values of the $x$-coordinates as well.

The approximation I'm currently using is simply the average $y$-value $\frac{y_1 + y_2 + y_3 + y_4}{4}$. I don't think this formula gives the actual $y$-value of the intersection though.

Part 2

The above is actually a reduction of a more general problem I'm trying to solve (approximately) in a computer program.

I have 2 monotone functions, one increasing and one decreasing, and I need to find their intersection. The functions are given as 1D arrays. A simple example is given below in python code:

import numpy as np

f1 = np.sort(np.random.rand(100))
f2 = np.sort(np.random.rand(100))[::-1]

These arrays represent the y-values of the function over some list of x-values. The x-values are the same for both functions, but they are unknown and, worse, are not uniformly distributed.

What I'm currently doing is finding the first array index where f1 > f2, using the below one-liner:

np.argwhere(np.diff(np.sign(f1 - f2))).flatten()[0]

then linearly interpolating the four points around it as described in Part 1.

Question

Can anyone recommend a better solution to either part?

Best Answer

For part (1), since you know $x_1 = x_3$ and $x_2 = x_4$, and compressing or stretching the lines horizontally won't change the $y$-coordinate of the intersection, you can just solve the problem for $x_1 = x_3 = 0$ and $x_2 = x_4 = 1$ in full generality. The exact $x$-coordinates are actually irrelevant.

More formally, define new coordinates $x', y'$, where $y = y'$ and $x = x_1 + (x_2 - x_1) x'$. Thus we can write $x'_1 = x'_3 = 0$ and $x'_2 = x'_4 = 1$. The equations of your lines in the new coordinates (dropping the redundant prime marks on $y$) are $$y - y_1 = (y_2 - y_1) x'$$ and $$y - y_3 = (y_4 - y_3) x'.$$ Rearrange the second equation to $$x' = \frac{y - y_3}{y_4 - y_3}$$ and substitute into the first equation to get \begin{align*}y - y_1 &= \frac{(y_2 - y_1) (y - y_3)}{y_4 - y_3} \\ \left( 1 - \frac{y_2 - y_1}{y_4 - y_3} \right)y &= y_1 - \frac{(y_2 - y_1) y_3}{y_4 - y_3} \\ (y_1 - y_2 - y_3 + y_4) y &= (y_4 - y_3) y_1 - (y_2 - y_1) y_3 \\ y &= \frac{y_1 y_4 - y_2 y_3}{y_1 - y_2 - y_3 + y_4}. \end{align*} Two sanity checks: $y$ is invariant under interchange of $(y_1, y_2)$ with $(y_3, y_4)$, and in the case $y_1 = y_4 = 0$ and $y_2 = y_3 = 1$ we get $y = \frac{1}{2}$, as we would expect.

For part (2), I don't think you could improve anything. If you knew the $x$-coordinates, then you could use quadratic or cubic splines, but with unknown $x$-coordinates, this is impossible.

Related Question