Game Development Reference
In-Depth Information
std::shared_ptr<node> Insert(std::shared_ptr<node>& n, const math::rectangle& rectangle)
{
if ( !n->IsLeaf() ) {
auto newNode = Insert( n->Child(0), rectangle );
if ( newNode != nullptr )
return newNode;
return Insert(n->Child(1), rectangle);
}
else
{
if ( !n->IsEmpty() )
return nullptr;
auto& parentRect = n->Rectangle();
if ( rectangle.Width() > parentRect.Width() || rectangle.Height() > parentRect.Height() )
return nullptr;
// If it fits perfectly, we found our node
if ( math::IsEqual(parentRect.Width(), rectangle.Width() ) && math::IsEqual(parentRect.Height(), rectangle.Height() ) )
{
n->IsEmpty() = false;
return n;
}
n->Child(0) = std::shared_ptr<node>(new node());
n->Child(1) = std::shared_ptr<node>(new node());
auto w = parentRect.Width() - rectangle.Width();
auto h = parentRect.Height() - rectangle.Height();
if ( w > h )
{
n->Child(0)->Rectangle() = math::rectangle::MakeRectangle(parentRect.Left(), parentRect.Top(), parentRect.Left() + w, paren-
tRect.Bottom());
n->Child(1)->Rectangle() = math::rectangle::MakeRectangle(parentRect.Left() + w, parentRect.Top(), parentRect.Right(), paren-
tRect.Bottom());
}
else
{
n->Child(0)->Rectangle() = math::rectangle::MakeRectangle(parentRect.Left(), parentRect.Top(), parentRect.Right(), paren-
tRect.Top() + h);
n->Child(1)->Rectangle() = math::rectangle::MakeRectangle(parentRect.Left(), parentRect.Top() + h, parentRect.Right(), paren-
tRect.Bottom());
}
return Insert(n->Child(0), rectangle);
}
}
At the beginning we check if the node is not a leaf, if it is not, it means it has children, so
wewillrecursivelycallInsertwiththefirstchildnodeandattempttofittherectanglethere,
if it fails, we will call Insert with the second child and we will return whether successful or
not.
Ifthenodeisaleaf,thenwecanbegintocheckifourrectanglecanfitinit,orifweneedto
partition the area. The first thing we check is if this node is already in use, meaning it's not
