Determinación del cuadrante de un punto

Question

Necesito determinar el cuadrante del punto, de una manera más rápida. Solo conozco el método "determinar el uso de los signos". Estoy buscando un buen enfoque, si hay alguno. Si no, cualquier corrección a mi código ayudaría. Supongamos que hay 4 quads en el avión. Mi código-

 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

ramificación y buscar la memoria ups son las cosas que debe evitar al hacer micro optimizaciones en un fragmento de código. Con el ensamblaje en línea, puede usar el CMOV (MOV Condicional) para acelerar los sistemas x86. El compilador de punto de acceso de Java también puede ser inducido a usar esta instrucción. Pero dado que el fragmento es tan simple, hacer demasiadas operaciones para evitar la ramificación o búsquedas de memoria podría ser (al final) derrotista.

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) ] 

Cuando se piensa en el resultado que se busca es

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

Se puede llegar a la fórmula

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

Así en Java

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

EDITAR sólo para la gente curiosa acerca de ensamblado en línea ...

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

Aquí está el método para usted. Parece simple ...

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

Debe ser sencillo! No hay necesidad de ramas, movimientos de memoria, búsquedas de memoria, lenguaje ensamblador u otras complicaciones. .

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

(Explicación Dada X y Y como en mi función, el cuadrante está dada por este polinomio de segundo grado:

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

y luego si recoge términos y simplificar, se obtiene la expresión Lo usé.)

Answer 5

Me gustó mucho el ejemplo de twiddle de bits anterior, pero lo necesitaba en 3D y en C ... por si acaso esto es útil. Estoy seguro de que esto está lo suficientemente cerca como para convertirlo a Java de todos modos si alguien lo necesita.

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