나는 공간 데이터를 저장할 좋은 기능적 데이터 구조를 찾고있다. 데이터 구조는 이미 존재하는 포인트에 대한 간단한 엡실론 쿼리를 허용해야합니다. 또한 데이터를 자주 수정해야합니다. 즉, 포인트가 움직일 수 있고 데이터 구조에서 포인트를 업데이트 할 수 있어야합니다. 이것은 보통 정상 삭제/추가를 사용하여 처리 할 수 있지만 실제 이동은 더 빠를 수도 있습니다.공간 데이터를위한 데이터 구조
현재로서는 quad/oct-trees (이상)을 사용하려고 생각하고 있습니다. 이동 부분은 매우 쉽게해야하기 때문입니다. 그러나 균형을 고려할 때 쿼드 트리는 더 나쁜 것으로 알려져 있습니다. KD-Trees이 다른 선택 일 수도 있지만 업데이트가 상당히 불쾌한 것처럼 보입니다. 또한 찾을 수있는 대부분의 공간 데이터 구조 구현은 절차 적이며 함수 언어를 사용하고 있습니다.
사용 방법에 따라 점이 빨리 이동하기 때문에 sweep and prune을 고려할 수도 있습니다. 기본적으로 포인트를 한 차원 (예 : x)으로 정렬합니다. 포인트가 장소를 거의 변경하지 않으면 모든 시뮬레이션 단계에서 삽입 정렬을 실행하는 것이 실제로 매우 빠릅니다.
는
R-Trees 및 R * -Tree는 구현하기 쉬운 또 다른 솔루션입니다.
예를 들어 https://github.com/mariusaeriksen/ocaml-rtree (OCaml)을 참조하십시오.
대피 시뮬레이션에서 사용 했으므로 업데이트 단계가 그렇게 느리지는 않습니다. 또한 삽입과 삭제 진행 자체의 균형을 수있는 쿼드 트리 - 오버 마스와 밴 Leeuwen에 의해
꽤 잘하는 것 같지만 여기에서 일하기 위해서는 몇 가지 문제를 해결해야했습니다. 도와 주셔서 감사합니다... – LiKao
This old paper는 의사 쿼드 트리에 대해 설명합니다. 할부 상환 비용은 O(log^d(n))과 비슷하며 균형 조정 금액과 상환 될 수 있습니다 (자세한 내용은이 백서에서 읽을 수 있습니다).
명확히하기 : 주어진 점의 지정된 거리 내에있는 점을 찾기 위해 엡실론 쿼리를 쿼리합니까? – aneccodeal