四叉树优化碰撞检测 lua版本

腾讯游戏学院有一篇四叉树优化碰撞检测的文章，不过是js版本的，感觉思路写得挺清晰的，所有想翻译成lua来以备不时之需。
不过翻译过程发现挺多问题的，虽然思路很清晰，但细节照它那样写会有问题，有兴趣的人也可以翻译成其他语言看看是不是有问题。原文地址
以下是代码

module("Rect", package.seeall)
local o
function Rect:New(x,y,width,height,o)
	o = o or {}
	o.x = x
	o.y = y
	o.width = width
	o.height = height
	o.centroid = {x = (x+width)*0.5,y = (y+height)*0.5}
	o.maxX = x + o.width
	o.maxY = y + o.height
	setmetatable(o,{__index = self})
	--self:Init(x,y,width,height)
	return o
end

function Rect:carve(bounds)
	local arr = {}
	if bounds.centroid.y > self.y and bounds.centroid.y < self.maxY and bounds.centroid.x > self.x and bounds.centroid.x < self.maxX then
		local rect1 = self:New(self.x,self.y,bounds.centroid.x - self.x,bounds.centroid.y - self.y)
		local rect2 = self:New(self.x,bounds.centroid.y,bounds.centroid.x - self.x,self.maxY - bounds.centroid.y)
		local rect3 = self:New(bounds.centroid.x,self.y,self.maxX - bounds.centroid.x,bounds.centroid.y - self.y)
		local rect4 = self:New(bounds.centroid.x,bounds.centroid.y,self.maxX - bounds.centroid.x,self.maxY - bounds.centroid.y)
		table.insert(arr,rect1)
		table.insert(arr,rect2)
		table.insert(arr,rect3)
		table.insert(arr,rect4)
	elseif bounds.centroid.y > self.y and bounds.centroid.y < self.maxY then
		local rect1 = self:New(self.x,self.y,self.width,bounds.centroid.y - self.y)
		local rect2 = self:New(self.x,bounds.centroid.y,self.width,self.maxY - bounds.centroid.y)
		table.insert(arr,rect1)
		table.insert(arr,rect2)
	elseif bounds.centroid.x > self.x and bounds.centroid.x < self.maxX then
		local rect1 = self:New(self.x,self.y,bounds.centroid.x - self.x,self.height)
		local rect2 = self:New(bounds.centroid.x,self.y,self.maxX - bounds.centroid.x,self.height)
		table.insert(arr,rect1)
		table.insert(arr,rect2)
	end
	return arr
end

module("QuadTree", package.seeall)

local MAX_OBJECTS = 10
local MAX_LEVELS = 5
local o
function QuadTree:New(bounds,level)
	--self._index = self
	o = {}
	o.objects = {}
	o.nodes = {}
	o.level = level and level or 0
	o.bounds = bounds
	setmetatable(o, {__index = self})
	return o
end



function QuadTree:getIndex(rect)
	local bounds = self.bounds
	local onBottom = rect.y + rect.height <= bounds.centroid.y
	local onTop = rect.y >= bounds.centroid.y
	local onLeft = rect.x + rect.width <= bounds.centroid.x
	local onRight = rect.x >= bounds.centroid.x
	if onTop then
		if onRight then
			return 1
		elseif onLeft then
			return 2
		end
	elseif onBottom then
		if onLeft then
			return 3
		elseif onRight then
			return 4
		end
	end
	return -1
end

function QuadTree:split()
	local level = self.level
	local bounds = self.bounds
	local x = bounds.x
	local y = bounds.y
	
	local sWidth = bounds.width *0.5
	local sHeight = bounds.height *0.5
	local t1 = QuadTree:New(Rect:New(bounds.centroid.x,bounds.centroid.y,sWidth,sHeight),level + 1)
	
	local t2 = QuadTree:New(Rect:New(x,bounds.centroid.y,sWidth,sHeight),level + 1)
	
	local t3 = QuadTree:New(Rect:New(x,y,sWidth,sHeight),level + 1)
	
	local t4 = QuadTree:New(Rect:New(bounds.centroid.x,y,sWidth,sHeight),level + 1)
	
	table.insert(self.nodes,t1)
	table.insert(self.nodes,t2)
	table.insert(self.nodes,t3)
	table.insert(self.nodes,t4)
