forked from boostorg/geometry
-
Notifications
You must be signed in to change notification settings - Fork 1
Geographic algorithms
Vissarion Fisikopoulos edited this page Jun 5, 2019
·
1 revision
We divide the 100K entries of randomly distributed points and the 50K entries with short distances of dataset https://zenodo.org/record/32156#.WOyaMrUmv7C in the following 15 categories with respect to distance of input points:
2 10 100 1K 2K 1000K 2000K 5000K 7500K 10000K 12500K 15000K 17500K 19000K 20000K
e.g. the data of 3-rd category are points with distance >10m and <100m.
We have the following number of data per category:
94 326 3979 40523 5077 614 1934 12386 16316 19078 19159 15886 10833 3634 160
Run on Intel(R) Core(TM) i5-5300U CPU @ 2.30GHz with gcc 7.4.
We test methods vincenty, thomas and andoyer as in Boost.Geometry 1.69 and series method from https://github.com/boostorg/geometry/pull/500. series-k denote the use of k-th order series.
We compute the maximum absolute error for distance (in meters), azimuth (in degrees) and area (in square meters). In all computations are performed with double(first rows) and long double(last rows). For area we also consider the following projections
- aea - Albers Equal Area (https://proj4.org/operations/projections/aea.html)
- cea - Equal Area Cylindrical (https://proj4.org/operations/projections/cea.html)
- leac - Lambert Equal Area Conic (https://proj4.org/operations/projections/leac.html)
- laea - Lambert Azimuthal Equal Area (https://proj4.org/operations/projections/laea.html)
followed by a cartesian area computation.
| 2 | 10 | 100 | 1K | 2K | 1000K | 2000K | 5000K | 7500K | 10000K | 12500K | 15000K | 17500K | 19000K | 20000K | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| vincenty | 4.248057384e-06 | 3.947048307e-06 | 3.593635242e-06 | 6.310545444e-06 | 4.329149533e-06 | 6.929389201e-06 | 1.434027217e-05 | 3.41385603e-05 | 4.836451262e-05 | 5.976483226e-05 | 6.797909737e-05 | 7.792189717e-05 | 7.868744433e-05 | 7.887929678e-05 | 1059.260239 |
| thomas | 0.1737279 | 0.001021178179 | 0.0002089783173 | 2.254560847e-05 | 5.039413963e-06 | 0.002755686874 | 0.005525078392 | 0.01340140309 | 0.01953940932 | 0.02994969301 | 0.09233240411 | 0.3136218823 | 1.71884165 | 48.67808169 | 927.742111 |
| andoyer | 0.0636499 | 0.002903012822 | 0.001193334267 | 0.01244442672 | 0.01396748535 | 11.39279713 | 23.9528954 | 51.61047244 | 63.08675041 | 67.83741458 | 68.35681641 | 68.04263538 | 130.3050551 | 811.9854736 | 3090.820303 |
| series-1 | 2.610695704e-06 | 1.22101419e-05 | 0.0001366513411 | 0.001394209173 | 0.001549297192 | 1.355012524 | 2.673575212 | 6.290930971 | 8.541003645 | 9.92855888 | 10.7255582 | 12.69478906 | 13.82121903 | 14.07305654 | 14.04968645 |
| series-4 | 1.851601095e-09 | 3.58336294e-09 | 3.442033858e-08 | 3.492912128e-07 | 3.884520083e-07 | 0.0003278704826 | 0.000682215672 | 0.001567726023 | 0.00204947032 | 0.00223742798 | 0.002237271518 | 0.002050759271 | 0.001576351002 | 0.0008415542543 | 0.000147651881 |
| series-8 | 1.851601095e-09 | 3.583277675e-09 | 3.442033858e-08 | 3.492914402e-07 | 3.884522357e-07 | 0.000327685615 | 0.0006825863384 | 0.001567084342 | 0.002049922943 | 0.002237433568 | 0.002237293869 | 0.002051241696 | 0.001577019691 | 0.0008410997689 | 0.0001475587487 |
| geographiclib | 2.299986646e-09 | 2.336426164e-09 | 2.803940191e-09 | 3.402533366e-09 | 3.573745744e-09 | 2.677552402e-09 | 2.328306437e-09 | 3.725290298e-09 | 4.656612873e-09 | 5.587935448e-09 | 5.587935448e-09 | 7.450580597e-09 | 7.450580597e-09 | 7.450580597e-09 | 3.725290298e-09 |
| vincenty | 4.248044318e-06 | 3.947043948e-06 | 3.593634969e-06 | 6.310541642e-06 | 4.329052881e-06 | 6.929256756e-06 | 1.434095066e-05 | 3.413950071e-05 | 4.836480775e-05 | 5.97624894e-05 | 6.798143113e-05 | 7.792071028e-05 | 7.868536795e-05 | 7.887827269e-05 | 1059.260239 |
| thomas | 0.0015686 | 4.341884984e-07 | 2.836961051e-07 | 2.79491353e-06 | 3.112101418e-06 | 0.002755687303 | 0.00552507779 | 0.01340140498 | 0.01953941166 | 0.02994969113 | 0.09233240479 | 0.3136218789 | 1.718841653 | 48.6780817 | 927.7421104 |
| andoyer | 0.0015686 | 0.0001086438954 | 0.001205257165 | 0.01244773396 | 0.01396338987 | 11.39279714 | 23.95289539 | 51.61047244 | 63.08675041 | 67.83741458 | 68.3568164 | 68.04263538 | 130.3050551 | 811.9854736 | 3090.820303 |
| series-1 | 2.610228815e-06 | 1.220963888e-05 | 0.0001366514903 | 0.001394208259 | 0.001549297198 | 1.355012524 | 2.673575212 | 6.290930972 | 8.541003647 | 9.928558879 | 10.7255582 | 12.69478907 | 13.82121903 | 14.07305654 | 14.04968645 |
| series-4 | 9.696168245e-10 | 3.299633669e-09 | 3.413937597e-08 | 3.499170214e-07 | 3.882842732e-07 | 0.0003278714397 | 0.0006822165277 | 0.001567726839 | 0.002049469235 | 0.002237428146 | 0.002237271905 | 0.002050759585 | 0.001576353336 | 0.0008415517168 | 0.0001476514717 |
| series-8 | 9.696164875e-10 | 3.297864363e-09 | 3.411900604e-08 | 3.497120364e-07 | 3.880596932e-07 | 0.0003276854559 | 0.0006825859259 | 0.001567084922 | 0.002049922404 | 0.0022374328 | 0.002237294189 | 0.002051239764 | 0.001577020446 | 0.0008410965074 | 0.0001475583686 |
| 2 | 10 | 100 | 1K | 2K | 1000K | 2000K | 5000K | 7500K | 10000K | 12500K | 15000K | 17500K | 19000K | 20000K | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| vincenty | 0.06122907628 | 0.0001061736336 | 2.218865609e-05 | 2.541963624e-06 | 3.499366699e-07 | 2.468254934e-09 | 3.113882485e-10 | 2.023341494e-10 | 2.591349357e-10 | 3.340829835e-10 | 4.653131214e-10 | 6.591776014e-10 | 1.336246669e-09 | 5.679915205e-09 | 5.738222017 |
| thomas | 179.882831 | 1.078333639e-06 | 1.079585331e-06 | 1.079699587e-06 | 1.079667513e-06 | 1.076029008e-06 | 1.074942276e-06 | 1.067273189e-06 | 1.031084665e-06 | 1.203123638e-06 | 3.430271406e-06 | 1.344940702e-05 | 0.0001408245561 | 0.01945634857 | 18.55140701 |
| andoyer | 135.5245742 | 0.0005571204485 | 0.0005679493512 | 0.000568103735 | 0.000568057219 | 0.0005664834217 | 0.0005661198788 | 0.0005640716677 | 0.0005506206157 | 0.0005280159761 | 0.0005546688209 | 0.001546024721 | 0.007805778626 | 0.202370693 | 3.871551831 |
| series-1 | 4.76185164e-05 | 4.006775561e-05 | 4.036415496e-05 | 4.038526248e-05 | 4.038152704e-05 | 4.346616072e-05 | 4.843488368e-05 | 6.71237493e-05 | 8.592067859e-05 | 0.0001100632372 | 0.000145521563 | 0.0002157326148 | 0.0004008759263 | 0.001774815035 | 0.006555645032 |
| series-4 | 4.76185164e-05 | 6.233504735e-08 | 3.595579301e-08 | 3.542157856e-08 | 3.513778779e-08 | 3.457467912e-08 | 3.484072408e-08 | 3.477677524e-08 | 3.28295755e-08 | 3.014636718e-08 | 2.98018179e-08 | 3.263015103e-08 | 3.382316649e-08 | 3.390450942e-08 | 2.832578616e-08 |
| series-8 | 4.76185164e-05 | 6.233504735e-08 | 3.595579301e-08 | 3.542157856e-08 | 3.521390113e-08 | 3.460015563e-08 | 3.486468358e-08 | 3.480084843e-08 | 3.284483796e-08 | 3.015296102e-08 | 2.980961966e-08 | 3.264579718e-08 | 3.384511871e-08 | 3.392769443e-08 | 2.83457382e-08 |
| geographiclib | 4.76185164e-05 | 6.545454312e-08 | 1.174844044e-08 | 1.179927267e-09 | 1.477360456e-10 | 5.542233339e-13 | 1.136868377e-13 | 5.684341886e-14 | 5.684341886e-14 | 5.684341886e-14 | 5.684341886e-14 | 5.86197757e-14 | 1.065814104e-13 | 2.98427949e-13 | 1.591615728e-12 |
| vincenty | 0.06119902749 | 0.0001061748829 | 2.218753914e-05 | 2.541962794e-06 | 3.499379569e-07 | 2.46826388e-09 | 3.113838076e-10 | 2.023323661e-10 | 2.591332704e-10 | 3.34084746e-10 | 4.653061443e-10 | 6.591748085e-10 | 1.336261133e-09 | 5.679999044e-09 | 5.738222017 |
| thomas | 126.4065304 | 1.078323414e-06 | 1.079578671e-06 | 1.07969971e-06 | 1.079667443e-06 | 1.076029004e-06 | 1.074942278e-06 | 1.06727317e-06 | 1.031084666e-06 | 1.203123645e-06 | 3.430271417e-06 | 1.344940702e-05 | 0.0001408245562 | 0.01945634857 | 18.55140702 |
| andoyer | 126.4065304 | 0.0005571203475 | 0.0005679493505 | 0.000568103735 | 0.0005680572189 | 0.0005664834217 | 0.0005661198788 | 0.0005640716677 | 0.0005506206156 | 0.0005280159761 | 0.0005546688209 | 0.001546024721 | 0.007805778626 | 0.202370693 | 3.871551831 |
| series-1 | 3.830968883e-05 | 4.005762289e-05 | 4.036431761e-05 | 4.038528684e-05 | 4.03815701e-05 | 4.346616075e-05 | 4.843488371e-05 | 6.712374931e-05 | 8.592067859e-05 | 0.0001100632372 | 0.0001455215631 | 0.0002157326148 | 0.0004008759264 | 0.001774815035 | 0.006555645032 |
| series-4 | 1.8196167e-05 | 3.306526525e-08 | 3.518680754e-08 | 3.519845501e-08 | 3.518816653e-08 | 3.457482014e-08 | 3.484071802e-08 | 3.477673555e-08 | 3.282955931e-08 | 3.014634813e-08 | 2.980180488e-08 | 3.26301656e-08 | 3.382316702e-08 | 3.390453042e-08 | 2.832579098e-08 |
| series-8 | 1.8196167e-05 | 3.308248933e-08 | 3.521261917e-08 | 3.522378354e-08 | 3.521342784e-08 | 3.460060101e-08 | 3.486468823e-08 | 3.48008353e-08 | 3.284483206e-08 | 3.015292158e-08 | 2.980961979e-08 | 3.264580779e-08 | 3.384510716e-08 | 3.392767744e-08 | 2.834561492e-08 |
| 2 | 10 | 100 | 1K | 2K | 1000K | 2000K | 5000K | 7500K | 10000K | 12500K | 15000K | 17500K | 19000K | 20000K | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| vincenty | 294826.7955 | 6151.358989 | 1841.908889 | 206.3319743 | 42.76292038 | 35.90026855 | 67.47851562 | 175.359375 | 275.7421875 | 398.6796875 | 606.234375 | 890.96875 | 1877.1875 | 8044.890625 | 8.165371929e+12 |
| thomas | 5277845.625 | 0.4612705521 | 4.777551055 | 62.609375 | 52.76881409 | 43617.13721 | 95401.24463 | 237754.0742 | 514751.7266 | 1464026.633 | 4479900.68 | 18550463.61 | 197631184.3 | 2.767418789e+10 | 2.638835358e+13 |
| andoyer | 468993.1572 | 13207.52671 | 5169.802537 | 38685.14441 | 42855.11346 | 38601578.79 | 80237700.34 | 213288901.2 | 290553300.4 | 324060203.5 | 706745298.3 | 2152213850 | 1.10203828e+10 | 2.879563103e+11 | 5.514279131e+12 |
| series-1 | 22.7920971 | 111.9784208 | 1133.046256 | 11477.36187 | 12784.12042 | 10898285.11 | 22396182.62 | 59548714.61 | 93385711.78 | 133167319.3 | 189965211.2 | 292666378.2 | 576760702.1 | 2524451940 | 9357538642 |
| series-4 | 0.08897829056 | 0.3128962517 | 9.831787109 | 87.828125 | 4.280014038 | 3765.701172 | 7722.847656 | 18521.61719 | 27294.17188 | 34779.71875 | 40677.98438 | 45383.29688 | 47865.64062 | 47860.375 | 40474.9375 |
| series-8 | 0.08897829056 | 0.3128962517 | 9.831787109 | 87.828125 | 4.265134811 | 3763.121094 | 7717.601562 | 18512.90625 | 27286.53125 | 34779.45312 | 40688.71875 | 45405.85938 | 47897.67188 | 47894.96875 | 40503.46875 |
| proj-aea | 2.712011337e-06 | 0.004220962524 | 94221.06006 | 8.032622936e+10 | 22005448.29 | 1.878518167e+11 | 1.318342693e+12 | 8.752704247e+12 | 2.028072412e+13 | 3.644145885e+13 | 9.285287621e+13 | 1.441971446e+14 | 1.739401411e+14 | 2.080209684e+14 | 2.103457394e+14 |
| proj-cea | 2.145767212e-06 | 0.0007476806641 | 24.06445312 | 472318.4531 | 40706.46875 | 1.675946949e+11 | 1.262569871e+12 | 1.345326292e+13 | 3.279934817e+13 | 5.589099649e+13 | 7.586953021e+13 | 1.039346802e+14 | 1.146652732e+14 | 1.25017136e+14 | 1.2406127e+14 |
| proj-leac | 0.0001802444458 | 1.037779808 | 28083341.09 | 2.225760292e+13 | 6546191360 | 1.088609774e+13 | 3.902130727e+13 | 4.936037911e+13 | 5.856880029e+13 | 6.947364003e+13 | 1.042015524e+14 | 1.391528746e+14 | 1.595842385e+14 | 1.866681965e+14 | 1.90043297e+14 |
| proj-laea | 2293817.575 | 14937780.18 | 248210741.4 | 7.111962905e+13 | 2.649881487e+10 | 3.662062906e+13 | 1.105067697e+14 | 1.274427736e+14 | 1.272158717e+14 | 1.274474122e+14 | 1.274518265e+14 | 1.275024104e+14 | 1.274892427e+14 | 1.27496124e+14 | 1.325364972e+14 |
| geographiclib | 0.007800199091 | 0.008114591241 | 0.008853912354 | 0.03125 | 0.009017944336 | 0.015625 | 0.03125 | 0.03125 | 0.046875 | 0.046875 | 0.0625 | 0.078125 | 0.140625 | 0.40625 | 2.2578125 |
| vincenty | 2384.45702 | 36.58234385 | 39.41058787 | 40.30743669 | 39.95229413 | 35.90020609 | 67.47455883 | 175.3672142 | 275.7505951 | 398.6749496 | 606.2301521 | 890.9422951 | 1877.153778 | 8046.671738 | 8.165371929e+12 |
| thomas | 11316.7576 | 0.4572235855 | 4.765071949 | 47.65162026 | 52.76075173 | 43617.13434 | 95401.23342 | 237754.0679 | 514751.7256 | 1464026.635 | 4479900.679 | 18550463.58 | 197631184.3 | 2.767418789e+10 | 2.638835358e+13 |
| andoyer | 11316.7576 | 369.3123038 | 3747.869114 | 38686.25095 | 42857.71696 | 38601578.79 | 80237700.34 | 213288901.2 | 290553300.4 | 324060203.5 | 706745298.3 | 2152213850 | 1.10203828e+10 | 2.879563103e+11 | 5.514279095e+12 |
| series-1 | 22.79728636 | 111.9718415 | 1133.044648 | 11477.36393 | 12784.12518 | 10898285.1 | 22396182.62 | 59548714.61 | 93385711.79 | 133167319.3 | 189965211.2 | 292666378.1 | 576760702.3 | 2524451940 | 9357538724 |
| series-4 | 0.007143652465 | 0.03569182609 | 0.3795686594 | 3.893578262 | 4.272559864 | 3765.707318 | 7722.829136 | 18521.61201 | 27294.17405 | 34779.70271 | 40677.95329 | 45383.26018 | 47865.61415 | 47860.33467 | 40474.97028 |
| series-8 | 0.007143313032 | 0.03566848458 | 0.3792867158 | 3.890755051 | 4.269623316 | 3763.119613 | 7717.607189 | 18512.89513 | 27286.49744 | 34779.43755 | 40688.74068 | 45405.88792 | 47897.67833 | 47894.97375 | 40503.29689 |
We measure the time in nsec average over 100 runs for double and 50 runs for long double. The latter are denoted with a * in the table.
| method | distance | azimuth | area | distance* | azimuth* | area* |
|---|---|---|---|---|---|---|
| vincenty | 534 | 566 | 1036 | 1403 | 1421 | 2692 |
| thomas | 267 | 384 | 748 | 832 | 1168 | 2350 |
| andoyer | 129 | 269 | 600 | 577 | 1066 | 2153 |
| series-1 | 7535 | 7705 | 7900 | 20783 | 21576 | 22156 |
| series-4 | 8952 | 8765 | 8916 | 25890 | 28306 | 28788 |
| series-8 | 16242 | 16111 | 16565 | 44957 | 44484 | 45106 |
| proj-cea | --- | --- | 2299 | --- | --- | --- |