k-d trees에 대한 위키 백과 항목을 보면 2D 공간을 직사각형으로 나누는 점과 평면으로 구성된 illustration이 표시됩니다.k-d 트리에서 사각형 집합을 얻으려면 어떻게해야합니까?
제 질문은 어떻게 결과 집합의 사각형을 얻습니까? 나는 잎 노드에 대한 각각의 '경로'가 내게 경계를 줄 것이라고 생각했다. 임의의 깊이에서 N 포인트에 대해이 작업을 수행하는 일반적인 방법이 있습니까?
내가 입력하지 않은 것은 hyperrectangle 구조의 kd 트리입니다. 주어진 입력은 범위 검색 등을 위해 쿼리 할 수있는 사각형 집합입니다. 입력은 임의의 점 집합이며, 직각 좌표계를 'tesselate'하거나 세분화하는 사각형 세트를 출력하고 싶습니다.
여기에 2 가지 질문이있는 것 같다. 임의의 점 집합으로부터 k-d 트리를 생성하는 알고리즘을 찾고 있습니까, 아니면 k-d 트리가 주어지면 분할 사각형 집합을 열거하는 알고리즘을 찾고 있습니까? 아니면 둘다? – eh9
k-d 나무는 일반적으로 직사각형을 저장하지 않으며 분할 축을 저장합니다. 간단히 말해서, 각 노드가 분할 축을 따라 자르는 2D 직사각형에서 기본적으로 통과하는 작은 사각형 분할 코드를 작성하여 2 개의 새로운 rect를 자식에게 보냄으로써 이것을 구현할 수 있습니다. – Jerdak