Hilbert R-Tree에서 사용할 점의 Hilbert 값을 계산하시겠습니까?

StackOverflow https://stackoverflow.com/questions/106237

  •  01-07-2019
  •  | 
  •  

문제

Hilbert R-Tree가 있는 애플리케이션이 있습니다. (위키피디아) (시민) 적절한 데이터 구조인 것 같습니다.특히, 많은 업데이트가 발생할 데이터 세트에 대해 합리적으로 빠른 공간 쿼리가 필요합니다.

그러나 내가 아는 한, 이 데이터 구조에 대한 알고리즘에 대한 설명은 전혀 없습니다. 언급하다 실제로 필요한 것을 계산하는 방법 힐베르트 값;이는 a를 따른 거리입니다. 힐베르트 곡선 요점까지.

그렇다면 이것을 계산하는 방법에 대한 제안이 있습니까?

도움이 되었습니까?

해결책

재미있는 질문입니다!

나는 약간의 인터넷 검색을 했고 좋은 소식은 Hilbert Value의 구현을 찾았다는 것입니다.

잠재적으로 나쁜 소식은 Haskell에 있다는 것입니다.

http://www.serpentine.com/blog/2007/01/11/two-Dimensional-spatial-hashing-with-space-filling-curves/

또한 더 쉽게 계산할 수 있는 르베그 거리 측정법을 제안합니다.

다른 팁

다음은 Software에 게시된 Xian Lu 및 Gunther Schrack의 "힐베르트 순서 인코딩 및 디코딩" 논문의 C 코드에서 채택된 Java 코드입니다.실천과 경험 Vol.26페이지 1335-46(1996).

도움이 되었기를 바랍니다.개선을 환영합니다!

남자 이름

/**
 * Find the Hilbert order (=vertex index) for the given grid cell 
 * coordinates.
 * @param x cell column (from 0)
 * @param y cell row (from 0)
 * @param r resolution of Hilbert curve (grid will have Math.pow(2,r) 
 * rows and cols)
 * @return Hilbert order 
 */
public static int encode(int x, int y, int r) {

    int mask = (1 << r) - 1;
    int hodd = 0;
    int heven = x ^ y;
    int notx = ~x & mask;
    int noty = ~y & mask;
    int temp = notx ^ y;

    int v0 = 0, v1 = 0;
    for (int k = 1; k < r; k++) {
        v1 = ((v1 & heven) | ((v0 ^ noty) & temp)) >> 1;
        v0 = ((v0 & (v1 ^ notx)) | (~v0 & (v1 ^ noty))) >> 1;
    }
    hodd = (~v0 & (v1 ^ x)) | (v0 & (v1 ^ noty));

    return interleaveBits(hodd, heven);
}

/**
 * Interleave the bits from two input integer values
 * @param odd integer holding bit values for odd bit positions
 * @param even integer holding bit values for even bit positions
 * @return the integer that results from interleaving the input bits
 *
 * @todo: I'm sure there's a more elegant way of doing this !
 */
private static int interleaveBits(int odd, int even) {
    int val = 0;
    // Replaced this line with the improved code provided by Tuska
    // int n = Math.max(Integer.highestOneBit(odd), Integer.highestOneBit(even));
    int max = Math.max(odd, even);
    int n = 0;
    while (max > 0) {
        n++;
        max >>= 1;
    }

    for (int i = 0; i < n; i++) {
        int bitMask = 1 << i;
        int a = (even & bitMask) > 0 ? (1 << (2*i)) : 0;
        int b = (odd & bitMask) > 0 ? (1 << (2*i+1)) : 0;
        val += a + b;
    }

    return val;
}

보다 우사이게젠.

위의 코드와 Java 코드는 2D 데이터 포인트에 적합합니다.그러나 더 높은 차원의 경우 Jonathan Lawder의 논문을 살펴봐야 할 수도 있습니다. J.K.로더.힐베르트 공간 채우기 곡선을 사용한 1차원 값과 n차원 값 사이의 매핑 계산.

비트를 인터리브하는 좀 더 효율적인 방법을 알아냈습니다.그것은에서 찾을 수 있습니다 스탠포드 그래픽 웹사이트.나는 두 개의 32비트 정수를 하나의 64비트 길이로 인터리브할 수 있는 버전을 만들었습니다.

