C 언어 구현 공간 색인 사지 수

머리말
프로그래머 로 서 이 진 트 리 에 대해 낯 설 지 않 을 것 입 니 다.이 진 트 리 의 변형 이 진 트 리 를 찾 는 것 은 1 차원 수열 에 대한 저장 과 검색 에 매우 적합 하고 O(logn)의 효율 을 달성 할 수 있다 는 것 을 잘 알 고 있 습 니 다.우 리 는 두 갈래 로 나 무 를 찾 아 데 이 터 를 삽입 할 때 한 데이터 의 값 과 나무 결점 값 의 대비 에 따라 두 갈래 나무의 두 갈래 중 하 나 를 아래로 선택 하고 잎 이 맺 힐 때 까지 이분법 을 사용 해도 필요 한 데 이 터 를 신속하게 찾 을 수 있다.
그러나 이 진 트 리 는 1 차원 데이터 만 지원 합 니 다.예 를 들 어 하나의 스칼라 수치 와 같이 지도 상의 위치 점 과 같은 xy 두 방향 에 있 는 정 보 는 어 쩔 수 없습니다.그러면 2 차원 데이터 의 빠 른 조 회 를 지원 할 수 있 는 나무 가 있 습 니까?
사지 수
소개 하 다.
4 원 나 무 는 사지 수 라 고도 부 르 는데 나무 모양 의 데이터 구조 로 모든 노드 에 네 개의 블록 이 있 을 것 이다.4 원 나 무 는 항상 2 차원 공간 데이터 의 분석 과 분류 에 사용 된다.그것 은 데 이 터 를 네 개의 상한 으로 구분한다.
오늘 소개 하고 자 하 는 사지 수 는 이 진 트 리 의 고 차원 변형 이 라 고 볼 수 있 습 니 다.이 는 2 차원 속성 이 있 는 데 이 터 를 저장 하고 조회 하기에 적합 합 니 다.물론 사지 수 는 2 차원 데이터 가 아니 라 2 차원 속성 을 가 진 데이터 입 니 다.예 를 들 어 x,y 정보의 점 이 있 으 면 선과 면 데 이 터 를 저장 할 수 있 습 니 다.이 는 네 개 가 있 는데 데이터 가 삽 입 될 때 우 리 는 2 차원 속성(보통 x,y)을 통 해 네 개의 포크 중 하 나 를 선택 하여 계속 아래로 내 려 가 잎 이 결 점 될 때 까지'4 분 법'을 사용 하여 데 이 터 를 신속하게 찾 습 니 다.사지 수의 일반 도형 구 조 는 다음 과 같다.

똑똑 한 동료 들 은 3 차원 데 이 터 를 저장 하고 조회 하기에 적합 한 팔자 수 트 리 를 생각 했 을 것 이다.그들의 원 리 는 일치 하지만 우 리 는 잠시 토론 하지 않 는 다.
분류 하 다.
사지 수 에서 흔히 볼 수 있 는 응용 은 이미지 처리,공간 데이터 색인,2D 의 빠 른 충돌 검 측,희소 데이터 등 이 있 습 니 다.오늘 우 리 는 순수 하 게 공간 색인 에 대한 응용 만 소개 합 니 다.
그 저장 내용 에 따 르 면 사지 수 는 점 사지 수,변 사지 수 와 사지 수 로 나 눌 수 있 는데 오늘 우리 가 실현 한 것 은 점 사지 수 이다.
그 구조 에 따라 사지 수 는 만 사지 수 와 비 만 사지 수 로 나 뉜 다.
만 사지 수 에 대해 모든 노드 는 네 개의 자 결점 이 있 고 고정된 깊이 가 있 으 며 데 이 터 는 모두 맨 밑 에 있 는 자 결점 에 존재 하 며 데 이 터 를 삽입 할 때 분열 할 필요 가 없다.
만 사지 수 는 깊이 를 정 한 후에 삽입 작업 을 하 는 것 이 매우 빠 릅 니 다.그러나 이 를 이용 하여 다음 그림 에 표 시 된 데 이 터 를 저장 하면 우 리 는 사지 수의 많은 포크 가 비어 있 는 것 을 발견 할 수 있 습 니 다.물론 메모리 공간의 대량 낭 비 를 초래 할 수 있 습 니 다.

