Растояние меду Почтовыми кодами(Индуская мысль)

[mak_sim2001]

Растояние меду Почтовыми кодами(Индуская мысль)

Просто ложу копию письма котрую выслад мне недоумённый работадатель.

Hi Denis,

Ram sent me this email (see below). Do you agree with the issues that he listed?

We can not use this database because each time we need to calculate distance between client city and user city. There are more than 70000 data in CSV because it’s contains all cities of Canada. Because of that, it will take too much time to execute. And if there were three banners in page, it will take more time to execute.

è Also, we do not have any way to find distance between two postal code using longitude and latitude and it will be very big issue. I hope you understand it.

è We need database structure like (Only for Calgary city)

Postal code Postal code distance

E5G 4C4 E5G 4J2 2.5 KM (approx.)

Маленькое пояснение до этого ему выслали БД в csv формате для всей Канады с полями
Postal_code|LATITUDE|LONGITUDE (почтовый код, широта, долгота)
Задача:
1. уметь находить растояние между двумя Postal Code
2. Находить все PostalCode в радиусе 'n' км

прикиньте количетво полей в Базе если в Канаде->Alberta около 75тыс. кодов
что-то типа 2^75000 - 1 ну минус повторяющиеся

 

[confguru]

Спасибо... теперь у нас будут новые тесты на собеседовании ..

 

[kruglov]

Формула не такая тривиальная, земля ж не плоская, длина градуса по долготе от широты зависит чтоб теорему пифагора применять.

Хотя, если ему для одного города всего надо... Там можно пренебречь, наверное.

 

[mak_sim2001]

Сам работадатель нашел в инете формулу за минуту хотя он далёк от математики и программирования

sqrt(x * x + y * y)
where x = 69.1 * (lat2 - lat1)
and y = 53.0 * (lon2 - lon1)

коофициенты я непроверял )))

согласен что земля круглая а инет большой )))

 

[Oleg Marchuk]

Мне кажется, что оценка размера таблицы не верная

 

[kruglov]

mak_sim2001
Че-та формула мне не нравится. y должен не только от lon зависеть. И вообще почему-то x по вертикали измеряется, а y - по горизонтали.

 

[Wicked]

да, формула заведомо неправильная.
см. http://gis-lab.info/qa/great-circles.html

я бы все таки оставил табличку с широтой и долготой хотя бы потому что в ней тоже можно осуществлять поиск, используя индексы. При том, что размер у нее так и так меньше.

 

[fixxxer]

если хочется быстрых расчетов то теоремой пифагора + поправочным коэффициентом можно получить довольно точную для этих целей аппроксимацию. =)

 

[desperado]

да, а потом между ближайшими точками так вдруг выростет Мак-Кинли (%

 

[CatManZero]

Автор оригинала: fixxxer
если хочется быстрых расчетов то теоремой пифагора + поправочным коэффициентом можно получить довольно точную для этих целей аппроксимацию. =)

А после этого, когда точек станет гораздо меньше, можно и более точные формулы использовать.
Если, конечно, это нужно...

 

[mak_sim2001]

fixxxer

если хочется быстрых расчетов то теоремой пифагора + поправочным коэффициентом можно получить довольно точную для этих целей аппроксимацию. =)

+1 А еще проще если база будет очень большой выбирать квадрат со сторонами 2*R а потом более точной формулой

Пример с точной формулой:

           $r = 6378.7; // radius of the earth in km
            $rad = $dist/$r;
            
            $sql = "SELECT Postalcode_title 
                         , Postalcode_city
                         , Postalcode_latitude
                         , Postalcode_longitude
                    FROM postalcode
                    WHERE
                    ACOS( SIN(RADIANS(".$lat.")) * SIN(RADIANS(Postalcode_latitude)) + 
                         COS(RADIANS(".$lat.")) * COS(RADIANS(Postalcode_latitude)) * 
                         COS(RADIANS((". $lon ." - Postalcode_longitude))) ) <= ". $rad;

это sql находит все Postal Code в радиусе $dist (км)
причем если задать радиус что бы в результат входили все 75тыс кодов он выполняется около секунды(дома под виндой) точность 15 знаков после запятой. Его конечно надо упростить, как минимум acos() не делать 75тыс раз(оставил Ram-у на доработку
Еще можно в базе поменять долготу и широту - сохранить уже в радианах.
Решение расширяемо можно легко добавлять новые PostalCode

-~{}~ 18.01.08 17:40:

http://www.meridianworlddata.com/Distance-Calculation.asp - здесь про формулу почитать можно