在 0 和 1 网格中找到所有三角形的最快方法

Question

考虑一个 5*5 大小的网格，由随机 0(o) 和 1(*) 组成。找到网格中所有三角形的最快方法是什么？ 一个四边形只能被视为两个三角形。

    /*
    ///
    singleP:   
    o o o o o
    o o * o o
    o o o o o


    triangles:
    face1_1,face1_2,face1_3; face2_1,face2_2,face2_3
    i, i+1, i+width, i+1, i+width, i+width+1
    o o o o o
    o o * * o
    o o * * o
    o o o o o

    e.g.
    5*5 grid:
    o o o o o
    * o * * o
    o o * * o
    * * o o o

    input:
    -indices: 5, 7, 8, 12,15,16
    -width：5
    -height: 5
    output:
    -isolatedPoints: 5, 15, 16
    -triFace: 7,8,12; 8,12,13
    ///
    */

一个四边形可以被视为两个三角形：

*-* 
|/| 
*-*

像这样的图案可以被视为三个三角形和一个孤立点：

   * *-*-* 
      \|/| 
       *-*

这是我当前的 c++ 代码：

 long extractTriangle(vector<int> indices, int width, int height, 
    vector<int>* singleP, vector<int>*triFace)
{
vector<int> flag(width*height, 0);
int maxInd = (width)*(height - 1) - 1;
for (int i = 0; i < indices.size(); i++)
    flag[indices[i]] = 1;


for (int i = 0; i < indices.size(); i++)
{
    int c = indices[i]; //c:center
    int down = indices[i] + width;
    if (down > maxInd)
        continue;

    int downleft = indices[i] + width - 1;
    int downright = indices[i] + width + 1;

    //left down triangle
    //o c
    //* *       
    if (flag[down] && flag[downleft])
    {
        triFace->push_back(c);
        triFace->push_back(downleft);
        triFace->push_back(down);
        flag[c] = 2;
        flag[downleft] = 2;
        flag[down] = 2;
    }
    int right = indices[i] + 1;
    if (right > maxInd)
        continue;
    //right down quad
    //c *
    //* *
    if (flag[down] && flag[right] && flag[downright])
    {
        triFace->push_back(c);
        triFace->push_back(down);
        triFace->push_back(right);
        flag[c] = 2;
        flag[down] = 2;
        flag[right] = 2;
    }
    // up right triangle
    //c *
    //* o
    else if (flag[down] && flag[right])
    {
        triFace->push_back(c);
        triFace->push_back(down);
        triFace->push_back(right);
        flag[c] = 2;
        flag[down] = 2;
        flag[right] = 2;
    }
    // down right triangle
    //c o
    //* *
    else if (flag[down] && flag[downright])
    {
        triFace->push_back(c);
        triFace->push_back(down);
        triFace->push_back(downright);
        flag[c] = 2;
        flag[down] = 2;
        flag[downright] = 2;
    }

}
for (int i = 0; i < indices.size(); i++)
    if (flag[indices[i]] == 1)
        singleP->push_back(indices[i]);
return 0;
}