2DTile

2D 지도에서 도형이 주어질 때, 도형이 어떤 타일에 속하는지 구함

문제 예시

왼쪽 밑 부터 0번 타일이라고 가정하면 다음과 같다.

(x, y)는 타일의 왼쪽 밑의 좌표 값이다.

2(0,1)  3(1,1)
0(0,0)  1(1,0)

주어진 도형은 다음과 같다.

레벨 0 타일 에서는, 도형이 1번 타일을 덮으므로, lv0-1-0(1번 타일)을 리턴한다. (레벨 0타일, x: 1, y: 1)

그러나 나머지가 존재하므로, 0과 3번 타일을 각각 4타일씩 나눈다. 그리고 타일의 레벨은 1 증가한다.

이제, 우리는 0, 3번 타일에 각각 4타일 씩, 총 8타일을 조사한다.

이것을 x, y 좌표, 타일 번호를 매기면 다음과 같다.

22(0,1.5)   23(0.5,1.5) 32(1,1.5)   33(1.5,1.5)
20(0,1)     21(0.5,1)   30(1,1)     31(1.5,1)
02(0,0.5)   03(0.5,0.5) 12(1,0.5)   13(1.5,0.5)
00(0,0)     01(0.5,0)   10(1,0)     11(1.5,0)

도형이 01번 타일(x: 0.5, y: 0), 31번 타일(x: 1.5, y: 1)을 덮으므로, (lv1-0.5-0), (lv1-1.5-1)을 리턴한다.

역시나 나머지가 존재하므로, 30번 타일(x: 1, y: 1)을 4타일로 나눈다.

30번 타일(x: 1, y: 1)은 다음과 같이 된다. (나머지 타일들은 생략)

302(1,1.25) 303(1.25,1.25)
300(1,1)    301(1.25,1)

도형이 301번 타일(x: 1.25, y: 1)을 덮으므로, lv2-1.25-1을 리턴한다.

마침내 우리는 도형을 덮는 모든 타일들을 찾아냈다. 따라서 알고리즘을 종료한다.

문제 정의

레벨 0 타일은 총 50개의 타일(0\~9, 0\~4)이 존재한다. 또한 레벨은 15까지 있다.

레벨이 증가함에 따라, 각 타일은 4개의 작은 타일들로 분할할 수 있다.

(레벨 1의 총 타일 수는 레벨 0타일의 4배, 50*4 = 200개)

그리고 점의 집합이나 리스트가 주어지면, 그것은 도형으로 만들 수 있다.

또한 레벨 0에서, 도형이 레벨 0 타일의 어떤 것이라도 정확히 포함하면, 어딘가에 그 정보를 저장하고 나머지에 대해 계산한다.

만약 도형이 불완전하게 레벨 0타일을 덮는다면, 레벨 1을 증가시키고, 그 타일은 4 타일로 분할된다.

그리고 도형이 타일을 다 덮을 때까지 비교하고 진행한다.

저장할 정보는 타일의 x, y 좌표, 그리고 레벨이다(LVn-x-y)

어떤 타일이 도형을 덮는지 어떻게 계산할 것인지?

제한된 범위의 직선의 방정식과 그의 교점을 통해 계산할 것이다.

(2018. 12. 03) 타일은 네 꼭지점으로 이루어져 있다.

P3(x, y+n)      P4(x+n, y+n)
P1(x, y)        P2(x+n, y)

특정 타일이 도형 안에 있는지 판별하는 것은, 이 네개의 점이 도형 안에 있는지 검사하면 된다.

이 방법은 Ray Casting을 사용하여 검출한다.

하지만 특정 모양에서는 이 방법에 문제가 있는데, 도형의 변과, 타일의 네 꼭지점으로 이루어진 선분끼리 교점이 있는지 비교한다.

대략적인 알고리즘은 다음과 같다.

*(레벨 0)*
while(레벨 0의 모든 타일에 대해)
    if(레벨 0 타일의 4 꼭지점이 도형 안에 있지만,
    4 꼭지점으로 이루어진 선분들이 도형 변에 하나라도 겹쳐진다면)
        타일을 4분할 하고, 레벨을 1 증가시키며, 큐에 넣는다.
    else if(위의 if문에 걸리지 않고 타일의 4 꼭지점에 도형 안에 있다면)
        해당 타일을 결과 리스트에 추가한다.
    else if(네 점으로 이루어진 선분이 하나라도 도형의 변에 걸친다면)
        타일을 4분할 하고, 레벨을 1 증가시키며, 큐에 넣는다.
    // else가 없음에 주의하라

