1. 建立類

由於每個四叉樹容器需要的屬性為一個容器的大小和中心，以及框架的容量，作為分割的指標。需要容器來裝載資料，給容器標記是否已被分割來避免多重分割。    
每次分割時又需要繼承母屬性的一部分，因此建立一個類來重複註冊行為頗為方便。

Code

```
function QuadTree.new(boundary, capacity)
	local o = {
		center   =  boundary.center,
		size = boundary.size,
		capacity = capacity or 4,
		points = {},
		isdivided = false
	}
	return setmetatable(
		o, {
		__index = QuadTree
	})
end
```

2. 分割

主要以母屬性大小的一半作為子容器的大小，此大小的一半（母屬性大小一半的一半）作為子容器的中心。變量的預定義是為了減少table.的讀取，缺點是減少易讀性。

Code

```
function QuadTree:inner_subdivide()
	local parentcenter = self.center
	local parentsize = self.size
	local parentwidth =  parentsize.x
	local parentheight = parentsize.y
	local parentcenterx = parentcenter.x
	local parentcentery = parentcenter.y
	local childwidth = parentwidth/2
	local childheight = parentheight/2
	local childhalfwidth = childwidth/2
	local childhalfheight = childheight/2
	
	local toleftX = parentcenterx - childhalfwidth
	local torightX = parentcenterx + childhalfwidth
	local toupY = parentcentery - childhalfheight
	local todownY = parentcentery + childhalfheight

	local childsize = vector2(childwidth, childheight)
	local parentcapacity = self.capacity

	--create new quadtrees in 4 sub-regions
	self.topright = QuadTree.new({
		center = vector2(torightX, toupY),
		size = childsize
	}, parentcapacity)
	self.bottomright = QuadTree.new({
		center = vector2(torightX, todownY),
		size = childsize
	}, parentcapacity)
	self.bottomleft = QuadTree.new({
		center = vector2(toleftX, todownY),
		size = childsize
	}, parentcapacity)
	self.topleft = QuadTree.new({
		center = vector2(toleftX, toupY),
		size = childsize
	}, parentcapacity)

	self.isdivided = true
		
end
```

3. 新增物件：一點

新增一點於容器內，若不在母容器內，則不可能在其子容器內，  
若物件數在容器之容量範圍內，繼續添加物件。  
否則對目前容器進行分割出4個子容器，把物件添加到子容器內，並重複上述行為，若過程其中成功添加，即返回true。完成新增。   ### Code 
```
function QuadTree:inner_point_contains (point, radius)
	local radius = radius or 0.0
	local selfcenter = self.center
	local selfcenterx = selfcenter.x
	local selfcentery = selfcenter.y
	local selfhalfsize = self.size/2
	local pointx = point.x
	local pointy = point.y
	--return point.x + radius >= self.center.x - self.size.x/2 and point.x - radius <= self.center.x + self.size.x/2 and point.y + radius >= self.center.y - self.size.y/2 and point.y - radius <= self.center.y + self.size.y/2
	return pointx + radius >= selfcenterx - selfhalfsize.x and pointx - radius <= selfcenterx + selfhalfsize.x and pointy + radius >= selfcentery - selfhalfsize.y and pointy - radius <= selfcentery + selfhalfsize.y
end

function QuadTree:insert_point(point)
	if not self:inner_point_contains(point) then
		return false
	end
	if #self.points < self.capacity then
		table.insert(self.points, point)
		return true
	else 
		if not self.isdivided then
			self:inner_subdivide()
		end
		if self.topright:insert_point(point) then
			return true
		elseif self.bottomright:insert_point(point) then
			return true
		elseif self.bottomleft:insert_point(point) then
			return true
		elseif self.topleft:insert_point(point) then
			return true
		end
	end
end
```

4. 獲得容器某範圍內的物體列表

若無成果列表新建空的成果列表，若搜索範圍不在容器內則不用找了，不可能找到物體。    
若此容器的物件在搜索範圍內則添加到成果列表中，接著  
若此容器已被分割，則在此容器分割的四個容器內進行同範圍搜索。直到沒有分割的容器及沒有在搜索範圍內的物件。  
由於函數未執行完不會進行下一行，所以在執行完上述行為後，才會到達最後的return found。

Code

