Определение квадранта точки

Question

Мне нужно быстрее определить квадрант точки.Мне известно только о методе «определить с помощью знаков».Я ищу хороший подход, если таковой имеется.Если бы не какие-либо исправления в моем коде помогли бы.Предположим, что на самолете 4 квадрацикла.Мой код -

        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

Разветвления и поиск в памяти - это то, чего следует избегать при выполнении микрооптимизации на фрагменте кода.Со встроенной сборкой вы можете просто использовать CMOV (Условное MOV), чтобы ускорить работу на системах x86.Компилятор горячей точки Java также может быть использован для использования этой инструкции.Но так как фрагмент очень прост, выполнение слишком большого количества операций, чтобы избежать разветвлений или поиска в памяти, может (в конце концов) быть пораженческим.

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

Когда вы думаете о результате, то после

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

Вы можете получить по формуле

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

Так в Java

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

РЕДАКТИРОВАТЬ Только для людей, интересующихся встроенной сборкой ...

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

Вот метод для вас. Выглядит просто ...

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

Мне очень понравился приведенный выше пример с битами, но мне нужно было это в 3d и в C ... так что на всякий случай это полезно Я уверен, что это достаточно близко, чтобы конвертировать в Java в любом случае, если это кому-то нужно.

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

Answer 5

Будьте проще! Нет необходимости в ветвлениях, перестановке битов, поиске в памяти, ассемблере или других сложностях.

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

( Объяснение . Учитывая X и Y, как в моей функции, квадрант задается этим квадратичным полиномом:

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

и затем, если вы соберете термины и упростите, вы получите выражение, которое я использовал.)