Xác định góc phần tư của một điểm

Question

Tôi cần xác định góc phần tư của điểm, theo cách nhanh hơn. Tôi chỉ biết phương pháp "xác định sử dụng dấu hiệu". Tôi đang tìm một cách tiếp cận tốt, nếu có. Nếu không có bất kỳ bản sửa lỗi nào cho mã của tôi sẽ hữu ích. Giả sử có 4 quad trên mặt phẳng. Mã của tôi-

 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

nhánh và bộ nhớ nhìn ups là những điều cần tránh khi thực hiện tối ưu hóa vi trên một đoạn mã. Với việc lắp ráp nội tuyến, bạn có thể sử dụng CMOV (MOV có điều kiện) để tăng tốc trên các hệ thống x86. Trình biên dịch hotspot của Java cũng có thể được sử dụng trong hướng dẫn này. Nhưng vì đoạn mã đơn giản như vậy, nên thực hiện quá nhiều thao tác để tránh việc phân nhánh hoặc tìm kiếm bộ nhớ có thể (cuối cùng) là kẻ đánh bại.

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

Khi bạn nghĩ về kết quả sau khi bạn

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

Bạn có thể nhận được công thức

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

Vì vậy, trong Java

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

EDIT Chỉ cần cho những người tò mò về lắp ráp nội tuyến ...

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

Đây là phương pháp dành cho bạn. Có vẻ đơn giản ...

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

Giữ nó đơn giản! Không cần các chi nhánh, bit-twiddling, tra cứu bộ nhớ, ngôn ngữ lắp ráp, hoặc các biến chứng khác. .

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

(Giải thích Với X và Y như trong chức năng của tôi, góc phần tư được đưa ra bởi đa thức bậc hai này:

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

và sau đó nếu bạn thu thập các điều khoản và đơn giản hóa, bạn sẽ có được sự biểu hiện Tôi đã sử dụng.)

Answer 5

Tôi thực sự thích ví dụ bit xoắn ở trên - nhưng tôi cần điều này trong 3d và trong C ... vì vậy chỉ trong trường hợp điều này là hữu ích. Tôi chắc rằng điều này là đủ gần để chuyển đổi sang java anyway nếu ai đó cần nó.

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