Проверьте, находится ли точка внутри растрового изображения

От: Из: Общие

Вдохновленный этим вопросом, вот некоторый код C, чтобы проверить, находится ли точка «внутри» фигуры на простом черно-белом растровом изображении.

Для этого упражнения:

  • Биты набора образуют «очертания» формы (и никогда не находятся внутри).
  • Неустановленные биты могут находиться внутри или вне формы.
  • Неустановленные биты с путем к краю растрового изображения находятся «снаружи».
  • Неустановленные биты без пути к краю растрового изображения находятся «внутри».
  • Пути могут идти по диагонали между установленными битами.

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void die() { __debugbreak(); }
void die_if(bool condition) { if (condition) die(); }

struct bitmap
{
    size_t m_w;
    size_t m_h;
    bool* m_pixels;
};

struct bitmap bitmap_from_string(size_t width, size_t height, char const* str)
{
    die_if(!str);
    die_if(strlen(str) != width * height);

    bool* pixels = malloc(sizeof(bool) * width * height);
    die_if(!pixels);

    char const* src = str;
    bool* dst = pixels;

    char const set="https://codereview.stackexchange.com/questions/260494/#";
    for (size_t i = 0; i != width * height; ++i)
        *dst++ = (*src++ == set ? true : false);

    return (struct bitmap){ width, height, pixels };
}

bool bitmap_is_in_bounds(struct bitmap* bmp, size_t x, size_t y)
{
    die_if(!bmp);
    return (x < bmp->m_w) && (y < bmp->m_h);
}

bool bitmap_at(struct bitmap* bmp, size_t x, size_t y)
{
    die_if(!bmp);
    die_if(!bitmap_is_in_bounds(bmp, x, y));

    return bmp->m_pixels[y * bmp->m_w + x];
}

bool bitmap_is_at_edge(struct bitmap* bmp, size_t x, size_t y)
{
    die_if(!bmp);
    die_if(!bitmap_is_in_bounds(bmp, x, y));

    return (x == 0 || y == 0 || x == (bmp->m_w - 1) || y == (bmp->m_h - 1));
}

void bitmap_free(struct bitmap* bmp)
{
    die_if(!bmp);

    free(bmp->m_pixels);
    bmp->m_pixels = NULL;
}

/* bitmap_is_in_shape
 *    A "shape" is composed of unset bits, fully enclosed (on axes and 
 * diagonally) by set bits (so there should not exist a path of unset bits from 
 * the start point to the edge of the bitmap).
 *    Start points on set bits are not considered to be "inside" a shape.
 */
bool bitmap_is_in_shape(struct bitmap* bmp, size_t x, size_t y)
{
    die_if(!bmp);
    die_if(!bitmap_is_in_bounds(bmp, x, y));

    /* trivial rejection */
    if (bitmap_at(bmp, x, y)) return false; /* on outline */
    if (bitmap_is_at_edge(bmp, x, y)) return false; /* at edge */

    /* depth first search */
    struct coords { size_t x, y; };

    size_t stack_size = 0;
    struct coords* stack = malloc(sizeof(struct coords) * bmp->m_w * bmp->m_h); /* coords to visit next */
    die_if(!stack);

    bool* visited = calloc(bmp->m_w * bmp->m_h, sizeof(bool)); /* points added to stack - indexed the same as bitmap pixels */
    die_if(!visited);
    
    visited[y * bmp->m_w + x] = true; /* start point already visited */

    /* for each neighbour... */
#define N(c_x, c_y) 
    X(c_x, c_y, -1, -1) 
    X(c_x, c_y, -1,  0) 
    X(c_x, c_y, -1, +1) 
    X(c_x, c_y,  0, -1) 
    X(c_x, c_y,  0, +1) 
    X(c_x, c_y, +1, -1) 
    X(c_x, c_y, +1,  0) 
    X(c_x, c_y, +1, +1)

    /* check visited list and push to stack */
#define X(c_x, c_y, o_x, o_y) 
    if (!visited[(size_t)(c_y + o_y) * bmp->m_w + (size_t)(c_x + o_x)]) 
    { 
        visited[(size_t)(c_y + o_y) * bmp->m_w + (size_t)(c_x + o_x)] = true; 
        stack[stack_size++] = (struct coords){ (size_t)(c_x + o_x), (size_t)(c_y + o_y) }; 
    }

    N(x, y); /* add neighbours */

    bool result = true;

    while (stack_size != 0)
    {
        struct coords c = stack[--stack_size]; /* pop */

        if (bitmap_at(bmp, c.x, c.y)) continue; /* on outline */
        if (bitmap_is_at_edge(bmp, c.x, c.y)) { result = false; break; } /* at edge */

        N(c.x, c.y); /* add neighbours */
    }

#undef X
#undef N

    free(stack);
    free(visited);

    return result;
}