비 만 사지 수 는 이 문 제 를 해결 했다.이 문 제 는 모든 노드 에'용량'의 속성 을 추가 하고 사지 수 초기 화 시 하나의 노드 만 있 으 며 데 이 터 를 삽입 할 때 하나의 노드 안의 데이터 양 이 노드'용량'보다 많 으 면 결점 을 분열 시킨다.이렇게 하면 모든 노드 에 데 이 터 를 저장 하고 메모리 공간의 낭 비 를 피 할 수 있다.
조회 할 때 위치 에 대응 하 는 결점 만 찾 았 다 면 결점 아래 의 모든 점 은 이 위치의 부근 점 이 고 더 작은'용량'은 모든 결점 내 점 이 적 을 수록 조회 의 정밀도 가 높다 는 것 을 의미한다.
코드 구현
우선 데이터 구조의 정의:
나무 노드:

struct QuadTreeNode {
    int depth; //     
    int is_leaf; //        
    struct Region region; //     
    struct QuadTreeNode *LU; //        
    struct QuadTreeNode *LB; //        
    struct QuadTreeNode *RU; //        
    struct QuadTreeNode *RB; //        
    int ele_num; //     
    struct ElePoint *ele_list[MAX_ELE_NUM]; //      
};

삽입 과 조회 속 도 를 가속 화하 기 위해 데이터 구조 디자인 이 약간 지루 해 졌 다.
사지 수 위치 점 의 삽입 절 차 는 다음 그림 과 같다.

결점 의 분열 이 중점 입 니 다.여기 서 소개 하 겠 습 니 다.

void splitNode(struct QuadTreeNode *node) {
    //   xy       ，           
    double mid_vertical = (node->region.up + node->region.bottom) / 2;
    double mid_horizontal = (node->region.left + node->region.right) / 2;

    node->is_leaf = 0; //            
    //        
    node->RU = createChildNode(node, mid_vertical, node->region.up, mid_horizontal, node->region.right);
    node->LU = createChildNode(node, mid_vertical, node->region.up, node->region.left, mid_horizontal);
    node->RB = createChildNode(node, node->region.bottom, mid_vertical, mid_horizontal, node->region.right);
    node->LB = createChildNode(node, node->region.bottom, mid_vertical, node->region.left, mid_horizontal);

    //          ，         
    for (int i = 0; i < node->ele_num; i++) {
        insertEle(node, *node->ele_list[i]);
        free(node->ele_list[i]);
        node->ele_num--;
    }
}

문제 와 최적화
경계 점 문제
사지 수 는 아직도 경계 점 문제 에 직면 하고 있다.모든 결점 안의 점 은 반드시 인접 해 야 한다.그러나 인접 한 점 이 반드시 같은 결점 안에 있 는 것 이 아니다.다음 과 같은 그림 은 A 점 과 B 점 이 가 까 워 서 A 점 이 우리 가 찾 는 목표 점 이 라면 A 점 이 있 는 결점 안의 모든 위치 점 만 찾 는 것 이 부족 하 다.우 리 는 그의 주변 결점 을 찾 아야 한다.