*(레벨 1이상)*
while(큐에 아이템이 있을 때)
    타일 = 큐에서 아이템 하나를 빼낸다.

    if(현재 타일의 레벨이 16이상이면) 
        continue
    타일의 네 꼭지점을 구한다.

    if(현재 타일의 4 꼭지점이 도형 안에 있지만,
    4 꼭지점으로 이루어진 선분들이 도형 변에 하나라도 겹쳐진다면)
        타일을 4분할 하고, 레벨을 1 증가시키며, 큐에 넣는다.
    else if(위의 if문에 걸리지 않고 타일의 4 꼭지점에 도형 안에 있다면)
        해당 타일을 결과 리스트에 추가한다.
    else if(네 점으로 이루어진 선분이 하나라도 도형의 변에 걸친다면)
        타일을 4분할 하고, 레벨을 1 증가시키며, 큐에 넣는다.
    // else가 없음에 주의하라

여기서 볼 수 있듯이, 레벨 0에서는, brute force방식을 통해, 50개의 타일을 모두 검사한다.

그리고 나눌 타일에 대해서만 연산이 진행된다.

참고

Flood Fill (이 문제에 대해선 딱히 좋은 방법은 아닌 것 같음)
QuadTree (이 아이디어를 이용하긴 했음)
Ray casting algorithm(Detect point in polygon)
Convex hull (도형을 만들 때, 이 방법을 통하면 넓이를 최대화한 도형을 얻을 수 있음)

QuadtreeUI

완벽하지 않은 쿼드트리의 가시화(버전 1)

쿼드트리를 수정했으나, 좀 더 수정할 것이 남아 있습니다.

2018.12.11) 분홍색 타일의 경우, 점 네개는 도형에 포함되어 있지만 초록색 타일로 인식되면 안 됩니다.

이 곳을 참조하여 에러를 고쳤습니다.

이전에는, 분홍색 타일이 초록색 타일로 인식되었었는데 이제는 그렇지 않게 되었습니다.

honeycam 2018-11-23 20-41-37

2018.11.23) 드디어 이 일을 끝낸 것 같습니다(2018. 11. 23).

위의 그림에서 각각의 타일은 레벨에 따라 다른 색깔로 표시됩니다.

15레벨까지 표현되는 것을 원했으나, 제 컴퓨터에서 11레벨만 넘어가도 컴퓨터가 도형을 표현하는데 시간을 오래 잡아먹습니다.

또한, 쿼드 트리를 구현은 했지만 그 코드 자체는 필요가 없었습니다(물론 이 아이디어 자체는 좋았고, 참고할만 했음).

도형을 만드는데, 컨벡스 헐 알고리즘을 사용하지 않았습니다.

만약에 컨벡스 헐을 사용하여 주어진 점에서 최대 넓이를 갖는 도형을 만들기 원한다면, Point 클래스 코드를 수정하여 점들의 집합을 재구성하면 됩니다.

XDOErrorDectectorUI

이 프로그램은 DAT, XDO 내부의 데이터와 DAT파일이 참조하는 XDO 파일, 그 XDO가 참조하는 텍스쳐 파일들을 체크하고 그 결과를 가시화해줍니다.

DB(PostgreSQL을 사용하는)에 연결하기 위해 정보를 입력할 수 있습니다. 만약 성공적으로 연결되었다면, 접근하고 싶은 테이블을 정할 수 있게 됩니다.

입력한 테이블 이름을 만들거나, 삭제하거나, 초기화할 수 있습니다.

테이블 불러오기(Load Table):

DB에서 데이터를 불러와 리스트 뷰에 추가합니다.

검색 및 DB에 저장(DAT, XDO Search & Save at DB):

프로그램이 주어진 폴더에 대해 재귀적으로 DAT, XDO 파일을 검색합니다.
프로그램이 DAT, XDO 파일을 파싱하고 그에 해당하는 텍스쳐 에러, 참조하는 파일 유무를 할 것입니다. 또한 쓰이지 않는 텍스쳐에 대해서도 기록합니다.
그 이후에, 결과들을 DB에 저장합니다.

rlaehgns5399 / 2DTile