在amxn矩阵中绘制矩形,圆形或任意多边形

Question

我想模拟二维物体周围的流动.因此我在C中编写了一个程序,它使用Navier-Stokes方程来描述流体的运动.现在我想到的不仅仅是在模拟域中放置一个矩形.要绘制这样一个矩形,我只需要执行以下操作:

for(int i=start_x; i<end_x; i++)
    for(int j=start_y; j<end_y; j++)
        M[i][j] = 1; // barrier cell = 1

这样做我得到一个漂亮的矩形.没有惊喜.但是,如果我想模拟圆形,十字形,三角形,翼形轮廓或任何其他任意多边形的流动,那会是什么方法呢？有没有一种简单的方法可以在M大小矩阵中绘制这样的2D对象m x n？

---

我刚刚找到了一种简单的方法来绘制我想要的几乎任何形状.@Nominal Animal的答案激励我找到这个解决方案.我只是使用一个.png文件并.pgm使用该命令将其转换为文件convert picture.png picture.pgm(使用Linux).在我的代码中,我只需要更多行:

FILE *pgmFile;
pgmFile = fopen("picture.pgm", "r");
for(int i=0; i<1024; i++){
    for(int j=0; j<1024; j++){
        int d = fgetc(pgmFile);
        if(d < 255){
            M[i][j] = 1; // barrier cell = 1
        }
    }
}
fclose(pgmFile);

这里我使用1024 x 1024像素的图片.如果像素的值小于255(不是白色),则将像素设置M[i][j]为1.这是我使用Stack Overflow标识生成的结果(通量来自左侧):

速度图,Re = 20000(雷诺数)

Answer 1

可能有更有效的方法来做到这一点,但这是一种方式.

使用您想要绘制的多边形的等式在C中定义一个函数.定义该函数使得它接受点坐标,并返回该点是否位于多边形内部.例如,对于圆,该函数可以接受点(x,y),中心(x0,y0)和半径r,然后返回(x-x0)^2 + (y-y0)^2 - r^2 < 0.让这个功能成为f.

如果可能,确定多边形的边界框矩形,否则,可以确定哪个完全包围多边形的最小矩形.这将为您提供矩形矩阵.

现在,迭代矩形矩阵中的点.对于每个点,调用先前定义的函数.1如果坐标a 返回True,则返回坐标a ,0如果返回False.这将构造多边形.

假设您想要绘制一个中心(x0,y0),半径的圆r,那么您可以使用:

int f(int i, int j, int x0, int y0, int r)
{
    return pow((i-x0),2) + pow((j-y0),2) - pow(r,2) < 0;        
}


for(int i = x0-r; i <= x0 + r; i++)
{
    for(int j = y0-r; j <= y0 + r; j++)
    {
        if(f(i,j,x0,y0,r))
        {
            M[i][j] = 1;
        }
        else
        {
            M[i][j] = 0;
        }
    }
}

Answer 2

当前的问题归结为光栅化（维基百科）；特别是扫描线转换（siggraph.org）。

siggraph.org 文章包含有关如何绘制直线、圆和椭圆以及凸多边形和凹多边形的详细说明。

然而，这是一个已经被解决过很多次的问题。虽然 OP 当然可以实现必要的图元（直线、椭圆、三角形、多边形），但还有一种更简单的方法。

我建议 OP为 P5（二进制灰度像素图）格式实现一个简单的NetPBM 格式阅读器，并使用netpbm 工具（来自netpbmLinux 发行版和 BSD 变体中的包；其他系统请参阅Netpbm 主页）将任何图像转换为简单的格式读取 PGM (P5) 文件，其中每个像素对应于 OP 矩阵中的一个元素。

这样，人们可以使用 Inkscape 等使用矢量图形绘制系统，将其光栅化为任意大小（例如导出为 PNG 图像），使用 netpbm 工具转换为 PGM (P5) 格式（或 ，pngtopnm后跟anytopnm）ppmtopgm，然后读取文件。事实上，在 POSIX.1 系统中（除了 Windows 之外几乎所有地方），都可以使用popen("anytopnm path-to-file | pnmtopng", "r")（或者稍微复杂一点的双fork()管道解决方案）来读取 PGM (P5) 格式的任何像素图图像。

或者，可以考虑使用 ImageMagick 库来读取任何格式的像素图图像（JPEG、GIF、PNG 等）。

