Hi. I'm trying to write a pr quadtree. My code might be ugly, so bear with me. The problem I'm having is that I'm trying to reinsert a node into the tree so that it will become part of the next subtree.
for example
()
/ / \ \
(A) () () ()
/ / \ \
() () () ()
and when I insert B which falls in the region of A, the tree becomes. A falls under the region where B is.
()
/ / \ \
() () () ()
/ / \ \
(B)()(A)()
it can even be, as the leaves only matter
()
/ / \ \
(A) () () ()
/ / \ \
(B)()(A)()
where points B and A fall in their respective region. I can't find a way to insert A back into the tree without falling into infinite recursion. I'm thinking I just need a case where it won't keep looping. any help would be appreciative, thanks. sorry about the length.
edit: my code is modified from below. its similiar but its correct now. but the problem I described is still the same. Again, any help would be appreciative.
<br />
void insert(node *&root, double x, double y, double xmax, double ymax, double xmin, double ymin, int j )<br />
{<br />
if (root == NULL)<br />
{<br />
root = new node ( x, y, xmax/2, ymax/2, xmin/2, ymin/2 );<br />
return;<br />
}<br />
else if ( x < 0 && y > 0 && root->xmax == 1024 && root->xmin == -1024 && root->nwnode == NULL)<br />
{<br />
root->nwnode = new node ( x, y, 1024, 1024, 0, 0 );<br />
}<br />
else if ( x > 0 && y > 0 && root->xmax == 1024 && root->xmin == -1024 && root->nenode == NULL)<br />
{<br />
root->nenode = new node ( x, y, 1024, 1024, 0, 0 );<br />
}<br />
else if ( x < 0 && y < 0 && root->xmax == 1024 && root->xmin == -1024 && root->swnode == NULL)<br />
{<br />
root->swnode = new node ( x, y, 1024, 1024, 0, 0 );<br />
}<br />
else if ( x > 0 && y < 0 && root->xmax == 1024 && root->xmin == -1024 && root->senode == NULL)<br />
{<br />
root->senode = new node ( x, y, 1024, 1024, 0, 0 );<br />
}<br />
else if ( x >= 0 && y >= 0)<br />
{<br />
if ( root->xmax/2 <= x )<br />
{<br />
if ( root->ymax/2 <= y )<br />
{<br />
<br />
insert( root->nenode, x, y, root->xmax, root->ymax, root->xmin, root->ymin, j);<br />
}<br />
else<br />
{<br />
insert( root->senode, x, y, root->xmax, root->ymax, root->xmin, root->ymin, j);<br />
}<br />
}<br />
else<br />
{<br />
if ( root->ymax/2 <= y )<br />
{<br />
insert( root->nwnode, x, y, root->xmax, root->ymax, root->xmin, root->ymin, j);<br />
}<br />
else<br />
{<br />
insert( root->swnode, x, y, root->xmax, root->ymax, root->xmin, root->ymin, j);<br />
}<br />
}<br />
}<br />
else if ( x >= 0 && y <= 0 )<br />
{<br />
if ( root->xmax/2 <= x )<br />
{<br />
if ( root->ymin/2 <= y )<br />
{<br />
insert( root->nenode, x, y, root->xmax, root->ymax, root->xmin, root->ymin, j);<br />
}<br />
else<br />
{<br />
insert( root->senode, x, y, root->xmax, root->ymax, root->xmin, root->ymin, j); <br />
}<br />
}<br />
else <br />
{<br />
if ( root->ymin/2 <= y )<br />
{<br />
insert( root->nwnode, x, y, root->xmax, root->ymax, root->xmin, root->ymin, j);<br />
}<br />
else<br />
{<br />
insert( root->swnode, x, y, root->xmax, root->ymax, root->xmin, root->ymin, j);<br />
}<br />
}<br />
}<br />
else if ( x <= 0 && y >= 0 )<br />
{<br />
if ( root->xmin/2 <= x )<br />
{<br />
if ( root->ymax/2 <= y )<br />
{<br />
insert( root->nenode, x, y, root->xmax, root->ymax, root->xmin, root->ymin, j);<br />
}<br />
else<br />
{<br />
insert( root->senode, x, y, root->xmax, root->ymax, root->xmin, root->ymin, j);<br />
}<br />
}<br />
else<br />
{<br />
if ( root->ymax/2 <= y )<br />
{<br />
insert( root->nwnode, x, y, root->xmax, root->ymax, root->xmin, root->ymin, j);<br />
}<br />
else<br />
{<br />
insert( root->swnode, x, y, root->xmax, root->ymax, root->xmin, root->ymin, j);<br />
}<br />
}<br />
}<br />
else if ( x <= 0 && y <= 0 )<br />
{<br />
if ( root->xmin/2 <= x )<br />
{<br />
if ( root->ymin/2 <= y )<br />
{<br />
insert( root->nenode, x, y, root->xmax, root->ymax, root->xmin, root->ymin, j);<br />
}<br />
else<br />
{<br />
insert( root->senode, x, y, root->xmax, root->ymax, root->xmin, root->ymin, j);<br />
}<br />
}<br />
else<br />
{<br />
if ( root->ymin/2 >= y )<br />
{<br />
insert( root->nwnode, x, y, root->xmax, root->ymax, root->xmin, root->ymin, j);<br />
}<br />
else<br />
{<br />
insert( root->swnode, x, y, root->xmax, root->ymax, root->xmin, root->ymin, j);<br />
}<br />
}<br />
}<br />
<br />
}<br />
-- modified at 5:09 Sunday 25th February, 2007
|