Den Hilbert-Wert eines Punktes zur Verwendung in einem Hilbert-R-Baum berechnen?

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

  •  01-07-2019
  •  | 
  •  

Frage

Ich habe eine Anwendung mit einem Hilbert R-Tree (Wikipedia) (Zitierer) scheint eine geeignete Datenstruktur zu sein.Insbesondere sind relativ schnelle räumliche Abfragen über einen Datensatz erforderlich, der häufig aktualisiert wird.

Soweit ich sehen kann, gibt es jedoch keine Beschreibung der Algorithmen für diese Datenstruktur erwähnen wie man den Bedarf tatsächlich berechnet Hilbert-Wert;Das ist die Entfernung entlang a Hilbert-Kurve auf den Punkt.

Gibt es also Vorschläge, wie man das berechnen kann?

War es hilfreich?

Lösung

Spaß Frage!

habe ich ein bisschen googeln, und die gute Nachricht ist, habe ich eine Implementierung von Hilbert Wert gefunden.

Die potenziell schlechte Nachricht ist, es ist in Haskell ...

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

Außerdem schlägt sie eine Lebesgue Distanzmaß Sie könnten in der Lage sein, leichter zu berechnen.

Andere Tipps

Unten ist mein Java-Code von C-Code in dem Papier angepasst "Codierung und Decodierung die Hilbert Ordnung" von Xian Lu und Gunther Schrack, veröffentlichte in Software: Praxis und Erfahrung Vol. 26 S. 1335-1346 (1996).

Hoffe, das hilft. Verbesserungen willkommen!

Michael 

/**
 * 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;
}

Siehe uzaygezen .

Der Code und Java-Code ist oben in Ordnung für 2D-Datenpunkte. Aber für höhere Dimensionen können Sie bei Jonathan Lawder das Papier aussehen müssen: JKLawder . Berechnung des Mappings zwischen einem und n-dimensionalen Werten der Hilbert Mit raumfüllende Kurve.

dachte ich einen etwas effizienten Weg aus Bits verschachteln. Es kann auf der Stanford Graphics-Website finden . Ich enthalten eine Version, die ich erstellt, dass zwei 32-Bit-Integer in einen 64-Bit langen verschachteln kann. 

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);
}

Offensichtlich ist der B und S lokale Variablen Klasse Konstanten sein sollte, aber es wurde auf diese Weise der Einfachheit halber links.

Michael,

Dank für Ihre Java-Code! Ich habe es getestet und es scheint gut zu funktionieren, aber ich bemerkte, dass die Bit-Verschachtelung Funktion bei Rekursionstiefe 7 überläuft (zumindest in meinen Tests, aber ich habe lange Werte), weil die „n“ -Wert berechnet wird highestOneBit ( ) -Funktion, die den Wert und die Position des höchsten ein Bit liefert; so dass die Schleife tut unnötig viele Verschachtelungen.

Habe ich es nur zu folgendem Ausschnitt und nach, dass es funktionierte gut. 

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

Wenn Sie einen räumlichen Index mit schnellen Lösch- / Insert-Funktionen benötigen, haben einen Blick auf den PH-Baum. Es basiert teilweise auf Quadtrees aber schneller und platzsparend. Intern verwendet es eine Z-Kurve, die etwas schlechter räumliche Eigenschaften als eine H-Kurve hat, aber viel leichter zu berechnen.

Papier: http://www.globis.ethz.ch/ script / Veröffentlichung / download? docid = 699

Java-Implementierung: http: // Globis .ethz.ch / files / 2014/11 / ph-tree-2014-11-10.zip

Eine weitere Option ist der X-Baum, der auch hier verfügbar: https://code.google.com/p/xxl/

Anregung:Eine gute einfache effiziente Datenstruktur für räumliche Abfragen ist ein mehrdimensionaler Binärbaum.

In einem traditionellen Binärbaum gibt es eine „Diskriminante“;Der Wert, der verwendet wird, um zu bestimmen, ob Sie den linken oder den rechten Zweig nehmen.Dies kann als eindimensionaler Fall betrachtet werden.

In einem mehrdimensionalen Binärbaum gibt es mehrere Diskriminanten;Aufeinanderfolgende Ebenen verwenden unterschiedliche Diskriminanten.Für zweidimensionale räumliche Daten könnten Sie beispielsweise die X- und Y-Koordinaten als Diskriminanten verwenden.Aufeinanderfolgende Ebenen würden X, Y, X, Y ... verwenden.

Für räumliche Abfragen (zum Beispiel das Finden aller Knoten innerhalb eines Rechtecks) führen Sie eine Tiefensuche des Baums beginnend an der Wurzel durch und verwenden die Diskriminante auf jeder Ebene, um zu vermeiden, dass Zweige nach unten durchsucht werden, die keine Knoten im gegebenen Rechteck enthalten.

Dadurch können Sie den Suchraum auf jeder Ebene möglicherweise halbieren, was die Suche nach kleinen Regionen in einem riesigen Datensatz sehr effizient macht.(Übrigens ist diese Datenstruktur auch für Abfragen mit teilweiser Übereinstimmung nützlich, d. h.Abfragen, die eine oder mehrere Diskriminanten auslassen.Sie durchsuchen einfach beide Zweige auf Ebenen mit einer weggelassenen Diskriminante.)

Ein gutes Papier zu dieser Datenstruktur: http://portal.acm.org/citation.cfm?id=361007Dieser Artikel enthält gute Diagramme und Algorithmusbeschreibungen: http://en.wikipedia.org/wiki/Kd-tree

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top