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
|