여기 서 우 리 는 사지 수의 또 다른 특성 을 소개 해 야 한다.
사전 트 리
사전 트 리 는 접두사 트 리 나 trie 트 리 라 고도 부 르 며,관련 배열 을 저장 하 는 데 사용 되 며,키 는 보통 문자열 입 니 다.이 진 트 리 와 달리 키 는 노드 에 직접 저장 되 는 것 이 아니 라 노드 가 트 리 에 있 는 위치 에 의 해 결정 된다.한 노드 의 모든 자손 은 같은 접 두 사 를 가지 고 있 습 니 다.즉,이 노드 에 대응 하 는 문자열 이 고 뿌리 노드 는 빈 문자열 에 대응 합 니 다.
우 리 는 사전 의 특성 을 비교 할 수 있다.우 리 는 사전에 서 병 음 을 통 해 흔 들 림(huang)이라는 글 자 를 찾 을 때,우 리 는 그것 의 부근 이 모두 huang 이 라 고 읽 는 것 을 발견 할 수 있다.아마도 성조 에 차이 가 있 을 것 이다.다시 앞으로 넘 어가 면,우 리 는 독음 접두사 가 huan 이라는 글 자 를 볼 수 있다.다시 앞으로,독음 접두사 가 hua 인 글 자 를 볼 수 있다.그들의 독음 접 두 사 를 취하 면 각각 h qu hua huan huang 이다.우리 가 찾 을 때 abc...xyz 의 순서에 따라 h 접두사 부분 을 찾 은 다음 에 ha he hu 에 따라 hu 접두사 부분 을 찾 습 니 다.마지막 으로 huang 을 찾 으 면 뒤로 읽 을 수록 접두사 가 길 어 지고 찾 는 것 도 정확 합 니 다.이런 사전 과 유사 한 나무 구 조 는 사전 나무 이자 접두사 나무 입 니 다.
사지 수 에 도 이런 특성 이 있 습 니 다.우 리 는 모든 자 결점 에 번 호 를 매 깁 니 다.그러면 모든 자 결점 은 부모 결점 의 번 호 를 접두사 로 계승 하고 이 를 바탕 으로 형제 결점 에 비해 독특한 번호 가 있 습 니 다.
GeoHash 와 비슷 한 점.
만약 에 우리 가 오른쪽 위,왼쪽 위,왼쪽 아래,오른쪽 아래 네 개의 자 결점 에 각각 00010111 번 호 를 주면 생 성 된 사지 수 는 다음 과 같다.

우 리 는 목표 노드 를 찾 을 때 인 코딩 에 따라 주변 8 개의 노드 의 인 코딩 을 얻 고 각 주변 노드 안의 위치 점 을 얻 습 니 다.
음,인 코딩 을 통 해 주변 칸 을 확인 하 는 방식 은 확실히 GeoHash 와 같 지만 그들 이 찾 는 원리 가 전혀 다르다 는 것 을 헷 갈 리 지 마 세 요.

GeoHash 는 본질 적 으로 격자 인 코딩 을 통 해 2 차원 정 보 를 1 차원 으로 표시 하 는데 그 검색 원 리 는 근본적으로 이 진 트 리(B 트 리)이 고 검색 할 때 격자 인 코딩 에 따라 두 방향 중 하 나 를 선택 하여 계속 정확 하 며 조회 효율 은 정확하게 log2N 이다.

사지 수 는 2 차원 검색 의 특성 을 유지 하고 그 검색 은 x,y 에 따라 네 가지 방향 중 하 나 를 선택 하여 계속 찾 습 니 다.방향 선택 시의 계산 을 무시 하고 조회 효율 은 log 4 N 이 어야 합 니 다.

우 리 는 이 방법 을 사용 하여 사지 수 를 계속 최적화 시 킬 수 있 습 니 다.노드 에'번호'속성 을 추가 하면 됩 니 다.시(bo)간(zhu)관(fan)계(lan)로 인해 더 이상 실현 되 지 않 습 니 다.
작은 매듭
C 언어의 높 은 효율 로 인해 이 루어 진 사지 수 는 효율 이 매우 높다.10 만 데이터 의 삽입 과 조회 총 체 조 를 7 밀리초 로 한다.데이터 양 이 더 많은 삽입 을 할 때 결점 의 여러 번 분열 을 해 야 하기 때문에 효율 이 떨 어 질 수 있 습 니 다.8 백만 데이터 의 테스트 삽입 을 하 는 데 2 분 이상 걸 립 니 다(16 년 의 mac pro).조 회 는 모두 메모리 주소 지정 작업 이 므 로 시간 은 무시 할 수 있 습 니 다.더 많은 등급 의 테스트 는 도망 가지 않 고 달 릴 때 방열 선풍기 속 전 시스템 의 온도 가 빠르게 상승 했다.
그러나 이렇게 높 은 효율 은 모두 메모리 작업 이기 때문에 진정한 데이터 베 이 스 는 반드시 땅 에 떨 어 질 것 이다.그 때 는 디스크 와 IO 작업 이 많 고 효율 도 떨 어 질 것 이다.그러나 최종 효율 과 노드 데이터 의 확장 능력 은 GeoHash 에 비해 사지 수 가 더 좋다.
이상 은 C 언어 가 공간 색인 사지 수 를 실현 하 는 상세 한 내용 입 니 다.C 언어 가 공간 색인 사지 수 를 실현 하 는 데 관 한 자 료 는 저희 의 다른 관련 글 을 주목 하 십시오!