기수정렬(Least Significant Digit 방식) 관련 글들을 찾아보면 개념을 쉽게 설명하기 위해 십진수 단위를(base 10) 사용한 것들이 많은데 실제로 이것을 구현하면 생각보다 느린 것을 볼 수 있다. 나눗셈 연산과 나머지연산이 수행되기 때문이다.  예를 들어 100의 자리에서 기수정렬할 단계를 보면, (현 상태에서 m은 100이라고 가정한다.)


arr[i]/m%10    


위와 같이 / 연산과 % 연산이 사용된다.



 이러한 문제를 개선하기 위해 버킷의 개수를 2의 거듭제곱으로 하면 속도가 빠른 비트연산을 사용할 수 있다. 버킷의 개수를 8로 하면 위 연산식이 아래와 같이 된다. (현 상태에서 m은 64라고 가정)


(arr[i]>>m)&7


2의 거듭제곱으로 나누었을 때의 나머지는, 굳이 나누어서 계산해볼 필요 없이 해당 위치의 비트만 AND연산으로 추출하면 되는 것이다.




구현


 아래 코드는 0부터 99,999,999까지의 정수 데이터들을 정렬할 수 있는 기수정렬(base 8) 알고리즘을 코드로 구현한 것이다. 

     for(int i=0; i<9; ++i) {


           idx = 0;

       for(int j=0; j<8; ++j) {
            counts[j] = 0;
        }
     
        for(int j=0; j<n; ++j) {
            digit = (arr[j]>>i*3)&7;
            bucket[digit][counts[digit]++] = arr[j];
        }
    
        for(int j=0; j<8; ++j) {
            for(int k=0; k<counts[j]; ++k) {
                arr[idx++] = bucket[j][k];
            }
        }
    }


비트시프트 연산을 보면, i는 데이터를 8진수로 나타냈을 때 특정 자리의 숫자를 얻을 때 사용된다. i를 8이 될때까지만 반복시키는 이유는  으로, 99,999,999를 8진수로 나타낼 수 있는 가장 큰 자릿수가 8이기 때문이다.




수행시간 분석


 base 8 기수정렬에서 전체 데이터의 양을 N개라고 했을 때 버킷의 크기는 bucket[8][N]이다. base 8 대신 base 4나 base 2를 사용하면 메모리 사용량은 각각 2배, 4배 줄어들게 된다. 반면, 기수정렬의 시간복잡도가 O(dN)이므로, 수행시간은 더 늘어난다. (d는 해당 base에서 데이터의 최대 자릿수이다.) 표 1은 내림차순으로 정렬된 100만개 ~ 500만개 데이터를 오름차순으로 정렬했을 때 각 알고리즘의 수행 시간(ms)이다. 표 2는 랜덤함수로 생성한 무작위 데이터를 오름차순으로 정렬했을때의 결과이다.


표 1


표 2




 표 1의 결과를 그래프로 나타내 보면 다음과 같다.




 base 8 대신 16이나 32를 사용하면 메모리 사용량이 늘어나고, 속도가 약간 줄어들겠지만, 값 복사시간이 기본적으로 존재하기 때문에 속도가 줄어드는 데에는 한계가 있다. 수행시간이 카운팅 정렬을 사용했을때 이하로 떨어지지는 않을 것이다.





2차원 평면상에서 선분 AB와 CD의 정보가 주어질 때, 두 선분의 교차 여부를 빠르게 판단할 수 있는 방법이 있다. 벡터의 외적(벡터곱)을 이용하는 방법이다.


그림 1과 같이 두 선분이 교차하는 경우를 생각해 보자. 벡터 BA를 기준으로 점 C와 점 D가 서로 다른 회전방향에 있으므로, 아래 두 경우는 벡터곱 연산의 결과로 나온 z값의 부호가 다르다.

- 벡터 BA와 벡터 BC를 외적한 결과

- 벡터 BA와 벡터 BD를 외적한 결과


벡터 DC에 대해서도 역시 부호가 다르게 된다.

- 벡터 DC와 벡터 DA를 외적한 결과

- 벡터 DC와 벡터 DB를 외적한 결과 


     

그림 1. 교차하는 두 선분                                  


즉, 벡터곱 연산을 이용하여 한 선분의 벡터를 기준으로, 다른 선분의 두 점들이 같은 회전뱡향에 있는지, 다른 회전방향에 있는지 검사하면 교차 여부를 판단할 수 있는 것이다.
두 선분에 대해 이러한 판단을 수행하여 모두 만족하면 교차하는 것으로 판정한다.


그림 2에서는 벡터 CD에 대해 다른 선분의 두 점(A, B)는 서로 다른 회전방향이지만, 벡터 AB에 대해서는 두 점(C ,D)가 같은 회전방향에 있기 때문에 교차하지 않는 것으로 판정한다.


 

그림 2. 교차하지 않는 두 선분



Javascript로 표현하면 아래와 같이 쓸 수 있다.

    let p1 = line1.p1;

    let p2 = line1.p2;

    let p3 = line2.p1;

    let p4 = line2.p2;


    let sign1 = (p2.x-p1.x)*(p3.y-p1.y) - (p3.x-p1.x)*(p2.y-p1.y);

    let sign2 = (p2.x-p1.x)*(p4.y-p1.y) - (p4.x-p1.x)*(p2.y-p1.y);


    let sign3 = (p4.x-p3.x)*(p1.y-p3.y) - (p1.x-p3.x)*(p4.y-p3.y);

    let sign4 = (p4.x-p3.x)*(p2.y-p3.y) - (p2.x-p3.x)*(p4.y-p3.y);


    return sign1*sign2<0 && sign3*sign4<0;




그러나 위 코드에는 문제점이 있는데, 그림 3과 같이 두 선분의 기울기가 같을 때는 교차하지 않는 것으로 판단한다는 것이다. (이런 결과를 의도했다면 문제가 되지 않겠지만..)


그림 3. 두 선분의 기울기가 같고, 교차점이 무수히 많은 경우



그림 3과 같은 경우에도 두 선분이 교차하는 것으로 판정하기 위해, 비교문을 아래와 같이 고치면 또다른 문제가 발생한다. 그림 4와 같이 기울기가 같고 서로 떨어져 있을 때 잘못 판정한다는 것이다.

return sign1*sign2<=0 && sign3*sign4<=0;



그림 4. 교차 여부를 잘못 판정한 경우




두 선분이 완전히 떨어져 있을 경우(더 정확히 말하면, 각각의 선분이 이루는 직사각형 영역이 서로 겹치지 않는 경우)에 false를 리턴하면 이 문제를 해결할 수 있다. 외적 연산에 앞서 사전 영역 검사를 하는 것이다.

