احسب قيمة هيلبرت للنقطة المستخدمة في شجرة هيلبرت آر؟

Question

لدي تطبيق حيث هيلبرت R-شجرة (ويكيبيديا) (المستشهد) يبدو أن بنية البيانات المناسبة.على وجه التحديد، يتطلب الأمر استعلامات مكانية سريعة إلى حد معقول عبر مجموعة بيانات ستواجه الكثير من التحديثات.

ومع ذلك، بقدر ما أستطيع أن أرى، لا يوجد حتى أي من أوصاف الخوارزميات الخاصة ببنية البيانات هذه يذكر كيفية حساب المطلوب فعلا قيمة هيلبرت;وهي المسافة على طول أ منحنى هيلبرت الى حد، الى درجة.

إذن هل هناك أي اقتراحات حول كيفية القيام بحساب ذلك؟

Answer 1

سؤال ممتع!

لقد قمت بالبحث قليلاً على Google، والخبر السار هو أنني وجدت تطبيقًا لقيمة هيلبرت.

الأخبار السيئة المحتملة هي أنها في هاسكل...

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

يقترح أيضًا مقياس مسافة Lebesgue الذي قد تتمكن من حسابه بسهولة أكبر.

Answer 2

يوجد أدناه كود Java الخاص بي المقتبس من كود C في المقالة "تشفير وفك تشفير أمر هيلبرت" بقلم Xian Lu وGunther Schrack، المنشورة في البرامج:الممارسة والخبرة المجلد.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;
}

Answer 3

يرى uzaygezen.

Answer 4

يعد الكود ورمز Java أعلاه مناسبين لنقاط البيانات ثنائية الأبعاد.لكن بالنسبة للأبعاد الأعلى قد تحتاج إلى إلقاء نظرة على ورقة جوناثان لودر: جي كيه لودر.حساب التعيينات بين القيم ذات البعد الواحد والقيم ذات البعد n باستخدام منحنى هيلبرت لملء الفضاء.

Answer 5

لقد اكتشفت طريقة أكثر فعالية قليلاً لتشذير البتات.يمكن العثور عليها في موقع ستانفورد جرافيك.لقد قمت بتضمين إصدار قمت بإنشائه يمكنه دمج عددين صحيحين 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);
}

ومن الواضح أن ب و س يجب أن تكون المتغيرات المحلية ثوابت فئة ولكن تم تركها بهذه الطريقة من أجل البساطة.

Answer 6

ميخائيل،

شكرا لكود جافا الخاص بك!لقد قمت باختبارها ويبدو أنها تعمل بشكل جيد، لكنني لاحظت أن وظيفة تشذير البت تفيض عند مستوى التكرار 7 (على الأقل في اختباراتي، لكنني استخدمت قيمًا طويلة)، لأن القيمة "n" يتم حسابها باستخدام أعلى OneBit( ) - الدالة، التي تُرجع القيمة وليس موضع أعلى بتة واحدة؛لذا فإن الحلقة تقوم بالعديد من التشذير دون داع.

لقد قمت بتغييره للتو إلى المقتطف التالي، وبعد ذلك كان يعمل بشكل جيد.

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

Answer 7

إذا كنت بحاجة إلى فهرس مكاني يتمتع بإمكانيات الحذف/الإدراج السريعة، فقم بإلقاء نظرة على شجرة PH.يعتمد جزئيًا على الأشجار الرباعية ولكنه أسرع وأكثر كفاءة في استخدام المساحة.داخليًا، يستخدم منحنى Z الذي له خصائص مكانية أسوأ قليلاً من منحنى H ولكنه كذلك كثيراً أسهل في الحساب.

ورق: http://www.globis.ethz.ch/script/publication/download?docid=699

تنفيذ جافا: http://globis.ethz.ch/files/2014/11/ph-tree-2014-11-10.zip

هناك خيار آخر وهو X-tree، وهو متاح أيضًا هنا:https://code.google.com/p/xxl/

Answer 8

اقتراح:إن بنية البيانات الجيدة والبسيطة والفعالة للاستعلامات المكانية هي شجرة ثنائية متعددة الأبعاد.

في الشجرة الثنائية التقليدية، يوجد "مميز" واحد؛القيمة المستخدمة لتحديد ما إذا كنت ستأخذ الفرع الأيسر أم الفرع الأيمن.ويمكن اعتبار هذه الحالة ذات بعد واحد.

في شجرة ثنائية متعددة الأبعاد، لديك تمييزات متعددة؛تستخدم المستويات المتتالية تمييزات مختلفة.على سبيل المثال، بالنسبة للبيانات المكانية ثنائية الأبعاد، يمكنك استخدام إحداثيات X وY كتمييزات.ستستخدم المستويات المتتالية X وY وX وY...

بالنسبة للاستعلامات المكانية (على سبيل المثال، العثور على جميع العقد داخل مستطيل)، يمكنك إجراء بحث عميق أولًا للشجرة بدءًا من الجذر، واستخدام المميز في كل مستوى لتجنب البحث أسفل الفروع التي لا تحتوي على عقد في المستطيل المحدد.

يتيح لك ذلك إمكانية تقليص مساحة البحث إلى النصف عند كل مستوى، مما يجعلها فعالة جدًا للعثور على مناطق صغيرة في مجموعة بيانات ضخمة.(راجع للشغل، بنية البيانات هذه مفيدة أيضًا لاستعلامات المطابقة الجزئية، أيالاستعلامات التي تحذف واحدًا أو أكثر من المميزات.ما عليك سوى البحث في كلا الفرعين على المستويات مع وجود تمييز محذوف.)

ورقة جيدة حول بنية البيانات هذه: http://portal.acm.org/citizen.cfm?id=361007تحتوي هذه المقالة على مخططات جيدة وأوصاف خوارزمية: http://en.wikipedia.org/wiki/Kd-tree