就个人而言，作为开发人员和用户（尽管请注意，我明确是非 Windows 用户；十多年来没有使用过 Microsoft 产品），我更喜欢 netpbm 方法。例如，该程序mysim将使用/usr/lib/mysim/read-imageshell 脚本（或 Windows 中的程序，可能是 mac；或者，如果已定义，则由环境变量定义的脚本或程序MYSIM_READ_IMAGE）来读取命令行上指定的图像，并以 PGM 形式发出它（ P5) 格式。主程序将简单地读取助手的输出。

这样，如果用户需要对输入文件进行特殊处理，他们可以轻松地复制现有脚本，修改它以满足自己的需要，然后安装在自己的主目录下的某个位置（或全局安装，甚至替换现有脚本，如果它无论如何，所有用户都会使用）。

程序可以使用 或popen()+fork()来execv()执行脚本，以输入文件名作为命令行参数，并读取父进程中的输出以构造初始矩阵。

出于多种原因，我更喜欢这种方法而不是图像库方法。首先，它更加模块化，允许用户覆盖图像读取机制并在必要时对其进行操作。（根据我的经验，此类覆盖并不经常需要，但当它们需要时，它们非常有用，并且总体上绝对值得。）其次，图像处理（在许多情况下相当复杂）是在单独的过程中完成的，这意味着当图像被完全读取时，读取和解密图像所需的所有内存（用于代码和数据）都将被释放。第三，这种方法遵循Unix 哲学和KISS 原则，它们在指导健壮且有用的工具的开发方面有着良好的记录。

下面是一个示例程序，它从标准输入读取二进制 PBM、PGM 或 PPM 文件（分别为 NetPBM P4、P5 和 P6 格式）到矩阵结构中，用 或 填充矩阵（基于0颜色1或灰度）从图像中读取的值）。为了便于测试，程序将矩阵以 PGM (P5) 格式输出到标准输出。

该程序遵循 NetPBM 手册页中的格式规范（分别针对PBM (P4)、PGM (P5)和PPM (P6)格式）。关于NetPBM 格式的维基百科文章当前显示了带有无效注释的示例（在标题和数据之间）。NetPBM 手册页指出，最终标头值后跟一个空白字符，而不是注释。（如果最终头值后面可能有注释，则无法知道#二进制数据中的a（二进制0x23 = 35）是否开始注释，或者是实际数据值。）

这明确属于公共领域，或者同等地，根据知识共享 CC0许可证获得许可。这意味着您可以完全自由地以任何方式、任何地方使用下面的代码，即使是在商业项目中，但不能保证：如果它损坏了，或损坏了某些东西，或使您的头发着火，您可以保留所有内容碎片，只能怪自己。

也就是说，它只是经过了轻微的测试，所以如果您发现其中有错误，请在评论中告诉我，以便我可以验证和修复。

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

/* Matrix to read data into */
typedef struct {
    int            rows;
    int            cols;
    long           rowstride;
    long           colstride;
    unsigned char *data;        /* data[row*rowstride + col*colstride] */
} matrix;
#define MATRIX_INIT { 0, 0, 0, 0, NULL }

/* NetPBM (binary) formats supported */
#define PNM_PBM  4
#define PNM_PGM  5
#define PNM_PPM  6

/* Error codes from pnm_*() functions */
#define PNM_EOF       -1
#define PNM_INVALID   -2
#define PNM_OVERFLOW  -3


/* This helper function returns the NetPBM file identifier;
   PNM_PBM, PNM_PGM, PNM_PPM, or PNM_INVALID if unsupported.
*/
static int pnm_type(FILE *in)
{
    /* First character must be 'P'. */
    if (getc(in) != 'P')
        return PNM_INVALID;

    /* Second character determines the type. */
    switch (getc(in)) {
    case '4': return PNM_PBM;
    case '5': return PNM_PGM;
    case '6': return PNM_PPM;
    default:  return PNM_INVALID;
    }
}

/* This helper function reads a number from a NetPBM header,
   correctly handling comments. Since all numbers in NetPBM
   headers are nonnegative, this function returns negative
   when an error occurs:
    -1: Premature end of input
    -2: Value is too large (int overflow)
    -3: Invalid input (not a NetPBM format file)
*/
static int pnm_value(FILE *in)
{
    int  c;

    /* Skip leading whitespace and comments. */
    c = getc(in);
    while (c == '\t' || c == '\n' || c == '\v' ||
           c == '\f' || c == '\r' || c == ' ' || c == '#')
        if (c == '#') {
            while (c != EOF && c != '\n')
                c = getc(in);
        } else
            c = getc(in);

    if (c == EOF)
        return PNM_EOF;

    if (c >= '0' && c <= '9') {
        int value = 0;

        while (c >= '0' && c <= '9') {
            const int oldvalue = value;
            value = 10*value + (c - '0');
            if ((int)(value / 10) != oldvalue)
                return PNM_OVERFLOW;
            c = getc(in);
        }

        /* Do not consume the separator. */
        if (c != EOF)
            ungetc(c, in);

        /* Success. */
        return value;
    }

    return PNM_INVALID;
}

