Geo yakınlık hesaplamak için Formüller

2 Cevap php

Benim uygulamada bir Geo yakınlık arama uygulamak gerekiyor ama ben kullanmak için doğru bir formül ile ilgili çok kafam karıştı. Web ve StackOverflow bazı aramalarda sonra çözüm olduğunu buldu:

  1. Kullanarak Haversine Formül
  2. Use the Great-Circle Distance Formula
  3. Veritabanında bir Spatial Search Engine kullanın

Seçenek # 3 ATM gerçekten benim için bir seçenek değildir. Şimdi biraz kafam karıştı çünkü ben her zaman olsa o Great-Circle Distance Formula ve Haversine Formül synonymous ama görünüşe göre yanılmışım?

Haversine Formül

Yukarıdaki ekran görüntüsü müthiş Geo (proximity) Search with MySQL kağıttan alınan ve aşağıdaki işlevleri kullanır edildi:

ASIN, SQRT, POWER, SIN, PI, COS

Ben de bunun gibi, same formula (Cosines küresel Hukuku) varyasyonlarını gördüm:

(3956 * ACOS(COS(RADIANS(o_lat)) * COS(RADIANS(d_lat)) * COS(RADIANS(d_lon) - RADIANS(o_lon)) + SIN(RADIANS(o_lat)) * SIN(RADIANS(d_lat))))

Yani aşağıdaki işlevleri kullanır:

ACOS, COS, RADIANS, SIN

Ben bir matematik uzmanı değilim, ama bu formülleri aynıdır? En doğru olarak görünüyor - bazı more variations, and formulas (gibi Cosines küresel Hukuku and the Vincenty's formulae geldim ) ve bu beni daha da karıştı yapar ...

PHP / MySQL uygulamak için iyi bir genel amaçlı formülü seçmeniz gerekir. Herkes bana yukarıda belirtilen formüller arasındaki farkları açıklayabilir misiniz?

  • Which one is the fastest to compute?
  • Which one provides the most accurate results?
  • Which one is the best in terms of speed / accuracy of results?

Ben bu sorulara verdiğiniz fikir için teşekkür ederiz.

theonlytheory cevap dayanarak ben aşağıdaki Büyük-Çember Mesafe Formülleri test:

  • Vincenty Formül
  • Haversine Formül
  • Cosines küresel Hukuku

Vincenty Formül ölü yavaş, ancak it's pretty accurate (down to 0.5 mm).

Haversine Formül Vincenty Formül daha hızlı şekilde, ben hemen hemen kabul benim ihtiyaçları için hangi yaklaşık 6 saniyede 1 milyon işlem çalıştırmayı başardı.

Cosines küresel Hukuku Formula olduğu ortaya almost twice as fast, Formül Haversine ve the precision difference is neglectfulness çoğu durumda kullanım için olduğu gibi.

İşte bazı test yerlerdir:

  • Google HQ (37.422045, -122.084347)
  • San Francisco, CA (37.77493, -122.419416)
  • Eiffel Tower, France (48.8582, 2.294407)
  • Opera House, Sydney (-33.856553, 151.214696)

Google HQ - San Francisco, CA:

  • Vincenty Formül: 49 087.066 meters
  • Haversine Formül: 49 103.006 meters
  • Cosines küresel Hukuku: 49 103.006 meters

Google HQ - Eiffel Tower, France:

  • Vincenty Formül: 8 989 724.399 meters
  • Haversine Formül: 8 967 042.917 meters
  • Cosines küresel Hukuku: 8 967 042.917 meters

Google HQ - Opera House, Sydney:

  • Vincenty Formül: 11 939 773.640 meters
  • Haversine Formül: 11 952 717.240 meters
  • Cosines küresel Hukuku: 11 952 717.240 meters

Gördüğünüz gibi no noticeable difference Haversine Formül ve cosines Küresel Kanunu arasındaki var olan bu toprak bir elipsoidal yaklaşım kullanır yerine, çünkü ancak iki distance offsets as high as 22 kilometers Vincenty Formül ile karşılaştırıldığında var Bir küresel bir.

2 Cevap

The Law of Cosines and the Haversine Formula will give identical results assuming a machine with infinite precision. The Haversine formula is more robust to floating point errors. However, today's machines have double precision of the order of 15 significant figures, and the law of cosines may work just fine for you. Both these formulas assume spherical earth, whereas Vicenty's iterative solution (most accurate) assumes ellipsoidal earth (in reality the earth is not even an ellipsoid - it is a geoid). Some references: http://www.movable-type.co.uk/scripts/gis-faq-5.1.html

Bu daha iyi olur: enlem cosines yasanın yanı sıra Haversine jeodezik enlem farklı jeosentrik enlem olduğunu kullanılacak unutmayın. Bir küre için, bu iki aynıdır.

Hangisi hesaplamak için hızlı mı?

Hızlı gelen yavaş amacıyla şunlardır: cosines kanunu (. 5 trigonometri aramalar) -> haversinüs (sqrt içerir) -> Vicenty (yinelemeli bu çözmek zorunda bir döngü için)

Hangisi en doğru olan?

Vicenty.

Hız ve doğruluk hem de dikkate alındığında hangisi en iyisi?

If your problem domain is such that for the distances you are trying to calculate, the earth can be considered as flat, then you can work out (I am not going to give details) a formula of the form x = kx * difference in longitude, y = ky * difference in latitude. Then distance = sqrt(dx*dx + dy*dy). If your problem domain is such that it can be solved with distance squared, then you won't have to take sqrt, and this formula will be as fast as you get possibly get. It has the added advantage that you can calculate the vector distance - x is distance in east direction, and y is distance in the north direction. Otherwise, experiment with the 3 and choose what works best in your situation.

Yani istediğiniz:

  • p0 uzaklığına göre sıralamak kayıtları
  • olan mesafe p0 gelen r azdır yalnızca kayıtları seçin

Hüner tam olarak bunun için büyük daire mesafe hesaplamak gerek kalmamasıdır! Sen gerçek bir değere puan çifti any fonksiyonu ile yapabilirsiniz that strictly grows with the great circle distance between the points. Birçok tür işlevleri vardır ve bazı kesin büyük daire mesafe için çeşitli formüller daha hesaplamak için çok daha hızlıdır. Böyle bir işlevi 3D Öklid mesafedir. Küre üzerinde bir 3D noktaya enlem ve boylam dönüştürme ters trigonometrik fonksiyonlar anlamına gelmez.

Eğer x var sonra, Y, Z, siz de p0 de teğet düzleminden mesafeyi kullanabilirsiniz, çünkü aslında, sizin noktasına p0 mesafeyi gerekmez olduğunu fark edebilirsiniz. Bu mesafe de kesinlikle büyük daire mesafesi ile büyür, ve X hesaplanan, Y lineer bir kombinasyonu olarak Z - bile bir karekök gereklidir. Sadece katsayıları ve istenen büyük daire mesafeye tekabül kesim mesafeyi precompute gerekir.

etiketler