Mae向きなブログ

Mae向きな情報発信を続けていきたいと思います。

kd木(2)

Ruby

5/1(Fri)の日記でkd木について書きました。5/1時点ではすっかりkd木について理解できたと思っていたのですが，今日，kd木について，いろんな方と話をする機会があって，いろんな質問に答えたつもりが，ホテルに帰ってから自分が思っていたことが間違いであることに気づきました。恩師の退職パーティまでに時間がありますので，ちょっとまとめてみます。

5/1時点で分かっていたのは，kd木の作り方であって，kd木を使って最近点を探すアルゴリズムについては理解が不十分でした。

分からないままだとちょっと気になるので，どうやって最近点を決定するのか調べてみました。kdtree_findメソッドは，再帰が入り組んでいてなかなか難しいですね。なんか良い方法はと考えたのですが，Point#closerメソッドで最近点の候補を探しているのだから，このメソッドで比較している座標を出力すると理解できるのではと思いやってみました。

汚いソースですが，以下に載せます。

kdtree.rb

# -*- coding: utf-8 -*-
class Point
  attr_accessor :x, :y
  def initialize(x, y)
    @x = x
    @y = y
  end
  def to_s
    '(' + @x.to_s + ', ' + @y.to_s + ')'
  end
  def dsquare(p)
    dx = @x - p.x
    dy = @y - p.y
    dx * dx + dy * dy
  end
  def closer(a, b)
    puts a.to_s + "," + b.to_s # この行を追加
    self.dsquare(a) < self.dsquare(b) ? a : b
  end
end

def pts2kdtree(ary, depth)
  return nil if ary.size == 0
  result = { }
  if ary.size == 1
    result[:mid] = ary[0]
    result[:head] = nil
    result[:tail] = nil
    return result
  end
  axis = depth % 2 == 1 ? 'y' : 'x';
  copy = ary.sort { |a, b|
    eval("a." + axis) <=> eval("b." + axis)
  }
  mid = copy.size >> 1
  result[:mid]  = copy[mid]
  result[:head] = pts2kdtree(copy.slice(0, mid), depth + 1)
  result[:tail] = pts2kdtree(copy.slice(mid + 1, copy.size), depth + 1)
  return result
end

def kdtree_find(qt, pt, depth)
  axis = depth % 2 == 1 ? 'y' : 'x';
  return nil if qt == nil
  return qt[:mid] if is_leaf(qt)
  leaf = nil
  if eval("pt." + axis) < eval("qt[:mid]." + axis)
    if qt[:head]
      if is_leaf(qt[:head])
        leaf = qt[:head][:mid]
      else
        leaf = kdtree_find(qt[:head], pt, depth + 1)
      end
    else
      leaf = kdtree_find(qt[:tail], pt, depth + 1)
    end
    if qt[:head] && qt[:tail] &&
        pt.dsquare(leaf) > (eval("pt." + axis) - eval("qt[:mid]." + axis))**2
      leaf = pt.closer(leaf, kdtree_find(qt[:tail], pt, depth + 1))
    end
  else
    if qt[:tail]
      if is_leaf(qt[:tail])
        leaf = qt[:tail][:mid]
      else
        leaf = kdtree_find(qt[:tail], pt, depth + 1)
      end
    else
      leaf = kdtree_find(qt[:head], pt, depth + 1)
    end
    if qt[:tail] && qt[:head] &&
        pt.dsquare(leaf) > (eval("pt." + axis) - eval("qt[:mid]." + axis))**2
      leaf = pt.closer(leaf, kdtree_find(qt[:head], pt, depth + 1))
    end
  end
  return pt.closer(qt[:mid], leaf)
end

def is_leaf(a)
  return true if a[:head] == nil && a[:tail] == nil
end

if __FILE__ == $0
  require 'pp'
  # 以下の10個の集合で考えました。
  ary = []
  ary << Point.new(57, 42)
  ary << Point.new(52, 57)
  ary << Point.new(99, 51)
  ary << Point.new(52, 46)
  ary << Point.new(15, 68)
  ary << Point.new(75, 11)
  ary << Point.new(69, 62)
  ary << Point.new(13, 39)
  ary << Point.new( 0, 64)
  ary << Point.new(67, 16)
  kdtree = pts2kdtree(ary, 0)
  pp kdtree_find(kdtree, Point.new(50, 50), 0)
end

実行結果

10個のデータに対して，(50, 50)を検索してみました。実行結果は以下です。

$ ruby kdtree.rb
(52, 46),(13, 39)
(52, 57),(52, 46)
(57, 42),(52, 46)
#

10個のサンプルデータから出来上がるkd木は以下です。この図を見ながら以下を読んでもらえればと思います。

(50, 50)の最近点を探すのに，まず(52, 46)と(13, 39)のどちらと近いか比較します。次に，(52, 57)と(52, 46)のどちらと近いかを比較しています。最後に，(57, 42)と(52, 46)のどちらと近いかとを比較し，最終的に最近点が(52, 46)であると求めています。

なるほど，ある点の最近点を求めるために，木の高さ分の比較を行っている訳ですね。バランスを保つことが重要だということがあらためて分かりました。今日，私に質問した方には間違って解答してしまったようです。すみません。

今日，改めて感じたのは，何事もそうだと思いますが，自分が

  • どこまで理解できているのか
  • どこが理解できていないのか

をしっかり見極めないといけないと感じました。5/1(Fri)時点では，kd木の作り方が分かったんだからあとは探すだけという中途半端な理解で終わってしまっていました。最後までちゃんと理解することが大切だなと思います。
あと，誰かと議論することの大切さも感じました。今日，いろんな方と議論する機会がなければ，ずっと分かったつもりで過ごすところでした。