여러 분야에서 이용할 수 있겠지만, 데이터 시각화를 위한 그래프를 구성하는 관점에서 볼때 marching squares 에 대한 부분은 contour plot을 구성할 때 긴요하게 사용할 수 있을 것 같습니다.
부드럽고 정교한 plot을 위해서는 더욱 깊은 생각과 학습이 필요하겠지만, 기본적인 내용은 이를 바탕으로 구성하여도 크게 문제가 될 것 같지는 않습니다.
Marching Squares 에 대한 내용은 영문사이트이긴 하지만,
http://en.wikipedia.org/wiki/Marching_squares 에서 상세한 내용을 확인하실 수 있으실 겁니다.
간단하게 보면 사각형을 중심으로 어느 지점에 데이터가 있는지에 따라 영역을 분할 하는 방법이라고 생각하면 될 것 같습니다.
4각형이니까 각 꼭지점을 기준으로 있을 경우 왼쪽 상단에서 시계방향으로 8, 4, 2, 1 의 값을 설정하겠습니다.
데이터의 수준을 '2'를 기준으로 아래의 원 배열을 [8,4,2,1] 배열로 찾아 보겠습니다.
1 1 1 1 8 4 2 3 1
1 2 2 1 -> 1 2 - > 4 12 8
1 1 1 1
왼쪽이 원본, 중앙은 꼭지점 기준값, 오른쪽은 원본을 꼭지점 유무로 재 구성한 배열 입니다.
오른쪽 배열은 원본배열에서 row, column 이 하나씩 작습니다.
처음 위치에서 보면 [8,4,2,1] 의 순서를 기준으로 볼 때 오른쪽 하단에 위치한 '2'이외는 모두 '1'입니다. 그래서 처음값은 2가 됩니다.
두번째 위치(x 가 하나증가된 위치 )에서 보면 하단 영역에 두개의 '2' 가 위치해 있습니다. 1|2 의 값인 3을 저장합니다. 이런식으로 구성하면 위의 오른쪽 배열의 값을 도출 할 수 있습니다.
다음은 위의 값을 기준으로 그래프 위치를 구성할 순서입니다.
1+2+4+8 = 15 입니다.(1|2|4|8). 네! 나올 수 있는 경우의 수는 15입니다.
1,2,4,8 의 값은 각 꼭지점에 값이 있다는 의미니까 꼭지점의 4 귀퉁이 삼각형을 생각할 수 있습니다.
11(1|2|8)은 4와 라인은 같지만 차지하는 면적은 4영역 이외의 모든 영역입니다.
14(2|4|8)은 1과 라인은 같지만 반대 영역을 차지하고 있습니다.
13(8|4|1), 7(1|2|4) 도 위와 같은 방식으로 생각해 볼 수 있습니다.
3(1|2),12(8|4) 는 아래 혹은 위를 기준으로 4각형을 구분짖는 것을 생각해 볼 수 있습니다.
9(1|8),6(2|4)은 좌우로 구분된 직사각형 영역을 생각해 볼 수 있습니다.
15(1|2|4|8) 모든 영역이 포함되어 있습니다.
다만 5, 10의 경우는 다소 애매한 구석이 있습니다.
분절이 될 수도 있고 중앙을 통과하는 것으로 여길 수도 있습니다.
일반적으로 4곳의 평균값을 기준으로 근접한 값을 설정하는 것이 일반적 일 수 있겠지만 다중 레벨을 기준으로 할 때 대각선의 값을 기준으로 상대편 대각선의 값이 같다면 누구의 영역도 아니게 하고 다르다면 통과하게 하는 방법을 사용해 보았습니다. polygon 으로 구성할 때 경우에 따라서는 빈 공간이 발생할 수도 있으나 예제로서는 의미가 있어서 구성해 보았습니다. 실제로는 그 마저 같은 경우 그 공간은 평균값으로도 애매한 영역에 있을 가능성이 높기 때문에 상위나 하위 레벨로 연결을 몰아 갈 수 있습니다.
하여간 그 부분을 해결하기 위해 21과 26의 값을 추가 하였습니다. 5+16 의 값과 10+16의 값을 추가한 것입니다.
아래는 소스 입니다.
테스트 용도의 소스이기 때문에 정돈되어 있지 않습니다.
또한 여러 클래스로 분화 중이기 때문에 역시 모두 기재하기는 어렵습니다.
핵심적인 구조로 보아 주시면 될 것 같습니다.
marching squares 영역을 구성하기 위한 메소드 입니다.
public static int[][] makeMarchingSquaresArray(int[][] orgArray, int matchLevelNum) {
int[][] result
= null;
int[][] filter
= new int[2][2];
filter[0][0] = 8;
filter[0][1] = 4;
filter[1][0] = 1;
filter[1][1] = 2;
if ( orgArray == null || orgArray.length == 0
|| orgArray[0] == null || orgArray[0].length == 0 ) {
return result;
}
int rowSize = orgArray.length;
int colSize = orgArray[0].length;
result = new int[rowSize-1][colSize-1];
for ( int i = 1; i < rowSize; i++ ) {
int py = i-1;
for ( int j = 1; j < colSize; j++ ) {
int px
= j-1;
int v
= 0;
for ( int t = 0; t < 2; t++ ) {
for ( int z = 0; z < 2; z++ ) {
if ( orgArray[py+t][px+z] == matchLevelNum ) {
v = (v|filter[t][z]);
}
}
}
if ( v == 5 ) {
if ( orgArray[py][px] == orgArray[py+1][px+1] ) {
v += 16;
}
}
if ( v == 10 ) {
if ( orgArray[py][px+1] == orgArray[py+1][px] ) {
v += 16;
}
}
result[py][px] = v;
}
}
return result;
}
다음은 위에서 구성한 값을 기준으로 라인 혹은 폴리곤을 구성하기 위한 좌표점을 계산하여 넘겨 주기 위한 메소드 입니다.
return 값의 GraphLinePoint 는 라인 좌표를 가지고 있는 데이터 형이라고 생각하시면 될것 같습니다.
위치는 정방형의 1.0 의 중간지점을 기준으로 하였습니다.
그 지점을 조정하시면 레벨간 선의 중복등을 조절 할 수 있습니다.
public static GraphLinePoint getLevelPoints(int x, int y, int levelNum) {
if ( levelNum <= 0 ) {
return null;
}
double x1, x2, x3, x4, y1, y2, y3, y4;
GraphLinePoint result = new GraphLinePoint();
switch ( levelNum ) {
case 1 :
x1 = 0.0;
y1 = 0.5;
x2 = 0.5;
y2 = 1.0;
result.appendLinePoint(new GraphLeafPoint(x1+x,y1+y), new GraphLeafPoint(x2+x,y2+y));
break;
case 2 :
x1 = 0.5;
y1 = 1.0;
x2 = 1.0;
y2 = 0.5;
result.appendLinePoint(new GraphLeafPoint(x1+x,y1+y), new GraphLeafPoint(x2+x,y2+y));
break;
case 3 :
x1 = 0.0;
y1 = 0.5;
x2 = 1.0;
y2 = 0.5;
result.appendLinePoint(new GraphLeafPoint(x1+x,y1+y), new GraphLeafPoint(x2+x,y2+y));
break;
case 4 :
x1 = 0.5;
y1 = 0.0;
x2 = 1.0;
y2 = 0.5;
result.appendLinePoint(new GraphLeafPoint(x1+x,y1+y), new GraphLeafPoint(x2+x,y2+y));
break;
case 5 :
x1 = 0.0;
y1 = 0.5;
x2 = 0.5;
y2 = 0.0;
x3 = 0.5;
y3 = 1.0;
x4 = 1.0;
y4 = 0.5;
result.appendLinePoint(new GraphLeafPoint(x1+x,y1+y), new GraphLeafPoint(x2+x,y2+y));
result.appendLinePoint(new GraphLeafPoint(x3+x,y3+y), new GraphLeafPoint(x4+x,y4+y));
break;
case 6 :
x1 = 0.5;
y1 = 0.0;
x2 = 0.5;
y2 = 1.0;
result.appendLinePoint(new GraphLeafPoint(x1+x,y1+y), new GraphLeafPoint(x2+x,y2+y));
break;
case 7 :
x1 = 0.0;
y1 = 0.5;
x2 = 0.5;
y2 = 0.0;
result.appendLinePoint(new GraphLeafPoint(x1+x,y1+y), new GraphLeafPoint(x2+x,y2+y));
break;
case 8 :
x1 = 0.0;
y1 = 0.5;
x2 = 0.5;
y2 = 0.0;
result.appendLinePoint(new GraphLeafPoint(x1+x,y1+y), new GraphLeafPoint(x2+x,y2+y));
break;
case 9 :
x1 = 0.5;
y1 = 0.0;
x2 = 0.5;
y2 = 1.0;
result.appendLinePoint(new GraphLeafPoint(x1+x,y1+y), new GraphLeafPoint(x2+x,y2+y));
break;
case 10 :
x1 = 0.0;
y1 = 0.5;
x2 = 0.5;
y2 = 1.0;
x3 = 0.5;
y3 = 0.0;
x4 = 1.0;
y4 = 0.5;
result.appendLinePoint(new GraphLeafPoint(x1+x,y1+y), new GraphLeafPoint(x2+x,y2+y));
result.appendLinePoint(new GraphLeafPoint(x3+x,y3+y), new GraphLeafPoint(x4+x,y4+y));
break;
case 11 :
x1 = 0.5;
y1 = 0.0;
x2 = 1.0;
y2 = 0.5;
result.appendLinePoint(new GraphLeafPoint(x1+x,y1+y), new GraphLeafPoint(x2+x,y2+y));
break;
case 12 :
x1 = 0.0;
y1 = 0.5;
x2 = 1.0;
y2 = 0.5;
result.appendLinePoint(new GraphLeafPoint(x1+x,y1+y), new GraphLeafPoint(x2+x,y2+y));
break;
case 13 :
x1 = 0.5;
y1 = 1.0;
x2 = 1.0;
y2 = 0.5;
result.appendLinePoint(new GraphLeafPoint(x1+x,y1+y), new GraphLeafPoint(x2+x,y2+y));
break;
case 14 :
x1 = 0.0;
y1 = 0.5;
x2 = 0.5;
y2 = 1.0;
result.appendLinePoint(new GraphLeafPoint(x1+x,y1+y), new GraphLeafPoint(x2+x,y2+y));
break;
case 15 :
break;
case 21 :
x1 = 0.0;
y1 = 0.5;
x2 = 0.5;
y2 = 1.0;
x3 = 0.5;
y3 = 0.0;
x4 = 1.0;
y4 = 0.5;
result.appendLinePoint(new GraphLeafPoint(x1+x,y1+y), new GraphLeafPoint(x2+x,y2+y));
result.appendLinePoint(new GraphLeafPoint(x3+x,y3+y), new GraphLeafPoint(x4+x,y4+y));
break;
case 26 :
x1 = 0.0;
y1 = 0.5;
x2 = 0.5;
y2 = 0.0;
x3 = 0.5;
y3 = 1.0;
x4 = 1.0;
y4 = 0.5;
result.appendLinePoint(new GraphLeafPoint(x1+x,y1+y), new GraphLeafPoint(x2+x,y2+y));
result.appendLinePoint(new GraphLeafPoint(x3+x,y3+y), new GraphLeafPoint(x4+x,y4+y));
break;
default :
break;
}
return result;
}
아래는 테스트 코드 입니다.
int rowSize = 6;
int colSize = 6;
int level
= 5;
// 레벨영역을 구성하기 위한 부분 입니다.
// 외각을 2로 그 안은 1로 중심부를 3이라는 값으로 구성 하고 있습니다.
int[][] levelArray = new int[rowSize][colSize];
for ( int i = 0; i < rowSize ;i++ ) {
for ( int j = 0; j < colSize; j++ ) {
if ( i > 0 && i < rowSize-1 && j > 0 && j < colSize-1 ) {
if ( (i == 2 && ( j == 2 || j == 3 )) || (i == 3 && ( j == 2 || j == 3 )) ) {
levelArray[i][j] = 3;
} else {
levelArray[i][j] = 1;
}
} else {
levelArray[i][j] = 2;
}
}
}
System.out.println("");
System.out.println("Level ");
for ( int i = 0; i < rowSize; i++ ) {
for ( int j = 0; j < colSize; j++ ) {
System.out.print("\t\t" + levelArray[i][j] );
}
System.out.println("");
}
// 레벨 1이라는 숫자의 영역만 marching squares 영역으로 구성하기 위한 메소드 입니다..
int[][] contourArray = makeMarchingSquaresArray(levelArray,1);
System.out.println("");
System.out.println("Contour ");
for ( int i = 0; i < rowSize-1; i++ ) {
for ( int j = 0; j < colSize-1; j++ ) {
System.out.print("\t\t" + contourArray[i][j] );
}
System.out.println("");
}
// 예제를 그림으로 출력하기 위한 영역입니다. 참고로 보아 주시면 될 것 같습니다.
int xSize = 820;
int ySize = 820;
BufferedImage bImg = new BufferedImage(xSize,ySize,BufferedImage.TYPE_INT_RGB);
Graphics2D gr
= bImg.createGraphics();
gr.setColor( Color.WHITE );
gr.fillRect(10,10,800,800);
gr.setColor(Color.BLUE);
getContourLineData(contourArray);
for ( int i = 0; i < rowSize-1; i++ ) {
for ( int j = 0; j < colSize-1; j++ ) {
GraphLinePoint gLine = getLevelPoints(j,i,contourArray[i][j]);
if ( gLine == null ) {
continue;
}
List<List<GraphLeafPoint>> points = gLine.getLines();
if ( points != null && points.size() > 0 ) {
for ( List<GraphLeafPoint> pList : points ) {
if ( pList == null || pList.size() != 2 || pList.get(0) == null || pList.get(1) == null ) {
System.out.println ( j + " : " + i + " SKIP ");
continue;
}
try {
gr.drawLine(10+(int)pList.get(0).getTransX(colSize-1,800),10+(int)pList.get(0).getTransY(rowSize-1,800)
, 10+(int)pList.get(1).getTransX(colSize-1,800),10+(int)pList.get(1).getTransY(rowSize-1,800) );
} catch ( Exception ee ) {
ee.printStackTrace();
break;
}
}
}
}
}
gr.dispose();
java.io.File f = new java.io.File("test.png");
if ( f.exists() ) {
f.delete();
}
try {
javax.imageio.ImageIO.write(bImg,"png",f);
} catch ( Exception ee ) {
}
아래는 그 결과 입니다.
Level
2
2
2
2
2
2
2
1
1
1
1
2
2
1
3
3
1
2
2
1
3
3
1
2
2
1
1
1
1
2
2
2
2
2
2
2
Contour
2
3
3
3
1
6
13
12
14
9
6
9
0
6
9
6
11
3
7
9
4
12
12
12
8
데이터가 많아지면 위의 예제에서 보다는 보다 부드러운 곡선이 가능해 집니다.
더 부드러운 곡면이 필요하다면 보간법과 영역에 대한 경계처리 등에서 작업할 내용이 더 많아 질 듯 합니다.
랜덤으로 좀 많은 데이터를 출력해 보았습니다. 레벨은 5가지중 2개만 출력해 보았습니다.
지금 예시한 소스는 marching squares 를 활용하는 방법을 코드화 해 보았습니다.
기본적인 구현이라 에러나 예외에 대한 부분은 많이 생략하였습니다.
이미지로 구성하기 위한 객체 등은 다 올릴 수 없어 핵심적인 영역만 기재해 보았습니다.
