Pseudo-code for Quadtree Implementation

quadtree_pseudocode.rb

class Point
	attr_accessor :x, :y
end

class QuadtreeNode
	attr_accessor :point, :name

	def northwest(other)
		self.point.x > other.point.x && self.point.y < other.point.y
	end

	def northeast(other)
		self.point.x < other.point.x && self.point.y < other.point.y
	end

	def southwest(other)
		self.point.x > other.point.x && self.point.y > other.point.y
	end

	def southeast(other)
		self.point.x < other.point.x && self.point.y > other.point.y
	end
end

class Quadtree
	root

	def initialize
		root = nil
	end

	def is_empty?
		root == nil
	end

	def find_in_quadtree(root, target_data)
		if !root
			return [false, nil]
		elsif same(target_data, root.point)
			return [true, root]
		elsif root.northwest(target_data)
			find_in_quadtree(root.northwest, target_data)
		elsif root.southwest(target_data)
			find_in_quadtree(root.southwest, target_data)
		elsif root.northeast(target_data)
			find_in_quadtree(root.northeast, target_data)
		else
			find_in_quadtree(root.southeast, target_data)
		end
	end

	def insert_in_quadtree(root, new_data)
		if !root
			add_leaf(root, new_data)
		elsif root.northwest(new_data)
			insert_in_quadtree(root.northwest, new_data)
		elsif root.southwest(new_data)
			insert_in_quadtree(root.southwest, new_data)
		elsif root.southeast(new_data)
			insert_in_quadtree(root.southeast, new_data)
		else
			insert_in_quadtree(root.northeast, new_data)
		end
	end

	def nearest_n_neighbors(root, n)
		#this is a modified BFS based on pseudocode from Wikipedia
		#the root in this case is the point to find the nearest n neighbors
		create a queue Q
		create a vector set V of size n, consisting of n elements [name, point,distance] initialzed to [nil, nil, Float.INFINITY]
		#do not put root onto Q
		enqueue root.NW, root.SW, root.SE, root.NE onto Q
		while Q is not empty
			t <- Q.dequeue()
			u <- payload of t
			if u.distance_from(root.point) < any element of V distance
				replace that element of V with u [name, point, distance]
			end
			enqueue t.NW, t.SW, t.SE, t.NE onto Q
		end loop
		return V.sort_by_distance
	end


	private

	def add_leaf(root, new_data)
		root = Quadtree.new
		root.payload = new_data
		root.northwest = root.northeast = root.southwest = root.southeast = nil
	end
end