아래 코드에서 모든 부호가 0일 때 true를 반환하는 부분을 추가한 이유는, 그림 3과 같이 교차점이 무수히 많은 경우도 교차하는 것으로 판단하기 위해서이다.


    let p1 = line1.p1;

    let p2 = line1.p2;

    let p3 = line2.p1;

    let p4 = line2.p2;


    if(Math.max(p1.x, p2.x) < Math.min(p3.x, p4.x)) return false;

    if(Math.min(p1.x, p2.x) > Math.max(p3.x, p4.x)) return false;

    if(Math.max(p1.y, p2.y) < Math.min(p3.y, p4.y)) return false;

    if(Math.min(p1.y, p2.y) > Math.max(p3.y, p4.y)) return false;


    let sign1 = (p2.x-p1.x)*(p3.y-p1.y) - (p3.x-p1.x)*(p2.y-p1.y);

    let sign2 = (p2.x-p1.x)*(p4.y-p1.y) - (p4.x-p1.x)*(p2.y-p1.y);


    let sign3 = (p4.x-p3.x)*(p1.y-p3.y) - (p1.x-p3.x)*(p4.y-p3.y);

    let sign4 = (p4.x-p3.x)*(p2.y-p3.y) - (p2.x-p3.x)*(p4.y-p3.y);


    if(sign1==0 && sign2==0 && sign3==0 && sign4==0) return true;


    return sign1*sign2<=0 && sign3*sign4<=0;



그림 5. 교차 여부를 정상적으로 판정한 경우




경우에 따라서 그림 6과 같이 선분의 끝점이 교차할 때는 교차하지 않는 것으로 판단하는 것이 필요할 때가 있다.

 

그림 6, 7. 두 선분이 교차하는 것으로 판단하는 경우



아래 코드에서와 같이 사전 영역 검사에 동등 조건을 넣어  좀더 엄격하게 바꾸고(그림 6과 관련), 마지막의 리턴 코드에서 동등 조건을 제거한다.(그림 7과 관련)


    let p1 = line1.p1;

    let p2 = line1.p2;

    let p3 = line2.p1;

    let p4 = line2.p2;


    if(Math.max(p1.x, p2.x) <= Math.min(p3.x, p4.x)) return false;

    if(Math.min(p1.x, p2.x) >= Math.max(p3.x, p4.x)) return false;

    if(Math.max(p1.y, p2.y) <= Math.min(p3.y, p4.y)) return false;

    if(Math.min(p1.y, p2.y) >= Math.max(p3.y, p4.y)) return false;


    let sign1 = (p2.x-p1.x)*(p3.y-p1.y) - (p3.x-p1.x)*(p2.y-p1.y);

    let sign2 = (p2.x-p1.x)*(p4.y-p1.y) - (p4.x-p1.x)*(p2.y-p1.y);


    let sign3 = (p4.x-p3.x)*(p1.y-p3.y) - (p1.x-p3.x)*(p4.y-p3.y);

    let sign4 = (p4.x-p3.x)*(p2.y-p3.y) - (p2.x-p3.x)*(p4.y-p3.y);


    if(sign1==0 && sign2==0 && sign3==0 && sign4==0) return true;


    return sign1*sign2<0 && sign3*sign4<0; 





결론


만들고자 하는 프로그램에 따라 선분 끝점을 어떻게 판단해야할지가 달라진다. 위 코드를 활용하여 비교문들을 조정하면 선분의 교차 판단을 목적에 맞게 할 수 있을 것이다.



 

소스코드


동작하는 전체 코드는(Javascript)는 아래 github에서 다운로드할 수 있습니다.

https://github.com/tibyte/algorithms/tree/master/line-intersection







십진수 11을 이진수로 바꾸려면 

아래와 같은 과정을 거치면 된다.

ⓛ 11을 2로 나누면 몫은 5, 나머지는 1이다.
② 5를  2로 나누면 몫은 2, 나머지는 1이다.
③ 2를 2로 나누면 몫은 1, 나머지는 0이다.
④ 1을 2로 나누면 몫은 0, 나머지는 1이다.

나머지가 순서대로 1, 1, 0, 1로 나오는데 이것을 뒤집으면
1, 0, 1, 1이 나오게 되고 이것이 십진수 11의 이진수 표현 1011이다.






십진수 m을 n진법으로 나타내는 과정도 이와 같다.

ⓛ m을 n으로 나누어 m을 몫으로 갱신하고 나머지 b1를 얻는다.

② m을 n으로 나누어 m을 몫으로 갱신하고 나머지 b2를 얻는다.

...

...


이같은 과정을 m이 0보다 작아질 때까지 반복하고,

얻은 b수열을 뒤집으면 n진법 표현을 얻을 수 있다.




아래는 C++로 구현한 코드이다. (예외처리는 하지 않음)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
#include <string>
#include <algorithm>
 
int main()
{
    std::string marks = "0123456789ABCDEF";
    std::string str;
    int num, base;
 
    std::cin >> num >> base;
    
    for(;num>0;) {
        str += marks[num%base];
        num /= base;
    }
    
    std::reverse(str.begin(), str.end());
    
    std::cout << str << std::endl;
    
    return 0;
}
cs




C++의 string를 사용하는 대신, 배열의 뒤쪽에서부터 값을 채워나가면

뒤집는 동작을 하는 코드를 사용하지 않아도 된다.

대신 출력할 때 시작 위치 주소를 맞게 설정해야 한다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <cstdio>
 
int main()
{
    int num, base;
    char res[32];
    int i = 30;
 
    scanf("%d%d", &num, &base);
    
    for(;num>0;) {
        res[i--] = "0123456789ABCDEF"[num%base];
        num /= base;
    }
    res[31] = '\0';
    
    printf("%s\n", res+i+1);
    
    return 0;
}
cs







격자 위에 원을 그려야 하거나 원 모양의 범위를 적용할 때

다음과 같은 식을 사용할 수 있다.



d가 0보다 크면 원 외부, d가 0보다 작으면 원 내부로 판단하는 것이다.


그러나 원을 그릴 때는 범위 내의 모든 점에 대입해야 할 뿐만 아니라 

매번 곱셈 연산을 3번 사용하여야 한다.



midpoint algorithm을 사용하면 이를 효율적으로 해결할 수 있다.

(원의 반지름이 n일 때 O(n))



원리




[그림1]

이 알고리즘의 원리는 결정된 한 점이 있을 때

한 칸 옆인 에 대응되는 y 값이 인지 인지 판단하는 것이다.  (위 그림에서 까만색 점 2개)



[그림 1]과 같이 원에 포함되는 것으로 결정된 한 점

가 있을 때 가 원의 내부인지 외부인지 판별하는 식은 아래와 같이 나타낼 수 있다.



중간점이 원 내부에 포함될 경우(p<=0), [그림1]에서 p의 위쪽 점을 선택하고,

p점이 원 밖일 경우(p>0) p의 아래쪽 점을 선택하는 것이다.


같은 방법으로 을 다음과 같이 점화식으로 나타낼 수 있다.




이제 을 결정해야 하는데,

위에서 서술한 바와 같이 의 부호에 따라 선택되므로 다음과 같이 나타낸다.



이를 활용하여 의 식을 간단히 하면



