0

For a program I am writing I need to calculate the distances between coordinates. Seeing as I need to perform a large number of these calculations for each coordinate (thousands) it makes sense to convert to UTM, then calculate the distance (seeing as I am just comparing distances, I can even work with the square of the distance between the points).

At what point does this trade off make sense? As far as I can tell by reading the relevant calculations Greater Circle would be the faster algorithm, but obviously once you do the conversion to UTM you don't need to do it again. How many times do you need to run the Greater Circle algorithm before it makes sense to convert to UTM instead? (Assume that the accuracy isn't a big deal in my situation).

whossname
  • 109
  • 2
  • How accurate do the distances need to be and what's the longest distance you plan to calculate? Transverse Mercator isn't a particularly speedy algorithm itself. – mkennedy Feb 11 '19 at 04:03
  • small distances think in the 100m range. I thought Transverse Mercator would be the slower algorithm, the advantage would be that I only need to run it once per point instead of thousands of times with Greater Circle. – whossname Feb 11 '19 at 04:12
  • as far as accuracy is concerned so long as it is within say 10cm, I'm happy. Is accuracy a concern with either of these algorithms? – whossname Feb 11 '19 at 04:14
  • 2
    Have you considered doing performance tests for comparison? – Kirk Kuykendall Feb 11 '19 at 04:37
  • 1
    Indeed, @KirkKuykendall has the right idea here. The best way to know how your data will perform on your hardware in two or three different algorithms is to perform a benchmark evaluation with a statistically significant sample of features. – Vince Feb 11 '19 at 11:19
  • Before considering UTM, make sure all your points are in the same zone – JGH Feb 11 '19 at 12:18
  • In the end it turned out that relying on UTM instead of greater circle removes a bottleneck in the program. Basically I designed an algorithm that could run part of the program in concurrent workers before feeding into an aggregator. The UTM calculation can be done in the workers while greater circle would need to be used in the aggregator. So for reasons that have nothing to do with the original question, UTM was the correct answer for me. – whossname Feb 21 '19 at 01:40
  • If 10cm accuracy is a problem, then UTM could be a concern. Per https://gis.stackexchange.com/a/212080/10229 the 0.04% accuracy of UTM within its +/-3 degree lat zone would mean you couldn't go above above 0.10/0.0004=250m between points. – Dave X Nov 07 '20 at 00:32

1 Answers1

1

1)

IMHO, If your app were to run on a present-day server/desktop/notebook, be it real or virtual, any amount of effort you put into ramping up the computation throughput will far outweigh the return. Thousands of points or thousands of pairs of points are relatively small amounts. I would just use a library, e.g., the Karney formula/function in GeoPy.

2)

For 10 cm error margin, I would turn to Vincenty or Karney. But since your distances are small (i.e., within 100 meters), I doubt this recommendation matters.

3)

As JGH had correctly cautioned, if you go the convert-to-UTM-first route, all your points must be in the same UTM zone, or projected into the same Transverse Mercator grid/plane. And you need to be aware that a UTM Zone or a projected Transverse Mercator grid plane has its valid bounds.

Ralph Tee
  • 1,722
  • 12
  • 17
  • It's actually millions of points, it's just that I'm running an O(nlogn) algorithm so I only need to run it thousands of times per point. The previous thing I tried took 17 hours for 2 weeks of data. We have years of data to process.
    • – whossname Feb 12 '19 at 12:12
  • Don't worry, I'm on top of this part of it. I've done a fait bit of work with UTM in the past
    • – whossname Feb 12 '19 at 12:14
  • thanks for this, I'll check those out
    • – whossname Feb 12 '19 at 12:14