/* This helper function consumes the single newline
   following the final value in the header.
   Returns 0 if success, PNM_INVALID otherwise.
*/
static int pnm_newline(FILE *in)
{
    int c;

    c = getc(in);
    if (c == '\r')
        c = getc(in);
    if (c == '\n')
        return 0;

    return PNM_INVALID;
}

static void pnm_matrix_free(matrix *to)
{
    if (to) {
        free(to->data);
        to->rows = 0;
        to->cols = 0;
        to->rowstride = 0;
        to->colstride = 0;
        to->data = NULL;
    }
}

static int pnm_matrix_init(matrix *to, int rows, int cols)
{
    size_t  cells, bytes;

    if (rows < 1 || cols < 1)
        return PNM_INVALID;

    cells = (size_t)rows * (size_t)cols;
    if ((size_t)(cells / (size_t)rows) != (size_t)cols ||
        (size_t)(cells / (size_t)cols) != (size_t)rows)
        return PNM_OVERFLOW;

    bytes = cells * sizeof to->data[0];
    if ((size_t)(bytes / sizeof to->data[0]) != cells)
        return PNM_OVERFLOW;

    to->data = malloc(bytes);
    if (!to->data)
        return PNM_OVERFLOW;

    to->rows = rows;
    to->cols = cols;

    /* Default to a row-major data order. */
    to->colstride = 1L;
    to->rowstride = cols;

    return 0;
}

static int pnm_p4_matrix(FILE *in, matrix *to)
{
    int rows, cols, result, r, c, byte = 0;

    cols = pnm_value(in);
    if (cols < 1)
        return PNM_INVALID;

    rows = pnm_value(in);
    if (rows < 1)
        return PNM_INVALID;

    if (pnm_newline(in))
        return PNM_INVALID;

    result = pnm_matrix_init(to, rows, cols);
    if (result)
        return result;

    for (r = 0; r < rows; r++) {
        const long ri = r * to->rowstride;
        for (c = 0; c < cols; c++) {
            const long i = ri + c * to->colstride;

            switch (c & 7) {
            case 0:
                byte = getc(in);
                if (byte == EOF) {
                    pnm_matrix_free(to);
                    return PNM_INVALID;
                }
                to->data[i] = !!(byte & 128);
                break;
            case 1:
                to->data[i] = !!(byte & 64);
                break;
            case 2:
                to->data[i] = !!(byte & 32);
                break;
            case 3:
                to->data[i] = !!(byte & 16);
                break;
            case 4:
                to->data[i] = !!(byte & 8);
                break;
            case 5:
                to->data[i] = !!(byte & 4);
                break;
            case 6:
                to->data[i] = !!(byte & 2);
                break;
            case 7:
                to->data[i] = !!(byte & 1);
                break;
            }
        }
    }

    return 0;
}

static int pnm_p5_matrix(FILE *in, matrix *to)
{
    int rows, cols, max, r, c, result;

    cols = pnm_value(in);
    if (cols < 1)
        return PNM_INVALID;

    rows = pnm_value(in);
    if (rows < 1)
        return PNM_INVALID;

    max = pnm_value(in);
    if (max < 1 || max > 65535)
        return PNM_INVALID;

    if (pnm_newline(in))
        return PNM_INVALID;

    result = pnm_matrix_init(to, rows, cols);
    if (result)
        return result; 

    if (max < 256) {
        const int limit = (max + 1) / 2;
        int val;
        for (r = 0; r < rows; r++) {
            const long ri = r * to->rowstride;
            for (c = 0; c < cols; c++) {
                const long i = ri + c * to->colstride;

                val = getc(in);
                if (val == EOF) {
                    pnm_matrix_free(to);
                    return PNM_INVALID;
                }

                to->data[i] = (val < limit);
            }
        }
    } else {
        const int limit = (max + 1) / 2;
        int val, low;
        for (r = 0; r < rows; r++) {
            const long ri = r * to->rowstride;
            for (c = 0; c < cols; c++) {
                const long i = ri + c * to->colstride;

                val = getc(in);
                low = getc(in);
                if (val == EOF || low == EOF) {
                    pnm_matrix_free(to);
                    return PNM_INVALID;
                }
                val = 256*val + low;

                to->data[i] = (val < limit);
            }
        }
    }

    return 0;
}

