LUA四叉樹與八叉樹
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)