코드를 좀더 간편하게 하기 위해 대신 를 활용하면

최종적으로 아래 식을 얻을 수 있다.




한편 p의 초기값 는 위에서 식에 x의 초기값 0과 y의 초기값 r을 대입하여

5/4 - r이라는 것을 알 수 있다.


그런데 p의 점화식을 보면 초기값 외에는 모두 정수의 덧셈/뺄셈 연산이므로 (2x는 x+x로 계산)

p0을 int형으로 하고 1-r로 두어도 무방하다.




위 과정을 x > y가 되기 전까지 반복한다.

[그림 2]




실제로 그려보면 아래 그림과 같은 8분원(octant)을 얻을 수 있다.


[그림 3]




그리고 아래와 같이 대칭인 8개 점을 동시에 그리면 전체 원이 그려진다.

(x, y)

(x, -y)

(-x, y)

(-x, -y)

(y, x)

(y, -x)

(-y, x)

(-y, -x)


[그림 4]




4방향으로 뚫려 있는 부분은 따로 채워준다. 


[그림 5]



8개 부분을 따로 표시해 보면 아래 그림과 같다.


[그림 6]







원 채우기



y값이 변할 때 해당 y좌표에 해당하는 부분을 모두 칠하면

가운데 정사각형 영역을 제외한 부분을 채울 수 있다.(하단 코드 참조)


[그림 7]



나머지 정사각형 부분은 쉽게 채울 수 있다.(하단 코드 참조)


[그림 8]


모두 단색으로 칠해보면 아래 그림과 같은 원이 나온다.


[그림 9]




콘솔창에서는 한계가 있어 Javascript를 사용하여 그린 큰 원.


[그림 10]






구현



[그림 9]를 그릴 때 작성한 C언어 코드이다.

gcc컴파일러로 컴파일 가능하다.


나머지 코드들은

https://github.com/tibyte/algorithms/tree/master/bresenham/midpoint_circle

에서 다운로드 가능.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <bits/stdc++.h>
 
const int SIZE = 28;
 
void drawCircle(int arr[SIZE][SIZE], int r, int x, int y);
void display(int arr[SIZE][SIZE]);
 
int main(void)
{    
    int arr[SIZE][SIZE] = {0,};
    
    drawCircle(arr, 11, 11, 13);
    display(arr);
    
    return 0; 
}
 
 
void drawCircle(int arr[SIZE][SIZE], int r, int cx, int cy)
{
    int x, y;
    int p;
    
    x = 0;
    y = r;
    p = 1 - r;
    
    arr[y+cy][x+cx] = 1;
    arr[-y+cy][x+cx] = 1;
    arr[x+cy][y+cx] = 1;
    arr[x+cy][-y+cx] = 1;
 
    x = 1;
    while(x < y) {
        
        if(p < 0) {
            p += x+x + 1;
        }
        else {
            p += x+x + 1 -y-y;
            --y;
            for(int i=0; i<x; i++) {
                arr[y+cy][i+cx] = 1;
                arr[-y+cy][i+cx] = 1;
                arr[y+cy][-i+cx] = 1;
                arr[-y+cy][-i+cx] = 1;
                arr[i+cy][y+cx] = 1;
                arr[-i+cy][y+cx] = 1;
                arr[i+cy][-y+cx] = 1;
                arr[-i+cy][-y+cx] = 1;
            }
        }
        arr[y+cy][x+cx] = 1;
        arr[-y+cy][x+cx] = 1;
        arr[y+cy][-x+cx] = 1;
        arr[-y+cy][-x+cx] = 1;
        arr[x+cy][y+cx] = 1;
        arr[-x+cy][y+cx] = 1;
        arr[x+cy][-y+cx] = 1;
        arr[-x+cy][-y+cx] = 1;
        
        ++x; 
    }
 
    for(int i=cy-y+1; i<cy+y; i++) {
        for(int j=cx-y+1; j<cx+y; j++) {
            arr[i][j] = 1;
        }
    }
}
 
 
void display(int arr[SIZE][SIZE])
{    
    for(int i=0; i<SIZE; i++) {
        for(int j=0; j<SIZE; j++) {
            if(arr[i][j])
                printf("■");
            else
                printf("　");
        }
        printf("\n");
    }
}
cs







01.
샌드박스 카페에서 이야기 중에 달팽이 배열(나선형 이차원 배열)에 대한 주제가 나왔다.
이 달팽이 배열을 출력하기 위해서는 프로그래밍 언어에서 제공하는 형태의 이차원 배열에, 수의 순서를 따라가며 값을 쓰면 된다.
하지만 이 문제를 이차원배열을 사용하지 않고도 풀 수 있을 것 같다는 이야기가 있어 직접 구현해보게 되었다.





02.
우선 '달팽이 배열(spiral matrix)'이란, 수가 행렬을 나선형으로 따라가며 순서대로 배열되어있는 형태를 말한다.


아래 그림은 알아보기 쉽게 선을 그은 것이다.




이와 같은 결과를 이차원배열을 쓰지 않고 구현하려면, x좌표와 y좌표를 매개변수로 넣었을 때 해당 위치의 달팽이배열 값을 반환하는 함수 f(x, y)를 정의해야 한다.






03.

일단 작은 크기인 6x6 달팽이 배열을 보고 규칙성을 찾아보았다.

행렬을 아래 그림과 같이 3부분으로 나누어 보면, 3부분 모두 ㅁ자 모양 안에서 수가 순차적으로 증가하는 패턴을 갖고 있다.

그러므로 ㅁ자 모양으로 수가 이어지는 가장 바깥쪽 패턴만 구현한다면 전체 달팽이 배열도 쉽게 구현할 수 있을 것이다.


이차원배열을 사용하지 않는다는 조건이 있기 때문에 이 부분도 g(x,y)형태의 함수로 나와야 한다.

0부터 10까지의 부분을 보면 이 함수가 g(x,y) = x+y  (x>=y일 때)라는 것을 알 수 있다.


이제 11~19번까지가 문제인데, 우선 19라는 숫자는 nxn배열에서 둘레에 배치된 요소의 수를 구할 때 (n-1)*4로 구하므로, 6x6 배열의 둘레인 20에서 1을 뺀 것이다.

따라서 함수 g(x,y)를 여기까지의 정보로 구해 보면 아래와 같다.

g(x,y) = 

x+y                 (x>=y 일 때)

(n-1)*4 - (x+y)    (x<y 일 때)

 

그런데 이 함수는 안쪽의 ㅁ자 패턴을 구할 때는 좌표가 달라지기 때문에 바로 적용할 수 없다.

행렬위의 임의의 위치(x,y)에 있는 요소가 가장자리에서 떨어져 있는 정도를 먼저 알아야 한다.






04.

임의의 위치 (x,y)에 있는 요소의 가장자리에서 떨어진 정도를 반환하는 함수 h(x,y)를 작성하기 전에, 6x6인 경우와 9x9인 경우의 출력결과를 보면 각각 아래와 같다.




