HiveBrain v1.2.0
Get Started
← Back to all entries
patterncppMinor

Determine quadrant of code

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
codequadrantdetermine

Problem

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()  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.

Solution

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;
}

Code Snippets

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;
}
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;
}

Context

StackExchange Code Review Q#45172, answer score: 8

Revisions (0)

No revisions yet.