tzaeschke / tinspin-indexes

Spatial index library with R*Tree, STR-Tree, Quadtree, CritBit, KD-Tree, CoverTree and PH-Tree
http://www.tinspin.org
Apache License 2.0
111 stars 24 forks source link

Improve m0/m1 computation #9

Open tzaeschke opened 7 years ago

tzaeschke commented 7 years ago

m0/m1 computation in the quadtree iterators could be improved by replacing

for (int d = 0; d < center.length; d++) {
    m0 <<= 1;
    m1 <<= 1;
    if (max[d] >= center[d]) {
        m1 |= 1;
        if (min[d] >= center[d]) {
            m0 |= 1;
        }
    }
}

with

for (int d = 0; d < center.length; d++) {
    m0 <<= 1;
    m1 <<= 1;
    //Extract signum bit
    m1 |= (Double.doubleToRawLongBits(center[d] - max[d]) >>> 63) & 1;
    m0 |= (Double.doubleToRawLongBits(center[d] - min[d]) >>> 63) & 1;
}