Re: [Algorithms] Neighbors in quad and oct trees

[Thatcher U. <tu...@tu...>]

From: Kelvin McDowell <to...@nu...>


> I need to construct graphs that connect all the leaf nodes with thier
> neighbors in quad and oct trees.  Is there a well-worn algorithm that
given
> a leaf can return all of its neighbors?

Didn't we just go through this?  I guess nobody posted actual code.  Here's
some code for quadtree neighbor-finding:

qsquare* GetNeighbor(int dir, const quadcornerdata& cd)
// Traverses the tree in search of the qsquare neighboring this
// square to the specified direction.  The directions are 0-3
// --> { E, N, W, S }.  Returns NULL if the neighbor doesn't
// exist.
//
// ChildIndex mapping:
// +-+-+
// |1|0|
// +-+-+
// |2|3|
// +-+-+
{
  // If we don't have a parent, then we don't have a neighbor.
  if (cd.Parent == 0) return 0;

  // Find the parent and the child-index of the square we want to locate.
  qsquare* p = 0;

  int index = cd.ChildIndex ^ 1 ^ ((dir & 1) << 1);
  bool SameParent = ((dir - cd.ChildIndex) & 2) ? true : false;

  if (SameParent) {
   p = cd.Parent->Square;
  } else {
   p = cd.Parent->Square->GetNeighbor(dir, *cd.Parent);

   if (p == 0) return 0;
  }

  qsquare* n = p->ChildLink[index];

  return n;
 }


--
Thatcher Ulrich
http://tulrich.com