0

I'm trying to find the point where 2 lines intersect. I am using this example on geeks for geeks.

This works well for small numbers. I am using "accurate" latitude and longitude points which are scaled by 10000000. So a latitude of 40.4381311 would be 404381311 in my program. I can't use double as I will lose accuracy and the whole point of getting the points scaled like this is for accuracy.

So in the geeks for geeks example I changed everywhere they use double to use int64_t. But unfortunately this is still not enough.

By the time you get to:

double determinant = a1*b2 - a2*b1;

or:

double x = (b2*c1 - b1*c2)/determinant;
double y = (a1*c2 - a2*c1)/determinant;

The number will be too big for int64_t. What is my best way around this issue while still keeping accuracy.

I am writing this code for an ESP32 and it doesn't seem to have __int128/__int128_t.

Thanks!

cigien
  • 57,834
  • 11
  • 73
  • 112
av4625
  • 303
  • 1
  • 11
  • 1
    gcc has __int128 from some processors. Depends on how portable it needs to be. – Jerry Jeremiah Jul 17 '22 at 22:06
  • @JerryJeremiah I did check if that is available to me and unfortunately it isn't, I am writing the code for an ESP32. I'll add this information to my question – av4625 Jul 17 '22 at 22:16
  • Here's a portable alternative: https://abseil.io/docs/cpp/guides/numeric – David Eisenstat Jul 17 '22 at 22:33
  • 1
    You understand that you can’t treat latitude and longitude as “x and y” when doing operations like this, right? That won’t produce an accurate intersection. – Sneftel Jul 17 '22 at 22:56
  • @Sneftel I didn't know this, why is that? I tested with some lat/long coordinates from google maps and it seemed to accurately show intersection of my imaginary line. It might be because my lines are short? I get my lat/long data at 10Hz so the "lines" are current fix and previous fix and are never very long – av4625 Jul 17 '22 at 23:07
  • Does this answer your question? [How to handle arbitrarily large integers](https://stackoverflow.com/questions/310276/how-to-handle-arbitrarily-large-integers) – cigien Jul 18 '22 at 01:41
  • 2
    @Sneftel is pointing out that using linear equations on a non-linear co-ordinate system is prone to inaccuracy. If you are not operating near the poles and you are localizing these intersections to a small area, then the linear approximation might be "close enough" depending on the level of precision you're aiming for. Outside of this, results might degrade, become wildly inaccurate, or simply be incorrect. – paddy Jul 18 '22 at 01:49
  • 1
    Are you sure `double` can't handle your coordinates? Your example has 9 decimal digits (assuming all are significant), while `double` has about 16 decimal digits of precision. I would be really surprised if doing calculations with `double` led to a meaningful loss of precision. – swineone Jul 18 '22 at 02:21
  • I suggest using a suitable unsigned type (e.g. `uint64_t`) to represent lat/long (e.g. latitudes in range [-90, 90) mapped to the range [0, ) (where is the maximum value the type can represent). All operations on unsigned variables use modulo arithmetic, so (e.g.) will correctly map a calculated latitude of 91 degrees to its equivalent of -89 degrees. Achievable accuracy depends only on the chosen type, not an arbitrary scale factor, so you only need to worry about loss of accuracy when mapping to/from human-readable values (or floating point) on output/input, not intermediate calcs – Peter Jul 18 '22 at 02:43
  • 1
    One option to increase precision beyond hardware is to use a "big number" software package. The GNU GMP library comes to mind. –  Jul 18 '22 at 04:56
  • Related and probably helpful: [Catch and compute overflow during multiplication of two large integers](https://stackoverflow.com/q/1815367/4561887), and my answer to this question: [Fixed Point Arithmetic in C Programming](https://stackoverflow.com/a/53936802/4561887)--see in particular my "Example 2" "8th approach". – Gabriel Staples Jul 18 '22 at 18:18
  • Also, don't use **linear** math to detect the intersection of **non-linear, spheroidal lines** around the Earth. Remember that you'd have to use the proper math for detecting the intersection of lines around the Earth. Spherical math would be better, but actually the Earth is an oblate spheroid, meaning a slightly squished-down or flattened sphere, since the centrifugal force of spinning makes it bulge out at the equator and flatten in at the poles. I learned this in my several orbital dynamics and rocket science classes. – Gabriel Staples Jul 18 '22 at 18:23
  • Have you tried 128bit `double`s in C or C++? It usually utilizes a better representation of floating point arithmetic that will trade of errors much better than any home brewed fixed-scale system you come up with (unless of course you only intend to work with rational numbers.) See for example: https://stackoverflow.com/questions/33584553/c-128-bit-double-type – ldog Jul 19 '22 at 06:33

0 Answers0