Quadtrees- how do I do em?

Hi FP,

I’ve been trying to find the closest point in an array of positions to another position. Say we have the following:

{(0,0,0),(1,1,1),(5,5,5),(6,6,6)}

And I test (2,2,2) it should return (1,1,1)

Normally this wouldn’t be problematic if we were using a small array, a simple priority queue of sorts sorted by distance would suffice. However when we have a large number of entries (40,000 for example) iterating through it is incredibly inefficient, especially if we need to do it a lot. I decided a Quadtree would be a simple way to resolve this. By splitting up each entry we turn the time complexity from O(n^2) to O(log n), a vast improvement (correct me if I’m wrong here).

Here’s some sample code to generate a map on gm_construct of a grid with each point touching the floor.

[lua]

local function createMap(startPos, endPos, height, step)

local depthMap = {}

for row = 0, 1, step do
	local curRow = Lerp(row, startPos.x, endPos.x)
	for col = 0, 1, step do
	
		--Trace down from a virtual grid in the sky to generate depth map.
		local curCol = Lerp(col, startPos.y, endPos.y)
		local nodeStart = Vector(curRow, curCol, height)
		local nodeTrace = util.TraceLine(
			{
				start = nodeStart,
				endpos = nodeStart + Vector(0, 0, -1)*10000, --Ensure no ground is left untouched
				mask = MASK_NPCWORLDSTATIC --Hit world only
			}
		)

		table.insert(depthMap, nodeTrace.HitPos)
	end
end

--This should convert our generated depth map into a quad tree.
--(Currently unimplemented)
depthMap = quadTreeMap(depthMap)

return depthMap

end

local map = createMap(Vector(-4836.620605,-3384.174072,5126.972168), Vector(1710.029419,6276.094238,5126.972168),5126,0.005)

PrintTable(#map)

[/lua]

I would greatly appreciate help and something like this would be very useful for all sorts of addons to have out there. For those interested, I’m looking to use it for a decent dynamic rain addon to help detect when the user is under cover or not, instead of spamming laggy particles that don’t look great. Cheers!

You’re going to want an octree. Quadtrees are for 2D.

the example I gave wasn’t great, given I’m using this only for a 2d plane it should be fine to use a Quadtree

During my bachelor I had a course which had a lecture on this. Check out the slides.
http://www.cs.uu.nl/docs/vakken/ddm/slides2014/datastructures-2014.pptx

It also shows some alternatives if you’re interested (specifically KD trees, R Trees and BSP trees don’t seem applicable in your case).

[editline]19th May 2015[/editline]

Here’s an idea for Lua, using simple tables. In this example, a tree is subdivided iff it contains more than **four **points. The number 4 here is arbitrary, choose it to your likings.

https://dl.pushbulletusercontent.com/YyX2UMJbZKRGrBYMtWuEviLptzcSN82L/TO%20DO%20-%20Page%203.png

Nearest neighbor queries are complicated with quadtrees. When checking the nearest neighbors of P4, you first find P5 (same node, then you look at the blue fields 2, 3 and 4 and find P6, P7 and P8, but after that it starts to get interesting. What if the orange trees 2 and 3 are subdivided? In orange tree 2 you’d have to look at subtrees 3 and 4 and walk everything there, in orange tree 3 you’d have to look at subtrees 2 and 4 and walk everything there.

To make this thing work, every subtree should link to its parent, so you can walk up and down the tree. Maybe you can even have a mapping between points and subtrees, so you can find the subtree that contains the point in O(1) time.

[editline]19th May 2015[/editline]

Oh, and in actual pseudoLua:

[lua]

Tree = {{P1, parent = Tree}, {P2, P3, parent = Tree}, {parent = Tree}, Blue}
Blue = {{P4, P5, parent = Blue}, {P6, parent = Blue}, {P7, P8, parent = Blue}, {parent = Blue}, parent = Tree}
[/lua]

Sure it has a mutual and recursive references that aren’t possible in actual Lua, but the point should be clear.

Thanks dude, I’ll see if one of these fits better

and damn how come your handwriting is so nice?

Haha, cheers! Two reasons:

  1. My handwriting used to be terrible and I actually took a course to improve it when I was about 12
  2. I put more effort into it because people should be able to read it.