void test(bool expected, bool actual, char const* name)
{
    printf("%s: %sn", name, (expected == actual ? "pass" : "FAIL"));
}

int main()
{
    {
        struct bitmap bmp = bitmap_from_string(1, 1, "#");

        test(false, bitmap_is_in_shape(&bmp, 0, 0), "one pixel - set");
        
        bitmap_free(&bmp);
    }
    {
        struct bitmap bmp = bitmap_from_string(1, 1, " ");

        test(false, bitmap_is_in_shape(&bmp, 0, 0), "one pixel - unset");

        bitmap_free(&bmp);
    }
    {
        struct bitmap bmp = bitmap_from_string(3, 3,
            "###"
            "# #"
            "###");

        test(false, bitmap_is_in_shape(&bmp, 0, 1), "three pixel - on outline"); 
        test(true, bitmap_is_in_shape(&bmp, 1, 1), "three pixel - bounded");
        
        bitmap_free(&bmp);
    }
    {
        struct bitmap bmp = bitmap_from_string(3, 3,
            "###"
            "# #"
            "## ");

        test(false, bitmap_is_in_shape(&bmp, 0, 1), "three pixel - on outline"); 
        test(false, bitmap_is_in_shape(&bmp, 1, 1), "three pixel - middle w/ outlet");
        
        bitmap_free(&bmp);
    }
    {
        struct bitmap bmp = bitmap_from_string(8, 4,
            "########"
            "###### #"
            "#      #"
            "########");
        
        test(true, bitmap_is_in_shape(&bmp, 1, 2), "corridor - start"); 
        test(true, bitmap_is_in_shape(&bmp, 6, 1), "corridor - end");
        test(false, bitmap_is_in_shape(&bmp, 3, 1), "corridor - on outline");
        
        bitmap_free(&bmp);
    }
    {
        struct bitmap bmp = bitmap_from_string(8, 4,
            "##### ##"
            "###### #"
            "# #    #"
            "########");
        
        test(true, bitmap_is_in_shape(&bmp, 1, 2), "corridor - room");
        test(false, bitmap_is_in_shape(&bmp, 3, 2), "corridor - start");
        test(false, bitmap_is_in_shape(&bmp, 6, 1), "corridor - end");
        test(false, bitmap_is_in_shape(&bmp, 3, 1), "corridor - on outline");
        
        bitmap_free(&bmp);
    }
}

Некоторые вещи:

  • Макрос X было интересно использовать … но он выглядит немного беспорядочным. Особенно добавление смещения к координатам.

  • Мне нравится использовать проверки типа assert (die_if()) везде … но не многовато ли? Часто есть проверка в функции более высокого уровня (например, bitmap_is_in_shape() проверяет, не является ли растровое изображение нулевым), что делает все следующие проверки нижнего уровня избыточными (например, в bitmap_at() проверяет еще раз).

    Были бы две версии функций доступа нижнего уровня (например, bitmap_at() а также bitmap_at_unsafe()) быть глупым?

  • Что-то еще чего-то C-ish (особенно более современного) не хватает?

Любые другие отзывы приветствуются. 🙂

2 ответа
2

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

Ненужное преобразование из строки в растровое изображение?

Преобразование входной строки в массив bool не делает ничего полезного. Почему бы просто не позволить вашему алгоритму работать с исходной строкой? Вы можете легко это сделать, написав:

struct bitmap {
    size_t m_w;
    size_t m_h;
    char const* m_pixels;
};

bool bitmap_at(struct bitmap* bmp, size_t x, size_t y)
{
    return bmp->m_pixels[y * bmp->m_w + x] == "https://codereview.stackexchange.com/questions/260494/#";
}

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

Рассмотрите возможность предварительной обработки растрового изображения

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

Сделайте функции, которые не должны быть общедоступными static

Должны быть созданы вспомогательные функции, которые не должны вызываться из других исходных файлов. static. Это может помочь компилятору сгенерировать более оптимальный код и позволит избежать возможных ошибок связывания, если другие части программы захотят использовать то же имя функции или переменной.

