http://en.wikipedia.org/wiki/Connected-component_labeling
import java.util.ArrayList;
import java.util.Enumeration;
import java.util.Hashtable;
public class ConnectedComponent {
/**
* @param args
*/
public static void main(String[] args) {
//int [][]data={{1,0,1},{0,0,1},{1,0,1}};
/*00100011010000101011111
10100011110010001110000
10001011000000010011000*/
int [][]data={{0,0,1,0,0,0,1,1,0,1,0,0,0,0,1,0,1,0,1,1,1,1,1},{1,0,1,0,0,0,1,1,1,1,0,0,1,0,0,0,1,1,1,0,0,0,0},{1,0,0,0,1,0,1,1,0,0,0,0,0,0,0,1,0,0,1,1,0,0,0}};
//get the lable matrix
int [][] result = TwoPassAlgorithm(data);
//find the size of available lands
int rowLength = result.length;
Hashtable<Integer, Integer> sizeCalculator = new Hashtable<Integer, Integer>();
for(int i=0; i<rowLength; i++){
int []resultRow = result[i];
int columnLength = resultRow.length;
for(int j=0; j<columnLength; j++){
int key = result[i][j];
if(key==0)
continue;
if(sizeCalculator.containsKey(key)){
Integer value = sizeCalculator.remove(key);
value = value + 1;
sizeCalculator.put(key, value);
}else{
sizeCalculator.put(key, 1);
}
}
}
//find the big land
Enumeration<Integer> Lands = sizeCalculator.elements();
int max = 0;
while(Lands.hasMoreElements()){
int landSize = Lands.nextElement();
if(landSize > max)
max = landSize;
}
System.out.println(max);
}
public static int[][]TwoPassAlgorithm(int[][]data){
int rowLength = data.length;
int columnLength = data[0].length;
int [][]Labels = new int[rowLength][columnLength];
//int result[rowLength][columnLength];//throws token error.
//first pass
int nextLabel = 2;
Hashtable<Integer, ArrayList<Integer>> Linker = new Hashtable<Integer, ArrayList<Integer>>();
for(int i=0;i<rowLength;i++){
for(int j=0;j<columnLength;j++){
if(data[i][j]!=0){
int []neighbourLabels = getNeighbourLabels(Labels, i, j);
if(neighbourLabels == null){
ArrayList<Integer> value = new ArrayList<Integer>();
value.add(nextLabel);
Linker.put(nextLabel,value);
Labels[i][j]=nextLabel;
nextLabel++;
}else{
Labels[i][j] = minimum(neighbourLabels);
for(int k=0; k<neighbourLabels.length; k++){
Linker = union(Linker,neighbourLabels[k],neighbourLabels);
}
}
}else{
Labels[i][j]=0;
}
}
}
//Second pass
for(int i=0;i<rowLength;i++){
for(int j=0;j<columnLength;j++){
if(Labels[i][j]!=0){
Labels[i][j] = minimum(Linker.get(Labels[i][j]));
}
}
}
return Labels;
}
public static int[] getNeighbourLabels(int[][]Labels, int row,int column){
ArrayList<Integer> neighbourLabels = new ArrayList<Integer>();
int columnLimit = Labels[0].length;
column--;
if(column>=0 && Labels[row][column]!=0)
neighbourLabels.add(Labels[row][column]);
row--;
if(column>=0 && row>=0 && Labels[row][column]!=0)
neighbourLabels.add(Labels[row][column]);
column++;
if(column>=0 && column<columnLimit && row>=0 && Labels[row][column]!=0)
neighbourLabels.add(Labels[row][column]);
column++;
if(column>=0 && column<columnLimit && row>=0 && Labels[row][column]!=0)
neighbourLabels.add(Labels[row][column]);
int neighbourLabelsSize = neighbourLabels.size();
if(neighbourLabelsSize != 0){
int [] neighbourLabelsArray = new int[neighbourLabelsSize];
for(int i=0;i<neighbourLabelsSize; i++){
neighbourLabelsArray[i] = neighbourLabels.get(i);
}
return neighbourLabelsArray;
}
return null;
}
public static int minimum(int[]labels){
int minimumLabel = labels[0];
for(int i=1;i<labels.length;i++){
if(minimumLabel>labels[i])
minimumLabel = labels[i];
}
return minimumLabel;
}
public static int minimum(ArrayList<Integer>labels){
int minimumLabel = labels.get(0);
for(int i=1;i<labels.size();i++){
if(minimumLabel>labels.get(i))
minimumLabel = labels.get(i);
}
return minimumLabel;
}
public static Hashtable<Integer, ArrayList<Integer>> union(Hashtable<Integer, ArrayList<Integer>> Linker, int key, int[] unionValues){
for(int i=0;i<unionValues.length;i++){
if(!Linker.get(key).contains(unionValues[i]))
Linker.get(key).add(unionValues[i]);
}
return Linker;
}
}
No comments:
Post a Comment