end

function QuadTree:insert(rect)
	local objs = self.objects
	local i,index
	if #self.nodes > 0 then
		index = self:getIndex(rect)
		if index ~= -1 then
			self.nodes[index]:insert(rect)
			return
		end
	end
	
	table.insert(objs,rect)
	

	if #self.nodes == 0 and #self.objects > MAX_OBJECTS and self.level < MAX_LEVELS then
		table.print(self.bounds)
		self:split()
		for i=#objs,1,-1 do
			index = self:getIndex(objs[i])
			if index ~= -1 then
				self.nodes[index]:insert(objs[i])
				table.remove(self.objects,i)
			else
				local arr = objs[i]:carve(self.bounds)
				for j=#arr,1,-1 do
					index = self:getIndex(arr[j])
					self.nodes[index]:insert(arr[j])
				end
				table.remove(self.objects,i)
			end
		end
	end
end

function QuadTree:retrieve(rect)
	local result = {}
	local arr,i,index

	if #self.nodes > 0 then
		index = self:getIndex(rect)
		if index ~= -1 then
			for k,v in pairs(self.nodes[index]:retrieve(rect)) do
				if #v > 0 then
					table.insert(result,v)
				end
			end
			--table.insert(result,self.nodes[index]:retrieve(rect))
		else
			arr = rect:carve(self.bounds)
			for i=#arr,1,-1 do
				index = self:getIndex(arr[i])
				-- table.print(self.nodes[index]:retrieve(rect))
				for k,v in pairs(self.nodes[index]:retrieve(rect)) do
					if type(v) == "table" and #v > 1 then
						for j,d in pairs(v) do
							table.insert(result,d)
						end
					else
						if next(v) then
							table.insert(result,v)
						end
					end
				end
				--table.insert(result,self.nodes[index]:retrieve(rect))
			end
		end
	else
	 	table.insert(result,self.objects)
	end
	--table.insert(result,self.objects)
	return result
end

local tree = QuadTree:New(Rect:New(0,0,1000,500))
	
	local rect1 = Rect:New(520,240,10,20)
	--local rect1 = Rect:New(520,250,10,10)
	local rect2 = Rect:New(530,240,10,30)
	--local rect2 = Rect:New(530,260,10,10)
	local rect3 = Rect:New(540,280,10,10)
	local rect4 = Rect:New(550,290,10,10)
	local rect5 = Rect:New(560,300,10,10)
	local rect6 = Rect:New(570,310,10,10)
	local rect7 = Rect:New(610,260,10,10)
	local rect8 = Rect:New(650,260,10,10)
	local rect9 = Rect:New(680,260,10,10)
	local rect10 = Rect:New(700,260,10,10)
	local rect11 = Rect:New(710,260,10,10)
	local rectInfo = {rect1,rect2,rect3,rect4,rect5,rect6,rect7,rect8,rect9,rect10,rect11}
	for i,v in ipairs(rectInfo) do
		tree:insert(v)
	end
	for i,v in ipairs(rectInfo) do
		local result = tree:retrieve(v)
		
	end

以上代码实测过检测能正确运行，但也有问题。问题就是原文的思路是把跨象限的rect拆分了，然后分别检测，这样导致的结果就是检测出来的结果是拆分后的rect，没有原先的rect。例如rect1是跨了1，4象限的，根据原文的思路是把rect1分成了rectA,rectB,检测的对象如果跟rect1碰撞的话结果只有rectA和rectB.。所以原文除了细节有问题思路实现出来也是有点问题的。因为实际只有rect1，没有rectA和rectB，但却只检测出了rectA和rectB.解决方案要不是就是加个方法判断出rectA和rectB就是rect1，要不就只能改检测的方法，具体实现细节等之后有时间再改下，今晚一晚都心不在焉想看演唱会，溜了溜了。