Использовать assert()

Вместо того, чтобы писать свою собственную функцию, например die() а также die_if(), просто используйте стандартную функцию assert(). Отладчики должны иметь возможность останавливаться при вызове этой функции.

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

Однако не используйте assert() для вещей, которые всегда следует проверять, даже в оптимизированных сборках. Например, при проверке наличия malloc() удалось. В таких случаях я бы рекомендовал написать явную проверку и немного подумать о том, какие действия предпринять в случае неудачи. Вам действительно нужно прервать программу в таком случае, или вы можете правильно восстановить?

Бесполезный троичный

В этой строке:

*dst++ = (*src++ == set ? true : false);

Тернарное выражение совершенно бесполезно. Вы проверяете то, что уже либо true или же false, так что вы можете просто написать:

*dst++ = *src++ == set;

Избегайте макросов

X-макрос не нужен. Вы можете создать массив со всеми 8 смещениями и просто использовать обычный for-loop для вызова кода, который нужно повторить. Например:

static const struct {
    int x;
    int y;
} offsets[8] = {
    {-1, -1},
    {-1, 0},
    ...
};

for (int i = 0; i < 8; i++) {
    int x = c_x + offsets[i].x;
    int y = c_y + offsets[i].y;
    size_t idx = y * bmp->m_w + x;

    if (!visited[idx]) {
        visited[idx] = true;
        stack[stack_size++] = (struct coords){x, y};
    }
}

Рассмотрите возможность использования рекурсии

Каждый раз, когда вы создаете стек вручную, спрашивайте себя, нужно ли вам это делать. Когда вы запускаете программу, ваш компьютер уже управляет стеком, так что, может быть, вы можете просто использовать это? Отколоть часть bitmap_is_in_shape() которые рекурсивно вызывают себя:

static bool recurse(struct bitmap* bmp, bool* visited, size_t x, size_t y)
{
    if (bitmap_is_at_edge(bmp, x, y))
        return false;

    size_t idx = bmp->m_w * y + x;

    if (visited[idx] || bitmap_at(bmp, x, y))
        return true;
    else
        visited[idx] = true;

    static const struct {...} offsets[8] = {...};

    for (int i = 0; i < 8; i++) {
         // Recursively check neighbors, but exit as soon as we have reached the edge.
         if (!recurse(bmp, visited, x + offsets[i].x, y + offsets[i].y))
             return false;
    }

    return true;
}

bool bitmap_is_in_shape(struct bitmap* bmp, size_t x, size_t y)
{
    ...
    bool* visited = calloc(bmp->m_w * bmp->m_h, sizeof(bool));
    bool result = recurse(bmp, visited, x, y);
    free(visited);
    return result;
}

Недостатком является то, что вы можете превысить объем доступного пространства стека, с другой стороны, он, вероятно, будет использовать гораздо меньше памяти, чем при резервировании массива m_w * m_h элементы.

  • Хороший обзор. Все же нашел еще и немного другой подход к соседям.

    — Дедупликатор

  • 1

    Спасибо за обзор. У меня сложилось впечатление, что хорошо иметь проверки с одинаковым поведением как в отладочной, так и в выпускной сборках. (В противном случае я не пойму таких проблем, как неудачное выделение памяти в сборках выпуска. Возможно, нет большой разницы между die() и просто рушится, но гораздо легче рассуждать о том, что происходит).

    — user673679

  • @ user673679 Вы правы, не стоит использовать assert() в тех случаях. Я обновил ответ.

    — Г. Сон

