From: Marcin Raczkowski <mailing.mr@...>
Date: 2008-01-16T05:52:32+09:00
Subject: kD-Trees implementation

Hello.

I started playing with ruby kD-Trees implementation, an thoughts?


# to be extended to allow for searching / parasing nodes
class KDTree
   attr_reader :root

   def initialize(points)
     @root = KDNode.new.parse(points)
   end

   def add_node(point)
     @root.add(point)
   end
end

# pretty standard tree node
class KDNode
   attr_reader :left, :right
   attr_reader :location

   def initialize(location=nil, left=nil, right=nil)
     @location = location
     @left = left
     @right = right
   end

   # parse list of points and build nodes
   def parse(points, depth = 0)
     @depth = depth  # save depth for this node for removing
     @dim = points[0].length # dimension based on point dimensions
     axis = depth % @dim

     points = points.sort_by{|point| point[axis]} # sorting by axis
     half = points.length / 2 # algoithm suggest using median
     # but in reality we don't need median value
     # we just need to cut it in half

     @location = points[half]  # here we can store just index
     @left = KDNode.parse(points[0..half-1], depth+1) unless half < 1
     @right = KDNode.parse(points[half+1..-1], depth+1) unless half+1 >= 
points.length
   end

   # add leaf to node, adding nodes will make tree unbalanced
   def add(point, depth = 0)
     @dim = point.length
     axis = depth % @dim

     if @location[axis] < point[axis]
       @left ? @left.add(point) : @left = KDNode.new(point)
     else
       @right ? @right.add(point) : @right = KDNode.new(point)
     end
   end

   # remove node from tree
   def remove
     self.parse(@left.to_a + @right.to_a, @depth)
     # no idea if it should be @depth or @depth + 1
   end

   # list all leafs including this node
   def to_a
     @left.to_a + [@location] + @right.to_a
   end
end

I'm thinking about storing only indexes in leaves, and storing point 
list in kD-Tree.

any suggestions?