Neighbor finding of multiple quadtree

Question

I need some help with this problem I'm having of how to do Neighbor find of multiple quadtrees.

I have a cube. Each side of the cube is made of N individually colored quads (as you can see from the image below). Each one of these individually colored quads has the ability to perform a quadtree (recursively sub-divide itself into 4 smaller parts). In addition, every quad has a location attribute that can tell you its local and global {x,y,z} position. Also, all the quads are stored in a 1D array.

Now let's say for example I select a random quad Q1, and that quad splits into 4 children:

Q1 → (Q1)(1), (Q1)(2), (Q1)(3), (Q1)(4)

And then I select (Q1)(1) child to split into 4.

(Q1)(1) → ((Q1)(1))(1), ((Q1)(1))(2), ((Q1)(1))(3), ((Q1)(1))(4),

And now I would like to find all ((Q1)(1))(2) neighboring quads

In general, I'm asking How do I perform neighbor finding on this data structure so that I can find any neighboring quad of a child or parent quad at any level?

user_9848484 · Answer

The way I'd go is by first renaming how you visualize your child nodes inside your quadtree. instead of using 1, 2, 3, 4 which can be confusing, we'll use NorthWest, NorthEast, SouthWest, SouthEast.

Then, you have to consider a list of neighbors for your node. Trivially, each node in the tree has 4 neighbors, that we will name South, North, East, West.

then you can use the following algorithm:

Entry: A node or a leaf 'N'
Entry: An empty list 'L' : [South = null, North = null, East = null, West = null]

=========

ParentNode = empty
childNode = N
while L not full && ChildNode.ParentNode != null:
    ParentNode = ChildNode.ParentNode
    if (childNode == ParentNode.SouthWest)
        L.North = (L.North == null) ? ParentNode.North : L.North
        L.East = (L.East == null) ? ParentNode.East : L.East
    if (childNode == ParentNode.SouthEast)
        L.North = (L.North == null) ? ParentNode.North : L.North
        L.West = (L.West == null) ? ParentNode.West : L.West
    if (childNode == ParentNode.NorthWest)
        L.South = (L.South == null) ? ParentNode.South : L.South
        L.East = (L.East == null) ? ParentNode.East : L.East
    if (childNode == ParentNode.NorthEast)
        L.South = (L.South == null) ? ParentNode.South : L.South
        L.West = (L.West == null) ? ParentNode.West : L.West
    childNode = ParentNode

that's just pseudo code on how i'd implement the search inside the quadtree. In case there are some values inside the list that are still null (mainly because it was in the border of your tree), you will need to look at your data stored in the 1D array that we'll name 'A'.

To do that, you need to know the number of quads in your radius. also, your quads need to have a function to search values provided a coordinate. named 'Search'.

then, you have to implement the following algorithm:

N = A.index(L) // should be known beforehand
C = sqrt(length(A))
if (L.East == null)
    if (N + 1 < length(A))
        L.East = A[N + 1].Search(L.position)
if (L.West == null)
    if (N - 1 >= 0)
        L.West = A[N - 1].Search(L.position)
if (L.North == null)
    if (N + C < length(A))
        L.North = A[N + C].Search(L.position)
if (L.South == null)
    if (N - C >= 0)
        L.South = A[N - C].Search(L.position)

there are a subtlety to consider though:

The search function should be able to return a quad despite the fact that the position provided is outside of it, if it is not possible, just change the value of the position that is outside to the value of the border of the quad.

And that's as far as I can go as I don't know how you implemented the different faces of your dice (or if there are any) or if you'd ever want to get those as neighbor as well.

Neighbor finding of multiple quadtree

1 Answers