patterncppMinor
Determine quadrant of code
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:
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.
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 subdivided1 indicates top right2 indicates top left3 indicates bottom left4 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:
But your code has the quadrants:
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;
Then, using this function you can:
2 1
3 4But your code has the quadrants:
1 0
2 3I 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.