public static long spreadBits32(int y) {
    long[] B = new long[] {
        0x5555555555555555L, 
        0x3333333333333333L,
        0x0f0f0f0f0f0f0f0fL,
        0x00ff00ff00ff00ffL,
        0x0000ffff0000ffffL,
        0x00000000ffffffffL
    };

    int[] S = new int[] { 1, 2, 4, 8, 16, 32 };
    long x = y;

    x = (x | (x << S[5])) & B[5];
    x = (x | (x << S[4])) & B[4];
    x = (x | (x << S[3])) & B[3];
    x = (x | (x << S[2])) & B[2];
    x = (x | (x << S[1])) & B[1];
    x = (x | (x << S[0])) & B[0];
    return x;
}

public static long interleave64(int x, int y) {
    return spreadBits32(x) | (spreadBits32(y) << 1);
}

분명히, 비 그리고 에스 지역 변수는 클래스 상수여야 하지만 단순화를 위해 이렇게 두었습니다.

남자 이름,

Java 코드를 보내주셔서 감사합니다!테스트했는데 잘 작동하는 것 같았지만 비트 인터리빙 함수가 재귀 레벨 7에서 오버플로되는 것을 발견했습니다(적어도 내 테스트에서는 그러나 긴 값을 사용했습니다). 왜냐하면 "n" 값은 maximumOneBit(를 사용하여 계산되기 때문입니다. )-함수는 가장 높은 1비트의 위치가 아닌 값을 반환합니다.그래서 루프는 불필요하게 많은 인터리빙을 수행합니다.

방금 다음 스니펫으로 변경했는데 그 후에는 제대로 작동했습니다.

  int max = Math.max(odd, even);
  int n = 0;
  while (max > 0) {
    n++;
    max >>= 1;
  }

빠른 삭제/삽입 기능을 갖춘 공간 인덱스가 필요한 경우 PH-트리를 살펴보세요.부분적으로 쿼드트리를 기반으로 하지만 더 빠르고 공간 효율적입니다.내부적으로는 H-곡선보다 공간적 특성이 약간 떨어지는 Z-곡선을 사용하지만 많이 계산하기가 더 쉽습니다.

종이: http://www.globis.ethz.ch/script/publication/download?docid=699

자바 구현: http://globis.ethz.ch/files/2014/11/ph-tree-2014-11-10.zip

또 다른 옵션은 X-트리이며, 여기에서도 사용할 수 있습니다.https://code.google.com/p/xxl/

제안:공간 쿼리를 위한 간단하고 효율적인 데이터 구조는 다차원 이진 트리입니다.

전통적인 이진 트리에는 하나의 "판별자"가 있습니다.왼쪽 가지를 택할지, 오른쪽 가지를 택할지 결정하는 데 사용되는 값입니다.이는 1차원적인 경우라고 볼 수 있다.

다차원 이진 트리에는 여러 판별자가 있습니다.연속적인 수준에서는 서로 다른 판별식을 사용합니다.예를 들어 2차원 공간 데이터의 경우 X 및 Y 좌표를 판별자로 사용할 수 있습니다.연속적인 레벨은 X, Y, X, Y...를 사용합니다.

공간 쿼리(예: 직사각형 내의 모든 노드 찾기)의 경우 루트에서 시작하여 트리에 대한 깊이 우선 검색을 수행하고 각 수준에서 판별식을 사용하여 주어진 직사각형에 노드가 없는 분기를 검색하지 않도록 합니다.

이를 통해 잠재적으로 각 수준에서 검색 공간을 절반으로 줄일 수 있으므로 대규모 데이터 세트에서 작은 영역을 찾는 데 매우 효율적입니다.(그런데 이 데이터 구조는 부분 일치 쿼리에도 유용합니다.하나 이상의 판별자를 생략하는 쿼리입니다.생략된 판별자를 사용하여 수준에서 두 분기를 모두 검색하면 됩니다.)

이 데이터 구조에 대한 좋은 논문: http://portal.acm.org/citation.cfm?id=361007이 기사에는 좋은 다이어그램과 알고리즘 설명이 있습니다. http://en.wikipedia.org/wiki/Kd-tree

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top