Как эффективно хранить расстояние между городами и поселками в БД

вы должны сохранить city_id, latitude, longitude по одному для каждого города, а затем рассчитать расстояния на основе ввода во время выполнения.

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

PHP-функция для вычисления ограничивающей рамки

function getBoundingBox($lat_degrees,$lon_degrees,$distance_in_miles)
{
       $radius = 3963.1; // of earth in miles

        // bearings
        $due_north = 0;
        $due_south = 180;
        $due_east = 90;
        $due_west = 270;

        // convert latitude and longitude into radians
        $lat_r = deg2rad($lat_degrees);
        $lon_r = deg2rad($lon_degrees);

        // find the northmost, southmost, eastmost and westmost corners $distance_in_miles away
        // original formula from
        // http://www.movable-type.co.uk/scripts/latlong.html

        $northmost  = asin(sin($lat_r) * cos($distance_in_miles/$radius) + cos($lat_r) * sin ($distance_in_miles/$radius) * cos($due_north));
        $southmost  = asin(sin($lat_r) * cos($distance_in_miles/$radius) + cos($lat_r) * sin ($distance_in_miles/$radius) * cos($due_south));

        $eastmost = $lon_r + atan2(sin($due_east)*sin($distance_in_miles/$radius)*cos($lat_r),cos($distance_in_miles/$radius)-sin($lat_r)*sin($lat_r));
        $westmost = $lon_r + atan2(sin($due_west)*sin($distance_in_miles/$radius)*cos($lat_r),cos($distance_in_miles/$radius)-sin($lat_r)*sin($lat_r));

        $northmost = rad2deg($northmost);
        $southmost = rad2deg($southmost);
        $eastmost = rad2deg($eastmost);
        $westmost = rad2deg($westmost);

        //return 2 points NW corner and SE corner
        return array($northmost,$westmost,$southmost,$eastmost);
}

тогда ваш SQL

SELECT * FROM table WHERE latitude <= $northmost AND longitude >= $westmost AND latitude >= $southmost AND longitude <= $eastmost

простое решение, которое я использовал несколько раз (но не с mysql): создать определяемую пользователем функцию some_distance_function с четырьмя параметрами latitude1,longitude1,latitude2,longitude2, которая возвращает расстояние, а затем просто проверить все на соответствие этому функцию расстояния и посмотрите для каждого элемента, меньше или равно расстояние заданному значению. Если у вас будет всего несколько тысяч мест, это вполне нормально и эффективно.

Если вам нужно выполнить этот запрос для миллионов записей, вы можете посмотреть, какие расширения ГИС (Географические информационные системы) доступны для выбранной вами базы данных, поскольку существуют лучшие (по крайней мере, с точки зрения возможности поиска) постоянные структуры данных. для поиска по огромному количеству местоположений.

Изменить: Чтобы привести пример того, как это делает Microsoft, см. http://technet.microsoft.com/en-us/library/bb964712(v=sql.105).aspx

Похоже, MySQL поддерживает пространственные расширения в целом:

http://dev.mysql.com/doc/refman/5.0/en/gis-introduction.html
http://dev.mysql.com/doc/refman/5.0/en/spatial-extensions.html

Редактировать II:

Похоже, этот вопрос также может быть полезен.

Найдите расстояние между двумя точками в MYSQL . (с использованием типа данных Point)

Вот решение с использованием СУБД. Держите два стола

• CityByLat { широта, city_id } с кластеризованным индексом по широте и
• CityByLng { logitude, city_id } с кластеризованным индексом по долготе

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

Я использую Neo4J для чего-то подобного, он очень хорошо масштабируется для любого типа данных, которые могут быть представлены в виде графика.

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

У вас есть контрольная точка (Сан-Хосе), и вы перебираете все записи своего города и вычисляете время выполнения (в случае большого количества записей, сделайте этот расчет клиентом, возможно, с помощью javascript или чего-то еще, потому что если у вас есть сервер, это будет стоить слишком рано). JavaScript может выглядеть примерно так:

var R = 6371; // Radius of the earth in km
var dLat = (lat2-lat1).toRad();  // Javascript functions in radians
var dLon = (lon2-lon1).toRad(); 
var a = Math.sin(dLat/2) * Math.sin(dLat/2) +
        Math.cos(lat1.toRad()) * Math.cos(lat2.toRad()) * 
        Math.sin(dLon/2) * Math.sin(dLon/2); 
var c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1-a)); 
var d = R * c; // Distance in km

Приведенный выше код взят из здесь

Примечание: это в километрах, так как я голландец и поэтому использую метрическую систему.

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

function distance($lat1, $lng1, $lat2, $lng2, $miles = true)
{
        $pi80 = M_PI / 180;
        $lat1 *= $pi80;
        $lng1 *= $pi80;
        $lat2 *= $pi80;
        $lng2 *= $pi80;

        $r = 6372.797; // mean radius of Earth in km
        $dlat = $lat2 - $lat1;
        $dlng = $lng2 - $lng1;
        $a = sin($dlat / 2) * sin($dlat / 2) + cos($lat1) * cos($lat2) * sin($dlng / 2) * sin($dlng / 2);
        $c = 2 * atan2(sqrt($a), sqrt(1 - $a));
        $km = $r * $c;

        return ($miles ? ($km * 0.621371192) : $km);
}

РЕДАКТИРОВАТЬ: Это не подходит для n совпадений в радиусе поиска. Учитывая плотность городов/городов в заданном радиусе, лучше перенести расчеты расстояния в SQL, так как это намного быстрее, и вы можете сопоставить их с расстояниями в пределах x км/миль.