이 함수는 간단하게 만들 수 있는데,

h(x,y) = min(x, y, n-x-1, n-y-1)

을 구하면 끝이다.






05.

이제 04장에서 구한 h(x,y)함수로 03장의 g(x,y)함수를 완성한다.


p = h(x,y)

g(x,y) = 

x+y  - 2p                      (x>=y 일 때)

(n-1 - 2p)*4 - (x+y - 2p)    (x<y 일 때)


2p를 뺀 이유는 한 단계 안쪽 패턴은 한 변을 이루는 요소의 수가 2 만큼 작기 때문이다. 


드디어 이렇게 같은 패턴이 반복되는 결과를 얻을 수 있다!





06. 

달팽이 배열을 얻으려면 아직 한 단계가 남아 있다. 

05장에 있는 그림에서 첫 번째 패턴(껍질)은 0부터 시작해야 하고, 두 번째 패턴은 20부터 시작해야 한다. 그리고 가장 안쪽 패턴은 32부터 시작해야 한다.


일반화를 위해 nxn 행렬에서 p=k일 때 어떤 수부터 시작해야 하는지 유도한다.

안쪽 껍질(p값이 높음)로 갈수록 한 변을 이루는 요소의 개수는 2씩 줄어들고, 바깥쪽 껍질로부터 값이 누적된다.

p=0:    0

p=1:    4*((n-1))

p=2:    4*((n-1)+(n-3))

p=3:    4*((n-1)+(n-3)+(n-5))

p=k:    4*((n-1)+(n-3)+(n-5)+(n-7)+...+(n-(2k-1)))


p=k인 경우를 보면 n이 k개 더해지고,

1+3+5+7+... 과 같이 나아가는 급수의 k번째 일반항은 k*k이므로

원하는 식은,

4*(p*n - (p*p))

이 된다. 이 값을 마지막에 더하면 된다.






07.

아래는 python 3으로 구현한 코드이다.

github 주소 : https://github.com/tibyte/algorithms


1
2
3
4
5
6
7
8
9
10
11
12
n = int(input())
 
for y in range(0, n):
    for x in range(0, n):
        p = min(x,y,n-x-1,n-y-1)
        if x>=y:
            q = x+y - 2*p
        else:
            q = (n-1 - 2*p)*4 - (x+y - 2*p)
        q += 4 * (p*n - (p*p))
        print("{:3d}".format(q), end="")
    print()
cs




08.

n=6일 때와 n=9일 때의 실행결과이다.


n=6



n=9






09.


07장의 코드에서 반복문을 제외한다면, 임의의 위치 (x,y)의 달팽이배열 값을 바로 구할 수 있다.










상자 채우기 (2D bin packing) - (2) Maxrects 알고리즘①

에서 이어지는 포스트입니다.



지난 글에서의 순서를 다시 보면 아래와 같다.


1. 넣을 아이템을 불러온다

2. 남은 공간들 중에서 아이템을 넣을 수 있는 공간을 선택한다. (다양햔 휴리스틱 존재)

3. 해당 공간에 아이템을 넣는다.

4. 넣은 아이템과 겹치는 모든 공간들을 검사한다

5. 넣은 아이템과 겹치는 공간을 분할한다

6. 유효하지 않은 공간을 제거한다. (다른 공간 안에 포함된 공간이나, 높이나 너비 값이 음수인 공간.)

7. 넣을 아이템이 남아있으면 (1)로 돌아간다.


3,4,5,6 번 과정을 그림으로 그려봤을 때


아래 그림은

item1이 넣어져 있는 상태에서 남은 공간은 A와 B로 나누어져 있고,

item2를 넣는 상황이다.

[그림6]

위 그림과 같이 공간 A는 item2에 의해 3개의 새로운 공간으로 나위며

공간 B는 2개의 새로운 공간으로 나뉜다.



그러면 기존 A, B 공간은 사라지고 새로운 5개의 공간이 생기게 된다.

[그림7]




마지막으로, 공간들 사이에 포함관계가 있는 것을 찾아 제거하여 최적화를 한다.

[그림8]




 코드로 작성할 때는 넣을 아이템들의 정보와 분할될 공간들의 정보를 선형적으로 탐색하도록 코드를 작성할 것이기 때문에 링크드 리스트(linked list)구조를 사용하였다. 


 5번 단계를 보면, 아이템과 겹치는 부분이 있는 공간 하나당 0~3개의 새로운 나눠진 공간이 생길 수 있다. 새로 생긴 공간들을 임시 리스트에 넣어두고, 기존에 겹쳤던 공간은 제거한다. 의사코드로 쓰면 아래와 같다.

width>0, height>0 부분은 크기가 음수로 되어 있어 유효하지 않은 공간이 생기는 것을 방지하는 것이다.


for s in spaceList

    if isIntersect(item, s) {

        s_top, s_right, s_bottom, s_left 생성

        if(s_top.width>0 && s_top.height>0) newList.push(s_top)

        if(s_right.width>0 && s_right.height>0) newList.push(s_right)

        if(s_bottom.width>0 && s_bottom.height>0) newList.push(s_bottom)

        if(s_left.width>0 && s_left.height>0) newList.push(s_left)

        spaceList.erase(s)

    }

}


이제 새로운 공간 리스트 (newList)를 기존 리스트(spaceList)와 병합해야 하는데

그 전에 [그림8]처럼 최적화를 해야 한다.

다음과 같은 4가지 조건을 생각해 볼 수 있다.


1. 기존 공간들 간의 포함관계

2. 기존 공간이 새로운 공간을 포함하는 경우

3. 새로운 공간이 기존 공간을 포함하는 경우

4. 새로운 공간 간의 포함관계


여기서 1번은 이 최적화과정이 item을 하나 넣을 때 마다 일어나므로 발생하지 않고, 

3번 또한 발생하지 않아서 고려하지 않아도 된다


2번과 4번의 경우 공간을 제거하여 최적화한 뒤,

newList를 기존 리스트 뒤에 병합하면 된다.



다음은 적용예이다.


적용 예시

아이템들이 모두 같은 크기인 경우

*'잔여 면적'은 적재하지 못한 아이템들의 면적입니다.

[그림9]





작은 아이템부터 큰 아이템까지 고르게 있는 경우

아이템들이 비효율적으로 적재되며 모든 아이템을 넣는 것도 실패한다.

[그림10]

*'잔여 면적'은 적재하지 못한 아이템들의 면적입니다.





작은 아이템부터 큰 아이템까지 고르게 있는 경우

+ 큰 아이템부터 내림차순으로 정렬

아이템을 면적으로 내림차순 정렬하면 공간의 단편화가 적어져서 연산 횟수가 줄어들고, 공간을 효율적으로 차지하게 된다. (정렬은 O(nlogn)으로 할 수 있으므로..)

[그림11]

*'잔여 면적'은 적재하지 못한 아이템들의 면적입니다.






같은 크기의 아이템 집단이 있을 때

