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?
