QuadTree 검색 Live Demo

Silverlight/Experiment 2009.01.22 16:58

바로 전 포스트에서 QuadTree가 데이터에 따라 어떻게 분화되는지를 보여드렸는데요,
이번엔 QuadTree를 이용한 Search를 테스트하기 위해서 만들어 본 데모입니다.

QuadTree를 통해서 검색을 하면
QuadTree Leaf Node의 Boundary들과 검색 영역을 먼저 비교하여 내부 노드로
더 깊숙히 들어가야 할지 말지를 미리 결정하기 때문에
, 전체 데이터를 모두 순회하면서 데이터들을 검색 영역과 비교하는 방법에 비해서 상당히 매력적인 자료구조입니다.


Live Demo

Mouse 왼쪽버튼 클릭 - 데이터 1개 추가
Random 버튼 - 한 번 누르실 때 마다, 임의의 위치에 200개 데이터가 추가됩니다.
화면 Drag - 선택 영역을 설정합니다.

선택 영역을 변경할 때마다, QuadTree를 통해 검색하여 영역 내의 데이터를 하이라이트합니다.


(Threshold = 25 입니다.)

설정

트랙백

댓글

  • BlogIcon Joyh 2009.01.23 10:59 신고 ADDR 수정/삭제 답글

    우왕 신기해용
    근데 랜덤을 1번만 클릭하는건 몇번을 해도 균등하게 나눠지는데 2회 클릭하면 불균등하게 나눠지는군요..

    ..100번 쯤 누르니깐 뭔가 그림이 떠오르는 것 같아요! @.@

    • BlogIcon 길버트 2009.01.23 13:43 신고 수정/삭제

      Threshold가 25인 상태에서 첫 클릭에서 불균등하게 나뉘려면,
      어느 사분면인가는 25개 이하의 데이터만 존재해야 하는데, 확률상 그러기가 힘들지.

      100번 쯤 누르니깐... -> 그러지마~~ =_=;;

  • BlogIcon 리피 2009.01.31 15:57 신고 ADDR 수정/삭제 답글

    저 트리가 DB를 사용하지 않을경우 대용량 데이터를 처리할때 필요한거죠?

    • BlogIcon 길버트 2009.02.01 12:59 신고 수정/삭제

      DB 사용 유무와 관계없이 2차원 데이터를 다룰 때 유용합니다.
      예를 들어 지도 위에 친구의 위치를 표시해 주는 어플리케이션을 제작했을 경우,
      사용자가 보고 있는 지도 영역에 따라 계속해서 DB에 쿼리를 날려서
      결과를 가져오는 것 보다는,
      친구목록을 DB로부터 미리 가져와서 메모리 상에
      QuadTree를 빌드해 놓고,
      사용자가 지도영역을 변경함에 따라 그 영역에 맞는
      친구들을 빠르게 찾아내서 화면에 표시할 수 있죠.