Optimizing quadrant selection

Question

I'm working on a data structure which subdivides items into quadrants, and one of the bottlenecks I've identified is my method to select the quadrant of the point. Admittedly, it's fairly simple, but it's called so many times that it adds up. I imagine there's got to be an efficient way to bit twiddle this into what I want, but I can't think of it.

private int Quadrant(Point p)
{
    if (p.X >= Center.X)
        return p.Y >= Center.Y ? 0 : 3;
    return p.Y >= Center.Y ? 1 : 2;
}

Center is of type Point, coordinates are ints. Yes, I've run a code profile, and no, this isn't premature optimization.

---

Because this is only used internally, I suppose my quadrants don't have to be in Cartesian order, as long as they range from 0-3.

Answer 1

My first try would be to get rid of the nested conditional.

int xi = p.X >= Center.X ? 1 : 0;
int yi = p.Y >= Center.Y ? 2 : 0;
int quadrants[4] = { ... };
return quadrants[xi+yi];

The array lookup in quadrants is optional if the quadrants are allowed to be renumbered. My code still needs two comparisons but they can be done in parallel.

I apologise in advance for any C# errors as I usually code C++.

---

Perhaps something more efficient is possible when two unsigned 31 bit coordinates are stored in a 64 bit unsigned long variable.

// The following two lines are unnecessary
// if you store your coordinated in unsigned longs right away
unsigned long Pxy = (((unsigned long)P.x) << 32) + P.y;
unsigned long Centerxy = (((unsigned long)Center.x) << 32) + Center.y;

// This is the actual calculation, only 1 subtraction is needed.
// The or-ing with ones hast only to be done once for a repeated use of Centerxy.
unsigned long diff = (Centerxy|(1<<63)|(1<<31))-Pxy;
int quadrant = ((diff >> 62)&2) | ((diff >> 31)&1);

---

Taking a step back, a different solution is possible. Do not arrange your data structure split into quadrants right away but alternately in both directions. This is also done in the related Kd-tree

Answer 2

The fastest way in C/C++ it would be

(((unsigned int)x >> 30) & 2) | ((unsigned int)y >> 31)

(30/31 or 62/63, depending on size of int). This will give the quadrants in order 0, 2, 3, 1.

Edit for LBushkin:

(((unsigned int)(x - center.x) >> 30) & 2) | ((unsigned int)(y-center.y) >> 31)

Answer 3

I don't know that you can make this code dramatically faster in C#. What you may be able to do, however, it look at how you're processing points, and see if you can avoid making unecessary calls to this method. Perhaps you could create a QuadPoint structure that stores which quadrant a point is in (after you compute it once), so that you don't have to do so again.

But, admittedly, this depends on what your algorithm is doing, and whether it's possible to store/memoize the quadrant information. If every point is completely unique, this obviously won't help.