이 알고리즘을 알아보게 되었던 목적이 게임 그래픽 리소스 패킹을 위해서였는데,

그 때 가장 많이 볼 수 있을 경우로,

아이템들이 모두 같은 크기일 때처럼 공간을 빼곡히 차지할 수 있다.

[그림12]

*'잔여 면적'은 적재하지 못한 아이템들의 면적입니다.






무작위 + 정렬

이전 포스트에서의 shelf 알고리즘보다 더 좋은 공간효율을 보여준다.

하지만 전체공간의 크기가 고정되어 있어서 모든 아이템들을 넣을 수 없는데,

이 전체공간의 크기를 PO2로 늘려 주는 부분을 다음다음 글에서 작성할 것이다.

[그림13]

*'잔여 면적'은 적재하지 못한 아이템들의 면적입니다.






아이템의 수와 연산횟수의 관계

단위연산은 정렬 시 비교연산 수,

넣을 공간을 찾을 때의 검사 수,

분할할 공간을 찾을 때의 검사 수,

포함관계에 있는 공간을 찾을 때의 검사 수를 더한 것으로 정했다.



아래 그래프에서처럼 아이템이 적을 때는, 아이템의 수가 늘어날수록 연산횟수의 변화율이 커지지만, 일정 수 이상에서는 선형적인 모양이 나온다.

공간을 점점 채워갈수록 고려해야 할 공간의 수가 더이상 늘어나지 않기 때문이다.

따라서 아이템에 비해 상대적으로 충분히 큰 공간을 두고 공간에 아이템이 50%정도 채워질 때까지를 봐야 한다.



[그림14] 가로축은 아이템의 수, 세로축은 연산횟수이다





그렇게 하면 아이템의 수에 따른 연산횟수가 점근적으로 O(n^2)에 근사하는 것을 볼 수 있다.


[그림15] 가로축은 아이템의 수, 세로축은 연산횟수이다




소스코드


GitHub gist에서도 볼 수 있습니다.

https://gist.github.com/tibyte/c0ef27311005e0f2476d


 mxrc3_1.html




관련글

상자 채우기 (2D bin packing problem) - (1) Shelf 알고리즘

상자 채우기 (2D bin packing problem) - (2) Maxrects 알고리즘①




참고글 : http://clb.demon.fi/files/RectangleBinPack.pdf









이전 글

상자 채우기 (2D bin packing problem) - (1) Shelf 알고리즘

에서 이어지는 포스트입니다.



Maxrects(Maximal Rectangle)알고리즘

목차

1. 원리

2. First Fit

3. Best Fit

4. Maxrects-CP



이전 글에서의 문제점을 해결하기 위해서는 남은 공간의 정보를 저장해 두어야 한다.

처음 공간에 아이템이 하나 배치됐을 때 아래와 같은 3개의 영역이 생긴다.

그림1



그런데 위와 같이 세 부분으로 나누면 단편화(fragmentation)가 심해져서 크기가 큰 아이템을 추가로 넣을 수 없다.

따라서 두 부분으로 나누어야 하는데 아래 그림처럼 2가지 선택지가 있다. 이렇게 나누는 방법을 Guillotine Algorithm이라고 한다. 

그림2


하지만 여전히 단편화 현상이 나타나게 된다. 왼쪽 그림에서 B영역과, 오른쪽 그림에서 A영역을 보면 알 수 있다.




따라서 두 공간을 직사각형 모양을 유지하며 최대한으로 확장하여 사용한다.

그림3




여기서 새 아이템을 넣을 때 아이템이 공간A와 공간 B 모두에 겹치는(intersect) 경우가 대부분이다.

겹치는지 아닌지를 판별하는 방법은 http://tibyte.kr/228 이 포스트의 return null 조건 참고.

그림4



다음 단계에서 공간A와 공간B 모두에 대해 새로운 공간을 다시 생성해야 하므로

상하좌우 4방향 모두 고려해야 한다.

그림5

그림에서 흰 부분이 아이템이고, 색이 칠해진 부분이 남은 공간이다.


속성으로 x, y ,w, h 값을 가지는 rectangle객체가 있다고 할 때

위 4개의 남은공간을 나타내는 rectangle객체는 쉽게 얻을 수 있다.


//r은 아이템, s는 아이템과 겹치는 공간.

    rt = {x:s.x     , y:s.y     , w:s.w               , h:r.y-s.y          }   //top

    rb = {x:s.x     , y:r.y+r.h , w:s.w               , h:s.y+s.h-(r.y+r.h)} //bottom

    rl = {x:s.x     , y:s.y     , w:r.x-s.x           , h:s.h              }  //left

    rr = {x:r.x+r.w , y:s.y     , w:s.x+s.w-(r.x+r.w) , h:s.h              }  //right


위 rt, rb, rl, rr 객체 중에서 w(width)나 h(height)속성값이 음수인 객체는 지우면 된다. 







▽ 자바스크립트와 canvas로 구현한 결과. 마우스로 조절점을 드래그해보세요.

(※인터넷 익스플로러 9이상 필요)





이제 Maxrects알고리즘으로 bin packing을 하는 단계를 보면 아래와 같다.

이번 포스트에서는 (4)번과 (5)번을 알아보았다.


(1) 넣을 아이템을 불러온다

(2) 남은 공간들 중에서 아이템을 넣을 수 있는 공간을 선택한다. (다양햔 휴리스틱 존재)

(3) 해당 공간에 아이템을 넣는다.

(4) 넣은 아이템과 겹치는 모든 공간들을 검사한다

(5) 넣은 아이템과 겹치는 공간을 분할한다

(6) 유효하지 않은 공간을 제거한다. (다른 공간 안에 포함된 공간이나, 높이나 너비 값이 음수인 공간.)

(7) 넣을 아이템이 남아있으면 (1)로 돌아간다.


참고로 실제 리소스 패킹 목적으로 구현할 때는 위 순서중 (2)번에서, 적당한 공간이 없으면 전체영역의 크기를 확장해야 한다. 



다음 포스트에서 이어집니다..



이전글

상자 채우기 (2D bin packing problem) - (1) Shelf 알고리즘


다음글

상자 채우기 (2D bin packing problem) - (3) Maxrects 알고리즘② 




참고글 : http://clb.demon.fi/files/RectangleBinPack.pdf


관련글

상자 채우기 (2D bin packing problem) - (1) Shelf 알고리즘

상자 채우기 (2D bin packing problem) - (2) Maxrects 알고리즘(1)  

