2012-11-19 11 views
3

k-d trees에 대한 위키 백과 항목을 보면 2D 공간을 직사각형으로 나누는 점과 평면으로 구성된 illustration이 표시됩니다.k-d 트리에서 사각형 집합을 얻으려면 어떻게해야합니까?

제 질문은 어떻게 결과 집합의 사각형을 얻습니까? 나는 잎 노드에 대한 각각의 '경로'가 내게 경계를 줄 것이라고 생각했다. 임의의 깊이에서 N 포인트에 대해이 작업을 수행하는 일반적인 방법이 있습니까?

내가 입력하지 않은 것은 hyperrectangle 구조의 kd 트리입니다. 주어진 입력은 범위 검색 등을 위해 쿼리 할 수있는 사각형 집합입니다. 입력은 임의의 점 집합이며, 직각 좌표계를 'tesselate'하거나 세분화하는 사각형 세트를 출력하고 싶습니다.

+0

여기에 2 가지 질문이있는 것 같다. 임의의 점 집합으로부터 k-d 트리를 생성하는 알고리즘을 찾고 있습니까, 아니면 k-d 트리가 주어지면 분할 사각형 집합을 열거하는 알고리즘을 찾고 있습니까? 아니면 둘다? – eh9

+1

k-d 나무는 일반적으로 직사각형을 저장하지 않으며 분할 축을 저장합니다. 간단히 말해서, 각 노드가 분할 축을 따라 자르는 2D 직사각형에서 기본적으로 통과하는 작은 사각형 분할 코드를 작성하여 2 개의 새로운 rect를 자식에게 보냄으로써 이것을 구현할 수 있습니다. – Jerdak

답변

0

감사합니다. eh9를 편집하십시오. 입력이 임의의 점 집합으로 구성된 k-d 트리임을 명확히하기 위해 출력은 결과로 생성 된 사각형 세트입니다.

'사소한 해결책'을 위해 Jerdak에게 감사드립니다. 실제로 루트 노드에서 트리를 걸어 내려 가서 각 축 깊이에서 분할 사각형을 유지하십시오. 유일한 추가 정보는 원래 사각형의 바깥 경계입니다. 모든 노드를 방문하면 전체 집합을 반환 할 수 있습니다.

0

많은 kD 트리가 실제로 각 하위 트리/리프의 경계 하이퍼 멘트를 저장하므로 더 나은 정리가 KNN 검색에서 수행 될 수 있습니다. 이 공간들은 모든 공간을 덮는 직사각형이 아니며 점이없는 곳 사이에 틈을 남겨 둡니다. 개인적으로 나는 그들이 더 시원하다고 생각한다 ;-)