Definition of the quadrant of a point

Question

I need to determine the quadrant of the point faster. I only know about the "method of identifying symptoms." I am looking for a good approach, if any. If no fixes for my code would help. Suppose there are 4 ATVs on the plane. My code is

int x = scan.nextInt() > 0 ? 1 : 0; int y = scan.nextInt() > 0 ? 1 : 0; switch (x) { case 1: switch (y) { case 1: quad = 1; break; case 0: quad = 4; break; } break; case 0: switch (y) { case 1: quad = 2; break; case 0: quad = 3; break; } break; } 

Answer 1

Branching and searching in memory are things that should be avoided when performing microoptimization on a piece of code. With the built-in build, you can simply use CMOV (Conditional MOV) to speed up work on x86 systems. The Java hotspot compiler can also be applied to this instruction. But since the fragment is very simple, performing too many operations to avoid branching or looking for memory can (in the end) be defeatist.

 static int[] QUAD_LUT = new int[]{1, 2, 4, 3}; ... // use the sign bit on the integers return QUAD_LUT[ (x >>> 31) | ((y >>> 30) & 0x2) ] 

When you think about the result, you are after

 x.sign y.sign Quad 0 0 1 0 1 4 1 0 2 1 1 3 

You can get to the formula

 (x.sign XOR y.sign + y.sign + y.sign) + 1 

So in Java

 y = (y>>>31); return ((x>>>31) ^ y) + y + y + 1; 

EDIT Only for people interested in embedded assembly ...

 ;; NASM/FASM syntax ;; GetQuadrant(int x, int y) ;; RETURN [1|2|3|4] in EAX register GetQuadrant: MOV eax, [esp+4] ;; = x MOV ecx, [esp+8] ;; = y SHR eax, 31 ;; = >> 31 SHR ecx, 31 ;; = >> 31 XOR eax, ecx ;; = x XOR y LEA eax, [eax + ecx * 2 + 1] ;; = x + y*2 + 1 RET 8 ;; correct stack and return 

Answer 2

Here is the method. It just looks ...

 getQuadrant(int x, int y) { if (x >= 0) { return y >= 0 ? 1 : 4; } else { return y >= 0 ? 2 : 3; } } 

Answer 3

 int[] quads = new int[] { 3, 2, 4, 1 }; int x = scan.nextInt() > 0 ? 2 : 0; int y = scan.nextInt() > 0 ? 1 : 0; int result = quads[x + y]; 

Answer 4

Keep it simple! There is no need for tweaking, bit-twiddling, memory searching, assembly language or other complications.

 int getQuadrant(int x, int y) { int X = (x >= 0); int Y = (y >= 0); return 3 + X - Y - 2 * X * Y; } 

(Explanation. Given X and Y , as in my function, the quadrant is defined by this quadratic polynomial:

 1 * X * Y + 2 * (1 - X) * Y + 3 * (1 - X) * (1 - Y) + 4 * X * (1 - Y) 

and then if you collect the terms and simplify, you get the expression that I used.)

Answer 5

I really liked the twiddle bit example above, but I needed it in 3d and in C ... so just in case, this is useful. I am sure this is close enough to convert to java anyway if someone needs it.

 int point_to_3d_quad (int x, int y, int z) { static int q[] = { 1, 2, 3, 4, 5, 6, 7, 8 }; int X = (x >> ((sizeof(x)*8)-1)) & 1; int Y = ((y >> ((sizeof(y)*8)-1)) & 1) << 1; int Z = ((z >> ((sizeof(z)*8)-1)) & 1) << 2; return (q[X | Y | Z]); }