길버트의 C#/XAML

바로 전 포스트에서 QuadTree가 데이터에 따라 어떻게 분화되는지를 보여드렸는데요, 이번엔 QuadTree를 이용한 Search를 테스트하기 위해서 만들어 본 데모입니다. QuadTree를 통해서 검색을 하면 QuadTree Leaf Node의 Boundary들과 검색 영역을 먼저 비교하여 내부 노드로 더 깊숙히 들어가야 할지 말지를 미리 결정하기 때문에, 전체 데이터를 모두 순회하면서 데이터들을 검색 영역과 비교하는 방법에 비해서 상당히 매력적인 자료구조입니다. Live Demo Mouse 왼쪽버튼 클릭 - 데이터 1개 추가 Random 버튼 - 한 번 누르실 때 마다, 임의의 위치에 200개 데이터가 추가됩니다. 화면 Drag - 선택 영역을 설정합니다. 선택 영역을 변경할 때마다, QuadTre..

제가 예전에 QuadTree에 대해서 간략하게 소개한 적이 있는데요, 아래 데모는 제가 만든 QuadTree 라이브러리를 테스트 하기 위한 용도로 만들어 본 것입니다. Threshold를 5로 지정해 놓아서 몇 번만 클릭하셔도 QuadTree가 분화되는 것을 체험하실 수 있습니다. QuadTree는 재귀적(Recursive)으로 구성되는데, 하나의 QuadTree 잎(Leaf) Node가 보유하고 있는 데이터 수가 Threshold 값을 넘어가면, 다시 4장의 잎(Leaf) Node 와 X줄기 Node, Y줄기 Node로 분열하면서, 데이터를 나누어 갖습니다. Live Demo Mouse LeftButton 클릭을 통해서 체험해 보시기 바랍니다. 이렇게 만들어지는 QuadTree는 2차원 상에 분포된 객..

지도, Deep Zoom 등 2차원 솔루션에서, 정보의 구축과 검색을 원활히 하기 위해서, QuadTree 형식의 자료 구조가 구현되는 것이 바람직합니다. 예를들면 방대한 영역에 존재하는 데이터 중, 보이는 화면영역에 해당하는 데이터만 빨리빨리 찾아와야 할 때 유용합니다. QuadTree는 4개의 자식을 갖는 트리구조입니다. 평면을 계속 4분할해 나가면서 트리가 구성됩니다. 1개의 Cell은 maximum capacity를 가지고 있어서, 그 값이 넘게 자식이 존재해야할 필요성이 있을 때 또 분할됩니다. 수직선, 수평선이란 자식까지 정의하여 총 6개의 자식을 갖도록 설계하는 경우도 있습니다. (CAD/CAM 프로그래밍 할 때 그렇게 했었음.) 한번 이렇게 구성된(Build) QuadTree는 영역에 대한..