데이터 구조는 N 포인트의 주어진 집합을 전처리하고 쿼리 병렬 스트립 출력 모든 지점은 스트립 내에 누워

Question

주어진 N 개의 병렬 처리와 같은 N 개의 주어진 포인트를 사전 처리하는 알고리즘을 설계하도록 요청 받았다. 스트립 내에 모든 포인트가 출력되도록 스트립합니다.

알고리즘을 디자인하려고했지만 쿼리를 개별적으로 해결할 수만 있습니다.

어떤 데이터 구조를 사용하고 N 포인트를 사전 처리하여 사전 쿼리를 쉽게 처리 할 수 ​​있는지 알지 못합니다.

나는 그것을하는 방법과 복잡성에 대한 아이디어가 필요합니다.

Answer 1

이러한 문제를 해결하는 일반적인 방법은 bounding volume hierarchy을 사용하는 것입니다.

상자에 점을 채우고 큰 상자에 상자를 넣는 것을 생각하십시오. 큰 상자 중 하나가 전체적으로 바깥쪽에 있으면 체크 할 필요가 없습니다. 그러나 스트립 내부에 있으면 내부에있는 것을 살펴 봐야합니다. 내부에있는 상자에 스트립에없는 상자가있는 경우 해당 상자의 내용도 확인할 필요가 없습니다. 물론, 열쇠는 상자를 포장하여 일반적으로 많은 하위 상자와 점을 건너 뛸 수 있습니다.

(모든 BVHs이 상자를 사용합니다 -. 일부 사용 분야, 일부 사용 simplices, 일부는 다소 괴상 분할을 사용하지만 대부분의 사용 상자를)

R-trees

큰 데이터베이스의 2D 응용 프로그램에 대한 인기 있습니다. space partitioning 구조 (BVH의 전문화 정도는 다소 차이가 있음)를 사용할 수도 있습니다. K-d 트리 (공간 분할 유형)에 이미 많은 라이브러리가 있기 때문에 그렇게 할 수 있습니다.

는

은 아무리 당신이 결국 어떤 구조, 최상위 알고리즘은 동일하게 유지되지 않습니다 :

# This algorithm could be implemented with a stack or recursively 
# instead of maintaining a potentially very long list of nodes. 
nodes = { top_level_node } 
loop while there are nodes left to process 
    set node = first element of nodes 
    remove node from nodes 
    if node does not intersect strip continue loop 
    if node directly contains points that are within the strip add them to the output 
    if node directly contains subnodes that intersect the strip add them to nodes 
end loop 

를 사용하는 구조에 따라, 크기의 고정 번호는 일반 작동 될 것으로 예상 할 수있다 O(o log n) 여기서 n은 총 포인트 수이고 o은 스트립 내의 포인트 수입니다. 이 다소 단순한 알고리즘은 O(o) 메모리를 사용하지만, 스택이나 재귀가 사용되는 경우에는 O(log n)을 대신 사용할 수 있습니다.

Box2D 물리 엔진은 2D BVH 구현을 상당히 쉽게 사용할 수 있습니다. (라이센스는 매우 관대하게 보인다.) 어느 시점에서 Box2D의 BVH는 Bullet에 기반을 두었습니다 (여전히있을 수 있습니다). Bullet 물리 엔진은 이전에 2D로 변환 한 3D BVH 구현이 있으며 zlib (매우 허용적인) 라이센스가 있습니다. 실시간 물리 엔진의 문제점은 일반적으로 최적의 트리를 얻는 데 관심이 없다는 것입니다. 최적의 트리가 필요하지 않기 때문에 몇 밀리 초 내에 "가능한 한 좋은"방법에 관심이 있습니다. 그러나, 그들은 당신의 목적을 위해 충분히 좋을 수도 있습니다.

Rosettacode 심지어 K-d tree entry을 가지고 -하지만 이러한 항목이 덜 잘 사용하는 라이브러리보다 테스트 할 예상대로 마일리지가 다를 수 있습니다 (저는 믿습니다 같은 FLANN는 가와사끼 트리가 포함되어 있습니다.)