@ G.Sliepen уже дал немало моментов для рассмотрения.
Тем не менее, есть еще кое-что, некоторые моменты нужно уточнить, а некоторые предлагают другое интересное решение:

  1. По его словам, ваш die() эквивалентно assert(0), а также die_if(!expr) эквивалентно assert(expr) пока не NDEBUG определено.

    Диагностика, вероятно, не так хороша, и код не удаляется в режиме выпуска.

    Хотя большинство проверок следует заменить на assert(), некоторые из них не указывают на ошибку программирования и, следовательно, всегда должны убивать программу, но никогда не взламывать отладчик. Чего я ожидал die() сделать, указав соответствующее сообщение об ошибке.

  2. Избегать sizeof(TYPE). Практически всегда можно использовать sizeof *pointer вместо этого, что позволяет избежать повторения информации и, возможно, ошибиться. Или не менять его сразу повсюду, если в этом возникнет необходимость.

  3. Решите, хотите ли вы сдать struct bitmap по стоимости или по ссылке. В настоящее время нет никаких преимуществ для передачи его по ссылке, хотя иногда вы все же делаете это.

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

  5. Если вы поместите начальную точку в открытый стек, вам не нужно отмечать ее соседей. Устранен один макрос. Простота!

  6. Управлять открытым стеком было бы проще, если бы вы использовали два указателя (стек и верх) вместо (стек и размер).

  7. Простой цикл намного лучше, чем использование макросов для многократного повторения одного и того же кода.

    Другой ответ имеет один вариант с использованием таблицы поиска. Учитывая, что необходимо только 8 очень коротких целых чисел (каждое из которых соответствует полубайту), одно (или два) 64-битных значения и некоторый сдвиг битов приводят к другому довольно производительному решению.

  8. К сожалению, многие из ваших комментариев очевидны.

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

  9. Хотя я понимаю, что в C ++, когда функции-члены становятся слишком большими, префикс или суффикс для переменных-членов могут, по крайней мере, облегчить путаницу, импорт этой бородавки в C, который имеет только бесплатные функции, является ненужным беспорядком, вытесняющим более полезное именование. Даже в C ++ правильным средством является извлечение функций и другие рефакторинги, ведущие к меньшим функциям.

Ниже только модифицированная основная функция, предполагая, что все остальные принимают struct bitmap по стоимости. Если вы хотите последовать предложению предварительной обработки и / или напрямую работать с источником, не стесняйтесь начинать отсюда.

void die(const char* p) {
    if (p) fprintf(stderr, "Fatal Error: %sn", p)
    exit(1);
}
bool bitmap_is_in_shape(struct bitmap bmp, size_t x, size_t y) {
    assert(bitmap_is_in_bounds(bmp, x, y));

    if (bitmap_at(bmp, x, y) || bitmap_is_at_edge(bmp, x, y)) return false;
    size_t* const stack = malloc(sizeof *stack * bmp.m_h * bmp.m_w);
    stack || die("Failed to allocate memory.");
    size_t* top = stack;

    bool *visited = calloc(bmp.m_h * bmp.m_w, sizeof *visited);
    visited || die("Failed to allocate memory.");

    *top++ = y * bmp.m_w + x;
    visited[y * bmp.m_w + x] = true;

    bool result = true;

    while (stack != top) {
        size_t linear = *--top;
        if (bitmap_is_at_edge(bmp, linear % bmp.m_w, linear / bmp.m_w)) {
            result = false;
            break;
        }
#if 1
        for (uint64_t which = 0x01011e021e0101ff; which; which >>= 8) {
            linear += (signed char)(which & 0xf0) / 16;
            linear += (signed char)((which << 4) & 0xf0) / 16 * bmp.m_w;
#else
        for (uint64_t x = 0x00000100010000ff, y = 0x0101fe02fe0101ff; y; x >>= 8, y >>= 8) {
            linear += (signed char)x;
            linear += (signed char)y * bmp.m_w;
#endif
            if (!visited[linear]) {
                visited[linear] = true;
                *top++ = linear;
            }
        }
    }

    free(stack);
    free(visited);

    return result;
}

  • Спасибо за обзор. __debugbreak() действительно убивает программу, если она не работает под отладчиком.

    — user673679

  • Re. комментарии … да, я, как правило, нахожу C достаточно неудобным, чтобы резюмировать на английском языке, что делает каждая часть кода. Но, может быть, это очевидно для того, кто разбирается в C.: D

    — user673679

  • 1

    @ user673679 Я думаю, что можно добавить комментарий, описывающий, что делает более крупный раздел кода, но комментарии, которые просто описывают, что делает однострочный, например c = stack[--stack_size]; /* pop */, часто бывают лишними.

    — Г. Сон

  • @ user673679 По-прежнему убивает его неправильным образом, так как подразумевает обнаруженную программную ошибку, а не несколько ожидаемую нехватку ресурсов.

    — Дедупликатор

Похожие записи:

  1. Оператор Собеля — внутренняя реализация SIMD x86
  2. C ++ 20: я — матрица, вещание, np.dot () и np.matmul ()
  3. Программа расчета небоскребов для размера NxN, версия 3 (с использованием битовых масок)
  4. повторная реализация std :: vector
  5. Реализация простого общего указателя C ++

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *