I'm currently in the process of coding a QuadTree. The QuadTree seperates into four quadrants, with 1 being the top right and 4 being the bottom right. I have this code to determine which quadrant the AABB fits into:

int getIndex(AABB aabb) {
int index = -1;
double vertMid = bounds.getX() + (bounds.getWidth() / 2);
double horzMid = bounds.getY() + (bounds.getHeight() / 2);

// Fits in top
bool topQuadrant = aabb.getY() < horzMid && aabb.getY() + aabb.getHeight() < horzMid;
// Fits in botom
bool bottomQuadrant = aabb.getY() > horzMid && aabb.getY() + aabb.getHeight() < bounds.getY() + bounds.getHeight();

// Fits in left
if (aabb.getX() < vertMid && aabb.getX() + aabb.getWidth() < vertMid) {
index = 1;
index = 2;
}
}
// Fits in right
else if (aabb.getX() > vertMid && aabb.getX() + aabb.getWidth() < bounds.getX() + bounds.getWidth()) {
index = 0;
index = 3;
}
}

return index;
}


-1 indicates it cannot be subdivided
1 indicates top right
2 indicates top left
3 indicates bottom left
4 indicates bottom right

How can I speed it up/make it cleaner? At the moment it is quite slow and I feel like there is an easier way to do it.

-

Assuming that getHeight is a non-negative number, this statement ...

bool topQuadrant = aabb.getY() < horzMid && aabb.getY() + aabb.getHeight() < horzMid;


... can be reduced to ...

bool topQuadrant = aabb.getY() + aabb.getHeight() < horzMid;


Similarly ...

bool bottomQuadrant = aabb.getY() > horzMid;


If the aabb.getY() + aabb.getHeight() < bounds.getY() + bounds.getHeight(); expression is necessary in the latter, then perhaps you need to add && aabb.getY() > bounds.getY() to your test for topQuadrant.

A similar comment for your horizontal tests.

if (!topQuadrant && !bottomQuadrant)
return -1;


... before you do the horizontal test (to avoid time spent doing the horizontal test if it's in neither the top nor bottom).

After that (if it's in the top or bottom) then if it's in the left quadrant you can do ...

return (topQuadrant) ? 1 : 2;


You won't need the index variable any more.

Consider precomputing/cacheing vertMid and horzMid inside the bounds structure.

AABB is a nasty name for a type.

Also you should pass it by const reference instead of by value (passing by value passes a copy of it, which is slower than passing by reference).

getIndex should perhaps be a method of whatever type your bounds is.

-
Thank you, Caching vertMid and horzMid really helped. – Tips48 Mar 24 '14 at 1:10
@Tips48 You can also precompute/cache getY() + getHeight() and getX() + getWidth() ... name them getLeft(), getRight(), getTop(), and getBottom(). – ChrisW Mar 24 '14 at 1:17

Note, you indicate in the text that you have quadrants:

 2 1
3 4


 1 0
2 3


I recommend you have a function that works on just one point at a time. There are two points, the 'bottom left', and the 'top right'.

So, calculate the quadrant of each point. If they are both in the same quadrant, return the quadrant, otherwise return -1;

int getPointIndex(double horzMid, double vertMid , double x, double y) {
if (y < horzMid) {
quad = x < vertMid ? 2 : 3;
} else {
quad = x < vertMid ? 1 : 0;
}
}


Then, using this function you can:

int getIndex(AABB aabb) {

double vertMid = bounds.getX() + (bounds.getWidth() / 2);
double horzMid = bounds.getY() + (bounds.getHeight() / 2);