Справка по сетке JavaScript

Question

Я работаю над циклическим просмотром нескольких элементов сетки и надеялся, что кто-нибудь может помочь мне найти способ найти нужные мне элементы, и, возможно, я лучше пойму, как получить доступ к элементам сетки. Так вот сетка.

[0]  [1]  [2]  [3]  [4]
[5]  [6]  [7]  [8]  [9]
[10] [11] [12] [13] [14]
[15] [16] [17] [18] [19]
[20] [21] [22] [23] [24]

Это в основном сетка 5х5, однако она может быть любого размера, но я просто использовал это для примера. Есть два способа, которыми я хотел бы пройти через это. Первый в этом порядке:

0,1,2,3,4,9,14,19,24,23,22,21,20,15,10,5,6,7,8,13,18,17,16,11,12

По сути, все, что делает, - это обходит снаружи, начиная с верхнего левого угла. Следующим способом, который я хотел бы пройти через это, являются те же самые точные значения, за исключением в обратном порядке (в основном наизнанку, а не снаружи внутрь), и на самом деле, думая об этом сейчас, я мог бы просто перебрать первый метод назад. Если кто-нибудь может помочь мне с этим, было бы здорово. Я действительно хочу узнать больше о том, как перебирать предметы в таких сумасшедших аранжировках, как этот.

Answer 1

Эта функция

function n(i, w, h)
{
    if (i < w)
        return i;
    if (i < w + h-1)
        return w-1 + (i-w+1)*w;
    if (i < w + h-1 + w-1)
        return w-1 + (h-1)*w - (i - (w + h-1 - 1));
    if (i < w + h-1 + w-1 + h-2)
        return (h - (i - (w + w-1 + h-1 - 2)))*w;
    var r = n(i - (w-1)*2 - (h-1)*2, w-2, h-2);
    var x = r % (w-2);
    var y = Math.floor(r / (w-2));
    return (y+1)*w + (x+1);
}

принимает в качестве ввода

• i: индекс элемента, который вы ищете
• w: ширинасетки
• h: высота сетки

и возвращает соответствующий элемент сетки при условии, что по часовой стрелке пройден спираль.

Реализацияпросто проверяет, находимся ли мы на верхней стороне (i<w), на нижней правой стороне (i<w+h-1) и так далее, и для этих случаев он явно вычисляет элемент ячейки.Если мы завершим одну поездку по спирали, то он рекурсивно вызывает сам себя, чтобы найти элемент во внутренней сетке (w-2)*(h-2), а затем извлекает и корректирует две координаты с учетом исходного размера сетки.

Это намного быстрее длябольшие сетки, чем просто итерация и эмуляция спирального обхода, например, вычисление n(123121, 1234, 3012) является немедленным, в то время как полная сетка имеет 3712808 элементов, и обход 123121 шагов потребует довольно длительного времени.

Answer 2

Вам просто нужен способ для представления шаблона обхода.

Учитывая матрицу NxM (например, 5x5), шаблон равен

GENERAL       5x5
-------     -------
N right        5
M-1 down       4
N-1 left       4
M-2 up         3
N-2 right      3
M-3 down       2
N-3 left       2
M-4 up         1
N-4 right      1

Это означает движение 5 вправо, 4 вниз, 4 влево, 3 вверх, 3 вправо, 2 вниз, 2 влево, 1 вверх, 1 вправо. Размер шага меняется после каждых двух итераций.

Таким образом, вы можете отслеживать текущий «размер шага» и текущее направление, уменьшая N, M до достижения конца.

ВАЖНО: не забудьте записать шаблон для неквадратной матрицы, чтобы увидеть, применяется ли тот же шаблон.

Answer 3

Вот метод "прогулки".Менее эффективно, но работает.

var arr = new Array();
for(var n=0; n<25; n++) arr.push(n);

var coords = new Array(); 

var x = 0;
var y = 0;
for(var i=0; i<arr.length; i++) {
     if( x > 4 ) {
          x = 0;
          y++;
     }

     coords[i] = {'x': x, 'y': y};

     x++;
}

// okay, coords contain the coordinates of each item in arr

// need to move along the perimeter until a collision, then turn.

// start at 0,0 and move east.

var dir = 0; // 0=east, 1=south, 2=west, 3=north.
var curPos = {'x': 0, 'y': 0};
var resultList = new Array();

for(var x=0; x<arr.length; x++) {
     // record the current position in results
     var resultIndex = indexOfCoords(curPos, coords);

     if(resultIndex > -1) {
         resultList[x] = arr[resultIndex];
     }
     else {
         resultList[x] = null;
     }

     // move the cursor to a valid position
     var tempCurPos = movePos(curPos, dir);

     var outOfBounds = isOutOfBounds(tempCurPos, coords);
     var itemAtTempPos = arr[indexOfCoords(tempCurPos, coords)];
     var posInList = resultList.indexOf( itemAtTempPos );

     if(outOfBounds || posInList > -1) {
          dir++;
          if(dir > 3) dir=0;
          curPos = movePos(curPos, dir);
     }
     else {
          curPos = tempCurPos;
     }
}


/* int indexOfCoords
 *
 * Searches coordList for a match to myCoords.  If none is found, returns -1;
 */
function indexOfCoords(myCoords, coordsList) {
    for(var i=0; i<coordsList.length; i++) {
        if(myCoords.x == coordsList[i].x && myCoords.y == coordsList[i].y) return i;
    }
    return -1;
}

/* obj movePos
 *
 * Alters currentPosition by incrementing it 1 in the direction provided.
 * Valid directions are 0=east, 1=south, 2=west, 3=north
 * Returns the resulting coords as an object with x, y.
 */
function movePos(currentPosition, direction) {
    var newPosition = {'x':currentPosition.x, 'y':currentPosition.y};
    if(direction == 0) {
        newPosition.x++;
    }
    else if(direction == 1) {
        newPosition.y++;
    }
    else if(direction == 2) {
        newPosition.x--;
    }
    else if(direction == 3) {
        newPosition.y--;
    }

    return newPosition;
}

/* bool isOutOfBounds
 *
 * Compares the x and y coords of a given position to the min/max coords in coordList.
 * Returns true if the provided position is outside the boundaries of coordsList.
 *
 * NOTE: This is just one, lazy way of doing this.  There are others.
 */
function isOutOfBounds(position, coordsList) {
    // get min/max
    var minx=0, miny=0, maxx=0, maxy=0;
    for(var i=0; i<coordsList.length; i++) {
        if(coordsList[i].x > maxx) maxx = coordsList[i].x;
        else if(coordsList[i].x < minx) minx = coordsList[i].x;

        if(coordsList[i].y > maxy) maxy = coordsList[i].y;
        else if(coordsList[i].y < miny) miny = coordsList[i].y;
    }

    if(position.x < minx || position.x > maxx || position.y < miny || position.y > maxy) return true;
    else return false;
}

Это будет перемещаться по сетке в направлении, пока не достигнет границ или элемента, уже находящегося в массиве результатов, а затем повернется по часовой стрелке.Это довольно элементарно, но я думаю, что это сработает.Вы можете изменить это довольно просто.

Вот рабочий пример: http://www.imakewidgets.com/test/walkmatrix.html