static int pnm_p6_matrix(FILE *in, matrix *to)
{
    int rows, cols, max, r, c, result;

    cols = pnm_value(in);
    if (cols < 1)
        return PNM_INVALID;

    rows = pnm_value(in);
    if (rows < 1)
        return PNM_INVALID;

    max = pnm_value(in);
    if (max < 1 || max > 65535)
        return PNM_INVALID;

    if (pnm_newline(in))
        return PNM_INVALID;

    result = pnm_matrix_init(to, rows, cols);
    if (result)
        return result;

    if (max < 256) {
        const int limit = 128 * max;
        int       val, rval, gval, bval;

        for (r = 0; r < rows; r++) {
            const long ri = r * to->rowstride;
            for (c = 0; c < cols; c++) {
                const long i = ri + c * to->colstride;

                rval = getc(in);
                gval = getc(in);
                bval = getc(in);
                if (rval == EOF || gval == EOF || bval == EOF) {
                    pnm_matrix_free(to);
                    return PNM_INVALID;
                }

                val =  54 * rval
                    + 183 * gval
                    +  19 * bval;

                to->data[i] = (val < limit);
            }
        }
    } else {
        const int limit = 128 * max;
        int       val, rhi, rlo, ghi, glo, bhi, blo;

        for (r = 0; r < rows; r++) {
            const long ri = r * to->rowstride;
            for (c = 0; c < cols; c++) {
                const long i = ri + c * to->colstride;

                rhi = getc(in);
                rlo = getc(in);
                ghi = getc(in);
                glo = getc(in);
                bhi = getc(in);
                blo = getc(in);
                if (rhi == EOF || rlo == EOF ||
                    ghi == EOF || glo == EOF ||
                    bhi == EOF || blo == EOF) {
                    pnm_matrix_free(to);
                    return PNM_INVALID;
                }

                val =  54 * (rhi*256 + rlo)
                    + 183 * (ghi*256 + glo)
                    +  19 * (bhi*256 + blo);

                to->data[i] = (val < limit);
            }
        }
    }

    return 0;
}

int pnm_matrix(FILE *in, matrix *to)
{
    /* If the matrix is specified, initialize it. */
    if (to) {
        to->rows = 0L;
        to->cols = 0L;
        to->rowstride = 0L;
        to->colstride = 0L;
        to->data = NULL;
    }

    /* Sanity checks on parameters. */
    if (!to || !in || ferror(in))
        return PNM_INVALID;

    switch (pnm_type(in)) {
    case PNM_PBM: return pnm_p4_matrix(in, to);
    case PNM_PGM: return pnm_p5_matrix(in, to);
    case PNM_PPM: return pnm_p6_matrix(in, to);
    default:      return PNM_INVALID;
    }
}

int main(void)
{
    int r, c;
    matrix m = MATRIX_INIT;

    if (pnm_matrix(stdin, &m)) {
        fprintf(stderr, "Cannot parse standard input.\n");
        return EXIT_FAILURE;
    }

    fprintf(stderr, "Read %d rows, %d columns, from standard input.\n", m.rows, m.cols);

    /* For ease of debugging, we output the matrix as a PGM file. */
    printf("P5\n%d %d\n255\n", m.cols, m.rows);
    for (r = 0; r < m.rows; r++)
        for (c = 0; c < m.cols; c++)
            if (m.data[r * m.rowstride + c * m.colstride] == 0)
                putchar(255); /* White */
            else
                putchar(0);   /* Black */

    return EXIT_SUCCESS;
}

请注意，我没有验证位/灰度/颜色转换是否是OP打算如何使用矩阵的正确方法。（也就是说，无论“白色”还是浅色都应该在矩阵中产生 a0或 a 。）如果您需要将其反转以用于 PBM 图像，请改用。如果您需要将其反转为 PGM 或 PPM 图像，请改用。1!(byte & NUMBER)(val >= limit)

该程序应该是有效的 C（甚至低至 C89），并且可以在任何体系结构上编译。b在像 Windows 这样的愚蠢架构上，您可能必须以“二进制模式”（包含在标志中）打开/重新打开标准输入fopen()，否则它们可能会破坏输入。

在 Linux 上，我编译并测试了程序 ( example.c)

gcc -Wall -O2 example.c -o example
./example < inputfile.pbm > result-pbm.pgm
./example < inputfile.pgm > result-pgm.pgm
./example < inputfile.ppm > result-ppm.pgm