Самый простой способ сгенерировать 8-соседние координаты

Я ищу способ сгенерировать следующую последовательность чисел (которые являются относительными координатами 8 соседей пикселя, начиная с северо-западного пикселя и заканчивая западом). Первое число - это координата y, а второе - координата x:

 y,  x
 _____

 1, -1   // N-W
 1,  0   // N
 1,  1   // N-E
 0,  1   // E
-1,  1   // S-E
-1,  0   // S
-1, -1   // S-W
 0, -1   // W

Я могу придумать несколько уродливых способов добиться этого, например, просто поместить координаты в массив, но мне интересно, есть ли чистый и эффективный способ, о котором я не думал.

Изменить: из-за того, как разработан алгоритм, который я пытаюсь реализовать, пиксели должны повторяться в определенном порядке (с северо-запада на запад).


pixel language-agnostic flip-flop pixels
person user2398029    schedule 23.11.2012    source источник
comment
Можете ли вы объяснить, для чего вам это нужно и почему это должно быть в таком порядке?   -  person AlexWien    schedule 24.11.2012
comment
Это для алгоритма сегментации водораздела; Основная причина, по которой мне нужно, чтобы это было в таком порядке, - это возможность проверить мои решения на основе эталонной реализации. Использование одного и того же порядка гарантирует, что поведение при разрешении галстуков будет одинаковым в обоих случаях.   -  person user2398029    schedule 24.11.2012

Ответы (2)


arrow_upward
3
arrow_downward

Рассмотрим сначала только следующий метод генерации Y-координат.

Начиная с NW, мы хотим достичь {1, 1, 1, 0, -1, -1, -1, 0}. Это повторяющийся шаблон, заданный циклом:

for( int i = 0; i < 8; i++ )
{
    // You can combine into one ternary if you are adventurous
    int y = (i % 4 == 3) ? 0 : 1;
    y *= (i > 3) ? -1 : 1;
}

Таким образом, это сгенерирует желаемую последовательность для значений y.

Теперь рассмотрим последовательность значений x, начиная с NE: {1, 1, 1, 0, -1, -1, -1, 0}. Вы можете видеть, что это та же последовательность.

Таким образом, мы можем создать желаемую последовательность, начиная с NW, используя смещение 2 к предыдущему циклу и исправив последнюю тройку, чтобы учесть перенос в конце последовательности:

for (int i = 2; i < 10; i++ )
{
    int x = (i % 4 == 3) ? 0 : 1;
    x *= (i % 8 > 3) ? 1 : -1;   
}

Теперь объединить два в один цикл тривиально:

for (int i = 0; i < 8; i++)
{
    int y = (i % 4 == 3) ? 0 : 1;
    y *= (i > 3) ? -1 : 1;

    int x = ( (i+2) % 4 == 3) ? 0 : 1;
    x *= ( (i+2) % 8 > 3) ? 1 : -1;
}
person ose    schedule 23.11.2012
comment
upvoted: хорошо, вы создали это сейчас или уже знали? - person AlexWien; 24.11.2012
comment
Я создал его на основе вопроса OP. Раньше я не видел этой проблемы. Было бы интересно узнать, какой алгоритм вы (OP) пытаетесь создать с этой последовательностью значений. - person ose; 24.11.2012
comment
Обычно такие алгоритмы используются для так называемой свертки при обработке изображений, но мы будем ждать ответа ОП. - person AlexWien; 24.11.2012
comment
Хороший ответ. И да, это для обработки изображений, в частности для сегментации водораздела на базе графического процессора. - person user2398029; 24.11.2012

arrow_upward
1
arrow_downward

Другая удобочитаемая альтернатива - явно перечислить стороны следующим образом:

int x = -1;
int y = 1;
for (int side = 0; side < 4; side++)
{
    for (int steps = 0; steps < 2; steps++)
    {
        // use coordinates here
        printf("%d, %d\n", y, x);

        if (side == 0) { x++; }
        else if (side == 1) { y--; }
        else if (side == 2) { x--; }
        else /* if side == 3) */ { y++; }
    }
}

/*
result:
1, -1
1, 0
1, 1
0, 1
-1, 1
-1, 0
-1, -1
0, -1
*/

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

@louism: «Я могу придумать несколько уродливых способов добиться этого, например, просто поместить координаты в массив» - на самом деле, я думаю, что это лучший способ. Он четкий и читаемый (в отличие от метода арифметики модуля, описанного выше с помощью @ose) и, возможно, самый быстрый.

@louism: не могли бы вы протестировать три разных метода (поиск в массиве, перечисление сторон, арифметика модуля) и опубликовать результаты? Я был бы скорее заинтересован в этом, поскольку это то, что я бы использовал в коде, который пишу прямо сейчас.

person Alex I    schedule 24.11.2012