Kd-Trees를 언제 사용합니까?

Question

나는 Kd-Trees에 관해 얼마전에 읽었으며, 그러한 데이터 구조가 유용 할 수있는 구체적/단순한 상황을 찾고있었습니다.

누구나 그런 예가 있습니까? 나는 기계 학습에 대한 특정 시점의 가장 가까운 이웃을 찾아 효율적인 방법으로 그들을 사용했습니다

Answer 1

감사합니다.

Answer 2

장면을 두 개의 상자로 나누기 위해 광선 추적에 사용됩니다. 광선이 경계 상자와 충돌하지 않으면 반드시 내용과 충돌하지 않기 때문에 충돌 속도가 빨라집니다.

Answer 3

VTK는 예를 들어 http://www.vtk.org/doc/nightly/html/classvtkKdTree.html입니다.

"FindClosestPoint"와 같은 기능을 살펴보십시오. 이 클래스는 많은 입력 지점이 주어지면 빌드하는 데 비교적 오랜 시간이 걸립니다. 그러나 나무가 만들어지면이 기능은 매우 빠르게 실행됩니다.

Answer 4

가격 프로젝트에 사용했습니다. 목표는 여러 기준과 일치하는 최적의 가격을 찾는 것이 었습니다.

Answer 5

파도에 의해 생성 된 스프레이를 통해 빛의 이동을 시뮬레이션하기 위해 kd 트리를 사용했습니다. 이로 인해 램프로 조명 된 스프레이뿐만 아니라 다른 물방울에서 나오는 간접 조명을 렌더링 할 수있었습니다. 나는 kd- 나무에 스프레이 포인트를 저장하고 kd- 트리를 사용하여 어떤 포인트가 서로 가까이 있었는지, 그리고 어느 물방울이 서로 비춰 졌는지 빠르게 찾았다. (사실, 좀 더 정교했지만 구조는 여전히 kd- 나무였습니다.) 이렇게하면 스프레이를 통해 멋진 빛을 낼 수있었습니다. 다음은 사용중인 방법에 대한 그림입니다. 빛 주위의 스프레이가 어떻게 흩어져있는 빛으로 빛나고있는 것은 아닙니다.