움직이는 구에 포함 된 모든 점의 집합을 찾으십시오.

Question

저는 3 차원 공간에 수천 개의 희소 한 점으로 구성된 P과 고정 된 반경으로 움직이는 구체 S을 가지고 있습니다. 매 순간마다 t은 구체 (球)가 차지하는 공간의 볼륨 인 S_t을 알고 있습니다. 나는 어느 방향으로 S가 다음에 움직일 것인지 미리 모른다. S_t에 포함 된 모든 점수의 하위 집합 Q_t을 어떻게 찾을 수 있습니까? 다음과 같이

나는 할 생각 :

1. 는 R-트리에있는 모든 점을 넣고 계산 Q_0

2. 을 모든 t> 0의 경우, 계산 상대적 보완

   N_t = S_t \ S_(t-1) 및 M_t = S_(t-1) \ S_t

3. 그런 다음 상대 보완 물인 P(N_t)과에 포함 된 모든 점을 R- 트리에 쿼리합니다

   Q_t = Q_(t-1) + P(N_t) - P(M_t)

이 일을합니까 :

마지막으로, 나는 같은 결과를 업데이트? 이것을 계산하는보다 효율적인 방법이 있습니까?

또한 효율적으로이 문제를 해결할 수있는 라이브러리가 있습니까?

Answer 1

포인트를 kD 트리 (k = 3)에 저장하고 고정 반경 근처 인접 검색을 수행합니다.

작은 증분을 활용하고 이전 위치를 사용하여 한 위치에 대해 해결하려는 전략이 실제로 지불하게 될지 확신하지 않습니다.