간단한 사각형의 세계를 어떻게 색인화해야합니까?

Question

세계는 비슷한 크기의 많은 (1k-10k) 사각형으로 이루어져 있으며 새 사각형을 추가 할 때 잠재적 인 중복을 빠르게 판별 할 수 있어야합니다. 사각형이 동적으로 추가되고 제거됩니다. R-Trees는 여기에 적합한가? 그렇다면 고려해야 할 좋은 라이브러리가 있습니까? (나는 어떤 언어로든 제안에 개방적이다.)

Answer 1

R-Trees가 적합합니다.

quad trees은 2D 공간 영역에서 객체를 빠르게 찾을 수있는 좋은 데이터 구조이기도합니다. 그것들은 정말로 더 균일 한 r-tree 버전입니다. 이러한 구조를 사용하면 대용량 데이터 세트를 사용하는 경우에도 테스트가 거의없이 공간의 작은 영역을 빠르게 활용할 수 있습니다.

나는 그것을 보지 않았지만 C# 구현 here가 있습니다.

이러한 종류의 데이터 구조 (및 그것의 3D 버전은 Octrees)는 게임에서 충돌 테스트를 위해 다른 객체 근처에 있는지를 알아야하는 대용량 데이터 세트를 관리하는 데 종종 사용됩니다. 재미있는 이유.

당신은 또한 kd-trees를 찾아 볼 수 있습니다 gamasutra 및 opengl.org

Answer 2

처럼 기사와 게임 산업 사이트의 데이터 구조, 이러한 종류의 예를 많이 찾을 수 있어야합니다.

구현 방법을 모르지만 3D에서는 적어도 Octrees보다 성능이 좋습니다. 예를 들어, 다음은 경험이 I just googled it 인 결과입니다.

성능 문제가있는 경우 쿼드 트리의 대안을 고려할 수 있습니다.

그러나 kd 나무는 균형을 맞추기가 어렵다는 점에 유의해야합니다.