title: Intersection of hyperbolae in R based on line equations
body: <p>I am trying to find a method for finding the point of intersection of 2 hyperbolae in R. Single-branch hyperbloae can be described by the following equation:</p>
  <p><a href="https://i.stack.imgur.com/HepLb.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/HepLb.png" alt="equation image here" /></a></p>
  <p>or</p>
  <p><a href="https://i.stack.imgur.com/1ah4E.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/1ah4E.png" alt="enter image description here" /></a></p>
  <p>where <code>(xi, yi)</code> and <code>(xj, yj)</code> are the coordinates of 2 foci (<code>i</code> and <code>j</code>), and <code>r</code> is the difference in distance between a given point on the hyperbola <code>(x, y)</code> and each of the foci.</p>
  <p>It seems the best way to visualise a hyperbola using R is to visualise contour lines (when contour level = 0) of a 3D hyperboloid, determined using the above equation and implementing it into a function</p>
  <pre><code>f1 &lt;- function(xi, yi, xj, yj, x, y, r){
    sqrt((xj - x)^2 + (yj - y)^2) - sqrt((xi - x)^2 + (yi - y)^2) - r
    }
  </code></pre>
  <p>As an example, we can build a grid and visualise the contour level 0 for both hyperbolae:</p>
  <pre><code>library(tidyverse)
  library(sf)
  
  # sample points
  tribble(
    ~name, ~x, ~y,
    'a', 25, 25,
    'b', 75, 25,
    'c', 50, 75,
  ) %&gt;%
    {. -&gt;&gt; sample_points}
  
  # sample hyperbolae
  expand.grid(
    x = seq(0, 100, length = 100),
    y = seq(0, 100, length = 100)
  ) %&gt;%
    as_tibble %&gt;%
    mutate(
      z1 = f1(xi = 25, yi = 25, xj = 75, yj = 25, x, y, r = 5), # i = point a, j = point b
      z2 = f1(xi = 25, yi = 25, xj = 50, yj = 75, x, y, r = 5)  # i = point a, j = point c
    ) %&gt;%
    {. -&gt;&gt; hyp_data} %&gt;%
    ggplot()+
    geom_contour(aes(x, y, z = z1), breaks = 0, colour = 1)+
    geom_contour(aes(x, y, z = z2), breaks = 0, colour = 2)+
    geom_point(data = sample_points, aes(x, y, color = name), size = 3)+
    coord_sf()
  </code></pre>
  <p><a href="https://i.stack.imgur.com/ZySRd.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/ZySRd.png" alt="enter image description here" /></a></p>
  <p>Currently, I can find the point of intersection by extracting the line data from the two <code>geom_contour</code> lines, using <code>ggplot_build()</code>, converting the line coordinates to an <code>sf</code> <code>LINESTRING</code>, and use <code>st_intersection</code> to find the point of intersection:</p>
  <pre><code># extract the data from the ggplot using ggplot_build()
  ggplot_build(
  
    hyp_data %&gt;%
      ggplot()+
      geom_contour(aes(x, y, z = z1), breaks = 0, colour = 1)+
      geom_contour(aes(x, y, z = z2), breaks = 0, colour = 2)+
      # geom_point(data = sample_points, aes(x, y, color = name), size = 3)+ # we dont need the point data in ggplot_build()
      coord_sf()
  
  ) %&gt;%
    .$data %&gt;%  # keep only the data component
    map(. %&gt;% select(x, y) %&gt;% as.matrix %&gt;% st_linestring) %&gt;% # keep coordinates, turn into a linestring
    {. -&gt;&gt; lines1}
  
  # make the lines an sf object
  tibble(a = 1:2) %&gt;%
    mutate(
      geom = st_sfc(lines1),
      ) %&gt;%
    st_as_sf %&gt;% # then make the whole thing an sf object
  
    # use st_intersection to find the point of intersection
    st_intersection %&gt;%
  
    # then keep only the 'point' (exclude the original 'lines')
    filter(
      st_is(geom, 'POINT') 
    ) %&gt;%
    {. -&gt;&gt; intersection_point} %&gt;%
    ggplot()+
    geom_sf(colour = 'red', size = 5)+
    geom_contour(data = hyp_data, aes(x, y, z = z1), breaks = 0, colour = 1)+
    geom_contour(data = hyp_data, aes(x, y, z = z2), breaks = 0, colour = 2)+
    geom_point(data = sample_points, aes(x, y, colour = name), size = 3)
  </code></pre>
  <p><a href="https://i.stack.imgur.com/aNBvY.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/aNBvY.png" alt="enter image description here" /></a></p>
  <p>The limitation of this method is that it relies upon the ability of <code>ggplot</code>'s <code>geom_contour</code> to visualise the contour lines. When the absolute value of <code>r</code> approaches the distance between two points (dist between a-b = 50), the hyperbola narrows and eventually becomes a straight line 'behind' one of the points. Here, <code>geom_contour</code> can't build contour lines, and therefore no line data is created, so the intersection can't be found. See how the following plot only has 5 lines when there should be 6; <code>z6</code> doesn't plot and causes a warning message:</p>
  <pre><code>expand.grid(
    x = seq(0, 100, length = 100),
    y = seq(0, 100, length = 100)
  ) %&gt;%
    as_tibble %&gt;%
    mutate(
      # z = f1(x, y, nr)
      z1 = f1(xi = 25, yi = 25, xj = 75, yj = 25, x, y, r = 5),
      z2 = f1(xi = 25, yi = 25, xj = 75, yj = 25, x, y, r = 15),
      z3 = f1(xi = 25, yi = 25, xj = 75, yj = 25, x, y, r = 25),
      z4 = f1(xi = 25, yi = 25, xj = 75, yj = 25, x, y, r = 35),
      z5 = f1(xi = 25, yi = 25, xj = 75, yj = 25, x, y, r = 45),
      z6 = f1(xi = 25, yi = 25, xj = 75, yj = 25, x, y, r = 50),
    ) %&gt;%
    ggplot()+
    geom_contour(aes(x, y, z = z1), breaks = 0, colour = 1)+
    geom_contour(aes(x, y, z = z2), breaks = 0, colour = 2)+
    geom_contour(aes(x, y, z = z3), breaks = 0, colour = 3)+
    geom_contour(aes(x, y, z = z4), breaks = 0, colour = 4)+
    geom_contour(aes(x, y, z = z5), breaks = 0, colour = 5)+
    geom_contour(aes(x, y, z = z6), breaks = 0, colour = 6)+
    geom_point(data = sample_points, aes(x, y, color = name), size = 3)+
    coord_sf()
  
  # Warning messages:
  # 1: stat_contour(): Zero contours were generated 
  # 2: In min(x) : no non-missing arguments to min; returning Inf
  # 3: In max(x) : no non-missing arguments to max; returning -Inf
  </code></pre>
  <p><a href="https://i.stack.imgur.com/lh4kS.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/lh4kS.png" alt="enter image description here" /></a></p>
  <p><code>z6</code> in theory should be represented by the dashed line below:
  <a href="https://i.stack.imgur.com/AP8MR.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/AP8MR.png" alt="enter image description here" /></a></p>
  <p>I have developed methods for creating these straight lines when contour lines can't be generated, but I would like to be able to use a &quot;mathematical/algebraical&quot; approach to finding the point of intersection of the two lines, and not rely on the spatial/mapping/countour approach within R.</p>
  <p>I have explored options using functions such as <code>uniroot()</code> and <code>solve()</code>, but have had limited success, possibly due to my limited understanding of the fundamental mathematics and/or the fact that the equation describing the hyperbola has both <code>x</code> and <code>y</code> terms?</p>
  <br>
  <p>My current idea involves writing a pair of equations, with an equal right hand side of 0 (apologies for incorrect maths language?):</p>
  <p><a href="https://i.stack.imgur.com/9K018.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/9K018.png" alt="enter image description here" /></a>
  <a href="https://i.stack.imgur.com/Lo3so.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/Lo3so.png" alt="enter image description here" /></a></p>
  <p>(or a trio of equations):</p>
  <p><a href="https://i.stack.imgur.com/9K018.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/9K018.png" alt="enter image description here" /></a>
  <a href="https://i.stack.imgur.com/Lo3so.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/Lo3so.png" alt="enter image description here" /></a>
  <a href="https://i.stack.imgur.com/uHOvV.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/uHOvV.png" alt="enter image description here" /></a></p>
  <p>whereby as above, <code>(xi, yi)</code>, <code>(xj, yj)</code> and <code>(xk, yk)</code> are the coordinates of three foci (<code>i</code>, <code>j</code> &amp; <code>k</code>), and <code>r</code> is the range difference. <code>xi, yi, xj, yj, xk, yk</code> can be substituted for the coordinates of points <code>a, b, c</code> in the above example</p>
  <p>Then, I <em>think</em> it should be possible to solve the equations using a similar process to that described here <a href="https://www.wikihow.com/Algebraically-Find-the-Intersection-of-Two-Lines" rel="nofollow noreferrer">https://www.wikihow.com/Algebraically-Find-the-Intersection-of-Two-Lines</a>, but I don't know how this translates into R code and/or existing R functions.</p>
  <br> 
  <p>The aim of this is to determine the location of a transmitter (point of intersection), based on time-difference-of-arrival (TDOA) of transmissions received by receiving antennae (foci) and hyperbolic positioning principles and trilateration/multilateration (similar to how GPS works).</p>
  <p>I will be dealing with thousands to millions of pairs of hyperbolae, so ideally this process is relatively fast and manageable by a regular computer. Also, <em>not essential but hopefully achievable</em> is the ability to 'scale up' a process to handle more than a pair/trio of equal equations (max ~10), in instances where the same transmission is received by more than three stations (eg 'number of satellites' when using GPS).</p>
  <p>I would greatly appreciate absolutely any ideas or help anyone can offer, as I have been thinking about and working on trying to figure this out for quite some time. Thank you.</p>