회선에 대한 공간 인덱스

Question

나는 많은 선분 (벽, 천장 및 바닥과 같은 다양한 표면을 나타냄)이 있습니다. 플레이어의 경계 상자 안에있는 선을 효율적으로 결정하고 싶습니다.

(지금은 모든 라인을 순환하고 있지만 정확한 것은 있지만 너무 느립니다).

Javascript에는 여러 kd 트리 및 기타 공간 인덱스가 있지만 모두 점이 아닌 점을 저장합니다.

실제로는 x 축만 쿼리하면됩니다. 그것은 일종의 1D 범위 트리로 충분할 것입니다.

선과 같은 도형을 효율적으로 저장하고 검색하려면 어떻게해야합니까?

일단 빌드되면 인덱스가 추가되지 않습니다. 당신은 전체 공간 확장을 통해 좋은 제어 할 수 있습니다 단지 2 차원에서

Answer 1

은 (즉 최소 및 최대를 알고, 이러한 증가하지 않습니다), 그리드 등의 일반 그리드 또는 쿼드 트리로 접근 방식은 매우 잘 작동을 기반으로. 특히 쿼리 반경 (플레이어 상자 크기)을 알고있는 경우 정확하게이 크기의 격자가 일 것입니다.

많은 게임에서는 이진 공간 파티셔닝 트리 인 BSP 트리를 사용했습니다. 그러나 좋은 성능을 위해,이 나무는 보통 AFAIK가 레벨이 만들어지면 미리 계산 된 다음지도로로드됩니다.