사각형이있는 k-d 트리

Question

주어진 포인트로 작업하는 k-d 트리를 구현했습니다. 예를 들어 트리에 점을 추가 한 다음 주어진 x, y 좌표에 가장 가까운 점을 찾을 수 있습니다.

예를 들어 사용자가 x와 y 좌표, 너비 및 높이를 제공하는 등 사각형으로 작업하려면이 기능을 확장하고 싶습니다. 그런 다음 범위 쿼리와이 구조에서 가장 가까운 이웃 검색을 수행 할 수 있기를 원합니다. 직사각형 데이터로 작업해야하는 현재 트리를 확장하는 방법은 무엇입니까?

Answer 1

K-d 트리는 저 차원 데이터에 적합합니다. 여러 점 (선, 직사각형 등)으로 구성된 것이면 R- 트리를 사용하는 것이 좋습니다.

Answer 2

나는 직사각형을 처리하기 위해 k-d 트리를 크게 확장한다는 것을 알고있다. 상자 정렬 알고리즘이라고하며 여기에서 찾을 수 있습니다 Box sort. 아이디어는 k-d 나무와 거의 같습니다. 이 신문은 파스칼에서도 구현되었지만 Java 로의 변환은 간단해야합니다.