C语言三角形邻接

Question

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

有一个板，使用如下所示的 2D 矩阵表示

---

[
{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}
]

---

1. 每当看到 00 就表示 0 0 表示矩阵有一些空间

2. 相邻意味着找到另一个三角形共享相同的索引或接触另一个三角形 意味着必须有水平或垂直的，如下面的类型2所示

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

   在上面的矩阵中输入示例

即

---

Type1 : a[0][2],a[1][1],a[1][2] 类型 2:a[0][4]、a[0][5]、a[1][4] 和 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) 和 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 的 block 上对每个类型使用memcmp 表示每个 block 上有四个内存比较函数

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

Answer 1

此回复可能无法回答您的全部问题，但至少会有一些代码可供讨论。我认为很难对 block 进行 memcmp，因为三角形的 2x2 block 作为 2+2 block 数据放置在内存中的两个不同位置。 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 */

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