2点間の距離検索をgeokit-railsからelasticsearchに切り替えのため、検索手法を調査した

はじめに

Railsで緯度経度の2点間の距離を検索するために、geokit-railsを使っていたが、全ての検索をelasticsearchにしたいので、検索手法を調査した

geokit-railsによる距離検索

geokit-railsによる距離検索はsphere_distance_sqlとflat_distance_sqlの2種類ある

def distance_sql(origin, units=default_units, formula=default_formula)
  case formula
  when :sphere
    sql = sphere_distance_sql(origin, units)
  when :flat
    sql = flat_distance_sql(origin, units)
  end
  sql
end

デフォルトはGeokit::default_formulaが使われている

self.default_formula = options[:default_formula] || Geokit::default_formula

Geokit::default_formulaの値は:sphereが設定されている

Geokit::default_formula = :sphere

では、sphere_distance_sqlとflat_distance_sqlの違いは何か？？

大円距離（sphere_distance_sql）

sphere_distance_sqlは大円距離という球面上の2点間の長さが最短となる距離で計算している

geokit-railsでの計算箇所

def sphere_distance_sql(lat, lng, multiplier)
  %|
    (ACOS(least(1,COS(#{lat})*COS(#{lng})*COS(RADIANS(#{qualified_lat_column_name}))*COS(RADIANS(#{qualified_lng_column_name}))+
    COS(#{lat})*SIN(#{lng})*COS(RADIANS(#{qualified_lat_column_name}))*SIN(RADIANS(#{qualified_lng_column_name}))+
    SIN(#{lat})*SIN(RADIANS(#{qualified_lat_column_name}))))*#{multiplier})
    |
end

ピタゴラスの定理（flat_distance_sql）

ピタゴラスの定理は、直角三角形の3辺の長さの関係を表す
2点を斜辺とする直角三角形から距離を計算している

geokit-railsでの計算箇所

def flat_distance_sql(origin, lat_degree_units, lng_degree_units)
  %|
    SQRT(POW(#{lat_degree_units}*(#{origin.lat}-#{qualified_lat_column_name}),2)+
    POW(#{lng_degree_units}*(#{origin.lng}-#{qualified_lng_column_name}),2))
    |
end

次に、elasticsearchはどの計算手法を使っているのか？？

elasticsearchによる距離検索

distance_typeでarcかplaneを指定することができる
デフォルトではarcで計算される

distance_type
How to compute the distance. Can either be arc (default), or plane (faster, but > inaccurate on long distances and close to the poles).

まとめ

• geokit-railsはデフォルトでは大円距離の計算手法
• Elasticsearchはデフォルトでarc

余談

もう少し、elasticsearchの計算分岐箇所を追ってみた

public double calculate(double srcLat, double srcLon, double dstLat, double dstLon, DistanceUnit unit) {
    if (this == PLANE) {
        return DistanceUnit.convert(GeoUtils.planeDistance(srcLat, srcLon, dstLat, dstLon),
            DistanceUnit.METERS, unit);
    }
    return DistanceUnit.convert(GeoUtils.arcDistance(srcLat, srcLon, dstLat, dstLon), DistanceUnit.METERS, unit);
}

大円距離の方も見ていくと

DistanceUnit.convert(GeoUtils.arcDistance(srcLat, srcLon, dstLat, dstLon), DistanceUnit.METERS, unit)

/** Return the distance (in meters) between 2 lat,lon geo points using the haversine method implemented by lucene */
public static double arcDistance(double lat1, double lon1, double lat2, double lon2) {
    return SloppyMath.haversinMeters(lat1, lon1, lat2, lon2);
}

public static double haversinMeters(double lat1, double lon1, double lat2, double lon2) {
  return haversinMeters(haversinSortKey(lat1, lon1, lat2, lon2));
}

public static double haversinMeters(double sortKey) {
  return TO_METERS * 2 * asin(Math.min(1, Math.sqrt(sortKey * 0.5)));
}

ぱっと見、geokitのsphereの計算式と違うように見える、、時間ある時に調べよ、、