Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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) {
        if (topQuadrant) {
            index = 1;
        } else if (bottomQuadrant) {
            index = 2;
        }
    }
    // Fits in right
    else if (aabb.getX() > vertMid && aabb.getX() + aabb.getWidth() < bounds.getX() + bounds.getWidth()) {
        if (topQuadrant) {
            index = 0;
        } else if (bottomQuadrant) {
            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.

share|improve this question
add comment

2 Answers 2

up vote 6 down vote accepted

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.


You can add ...

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.

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

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

 2 1
 3 4

But your code has the quadrants:

 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) {
    int quad = 0;
    if (y < horzMid) {
        quad = x < vertMid ? 2 : 3;
    } else {
        quad = x < vertMid ? 1 : 0;
    }
    return quad;
}

Then, using this function you can:

int getIndex(AABB aabb) {

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

    // Quadrant of bottom-left point.
    int blQuad = getPointIndex(horzMid, vertMid, aabb.getX(), aabb.getY())
    // Quadrant of top-right point.
    int trQuad = getPointIndex(horzMid, vertMid, aabb.getX() + aabb.getWidth(), aabb.getY() + aabb.getHeight())

    if (blQuad == trQuad) {
        return blQuad;
    }

    return -1;
} 
share|improve this answer
    
Thank you, that should help with readability. –  Tips48 Mar 24 at 1:01
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.