Вращение двумерного массива -> обращение цикла - PullRequest
Новая
       12

Вращение двумерного массива -> обращение цикла

2 голосов
/ 11 ноября 2011

Я использую следующий код для поворота битовой маски (упакованный 2d массив).Честно говоря, у меня нет четкого понимания используемого алгоритма, я скопировал и изменил код поворота из библиотеки pygame (где он использовался для поворота поверхностей).Благодаря реализации bitmask я могу значительно ускорить это вращение, изменив внутренний цикл.Я имею в виду, вместо foreach y { foreach x { ... } } мне нужно сделать foreach x { foreach y { ... } }.У меня проблемы с обращением цикла, потому что тригонометрию нужно адаптировать так, как я сейчас не вижу.

Вот код: 

typedef struct bitmask {
  int w,h;
  BITMASK_W bits[1];
} bitmask_t;

bitmask_t* bitmask_rotate(const bitmask_t *mask, float angle) {
    bitmask_t *newmask = NULL;

    double radangle, sangle, cangle;
    int isin, icos;
    double cx, cy, sx, sy;
    int x, y, ax, ay, xd, yd, dx, dy;
    int nxmax, nymax, xmaxval, ymaxval;

    radangle = angle * DEG_TO_RAD;
    sangle = sin(radangle);
    cangle = cos(radangle);
    isin = (int)(sangle * 65536);
    icos = (int)(cangle * 65536);

    x = mask->w;
    y = mask->h;
    cx = cangle*x;
    cy = cangle*y;
    sx = sangle*x;
    sy = sangle*y;
    nxmax = (int) (MAX (MAX (MAX (fabs (cx + sy), fabs (cx - sy)), fabs (-cx + sy)), fabs (-cx - sy)));
    nymax = (int) (MAX (MAX (MAX (fabs (sx + cy), fabs (sx - cy)), fabs (-sx + cy)), fabs (-sx - cy)));

    newmask = bitmask_create(nxmax, nymax, 0);
    if (!newmask) return NULL;

    cy = newmask->h / 2;
    xd = ((mask->w - newmask->w) << 15);
    yd = ((mask->h - newmask->h) << 15);

    ax = ((newmask->w) << 15) - (int)(cangle * ((newmask->w - 1) << 15));
    ay = ((newmask->h) << 15) - (int)(sangle * ((newmask->w - 1) << 15));

    xmaxval = ((mask->w) << 16) - 1;
    ymaxval = ((mask->h) << 16) - 1;

    for (y = 0; y < newmask->h; y++) {
        dx = (ax + (isin * (cy - y))) + xd;
        dy = (ay - (icos * (cy - y))) + yd;
        for (x = 0; x < newmask->w; x++) {
            if (!(dx < 0 || dy < 0 || dx > xmaxval || dy > ymaxval)) {
                if (bitmask_getbit(mask, dx >> 16, dy >> 16)) {
                    bitmask_setbit(newmask, x, y);
                }
            }

            dx += icos;
            dy += isin;
        }
    }

    return newmask;
}

Прежде чем люди собираютсяспросите «что вы пробовали?» , я зациклил вращающиеся матрицы в Википедии, и я мог видеть, что там происходит и как они реализовали это в этом алгоритме (предварительно вычислили начальные dx и dy и затем увеличивайте с icos и isin), но битовые смещения и параметры, которые я не понимаю (например, ax), мешают мне следовать.

1 Ответ

1 голос
/ 11 ноября 2011 
for (x = 0; x < newmask->w; x++) {
    dx = (ax + (isin * cy + icos * x)) + xd;
    dy = (ay - (icos * cy - isin * x)) + yd;
    for (y = 0; y < newmask->h; y++) {
        if (!(dx < 0 || dy < 0 || dx > xmaxval || dy > ymaxval)) {
            if (bitmask_getbit(mask, dx >> 16, dy >> 16)) {
                bitmask_setbit(newmask, x, y);
            }
        }

        dx -= isin;
        dy += icos;
    }
}
...