상자 채우기 (2D bin packing problem) - (3) Maxrects 알고리즘(2) 




 상자 채우기 문제 (bin packing problem)는 최소한의 공간에 최대한의 아이템을 채워넣는 문제로 NP-hard분류에 속한다.

 이 문제를 적용할 수 있는 것은 1차원(linear)에서는 메모리(segmentation) 관리,  2차원에서는 그래픽 리소스 최적화, 3차원에서는 화물 적재 등 주변에서 쉽게 찾아볼 수 있다.

 게임 텍스쳐들을 모아 놓는 스프라이트 시트(sprite sheet)제작 툴에 활용하기 위해 이 알고리즘을 구현해보게 되었다. 참고글 : (http://clb.demon.fi/files/RectangleBinPack.pdf)

 이 글의 마지막에는 JS와 html5 canvas로 구현한 코드를 첨부했다.

 테스트할 사각형들은 미리 무작위로 생성해놓았다.




Shelf 알고리즘

 가장 간단한 해결방법은 Shelf(선반) 알고리즘을 사용하는 것이다. 평행한 선반 위에 물건(이하 아이템)을 올려놓듯이 순서대로 배치하는 것이다. 아이템의 배치 순서를 결정할 때  다양한 휴리스틱(heuristic)들을 적용할 수 있다.


목차

1. Next Fit

2. Smaller Height First

3. Lager Height First

4. Rotate - 회전하기

5. Shelf 알고리즘의 한계

6. Javascript 코드



1. Next Fit

 아이템들을 특별한 기준 없이 순서대로 배치한다. 좌측 상단부터 시작하여 오른쪽으로 아이템들을 배치해나가다가 오른쪽 변에 다다르면 그 층(row)의 최대 높이만큼 내려서 배치한다.

아래 그림과 같이 상당히 비효율적인 것을 확인할 수 있다. 

그림1


의사코드로 작성해 보면 아래와 같다.

nextPos = {x:0, y:0}

for i from 0 to items.length

    if(nextPos + items[i].width > spaceWidth)

        nextPos.x = 0

        nextPos.y += maxHeight

        maxHeight = 0; //reset

    end if

    if(nextPos.y + items[i].height > spaceHeight)

        break;

    end if

    /*allocating item*/

    /*finding a value of max height in this row*/

end for







2. Smaller height first


 넣을 아이템을 높이가 작은 순서대로 정렬한다.

시간복잡도가 O(nlogn)인 정렬 알고리즘으로 정렬한다면, 아이템 배치 부분은 O(n)이므로 총 시간복잡도는 O(nlogn)이다.

 이 테스트케이스에 크기가 더 큰 아이템들도 있지만 더 이상 넣을 공간이 없으므로 끝나게 되었다.

그림2







3. Lager height first


넣을 아이템을 높이가 큰 순서대로 정렬한다. 1.2에서 적재되지 못했던 아이템들을 볼 수 있다. 큰 순서대로 배치하였기 때문에 아래층에 넓은 공간이 남아버리게 된다.



따라서 높이가 맞지 않는 다음 아이템은 건너뛰고, 그 다음 아이템을 적재한다.

1번에 있는 의사코드를 다음과 같이 고칠 수 있다.

if(nextPos.y + items[i].height > spaceHeight)

    ++i;

end if

그림3

이제 아래쪽 빈 공간을 활용할 수 있게 되었다.




그러나 아직도 우측에 빈 공간이 남게 되는데, 아이템의 너비를 생각하지 않고

높이순으로만 정렬했기 때문이다. 

현재 층(row)에서 다음 아이템을 너비 때문에 넣지 못할 경우, 잠시 멈춰 두고 넣을 수 있는 아이템이 나올 때까지 순차탐색한다.  최악의 경우(아이템의 너비가 내림차순으로 정렬되어 있을 때 등)에는 이 때문에 시간복잡도가 O(n^2)가 된다.

다음 층로 넘어갔을 때는 공간이 많이 있으므로 멈췄던 인덱스부터 다시 배치를 시작한다.



배열을 탐색하면서 중간요소들을 지워야 하기 때문에 뒤에서부터 탐색하였다.

그래서 이번에는 items 배열을 높이가 작은 순서대로 정렬해두어야 한다. 

nextPos = {x:0, y:0}

i - items.length

while(i--)

    for j from i to 0

        if(nextPos + items[j].width >= spaceWidth)

            break

        end if

    end for

    if(j>0)

        j = i;

        nextPos.x = 0

        nextPos.y += maxHeight

        maxHeight = 0

    end if

    if(nextPos.y + items[j].height > spaceHeight)

        continue

    end if

    /*allocating item*/

    /*finding a value of max height in this row*/

    items.splice(j,1)

end while

그림4







4. rotate - 회전하기


3번에 있는 휴리스틱을 적용하면 채우기 효율이 매우 완벽해 보인다. 그러나 이런 경우도 있다.

그림5

이 포스트에서 구현한 선반 알고리즘은 높이에 관계없이 한 층 안에서 여러 개의 아이템을 쌓을 수 없기 때문에 위와 같이 두가지 아이템의 높이 차이가 많이 날 경우 빈 공간이 많이 남을 수 있다.


이 문제를 해결하기 위해 사각형을 회전할 수 있다.

현재 쓰고 있는 휴리스틱이 높이 순서 기반으로 되어 있기 때문에 너비가 높이보다 큰 사각형은

90도 돌려서 적재한다. 회전된 아이템은 파란색으로 표시하였다.

그림6

그림5에서 남았던 우측의 빈 공간들은 메워졌으나, 아이템이 수직으로 길게 되어버려서 이번에는 아래쪽 공간이 낭비된다.


 이 공간을 활용하려면 아래쪽 선반을 검사할 때, 회전한 아이템을 다시 원래대로 돌려야 한다.

위에 있는 의사코드에서 해당 부분을 수정했다.

if(nextPos.y + items[j].height > spaceHeight)

    if(items[j].w <= h-p.y)

        swap(items[j].w, items[j].h)

    end if

    else continue

end if

그림7


이제 두 가지 아이템의 크기가 다를 때 나타날 수 있는 문제도 해결된 것처럼 보인다!


한 가지 주의할 점은 회전을 쓸 수 없는 상황도 많다는 것이다. 이미지 리소스를 이 방식으로 저장해 두었다가 불러들일 때 적은 연산으로 다시 90도 복구할 수 없는 상황이라면 회전하지 않고 저장하는것이 더 나을 수도 있다.

그렇지만 OpenGL 등에서는 텍스쳐를 바인딩할 때 텍스쳐 좌표를 자유롭게 지정할 수 있으므로 문제가 되지 않는다. 저장할 이미지 리소스의 정보 파일에 x,y,w,h 및 회전 여부도 같이 저장해 두면 된다.





5. Shelf 알고리즘의 한계


4번까지의 결과를 보면 효율이 나쁠 수 있는 상황에서도 어느 정도 만족할 만한 해답을 이끌어낸 것 같다. 그러나 이 글에서 작성한 Shelf 알고리즘은 한 층 안에서 아이템을 수직으로 쌓을 수 없다는 결점이 있다.

가령 아래와 같이 사각형들의 크기차이가 심할 경우 그 차이만큼의 공간이 낭비될 수밖에 없다.

그림8


이 문제를 개선하려면 단순히 층을 나눠서 아이템을 적재하는 대신에

빈 공간에 대한 정보를 전체적으로 관리할 필요가 있다.

하지만 아이템의 크기가 다양하다면 빈 공간의 정보도 자잘하게 조각나서 매우 많아질 것이기 때문에 역시 문제가 된다.


다음 포스트에서 빈 공간의 정보를 최적화하는 Maxrects (Maximal rectangle) 알고리즘에 대해 알아본다! 



▽ Maxrects 알고리즘으로 그림8에서 사용했던 테스트케이스를 실행한 결과






6. Javascript code

이미지를 그리기 위해 작성한 자바스크립트 코드.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
<html>
    <meta charset="utf-8">
    <body>
    <canvas id="canvas1", width=256, height=256, style="border:1px solid #000000"></canvas>
    <script type = "text/javascript">
        var c = document.getElementById("canvas1");
        var ctx = c.getContext("2d");
 
        //var testCase = [11, 21, 43, 39, 13, 52, 35, 25, 28, 20, 66, 55, 54, 62, 50, 61, 49, 16, 60, 51, 39, 27, 54, 62, 65, 13, 34, 50, 48, 63, 19, 41, 18, 61, 23, 51, 39, 58, 35, 14, 35, 31, 67, 58, 25, 24, 58, 63, 59, 57, 69, 57, 34, 28, 61, 30, 18, 57, 10, 26, 42, 66, 31, 50, 63, 13, 42, 10, 57, 63, 61, 54, 50, 53, 20, 54, 66, 31, 48, 35, 28, 25, 37, 54, 32, 50, 42, 49, 62, 37, 31, 24, 63, 44, 66, 29, 25, 51, 52, 17, 67, 55, 27, 48, 23, 39, 38, 41, 46, 15, 46, 68, 24, 41, 38, 20, 33, 42, 12, 12, 51, 31, 53, 41, 25, 28, 39, 69, 61, 12, 55, 59, 35, 60, 13, 60, 22, 41, 60, 68, 28, 33, 31, 60, 27, 48, 38, 60, 19, 63, 28, 50, 24, 31, 42, 38, 11, 17, 50, 36, 27, 59, 42, 25, 16, 61, 35, 19, 32, 67, 40, 53, 33, 42, 15, 40, 62, 23, 42, 19, 57, 42, 43, 59, 12, 10, 45, 68, 16, 15, 15, 34, 67, 33, 27, 54, 53, 64, 18, 22];
        
        //var testCase = [20, 40,20, 40,20, 40,20, 40,20, 40,20, 40,20, 40,20, 40,20, 40,20, 40,20, 40,20, 40,20, 40,20, 40,20, 40,20, 40,20, 40,20, 40,20, 40,20, 40,40, 30,40, 30,40, 30,40, 30,40, 30,40, 30,40, 30,40, 30,40, 30,40, 30,40, 30,40, 30,40, 30,40, 30,40, 30,40, 30,40, 30,40, 30,40, 30,40, 30,16, 16,16, 16,16, 16,16, 16,16, 16,16, 16,16, 16,16, 16,16, 16,16, 16,16, 16,16, 16,16, 16,16, 16,16, 16,16, 16,16, 16,16, 16,16, 16,16, 16,36, 10,36, 10,36, 10,36, 10,36, 10,36, 10,36, 10,36, 10,36, 10,36, 10,36, 10,36, 10,36, 10,36, 10,36, 10,36, 10,36, 10,36, 10,36, 10,36, 10,10, 36,10, 36,10, 36,10, 36,10, 36,10, 36,10, 36,10, 36,10, 36,10, 36,10, 36,10, 36,10, 36,10, 36,10, 36,10, 36,10, 36,10, 36,10, 36,10, 36,6,15,6,15,6,15,6,15,6,15,6,15,6,15,6,15,6,15,15,6,15,6,15,6,15,6,15,6,15,6,15,6,15,6,15,6,15,6,15,6];
        
        //var testCase = [10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11];
 
        var testCase = [160,160,80,80,80,80,60,60,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10];
 
        //var testCase = [67,75,67,75,67,75,67,75,67,75,67,75,67,75,67,75,67,75,67,75,67,75,67,75,50,11,50,11,50,11,50,11,50,11,50,11,50,11,50,11,50,11,50,11,50,11,50,11,50,11,50,11,50,11,50,11,50,11,50,11,50,11,50,11,50,11,50,11,50,11,50,11,50,11,50,11,50,11,50,11,50,11,50,11];
 
        var numCase = testCase.length/2;
 
 
        var w = c.width;
        var h = c.height;
 
        var r = new Array();
        var s = new Array();
        for(var i = 0; i<numCase; i++) {
            r[i] = {};
            r[i].w = testCase[i*2];
            r[i].h = testCase[i*2+1];
            r[i].r = false;
 
            //rotation
            if(r[i].w > r[i].h) {
                var temp = r[i].w;
                r[i].w = r[i].h;
                r[i].h = temp;
                r[i].r = true;
            }
        }
        s.push({x:0, y:0, w:w, h:h, v:true});
 
        //sorting
        for(var i=0; i<numCase-1; i++) {
            for(var j=0; j<numCase-1-i; j++) {
                if(r[j].h > r[j+1].h) {
                    var temp = r[j];
                    r[j] = r[j+1];
                    r[j+1] = temp;
                }
            }
        }
        var u = 0; //used space
        var p = {x:0, y:0}; //next point
        var m = 0; //max height
        var i = r.length;
        var j;
        while(i--) {
            //find item for next column
            for(j=i; j>=0; j--) {    
                if(r[j].w <= w-p.x) {
                    break;
                }
            }
            //go to the next row
            if(j<0) {
                j=i;
                p.x = 0;
                p.y += m;
                m=0;
            }
 
            //find item for bottom of space
            if(r[j].h > h-p.y) {
                if(r[j].w <= h-p.y) {
                    var temp = r[i].w;
                    r[i].w = r[i].h;
                    r[i].h = temp;
                    r[i].r = false;                    
                } 
                else continue;
            }
 
            //draw
            var fillStyle;
            if(r[j].r) fillStyle = "#6699CC";
            else fillStyle = "#CC6699";
            drawRect(ctx, {
                x:p.x,
                y:p.y,
                w:r[j].w,
                h:r[j].h}, fillStyle);
            p.x += r[j].w;
            u += r[j].w*r[j].h;
            if(r[j].h>m) m=r[j].h;
 
            //remove item from array
            r.splice(j,1);
        }
        //efficiency
        var e = Math.floor(u/(w*h)*10000)/100; 
        ctx.font="20px Consolas";
        ctx.fillStyle = "#000000";
        ctx.fillText(e+"%",w-70,h-18);


function drawRect(ctx, rect, fillStyle) { ctx.beginPath(); ctx.rect(rect.x, rect.y, rect.w, rect.h); ctx.fillStyle = fillStyle; ctx.fill(); ctx.stroke(); }
    </script>
    </body>
</html>
cs







관련글

상자 채우기 (2D bin packing problem) - (1) Shelf 알고리즘

상자 채우기 (2D bin packing problem) - (2) Maxrects 알고리즘(1) 

상자 채우기 (2D bin packing problem) - (3) Maxrects 알고리즘(2) 










스포츠 경기 등의 리그전에서 각 팀이 다른 모든 팀과 한 번씩 경기를 치르는 것을 라운드 로빈(round robin)이라 한다. 이 리그의 한 주기 스케쥴을 짜는 것은 여러 방법이 있지만, 아래와 같은 방법으로 단순하게 해결할 수 있다.


http://www.sciencedirect.com/science/article/pii/S0166218X04001350

위 사이트의 내용을 참고하여 GIF 애니메이션 이미지를 만들어 보았다.



1. 팀 수가 홀수일 때

각 팀이 다각형의 꼭지점에 배치되어 있다고 생각하고, 수평으로 마주보고 있는 팀과 대전한다.

한 팀은 쉰다.(쉴 수밖에 없다.)

(GIF 애니메이션입니다.)





2. 팀 수가 짝수일 때

1에서 한 팀이 쉬는 대신, 나머지 팀과 대전하면 된다.

짝수 다각형을 사용하면 된다고 생각할 수도 있지만,

그렇게 하면 꼭지점 하나를 사이에 두고 있는 팀과의 대결이 성사되지 못한다.


(GIF 애니메이션입니다.)






3.

2번은 아래와 같이 팀이 이동한다고 생각할 수도 있다.

(GIF 애니메이션입니다.)






소스코드

3번을 C++코드로 작성해 보았다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <iostream>
#include <string>
#include <stdlib.h>
 
using namespace std;
 
 
int main(void)
{
    
    int *team_id;
    string team[] = { "Heros", "Eagles", "Dinos", "Lions", "Wiz",
                    "Twins", "Wyverns" ,"Tigers","Bears","Giants"};
    int numTeam = (sizeof team)/(sizeof string);
    team_id = (int*)malloc(numTeam*sizeof(int));
 
    for (int i = 0; i < numTeam; i++) {
        team_id[i] = i;
    }
 
    for (int i = 0; i < numTeam - 1; i++) {
        cout << i + 1 << "일차" << endl;
        for (int j = 0; j < numTeam/2; j++) {
            cout << team[team_id[j]] << ":" << team[team_id[numTeam-j-1]] << endl;
        }
 
        for (int j = 0; j < numTeam - 1; j++) {
            team_id[j] = (team_id[j] + 1) % (numTeam - 1);
        }
 
        cout << endl;
    }
    
    return 0;
}
cs




출력결과


1일차
Heros:Giants
Eagles:Bears
Dinos:Tigers
Lions:Wyverns
Wiz:Twins

2일차
Eagles:Giants
Dinos:Heros
Lions:Bears
Wiz:Tigers
Twins:Wyverns

3일차
Dinos:Giants
Lions:Eagles
Wiz:Heros
Twins:Bears
Wyverns:Tigers

4일차
Lions:Giants
Wiz:Dinos
Twins:Eagles
Wyverns:Heros
Tigers:Bears

5일차
Wiz:Giants
Twins:Lions
Wyverns:Dinos
Tigers:Eagles
Bears:Heros

6일차
Twins:Giants
Wyverns:Wiz
Tigers:Lions
Bears:Dinos
Heros:Eagles

7일차
Wyverns:Giants
Tigers:Twins
Bears:Wiz
Heros:Lions
Eagles:Dinos

8일차
Tigers:Giants
Bears:Wyverns
Heros:Twins
Eagles:Wiz
Dinos:Lions

9일차
Bears:Giants
Heros:Tigers
Eagles:Wyverns
Dinos:Twins
Lions:Wiz







두 직사각형이 평면상에 놓여져 있을 때 아래와 같이 7가지로 나누어 생각해 볼 수 있다.





회색 사각형을 기준으로

1. 한쪽 귀퉁이를 덮음

2. 한 변을 덮음

3. 자신의 한 변이 모두 덮임

4. 교차

5. 자신이 포함됨

6. 다른 사각형을 모두 덮음

7. 겹치지 않음



각각의 경우를 나누어 처리할 수도 있으나

1~6의 겹치는 영역(직사각형)을 보면 모두 공통적인 특징이 있다.


겹치는 영역(Intersection)의

왼쪽 변은, 기존 두 사각형의 왼쪽 변 중에서 더 오른쪽에 있는 것

오른쪽 변은, 기존 두 사각형의 오른쪽 변 중에서 더 왼쪽에 있는 것

위쪽 변은, 기존 두 사각형의 위쪽 변 중에서 더 아래쪽에 있는 것

아래쪽 변은, 기존 두 사각형의 아래쪽 변 중에서 더 위쪽에 있는 것

이 된다는 것을 확인할 수 있다.


화면 좌측상단이 원점인 좌표계를 기준으로  코딩할 때 사각형 구조체를 x, y, width, height로 정의한다면, 겹치는영역의

(왼쪽 변) x는 기존 두 사각형의 x중에서 큰 것
(오른쪽 변) width는 기존 두 사각형의 x+width 중에서 작은 것 - x좌표

(위쪽 변) y는 기존 두 사각형의 y중에서 큰 것

(아래쪽 변) height는 기존 두 사각형의 y+height 중에서 작은 것 - y좌표

으로 하면 된다.


-x, -y 가 붙어있는 이유는 해당 속성이 각각 너비와 높이이기 때문.



아래는 Javascript 코드로 작성해 본 것이다.


function getIntersection(r1, r2)
{
    if(r1.x > r2.x+r2.w) return null;
    if(r1.x+r1.w < r2.x) return null;
    if(r1.y > r2.y+r2.h) return null;
    if(r1.y+r1.h < r2.y) return null;

    var rect = {};
    rect.x = Math.max(r1.x, r2.x);
    rect.y = Math.max(r1.y, r2.y);
    rect.w = Math.min(r1.x+r1.w, r2.x+r2.w)-rect.x;
    rect.h = Math.min(r1.y+r1.h, r2.y+r2.h)-rect.y;

    return rect;
}

코드를 보면 두 사각형이 겹치지 않은 경우를 걸러내는 부분이 추가되었다.








이 문제에 대해 조금 다르게 생각해 볼 수도 있는데,

너비가 w이고 높이가 h인 screen이 있을 때

임의의 점에 대하여

그 점이 screen 안에 있을 때는 그대로 표시하고,

screen 밖에 있을 때는 screen의 안쪽 변 끝에 두는 간단한 식이 있다.


x' = min(w, max(0, x))

y' = min(h, max(0, y))


이 식을 한 사각형의 4 꼭지점(초록색)에 각각 적용한다면,

두 사각형의 겹치는 부분이 만드는 새로운 사각형의 4 꼭지점(파란색)을 얻을 수 있다.







연관글 :

자바스크립트로 구현한 결과는 여기에 올림.














+ Recent posts

티스토리툴바