버그 해결을 위한 모든 질문을 던져
0 votes
79 views
쿼드트리를 구현하고 싶은데 막막합니다...

제가 이해한 바에 따르면

노드에 물체(?)가 포함돼 있으면 4개의 작은 공간으로 재귀적으로 분할해가면서

최대 깊이에 도달하면 물체가 포함된 노드와 포함되지 않은 노드를 구분해주면서 물체를 표현하는것 같은데

제가 이해한게 맞는지도 모르겠네요

 

일단 제가 궁금한건 그렇게 쿼드트리가 만들어질려면 오브젝트 객체(?)를 읽어야 되는거 같은데

그 오브젝트 객체는 2차원 배열이여야 하나요?
asked (2 point) , 79 views

1 답변

0 votes

쿼드 트리는 이차원 적으로 배열된 어떤 정보 필드를 빠르게 검색하는 방법론 중 하나로 이해하는게 맞지 않나 싶습니다.

여기서 중요한 것은 이차원 적으로 구성된 정보를 빠르게 검색하는 데에 있지 검색이 가능한가 불가능한가를 논하는 문제는 그 이전의 문제라는 얘기이지요.

이게 무슨말인가 싶을 수 있는데 질문자 님께서 질문하신 오브젝트 객체를 읽어야 하는 데 라는 조건이 바로 이 영역의 문제라는 얘기입니다.

쿼드트리는 결국 어떤 필드위의 점 (x, y)의 위치에 오브젝트가 올라가 있는가를 빠르게 알아보는 방법이지 (x, y) 위치에 오브젝트가 있는지 아닌지에 대한 정보를 구성하는건 쿼드트리를 구성하는데 필수적으로 요구되는 사항이라는 뜻이죠.

오브젝트 객체가 2차원 배열로 존재하든 1차원 배열로 존재하든 그것은 중요하지 않구요. 일단 임의의 점 (x, y)에 오브젝트가 있는지 없는지 판단이 가능한 형태로 데이터가 구성되어 있기만 한다면 어쨌건 쿼드 트리를 구성할 수는 있습니다.

말마따나 모든 오드젝트를 매번 loop로 돌면서 체크하는 위치와 겹치는지를 일일이 비교하는 방법으로도 체크는 가능하니까요.

여타 구성하는 배경 문맥이나 환경이 고려되어야 할 것이라 어차피 상황에 맞게 구성해야 하겠지만 그런걸 모두 제외하고 단순히 물어보신다면 저는 (x, y) 좌표값을 키로 하는 map이나 set을 구성해서 쿼드트리 빌드를 진행할 것 같네요.

*수정합니다. 

쿼드트리의 빌드에는 영역 단위의 intersection 체크가 필요하니 그냥 위에서 언급한 loop체크가 나을지도 모르겠네요. 상황을 봐야 알 것 같습니다.

answered (274 point)

버그 해결을 위해 도움을 구하고, 도움을 주세요. 우리는 그렇게 발전합니다.

throw bug 는 프로그래밍에 대한 전분야를 다룹니다. 질문,논의거리,팁,정보공유 모든 것이 가능합니다. 프로그래밍과 관련이 없는 내용은 환영받지 못합니다.

610 질문
772 answers
731 댓글
118,370 users