빠른 삽입으로 직사각형에 대한 공간 인덱스

Question

직사각형에 대한 인덱싱을 제공하는 데이터 구조를 찾고 있습니다. 직사각형이 화면 주위를 돌아 다니기 때문에 가능한 한 빨리 삽입 알고리즘이 필요합니다 (마우스로 직사각형을 새로운 위치로 드래그하는 것을 생각하십시오).

내가 R-나무, R + 나무, KD-나무, 쿼드 나무와 B-나무로하지만 내 이해 삽입에서 검토 한의는 일반적으로 느리다. 하위 선형 시간 복잡성에 삽입을 가지고 싶다면 누군가가 나열된 데이터 구조 중 하나에 대해 나에게 틀린 것을 증명할 수 있습니다.

I 직사각형이 시점에서 무엇을 위해 데이터 구조 (X, Y) 또는 어떤 직사각형 직사각형 (x, y, 폭, 높이)를 교차를 조회 할 수 있어야한다.

편집 : 나는 너무 빨리 삽입하려는 이유는 당신이 구형의 생각하면 화면을 이동하고 있기 때문에, 그들은 제거하고 다시 삽입해야 할거야입니다.

감사합니다.

Answer 1

당신이 언급하는 데이터 구조는 상당히 혼재되어 있습니다 : 특히 B-Tree는 빠르지 만 삽입 비용은 존재하는 항목 수의 로그로 증가하지만 속도는 향상되지 않습니다 교차로 쿼리

공간 데이터 구조는 두 부분으로 나뉩니다. 첫 번째 부분에서는 데이터에서 트리 구조를 만드는 방법을 설명합니다. 두 번째 부분에서는 각 노드에서 해당 노드 아래에 저장된 항목을 설명하는 정보를 추적하는 방법과이를 사용하여 쿼리 속도를 높이는 방법을 설명합니다.

일반적으로 트리를 작성하는 방법에 대한 (비싼) 아이디어를 사용하지 않고 각 노드에서 정보를 추적하는 것에 대한 아이디어를 집어 넣을 수 있습니다. 예를 들어 포인트의 좌표를 비트 인터리빙하여 각 사각형의 키를 만든 다음 B- 트리 또는 AVL 트리 또는 빨강 - 검정 트리와 같은 완벽하게 일반적인 트리 구조를 사용하여 각 노드에 정보를 보관하면서 실제로는 실제 데이터에서 구현하고 테스트 할 때까지는 알 수 없지만 실제로는 쿼리 속도를 충분히 높일 수 있습니다. 대부분의 계획에서 나무 건축 지침의 목적은 성능 보장을 제공하는 것입니다.

두 postscripts : 이것에 대한

1) 내가 좋아하는 패트리샤 나무 - 그들은 실행하는데 쉽게, 당신은 너무 많은 일이되지 않도록 항목을 추가하거나 삭제하면 훨씬 트리 구조를 방해하지 않습니다 노드에 저장된 정보를 업데이트합니다.

2) 마지막으로 창 시스템을 살펴본 결과,이 영리한 물건에 대해 전혀 신경 쓰지 않았습니다. 항목의 선형 목록을 유지하고 필요할 때 모든 방법으로 검색했습니다. 충분히 빠르다.

Answer 2

이것은 아마도 대답이 아닌 확장 된 설명 일 것입니다.

나는 당신이 정말로 원하는 것을 조금 혼란스럽게 생각합니다. 데이터 구조가 '사각형의 ID가 주어지면 현재 좌표를 반환합니다'와 같은 질문에 대한 빠른 대답을 지원하기를 원합니다. 그게 맞습니까?

또는 '어떤 직사각형이 위치 (x, y)에 있습니까?'라고 대답 하시겠습니까? 이 경우 디스플레이의 높이와 너비가 일치하는 크기의 배열이면 충분할 수 있습니다. 배열의 각 요소는 해당 픽셀의 직사각형 목록 (아마도 짧음)입니다.

하지만 당신은 당신이 사각형 끊임없이 이동에 대처하기 위해 가능한 한 빨리으로 삽입 알고리즘을 필요로 상태. 화면에 10 개의 직사각형 만있는 경우 각 직사각형의 좌표가 포함 된 10 요소 배열을 간단히 가질 수 있습니다. 그들의 위치를 ​​업데이트하는 것은 데이터 구조에 삽입을 요구하지 않을 것이다.

몇 개의 직사각형이 있습니까? 얼마나 빨리 만들어 집니까? 파괴 됐어? 겹치는 부분에 어떻게 대처하고 싶습니까? 직사각형은 단지 경계입니까, 아니면 내부를 포함합니까?

Answer 3

나는 멀티 스케일 그리드 접근법 (어떤 형태로든 쿼드 트리와 동일)을 사용할 것입니다.

나는 당신이 (즉 픽셀) 정수 좌표를 사용하여 모든 픽셀을 보유 할 충분한 공간이있어 있으리라 믿고있어.

각 픽셀마다 하나씩 사각형 배열 목록이 있습니다. 그런 다음 2 ~ 2 칸을 비우고 다시 해보십시오. 그리고 다시, 그리고 다시, 그리고 다시, 모든 것을 다루는 한 픽셀을 가질 때까지.

이제는 사각형 크기에 맞는 수준으로 사각형 을 삽입하는 것이 중요합니다. 이것은 (pixel size) ~ = min (height, width)/2와 같습니다. 이제 각 사각형에 대해 목록에 삽입 할 수있는 소수의 삽입 만 있습니다 (상수로 묶을 수 있습니다 (예 : 4에서 16 픽셀 사이의 항목 선택).

x, y에서 모든 직사각형을 검색하려면 가장 작은 픽셀 목록을보고 그 다음에 포함 된 2x2 비닝 픽셀 목록을보고 4x4 등. 살펴볼 log2 (픽셀 단위) 단계가 있어야합니다.(큰 픽셀의 경우에는 (x, y)가 실제로 사각형인지 확인해야하며, 그 중 절반 정도가 테두리에서 성공할 것으로 예상하고 모든 사각형이 사각형 내부에서 성공할 것으로 기대하므로 기대할 수 있습니다. 픽셀을 직접 찾은 것보다 2 배 더 많은 작업이 필요하지 않습니다.)

이제 인서트는 어떻습니까? 그것은 매우 저렴합니다 - O (1)는 목록 앞에서 자신을 고수합니다.

삭제는 어떻게됩니까? 그것은 더 비싸다. 당신은 당신이 입력 한 각 픽셀에 대해 각리스트를 조사하고 치유해야만합니다. 대략 같은 크기의 공간 과에서 그 위치에 겹쳐있는 사각형의 수는 거의 O (n)입니다. 정말 많은 수의 직사각형을 가지고 있다면, 다른 데이터 구조를 사용하여이를 유지해야합니다 (해시 세트, RB 트리 등).

(최소 직사각형이 픽셀보다 커야하는 경우 실제로 픽셀 수준까지 멀티 스케일 구조를 형성 할 필요가 없으므로 가장 작은 사각형이 절망적으로 손실되지 않을 때까지 내려가십시오