i am searching for an algorithm that can find the the biggest Areas in a Grid.
if i have something like this:
Red Blocks = Blocks with Collision
i have to check 28 collision Objekts.
I need an algorithm that can find this:
now i only have to check 5 Objekts.
Is there an easy c# algorithm for that?
If you wanted the absolute minimum number of rectangles, then I would suggest this answer to you. Since you want easy, though, here's my suggestion, which is 2-competitive with the minimum. First, by scanning the rows one by one, find the minimum exact cover with rectangles only one row high.
00000000
1 2
3 44 5
6 77 8
99999999
Now for each pair of adjacent rows in turn, try to merge their rectangles. Assuming that they are sorted by horizontal position, then the loop looks like a sorted merge.
00000000
--------
1 2
No merges possible.
1 2
--------
3 44 5
Merge 1, 3 and 2, 5.
1 2
1 44 2
--------
6 77 8
Merge 1, 6 and 4, 7 and 2, 8.
1 2
1 44 2
1 44 2
--------
99999999
No merges possible. The final result is the following.
00000000
1 2
1 44 2
1 44 2
99999999
here is a solution for Unity
using UnityEngine;
using System.Collections;
public class CollisionTileMerger:MonoBehaviour{
ArrayList rects = new ArrayList();
public int[,] rowCheck(int[,]array)
{
int y = array.GetLength(0);
int x = array.Length /y ;
int count = 1;
ArrayList rec = new ArrayList ();
for(int i=0; i< y ;i++){
for(int j=0; j< x ;j++)
{
if(array[i,j] == -1)
{
array[i,j] = count;
rec.Add(i);
rec.Add(j);
}
else
{
if(rec.Count>0)
{
rects.Add (rec);
rec = new ArrayList();
count++;
}
}
}
if(rec.Count>0)
{
rects.Add (rec);
rec = new ArrayList();
count++;
}
}
return array;
}
public int[,] Merger(int[,]array)
{
int y = array.GetLength(0);
int x = array.Length /y ;
int[,] coppy = (int[,])array.Clone ();
for (int i=0; i< y-1; i++)
{
int row = i;
for (int j=0; j< x; j++)
{
if(coppy[row,j]>0&&coppy[row+1,j]>0)
{
if(j==0)
{
coppy[row+1,j] = coppy[row,j];
}
else
{
if((coppy[row,j-1]>0&&coppy[row+1,j-1]>0)||(coppy[row,j-1]==0&&coppy[row+1,j-1]==0))
{
coppy[row+1,j] = coppy[row,j];
if(j==x-1)
{
//letzte Zeile
//speichern
array = (int[,])coppy.Clone ();
}
}
else
{
//zurücksetzen
coppy = (int[,])array.Clone ();
}
}
}
else if(coppy[row,j]==0&&coppy[row+1,j]==0)
{
//speichern
array = (int[,])coppy.Clone ();
}
else
{
//zurücksetzen
coppy = (int[,])array.Clone ();
}
}
}
//speichern
array = (int[,])coppy.Clone ();
return array;
}
// Use this for initialization
void Start () {
int[,] a = new int[,] {
{-1,-1,-1,-1,-1,-1,-1,-1},
{-1, 0, 0, 0, 0, 0, 0,-1},
{-1, 0, 0, -1, 0, 0, 0,-1},
{-1, 0, 0, -1, 0, 0, 0,-1},
{-1, 0, 0, -1, 0, 0, 0,-1},
{-1, 0, 0,-1,-1, 0, 0,-1},
{-1, 0, 0,-1,-1, 0, 0,-1},
{-1, 0, 0,-1,-1, 0, 0,-1},
{-1,-1,-1,-1,-1,-1,-1,-1}};
displayArray (Merger(rowCheck (a)));
}
// Update is called once per frame
void Update () {
}
public void displayArray(int[,]array)
{
int y = array.GetLength(0);
int x = array.Length /y ;
string row="";
for (int i = 0; i< y; i++)
{
for(int j = 0; j<x;j++)
{
row+= array[i,j]+" ";
}
row+= "\r\n";
}
Debug.Log(row);
/*foreach( int a in array )
{
Debug.Log( array.GetLength(0) );
Debug.Log( array.Length );
}*/
}
}