I need to make a pattern detection code,
with the following conditions:
Given an image (square matrix) A[N,N], if point P(X,Y) is the center of a star, the following condition will be satisfied:
(1) A[X][j]=255, for all 0<=j<N (The values in the Xth row are all 255)
(2) A[i][Y]=255, for all 0<=i<N (The values in the Yth column are all 255)
(3)
A[X+i][Y+i]=255, for all -N<=i<N if 0<=(X+i)<N and 0<=(Y+i)<N
A[X+i][Y-i]=255, for all -N<=i<N if 0<=(X+i)<N and 0<=(Y-i)<N
(The values of two diagonals from the centers are all 255)
I would like to know a way to effectively solve this problem quickly.
What I have tried:
The way that my program works is as follows:
1. receive the input matrix
2. create an empty copy 2d matrix
2. scan for full row values whilst scanning. -> add the value of a the detected row into the copy
3. scan for full column values-> add the value of a the detected col into the copy
4. scan for full diagonal values -> same as above
5. scan for full anti-diagonal values. -> same as above
6. iterate through the copy matrix, and the center of star will be found with a point which has been intersected 4 times.
My full code as follows:
#include<stdio.h>
int constellation[2048][2048];
int copy[2048][2048]={};
int main()
{
int a,size;
int totalrow=0, totalcol=0;
scanf("%d", &a);
scanf("%d", &size);
for(int i=0; i<a; i++){
for(int row=0; row<size; row++){
for(int col=0; col<size; col++){
scanf("%d", &constellation[row][col]);
constellation[row][col]=(constellation[row][col]== 255)?1:0;
totalrow+=constellation[row][col];
}
if(totalrow==size)
{
for(int col = 0; col<size; col++)
copy[row][col]+=1;
}
totalrow=0;
}
for(int row=0; row<size; row++){
for(int col=0; col<size; col++)
totalcol+=constellation[col][row];
if(totalcol==size)
for(int x=0; x<size; x++)
copy[x][row]+=1;
totalcol=0;
}
int totaldiagonal=0, i=0, j=0;
for(int k=0; k<=size-1; k++)
{
i=k;
j=0;
while(i>=0)
{
totaldiagonal+=constellation[i][j];
i-=1;
j+=1;
}
if(totaldiagonal==j && totaldiagonal!=0){
i=k;
j=0;
while(i>=0){
copy[i][j]+=1;
i-=1;
j+=1;
}
}
totaldiagonal=0;
}
totaldiagonal=0;
for(int k=1; k<=size-1; k++){
i=size-1;
j=k;
while(j<=size-1)
{
totaldiagonal+=constellation[i][j];
i-=1;
j+=1;
}
if(totaldiagonal== size-i-1){
i=size-1;
j=k;
while(j<=size-1){
copy[i][j]+=1;
i-=1;
j+=1;
}
}
totaldiagonal=0;
}
int max=0;
for(int j=0; j<size ;j++)
{
max=0;
int i=size-1;
int y=j;
while(y>=0)
{
max++;
totaldiagonal+=constellation[i][y];
i--;
y--;
}
if(max==totaldiagonal){
int i=size-1;
int y=j;
while(y>=0)
{
copy[i][y]+=1;
i--;
y-=1;
}
}
totaldiagonal=0;
}
for(int k=size-1; k>=0; k--)
{
max=0;
i = k-1;
j = size-1;
while(i>=0)
{
max++;
totaldiagonal+=constellation[i][j];
i--;
j--;
}
if(totaldiagonal==max)
{
i=k-1;
j=size-1;
while(i>=0)
{
copy[i][j]+=1;
i--;
j--;
}
}
totaldiagonal=0;
}
int counter=0;
for(int i=0; i<size; i++){
for(int j=0; j<size; j++){
if(copy[i][j]>=4 && i>0 && i<size-1 && j>0 && j<size-1) counter++;
}
}
printf("%d\n", counter);
}
return 0;
}