CODEWITHSUNDEEP
calgorithmgraph-algorithm
anshkun
anshkun

Reputation: 115

C programming language triangle adjacency

Sorry last asked question is not clear Now rephrasing it

There is board which is represented using 2D matrix like below 

[
{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. Whenever 00 is seen it means 0 0 there is some space in representing matrix

  2. Adjacent means finding another triangle sharing the same indices or touching the other triangle Means there must be horizontal or vertical one as shown in type 2 below

    If joining 3 points in matrix represented using 1 it will make one right angle triangle, there are four types of right angled triangle

    types example in above matrix

i.e

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]

When join all the three vertexes gives right angled triangle of any of the four type In example above there is two right angled triangle are adjacent to each other ( means two consecutive ones horizontally or Vertically) i.e

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

Need efficient way to traverse the matrix to find count of each triangle pattern on Board which is represented using N*N matrix There is some conditions 1: if any triangle is adjacent to two triangles of any type then it will not be counted 2: one cell is used by one triangle type of any triangle share common cell then it will not be counted

I don't have much knowledge about graphs but I tried this logic using 1: define matrix 2*2 for each triangle type 2: determine size of board in granularity of 2*2 matrix, means ten matrix of 2*2 makes board 3 use memcmp for each type on every 2*2 of block means four memory compare function on each block

But this will not work because triangle can never be aligned to block it can start at odd indices of board After doing some study this can be implemented using graphs, but still don't know how to search a pattern on graph Please provide some inputs and some study exercises to learn in more detail for such problems

Upvotes: 3

Views: 391

Answers (1)

Henrik Carlqvist
Henrik Carlqvist

Reputation: 1158

This reply might not answer your entire question, but at least there will be some code to discuss. I think it will be hard to do memcmp of blocks as the 2x2 blocks of a triangle are placed as 2+2 pieces of data in memory at two different locations. Memcmp assumes all your data is in a continous memory.

The code below has the function find_triangles which we could continue to discuss and improve. It defines every triangle as a single point which is the intersection point of the two lines. To be a triangle, the intersection point has to be 1. Once we easily have found possible intersection points the next question is if the point is really a true intersection point of any triangle(s) and what types of triangles. I store types as bitfields in the result.

The main function might not be so easy to read, but it is only there to be short and print the result as proof of concept.

    #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 */

I don't think that I fully understood which adjacent triangles should not be counted, but I hope this code example will be a place to start.

Upvotes: 1

Related Questions