```
function QuadTree:query_points_by_point(point, radius, found)
	found = found or {}
	if not self:inner_point_contains(point, radius) then
		return found
	end
	for i, point_ in ipairs(self.points) do
		if Contains.pointtopoint(point_, point, radius) then
			table.insert(found, point_)
		end
	end
	if self.isdivided then
		self.topright:query_points_by_point(point, radius, found)
		self.bottomright:query_points_by_point(point, radius, found)
		self.bottomleft:query_points_by_point(point, radius, found)
		self.topleft:query_points_by_point(point, radius, found)
	end
	return found
end
```

八叉樹

原理與四叉樹差不多，由分割4容器變為分割8容器，每個子容器的大小為原容器的1/2，每個子容器的中心為原容器的中心加上原容器的1/4。
分割懶人包如下

Code

```
function OcTree:inner_subdivide()
	local parentcenter = self.center
	local parentcenterx = parentcenter.x
	local parentcentery = parentcenter.y
	local parentcenterz = parentcenter.z
	local parentwidth = self.size.x
	local parentlength = self.size.y
	local parenthight = self.size.z
	local childwidth = parentwidth / 2
	local childlength = parentlength / 2
	local childhight = parenthight / 2
	local childhalfwidth = childwidth / 2
	local childhalflength = childlength / 2
	local childhalfhight = childhight / 2
	local toleftX = parentcenterx - childhalfwidth
	local toupY = parentcentery - childhalflength
	local tofloorZ = parentcenterz - childhalfhight
	
	local torightX = parentcenterx + childhalfwidth
	local todownY = parentcentery + childhalflength
	local toroofZ = parentcenterz + childhalfhight

	local childlefttopcenter_topbox = vector3(toleftX , todownY, toroofZ)
	local childrighttopcenter_topbox = vector3(torightX , todownY, toroofZ)
	local childleftbottomcenter_topbox = vector3(toleftX , toupY, toroofZ)
	local childrightbottomcenter_topbox = vector3(torightX , toupY, toroofZ)

	local childlefttopcenter_bottombox = vector3(toleftX , todownY, tofloorZ)
	local childrighttopcenter_bottombox = vector3(torightX , todownY, tofloorZ)
	local childleftbottomcenter_bottombox = vector3(toleftX , toupY, tofloorZ)
	local childrightbottomcenter_bottombox = vector3(torightX , toupY, tofloorZ)

	local childsize = vector3(childwidth,childlength,childhight)
	--create new quadtrees in 8 box regions
	self.topbox_lefttop = OcTree.new(
		{
			center = childlefttopcenter_topbox,
			game_center = childlefttopcenter_topbox - vector3(0.0,0.0,childhight),
			size = childsize
		},
		self.capacity
	)
	self.topbox_righttop = OcTree.new(
		{
			center = childrighttopcenter_topbox,
			game_center = childrighttopcenter_topbox - vector3(0.0,0.0,childhight),
			size = childsize
		},
		self.capacity
	)
	self.topbox_leftbottom = OcTree.new(
		{
			center = childleftbottomcenter_topbox,
			game_center = childleftbottomcenter_topbox - vector3(0.0,0.0,childhight),
			size = childsize
		},
		self.capacity
	)
	self.topbox_rightbottom = OcTree.new(
		{
			center = childrightbottomcenter_topbox,
			game_center = childrightbottomcenter_topbox - vector3(0.0,0.0,childhight),
			size = childsize
		},
		self.capacity
	)
	self.bottombox_lefttop = OcTree.new(
		{
			center = childlefttopcenter_bottombox,
			game_center = childlefttopcenter_bottombox - vector3(0.0,0.0,childhight),
			size = childsize
		},
		self.capacity
	)
	self.bottombox_righttop = OcTree.new(
		{
			center = childrighttopcenter_bottombox,
			game_center = childrighttopcenter_bottombox - vector3(0.0,0.0,childhight),
			size = childsize
		},
		self.capacity
	)
	self.bottombox_leftbottom = OcTree.new(
		{
			center = childleftbottomcenter_bottombox,
			game_center = childleftbottomcenter_bottombox - vector3(0.0,0.0,childhight),
			size = childsize
		},
		self.capacity
	)
	self.bottombox_rightbottom = OcTree.new(
		{
			center = childrightbottomcenter_bottombox,
			game_center = childrightbottomcenter_bottombox - vector3(0.0,0.0,childhight),
			size = childsize
		},
		self.capacity
	)
	
	
	self.isdivided = true
end
```

Github: [octree](https://github.com/negbook/octree)  
Github [quadtree](https://github.com/negbook/quadtree)