mysql - 2つの緯度/経度ポイント間の距離を見つける最速の方法

Question

私は現在、mysqlデータベースに経度と緯度の情報をすべて含む100万弱の場所を持っています。

クエリを使用して、1つのポイントと他の多くのポイントの間の距離を見つけようとしています。特に1秒間に100回以上ヒットする場合は、私が望むほど速くはありません。

これのためのより速いクエリまたはおそらくmysql以外のより速いシステムはありますか？私はこのクエリを使用しています：

SELECT 
  name, 
   ( 3959 * acos( cos( radians(42.290763) ) * cos( radians( locations.lat ) ) 
   * cos( radians(locations.lng) - radians(-71.35368)) + sin(radians(42.290763)) 
   * sin( radians(locations.lat)))) AS distance 
FROM locations 
WHERE active = 1 
HAVING distance < 10 
ORDER BY distance;

注：提供される距離はマイル単位です。キロメートルが必要な場合は、6371の代わりにを使用してください3959。

score 120 · Accepted Answer

テーブルのデータ型Pointの値を使用してポイントを作成します。Mysql 5.7.5以降、テーブルはインデックスもサポートするようになりました。GeometryMyISAMInnoDBSPATIAL
SPATIALこれらのポイントにインデックスを作成します

MBRContains()値を見つけるために使用します。

  SELECT  *
  FROM    table
  WHERE   MBRContains(LineFromText(CONCAT(
          '('
          , @lon + 10 / ( 111.1 / cos(RADIANS(@lat)))
          , ' '
          , @lat + 10 / 111.1
          , ','
          , @lon - 10 / ( 111.1 / cos(RADIANS(@lat)))
          , ' '
          , @lat - 10 / 111.1 
          , ')' )
          ,mypoint)

、または、MySQL 5.1以上：

    SELECT  *
    FROM    table
    WHERE   MBRContains
                    (
                    LineString
                            (
                            Point (
                                    @lon + 10 / ( 111.1 / COS(RADIANS(@lat))),
                                    @lat + 10 / 111.1
                                  ),
                            Point (
                                    @lon - 10 / ( 111.1 / COS(RADIANS(@lat))),
                                    @lat - 10 / 111.1
                                  ) 
                            ),
                    mypoint
                    )

これにより、ほぼボックス内のすべてのポイントが選択されます(@lat +/- 10 km, @lon +/- 10km)。

これは実際にはボックスではなく、球形の長方形です。球の緯度と経度にバインドされたセグメントです。これは、フランツジョセフランドの単純な長方形とは異なる場合がありますが、ほとんどの人が住んでいる場所ではそれに非常に近いです。

追加のフィルタリングを適用して、（正方形ではなく）円の内側のすべてを選択します
おそらく、大きな円の距離を考慮して、追加の細かいフィルタリングを適用します（大きな距離の場合）

score 25 · Accepted Answer

同様の問題（一点からの距離で行をフィルタリングする）を解決する必要があり、元の質問と回答とコメントを組み合わせることで、MySQL 5.6と5.7の両方で完全に機能するソリューションを思いつきました。

SELECT 
    *,
    (6371 * ACOS(COS(RADIANS(56.946285)) * COS(RADIANS(Y(coordinates))) 
    * COS(RADIANS(X(coordinates)) - RADIANS(24.105078)) + SIN(RADIANS(56.946285))
    * SIN(RADIANS(Y(coordinates))))) AS distance
FROM places
WHERE MBRContains
    (
    LineString
        (
        Point (
            24.105078 + 15 / (111.320 * COS(RADIANS(56.946285))),
            56.946285 + 15 / 111.133
        ),
        Point (
            24.105078 - 15 / (111.320 * COS(RADIANS(56.946285))),
            56.946285 - 15 / 111.133
        )
    ),
    coordinates
    )
HAVING distance < 15
ORDER By distance

coordinatesはタイプを含むフィールドでPOINTあり、SPATIALインデックス
6371はキロメートル単位の距離を計算する
56.946285ためのものです中心点の緯度は中心点
24.105078の経度です
15キロメートル単位の最大距離です

私のテストでは、MySQL はフィールドで SPATIAL インデックスを使用して、coordinates長方形内にあるすべての行をすばやく選択し、フィルタリングされたすべての場所の実際の距離を計算して、長方形の角から場所を除外し、円の内側の場所のみを残します。

これは私の結果の視覚化です:

灰色の星はマップ上のすべてのポイントを視覚化し、黄色の星は MySQL クエリによって返されたものです。四角形の角の内側 (円の外側) の灰色の星は、によって選択され、句MBRContains()によって選択解除されました。HAVING

score 14 · Accepted Answer

次の MySQL 関数は、このブログ投稿に投稿されました。私はそれをあまりテストしていませんが、投稿から収集したものから、緯度と経度のフィールドがインデックス化されている場合、これはうまくいくかもしれません:

DELIMITER $$

DROP FUNCTION IF EXISTS `get_distance_in_miles_between_geo_locations` $$
CREATE FUNCTION get_distance_in_miles_between_geo_locations(
  geo1_latitude decimal(10,6), geo1_longitude decimal(10,6), 
  geo2_latitude decimal(10,6), geo2_longitude decimal(10,6)) 
returns decimal(10,3) DETERMINISTIC
BEGIN
  return ((ACOS(SIN(geo1_latitude * PI() / 180) * SIN(geo2_latitude * PI() / 180) 
    + COS(geo1_latitude * PI() / 180) * COS(geo2_latitude * PI() / 180) 
    * COS((geo1_longitude - geo2_longitude) * PI() / 180)) * 180 / PI()) 
    * 60 * 1.1515);
END $$

DELIMITER ;

使用例:

placesフィールドlatitude&で呼び出されるテーブルを想定しますlongitude。

SELECT get_distance_in_miles_between_geo_locations(-34.017330, 22.809500,
latitude, longitude) AS distance_from_input FROM places;

score 9 · Accepted Answer

SELECT * FROM (SELECT *,(((acos(sin((43.6980168*pi()/180)) * 
sin((latitude*pi()/180))+cos((43.6980168*pi()/180)) * 
cos((latitude*pi()/180)) * cos(((7.266903899999988- longitude)* 
pi()/180))))*180/pi())*60*1.1515 ) as distance 
FROM wp_users WHERE 1 GROUP BY ID limit 0,10) as X 
ORDER BY ID DESC

これは、MySQL のポイント間の距離計算クエリです。長いデータベースで使用しましたが、完璧に機能しています。注: 必要に応じて変更 (データベース名、テーブル名、列など) を行います。

score 8 · Accepted Answer

set @latitude=53.754842;
set @longitude=-2.708077;
set @radius=20;

set @lng_min = @longitude - @radius/abs(cos(radians(@latitude))*69);
set @lng_max = @longitude + @radius/abs(cos(radians(@latitude))*69);
set @lat_min = @latitude - (@radius/69);
set @lat_max = @latitude + (@radius/69);

SELECT * FROM postcode
WHERE (longitude BETWEEN @lng_min AND @lng_max)
AND (latitude BETWEEN @lat_min and @lat_max);

ソース

score 7 · Accepted Answer

   select
   (((acos(sin(('$latitude'*pi()/180)) * sin((`lat`*pi()/180))+cos(('$latitude'*pi()/180)) 
    * cos((`lat`*pi()/180)) * cos((('$longitude'- `lng`)*pi()/180))))*180/pi())*60*1.1515) 
    AS distance
    from table having distance<22;

score 5 · Accepted Answer

2 つの座標間のメートル数を返す MySQL 関数:

CREATE FUNCTION DISTANCE_BETWEEN (lat1 DOUBLE, lon1 DOUBLE, lat2 DOUBLE, lon2 DOUBLE)
RETURNS DOUBLE DETERMINISTIC
RETURN ACOS( SIN(lat1*PI()/180)*SIN(lat2*PI()/180) + COS(lat1*PI()/180)*COS(lat2*PI()/180)*COS(lon2*PI()/180-lon1*PI()/180) ) * 6371000

値を別の形式で返すには6371000、関数内のを、選択した単位の地球の半径に置き換えます。たとえば、キロメートルは6371、マイルはになります3959。

この関数を使用するには、MySQL の他の関数と同じように呼び出すだけです。たとえば、 table がある場合、cityすべての都市から他のすべての都市までの距離を見つけることができます。

SELECT
    `city1`.`name`,
    `city2`.`name`,
    ROUND(DISTANCE_BETWEEN(`city1`.`latitude`, `city1`.`longitude`, `city2`.`latitude`, `city2`.`longitude`)) AS `distance`
FROM
    `city` AS `city1`
JOIN
    `city` AS `city2`

score 4 · Accepted Answer

MySQL プラグインとしてインストールする方法の詳細を含む完全なコードは、https ://github.com/lucasepe/lib_mysqludf_haversine にあります。

昨年、コメントとして投稿しました。親切に@TylerCollierが回答として投稿するように提案してくれたので、ここにあります。

もう 1 つの方法は、2 点からのハバーサイン距離を返すカスタム UDF 関数を作成することです。この関数は入力を受け取ることができます:

lat1 (real), lng1 (real), lat2 (real), lng2 (real), type (string - optinal - 'km', 'ft', 'mi')

したがって、次のように書くことができます。

SELECT id, name FROM MY_PLACES WHERE haversine_distance(lat1, lng1, lat2, lng2) < 40;

距離が 40 キロメートル未満のすべてのレコードを取得します。または：

SELECT id, name FROM MY_PLACES WHERE haversine_distance(lat1, lng1, lat2, lng2, 'ft') < 25;

距離が 25 フィート未満のすべてのレコードを取得します。

コア機能は次のとおりです。

double
haversine_distance( UDF_INIT* initid, UDF_ARGS* args, char* is_null, char *error ) {
    double result = *(double*) initid->ptr;
    /*Earth Radius in Kilometers.*/ 
    double R = 6372.797560856;
    double DEG_TO_RAD = M_PI/180.0;
    double RAD_TO_DEG = 180.0/M_PI;
    double lat1 = *(double*) args->args[0];
    double lon1 = *(double*) args->args[1];
    double lat2 = *(double*) args->args[2];
    double lon2 = *(double*) args->args[3];
    double dlon = (lon2 - lon1) * DEG_TO_RAD;
    double dlat = (lat2 - lat1) * DEG_TO_RAD;
    double a = pow(sin(dlat * 0.5),2) + 
        cos(lat1*DEG_TO_RAD) * cos(lat2*DEG_TO_RAD) * pow(sin(dlon * 0.5),2);
    double c = 2.0 * atan2(sqrt(a), sqrt(1-a));
    result = ( R * c );
    /*
     * If we have a 5th distance type argument...
     */
    if (args->arg_count == 5) {
        str_to_lowercase(args->args[4]);
        if (strcmp(args->args[4], "ft") == 0) result *= 3280.8399;
        if (strcmp(args->args[4], "mi") == 0) result *= 0.621371192;
    }

    return result;
}

score 3 · Accepted Answer

球面投影を使用すると、高速でシンプルかつ正確な (距離が短い場合) 近似を行うことができます。少なくとも私のルーティングアルゴリズムでは、正しい計算と比較して 20% 向上しています。Java コードでは、次のようになります。

public double approxDistKm(double fromLat, double fromLon, double toLat, double toLon) {
    double dLat = Math.toRadians(toLat - fromLat);
    double dLon = Math.toRadians(toLon - fromLon);
    double tmp = Math.cos(Math.toRadians((fromLat + toLat) / 2)) * dLon;
    double d = dLat * dLat + tmp * tmp;
    return R * Math.sqrt(d);
}

MySQL については不明です (申し訳ありません!)。

制限について知っていることを確認してください (assertEquals の 3 番目のパラメーターは、キロメートル単位の精度を意味します)。

    float lat = 24.235f;
    float lon = 47.234f;
    CalcDistance dist = new CalcDistance();
    double res = 15.051;
    assertEquals(res, dist.calcDistKm(lat, lon, lat - 0.1, lon + 0.1), 1e-3);
    assertEquals(res, dist.approxDistKm(lat, lon, lat - 0.1, lon + 0.1), 1e-3);

    res = 150.748;
    assertEquals(res, dist.calcDistKm(lat, lon, lat - 1, lon + 1), 1e-3);
    assertEquals(res, dist.approxDistKm(lat, lon, lat - 1, lon + 1), 1e-2);

    res = 1527.919;
    assertEquals(res, dist.calcDistKm(lat, lon, lat - 10, lon + 10), 1e-3);
    assertEquals(res, dist.approxDistKm(lat, lon, lat - 10, lon + 10), 10);

mysql - 2つの緯度/経度ポイント間の距離を見つける最速の方法

15 に答える 15

使用例:

Related

Reference