사전 rtree 단계 : 점 세트를 각각 1 점을 포함하는 직사각형 영역으로 나눕니다.

Question

내 현재 위치 (LAT, Long)를 감안할 때 관심 지점에서 가장 가까운 이웃을 빨리 찾고 싶습니다. 따라서 R- 트리 데이터베이스를 사용하여 빠른 조회를 허용합니다. 그러나 먼저 데이터베이스를 채워야합니다. 따라서 각 지역에 관심있는 지점이있는 지역을 덮는 직사각형 영역을 결정해야합니다.

내 질문은 어떻게 데이터를 전처리 하는가, 즉 영역을 이러한 직사각형 하위 영역으로 어떻게 세분화합니까? (직사각형 영역은 더 일반적인 Voronoi 지역과 달리 rtree에 쉽게 추가되기 때문에 원합니다).

/남자

Answer 1

편집하다: 아래의 접근 방식은 작동하지만 R- 트리의 중요한 특징을 무시합니다. R- 트리 노드의 분할 동작이 잘 정의되고 균형 잡힌 트리 (B- 트리 유사 특성을 통해)를 유지합니다. 사실, 당신이해야 할 일은 다음과 같습니다.

1. 페이지 당 최대 사각형 수를 선택하십시오
2. 씨앗 사각형을 만듭니다 (서로 가장 멀리 떨어진 포인트, 중심 등).
3. 각 지점마다 사각형을 선택하여
   4. 이미 단일 사각형에 빠지면 거기에 넣으십시오.
   5. 그렇지 않은 경우 최저 확장 해야하는 사각형을 확장합니다 ( "최소한"출구를 측정하는 다른 방법 - 영역 작동)
   6. 여러 사각형이 적용되는 경우 - 가득한 곳 또는 다른 휴리스틱에 따라 하나를 선택하십시오.
4. 오버플로가 발생하는 경우 - 2 차 분할을 사용하여 물건을 움직입니다 ...
5. 그리고 교과서에서 바로 R- 트리 알고리즘을 사용합니다.

아래의 방법은 초기 시드 직사각형을 찾는 데 괜찮다고 생각합니다. 그러나 당신은 그런 식으로 전체 R- 트리를 채우고 싶지 않습니다. 스플릿을하고 항상 재조정하는 것은 약간 비쌀 수 있으므로 아래의 KD 접근 방식으로 괜찮은 작업을하고 싶을 것입니다. 모든 작업이 아닙니다.

---

KD 접근법 : 모든 것을 직사각형으로 둘러싸십시오.

사각형의 포인트 수가> 임계 값인 경우, 포인트의 절반을 덮을 때까지 방향 D로 청소하십시오.

분할 지점의 왼쪽과 오른쪽 (또는 위와 아래)으로 나누어냅니다.

다음 방향으로 새로운 사각형에서 동일한 절차를 재귀 적으로 호출하십시오 (왼쪽으로 오른쪽으로 이동하면 이제 맨 아래로 이동하고 그 반대도 마찬가지입니다).

다른 포스터가 제공하는 Divide-Into-Squares 접근 방식보다 이점이있는 이점은 비뚤어진 포인트 분포를 더 잘 수용한다는 것입니다.

Answer 2

오라클 공간 카트리지 문서는 원하는 작업을 수행 할 수있는 테셀레이션 알고리즘을 설명합니다. 요컨대 :

• 모든 지점을 정사각형으로 동봉하십시오
• Square에 1 점 - 인덱스 제곱이 포함 된 경우
• 정사각형에 점이 포함되어 있지 않으면 무시하십시오
• 사각형에 1 점 이상이 포함 된 경우
  • 사각형 4 개로 분할 및 각각의 새로운 광장에 대한 반복 분석

결과는 다음과 같아야합니다.
대체 텍스트 http://download-uk.oracle.com/docs/cd/a64702_01/doc/cartridg.805/a53264/sdo_ina5.gif

Answer 3

나는 당신이 문제 진술에서 무언가를 놓친 것으로 생각합니다. 모든 지점에 고유 한 x 및 y 좌표가 있도록 n 포인트 (x, y)가 있다고 가정합니다. 영역을 N 직사각형으로 나누어 N 세로 열로 나눌 수 있습니다. 그러나 그것은 가장 가까운 POI 문제를 쉽게 해결하는 데 도움이되지 않습니다. 그래서 나는 당신이 아직 표현하지 않은 사각형 구조에 대해 생각하고 있다고 생각합니다.

삽화:

| | | | |5| | |
|1| | | | |6| |
| | |3| | | | |
| | | | | | | |
| |2| | | | | |
| | | | | | |7|
| | | |4| | | |

숫자는 POI이고 수직선은 7 개의 직사각형 영역으로의 세분을 보여줍니다. 그러나 분명히 세분화에는 "흥미로운"정보가 많지 않습니다. 언급하지 않은 세분에 대한 추가 기준이 있습니까?