JTS の Geometry#isWithinDistance は Geometry#distance に立つ瀬を奪われている

JTS のクラス Geometry には、isWithinDistance という、近辺データ抽出によさそうなメソッドがあります。しかし、isWithinDistance よりも、distance を使ってユーザコード上で距離を比較するほうが速い傾向があることが分かりました。

Geometry#isWithinDistance

LineString 近辺の点を拾い出すには、 distance を使う方が buffer + within よりも 10 倍速い

LineString 近辺の点を拾い出すには、 distance を使う方が buffer + within よりも 10 倍速い - Relevant, Timely, and Accurate

ということを以前調べましたが、実は JTS のクラス Geometry には、isWithinDistance という、この目的にはちょうど良い関数があることが分かりました。すなわち、

geom1.distance(geom2) < threshold

の代わりに

geom1.isWithinDistance(geom2, threshold)

を使うことができます。これによって拾い出しが高速になるでしょうか？「LineString 近辺の点を拾い出すには、 distance を使う方が buffer + within よりも 10 倍速い - Relevant, Timely, and Accurate」のときと同じ条件で実験し、それぞれの方法での処理時間を LineString に対してプロットしたところ、次のようになりました。

凡例が見にくくて申し訳ないのですが、青色がバッファをとっての within を使った場合, 赤色が今回新しく検証した isWithinDistance を使った場合、緑色が distance による場合です。

考察

isWithinDistance は、distance を使った場合に比べ、おおよそ2倍強の時間がかかってしまっているようです。なお、処理時間の安定性は、distance と isWithinDistance は同程度です。一方、バッファをとっての within のほうは、処理時間が遅いのに加え、処理時間が安定しないようです。
現行バージョンの JTS では、より詳細な情報を返す distance の方が、真偽値を返すだけの isWithinDistance よりも高速なので、メソッド isWithinDistance には立つ瀬がないようです...*1。

結論

JTS 1.8 において近辺データの抽出処理を行う場合には、distance を使うのが最も高速らしいことが分かりました。

実験環境

この実験には、http://svgmapdata.sakura.ne.jp/geotools/ の geotools.rb を使いました。実験の時、使っていた GeoTools のバージョンは 2.4 で、GeoTools 2.4 が使う JTS のバージョンは 1.8 になります。また、実験用スクリプトの実行には、JRuby trunk *2を使い、-O -J-server オプションをつけています。
実験用コードのソースは、以下の通りです；

require 'geotools'

SRCES = %w{/Users/hfu/work/15_geotools/transl_1_1.shp /Users/hfu/work/15_geotools/hydrol_1_1.shp}
n_trials = 10000
buf_width = 10
wgs84 = Geo::import_epsg_crs(4326)

utms = {}
trs = {}
51.upto(56) do |i|
  utms[i] = Geo::import_epsg_crs(32600 + i)
  trs[i] = Geo::Transform.new(wgs84, utms[i])
end

wf = File.open('buffer_or_distance.tsv', 'w')
SRCES.each do |src|
  Geo::Reader.foreach(src, {:whitelist => []}) do |geom, attrs|
    # projection
    geom = geom.getGeometryN(0)
    next if geom.getLength == 0 # because there are such strange data...
    c = geom.getCentroid
    tr = trs[((c.getX + 180) / 6).ceil]
    geom = tr.transform(geom)
    n_points = geom.getNumPoints
    
    env = geom.getEnvelopeInternal
    points = []
    n_trials.times do |i|
      points << Geo::import_array_geometry([
        rand(nil) * env.getWidth + env.getMinX,
        rand(nil) * env.getHeight + env.getMinY])
    end
    
    start_time = Time.now
    buf = geom.buffer(buf_width)
    buffering_time = Time.now - start_time
    
    count_buffer = 0
    start_time = Time.now
    points.each do |point|
      count_buffer += 1 if point.within(buf)
    end
    process_time_buffer = Time.now - start_time
    print "#{count_buffer} points are in by within (#{process_time_buffer}s)\n"
    
    count_distance = 0
    start_time = Time.now
    points.each do |point|
      count_distance += 1 if point.distance(geom) < buf_width
    end
    process_time_distance = Time.now - start_time
    print "#{count_distance} points are in by distance (#{process_time_distance}s)\n"
    
    count_within_distance = 0
    start_time = Time.now
    points.each do |point|
      count_within_distance += 1 if point.isWithinDistance(geom, buf_width)
    end
    process_time_within_distance = Time.now - start_time
    print "#{count_within_distance} points are in by within_distance (#{process_time_within_distance}s)\n"
    
    print "n_points = #{n_points}\n\n"
    
    wf.print "#{geom.getLength},#{process_time_buffer},#{process_time_distance},#{process_time_within_distance}\n"
  end
end
wf.close

*1:Geometry の次元が違ったり、BBOX によるフィルタを行わずにデータ抽出に入れたり、データの複雑さが違ったりすると結果が違ってくるかもしれませんが、私の作業で使うようなデータについては、とりあえず distance を使っておいて良さそうです。

*2:最近同期していないので、ちょっと古い JRuby になっているかもしれません。