C语言三角形邻接

Question

抱歉，上次问的问题不清楚，现在重新措辞

有一块板使用二维矩阵表示，如下所示

[
{0 0 1 0 1 1 0 1 0 0 1 1},
{0 1 1 0 1 0 0 1 1 0 0 1},
{0 0 0 0 0 0 0 1 0 0 0 0}
]

只要看到 00 就表示 0 0 在表示矩阵
相邻意味着找到另一个共享相同索引或接触另一个三角形的三角形表示必须有水平或垂直的，如下面的类型 2

如果用1表示的矩阵中的3个点连成一个直角三角形，直角三角形有四种

在上面的矩阵中输入示例

即

Type1 : a[0][2],a[1][1],a[1][2] Type2 : a[0][4],a[0][5],a[1][4] and a[1][7],a[1][8],a[2][7] Type3 : a[0][7],a[1][7],a[1][8] Type4 : a[0][10],a[0][11],a[1][11]

当连接所有三个顶点时得到四种类型中任何一种的直角三角形在上面的示例中，有两个直角三角形彼此相邻（表示两个连续的水平或垂直三角形）即

a(0)(7), a(1)(7),a(1)(8)and a[1][7],a[1][8],a(2)(7)

需要有效的方法来遍历矩阵以找到 Board 上使用 N*N 矩阵表示的每个三角形图案的计数有一些条件 1：如果任何三角形与任何类型的两个三角形相邻，则不会被计算在内 2: 一个cell被一个三角形类型的任意三角形share common cell使用则不计入

我对图形的了解不多，但我尝试了这个逻辑 1：为每个三角形类型定义矩阵2*2 2：以2*2矩阵为粒度确定棋盘的大小，即10个2*2的矩阵做棋盘 3 在每 2*2 块上对每种类型使用 memcmp 意味着每个块上有四个内存比较函数

但这行不通，因为三角形永远无法对齐以阻止它可以从棋盘的奇数索引处开始做了一些研究后，这可以使用图形来实现，但仍然不知道如何在图形上搜索模式请提供一些输入和一些学习练习，以便更详细地学习此类问题

Answer 1

这个回复可能无法回答你的全部问题，但至少会有一些代码可以讨论。我认为很难对块进行 memcmp，因为三角形的 2x2 块作为 2+2 块数据放置在内存中的两个不同位置。 Memcmp 假定您的所有数据都在连续内存中。

下面的代码有函数find_triangles，我们可以继续讨论和改进。它将每个三角形定义为一个点，该点是两条线的交点。要成为三角形，交点必须为 1。一旦我们轻松找到可能的交点，下一个问题就是该点是否真的是任何三角形的真正交点以及什么类型的三角形。我在结果中将类型存储为位域。

main 函数可能不那么容易阅读，但它只是为了简短并打印结果作为概念证明。

    #include <stdio.h>

    #define TYPE1 0x01
    #define TYPE2 0x02
    #define TYPE3 0x04
    #define TYPE4 0x08

    void find_triangles(int h, int w, int data[h][w], int res[h][w])
    {
       int x, y;

       for(y=0; y<h; y++)
          for(x=0; x<w; x++)
             if(data[y][x])
                res[y][x] =
                   TYPE1*(y && data[y-1][x]) * (x && data[y][x-1])|
                   TYPE2*((y<(h-1)) && data[y+1][x]) * ((x<(w-1)) && data[y][x+1])|
                   TYPE3*(y && data[y-1][x]) * ((x<(w-1)) && data[y][x+1])|
                   TYPE4*((y<(h-1)) && data[y+1][x]) * (x && data[y][x-1]);
                else
                   res[y][x] = 0; 
    }

    int main(int argc, char **argv)
    {
       #define DATA_WIDTH 12
       #define DATA_HEIGHT 3
       int data[DATA_HEIGHT][DATA_WIDTH]={
          {0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1},
          {0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1},
          {0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0}};
       int result[DATA_HEIGHT][DATA_WIDTH];
       int x, y, type;

       find_triangles(DATA_HEIGHT, DATA_WIDTH, data, result);

       for(type=0; type<4; type++)
       {
          printf("Type%d : ", type+1);
          for(y=0; y<DATA_HEIGHT; y++)
             for(x=0; x<DATA_WIDTH; x++)
                if(result[y][x] & (1<<type))
                   printf("a[%d][%d],a[%d][%d],a[%d][%d] ",
                      y,x,
                      (type & 0x1) ? y+1 : y-1, x,
                      y, ((type >> 1)==(type & 0x1)) ? x-1 : x+1);
          printf("\n");
       }
       return 0;
    } /* main */

我不认为我完全理解哪些相邻三角形不应该被计算在内，但我希望这个代码示例可以作为一个起点。

C语言三角形邻接

C programming language triangle adjacency

c

algorithm

graph-algorithm

在上面的矩阵中输入示例